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 | [email protected] | 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 _______________________________________________ Development mailing list [email protected] http://lists.qt-project.org/mailman/listinfo/development
