[Development] Upgrading the sources to C++11 keywords (Q_NULLPTR, etc.)

[Mathias Hasselmann]

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