Solved Quiz Time! Prepending items to QVector
-
Hi @VRonin,
you first have to mention the Qt version you are using.
Are you still on 5.15 or already on a 6.x series where lots of optimizations for that case have been done?
Regards
-
@aha_1980 great question! I ran the benchmark for both 5.15.2 and 6.0.3 so chose your poison
-
@VRonin
My guess is thatappend
+reverse
is more efficient thanprepend
.My reason is why would you even bother to ask this question if
prepend
is more efficient?:)
-
@JonB said in Quiz Time! Prepending items to QVector:
My reason is why would you even bother to ask this question if prepend is more efficient?
I asked myself this question before benchmarking, that’s why
-
How many elements? can I use reserve? Are we talking 32 or 64 bits?
My cheat answer would by - it depends ;) -
Am I misreading the problem, or does this also need to have the initial sequence reversed prior to the append + reverse operation?
-
@jeremy_k My understanding was that we're starting from an empty container and only need it in correct order after everything is in, otherwise you'd need to do that double reversal on each addition. I could be wrong though.
-
It depends, I think.
I don't know, but I am putting on depends in case the answer is shocking. -
If the container starts empty, I would expect using a reverse iterator for reading and append for writing would beat both strategies mentioned in the initial post. Unless QVector has become a single linked list (edit: or the consumer demands a QVector).
-
My knowledge base is more in line with stl containers, but making the asusmption that QVector works the same, there is implicit preallocation ie reserve(n) involved in append+reverse that probably doesn't exist with the prepend call, so it stands to reason that few memory reallocations may be necesary using append+reverse.
but the larger issue is whether O(1) random access is needed or guaranteeed continuous element allocation...if not, the QList would be a much more efficient container.
-
In case you do not reserve memory for the QVector beforehand, I would say
append
+std::reverse
is fasterBecause I think, that prepend does not reserve additional memory, compared to append(size / 2 more IIRC). So you end up with an allocation and memory move/copy on each prepend
-
How many elements?
The benchmark tested 10, 50, 100, 500, 1000, 5000 but turns out the answer doesn't change with size
can I use reserve?
Yes, in both cases I first called
QVector::reserve
Are we talking 32 or 64 bits?
64
I would expect using a reverse iterator for reading and append for writing would beat both strategies mentioned in the initial post.
Yes, this is obvious but in my use case I can't read with reverse iterator
or does this also need to have the initial sequence reversed prior to the append + reverse operation?
To make it more explicit: If I have the sequence
1, 3, 2, 5
(that I can't reverse iterate) I want the vector to store those as5, 2, 3, 1
-
And the answer is:
In Qt5append
+std::reverse
is vastly superior, In Qt6prepend
is the much faster one.
-
What about just starting at the end of the data first and only appending?
-
@fcarney said in Quiz Time! Prepending items to QVector:
What about just starting at the end of the data first and only appending?
I guess you mean in Qt6. In that case
append
is slightly better but the difference is really tiny -
Is there any article about these specific changes in Qt 6 that I can read? What exactly has changed between Qt 5 and 6?
-
@SimonSchroeder said in Quiz Time! Prepending items to QVector:
What exactly has changed between Qt 5 and 6?
QVector is no longer in Qt6 and an alias for QList. I would guess QList in Qt5 will also show the same fast results for prepend since QList has an optimization for this usecase since ages.
-
From https://wiki.qt.io/New_Features_in_Qt_6.0
QVector and QList are unified. QList is updated and should be used by default when array-like behaviour is needed
QList, QString and QByteArray now have optimized complexity of insertion at the beginning (a.k.a. prepend) -
@VRonin I'm late to the party, as usual ...
... and also as usual I probably sound like a broken record, but what your task sounds like is actually a stack, not a vector ... ;) -
@kshegunov said in Quiz Time! Prepending items to QVector:
but what your task sounds like is actually a stack, not a vector
Indeed, this was an iper-semplification of my problem to solve the academic dilemma.
I agree that a stack or, as @jeremy_k already pointed out, using reverse iterators would achieve the same