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

[Sean Harmer]

On Monday 09 Feb 2015 09:49:08 Marc Mutz wrote:
> On Monday 09 February 2015 09:32:56 Marc Mutz wrote:
> > > 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.
> 
> To make my statement more precise: As soon as you provide insert_sorted, the
> same people who now use QSet + toList + sort() will invariably use it in a
> loop.
> 
> Using a plain vector *is* fine. One just need to get over the fact that this
> is not Python and one has to use std algorithms and function objects.
> 
> It's not the syntax that's a problem. It's the semantics that need to be
> understood. In this case, *both* algorithmic complexity *and* the cost of
> non- locality of reference (which is why QMap is so bad).

I guess depending upon the sizes of your key and value types and number of 
elements and typical frequencies of operations (inserts vs lookups vs 
removals) it may also possibly be better to use two vectors, one for the keys 
and one for the values.

The rationale being that if your value type is large you reduce the number of 
key values that can be stored in a cache line and therefore incur more cache 
misses when performing lookups. Of course you would still incur at least one 
cache miss when loading in the value to return.

It's surprising just how expensive cache misses are these days compared to 
traditionally thought-to-be-expensive CPU instructions.

Anyway, if somebody does implement a nice wrapper around such sorted vectors 
with sufficient controls to force/not-force the sorted invariant to allow 
efficient insertion/removal vs efficient lookups, we have a ton of places in 
Qt3D where you could test such a beast. :)

Cheers,

Sean

-- 
Dr Sean Harmer | sean.harmer at kdab.com | Managing Director UK
Klarälvdalens Datakonsult AB, a KDAB Group company
Tel. Sweden (HQ) +46-563-540090, USA +1-866-777-KDAB(5322)
KDAB - Qt Experts - Platform-independent software solutions