Am 09.02.2015 um 08:48 schrieb André Somers:
> Mathias Hasselmann schreef op 8-2-2015 om 22:28:
>>
>> Am 08.02.2015 um 14:28 schrieb Marc Mutz:
>>
>>> c. Using QMap. As Alex Stepanov put it: every use of a map should be
>>> discussed
>>> in a face-to-face meeting with your manager. Since we don't have that,
>>> I'd
>>> change this to: Everyone wishing to use a QMap should implement one
>>> before
>>> using it for the first time. Then you'd see what you inflict on the
>>> world.
>>>
>>> In the vast majority of cases, a sorted vector is much faster, due to
>>> locality-of-reference. A RB-tree is optimized for wildly mixing
>>> insertions,
>>> lookups, and removals. When you can batch updates and separate them
>>> from
>>> lookups, time-wise, then a sorted vector is usually preferrable.
>> I totally agree, thank you for raising this. Sadly a sorted vector isn't
>> as convenient to use as a map. Maybe there should some convenience API
>> added, Or does it exist already and I am just too ignorant to know it?
> How about this?
>
> |template< typename T>
> typename std::vector<T>::iterator
> insert_sorted( std::vector<T> & vec, Tconst& item)
> {
> return vec.insert
> (
> std::upper_bound( vec.begin(), vec.end(), item),
> item
> );
> }|
>
> (from http://stackoverflow.com/a/25524075/2151404)
>
> Something like this should work just as well on QVector, right? If you
> are doing multiple inserts, perhaps you should keep the inserts outside
> the main vector while you make them, and only at the end do a single
> std::merge.
Uh, seems you found one of the worse corners of Stackoverflow... :-)
To case of QMap vs. sorted vector really is, that QMap makes the
"mistake" of expensively sorting on each insert. In contrast to that,
when using sorted sorted vectors you simply append while building the
container and sort its content in a final step when done. Complexity
class for both approaches is O(n log n). I think you know that, but what
people often forget is, that Landau notation only describes the number
of iterations needed to execute an algorithm. What it hides is cost of
each iteration step, and that's where sorted vectors win over maps when
inserting during construction only: Swapping two elements is
significantly cheaper than rotating RB trees.
Finally there is the pathologic case where you receive elements in
sorted order already. In that case you can skip the final sorting step
for vectors, while maps still is sorting.
Also interesting is the case of merging two sorted vectors: Adopting
merge sort the problem implodes to O(n) while maps still do O(n log n).
Anyway, the real usability problem with sorted vectors is not with
building them:
foreach (Element x, input)
vector.append(x);
qSort(begin(vector), end(vector));
Is trivial to do. Similar:
c.reserve(a.size() + b.size());
for (auto itA = begin(a), itB = begin(b);
itA != end(a) && itB != end(b); )
c.append(*itA < *itB ? *itA++ : *itB++);
The convenience issue is for users of your sorted vector, who can't just
write "cout << sortedVector.value(key) << endl" anymore.
Ciao,
Mathias
_______________________________________________
Development mailing list
Development@qt-project.org
http://lists.qt-project.org/mailman/listinfo/development
