On 09/11/2015 09:19 AM, Andy Thomason wrote:
With my commercial background I am very septical about O(lg(N)) search algorithms as they do not work well on modern hardware unless you are very careful with the data layout.
I am very careful with the data layout, my container is implemented using a counted B+Tree which is cache efficient.
A vector will linear search faster than a tree with up to a few hundred elements. Easy to prove and search for Stroustrup's opininion on complex data structures.
A B+Tree has the same layout as a vector until a certain size. Your argumens seem to be against binary trees.
A middle-first tree is often better (I don't now if there is an academic equivlent). Store the middle element first in a vector and the two quartiles second and third etc.
The first few and last few accesses are in the same cache lines.
This is very similar to the layout of a B+Tree.
I see a lot of pointers and allocated data structures in this as well as about eight levels of indirection of push_back which will be fun in debug mode :) I don't want to piss on the bonfire...
Andy.