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

[Marc Mutz]

On Monday 09 February 2015 08:48:06 André Somers wrote:
> 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.

Boom. Enter quadratic behaviour.

There _is_ Loki::AssociativeVector, but things like the above is why no-one is 
using it. You only gain if you don't contantly maintain the is_sorted 
invariant.

-- 
Marc Mutz <marc.mutz at kdab.com> | Senior Software Engineer
KDAB (Deutschland) GmbH & Co.KG, a KDAB Group Company
www.kdab.com || Germany +49-30-521325470 || Sweden (HQ) +46-563-540090
KDAB - Qt Experts - Platform-Independent Software Solutions