Re: [boost] Determining interest in container with efficient random access insert and erase

Subject: Re: [boost] Determining interest in container with efficient random access insert and erase
From: Chris Clearwater (chris_at_[hidden])
Date: 2015-09-11 13:17:01

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.