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: Phil Endecott (spam_from_boost_dev_at_[hidden])
Date: 2015-09-12 16:53:45

Hi Chris,

Chris Clearwater wrote:
> I have written a library with the intention of submitting it to 
> Boost.Container. My container implements O(log n) random access 
> insert/erase and has a strong focus on performance while supporting the 
> interfaces of the standard library sequence types. An example 
> application would be the character buffer of a text editor.

I think this could be most useful if it were decomposed into
several layers:

- An in-memory B+-Tree
- An augmented tree
- An order-statistics tree

That way, we could have in-memory B+-trees the provide a std::map-like
interface, which would surely be useful, and we could have O(log N)
random access insert/erase on a binary tree where that is appropriate,
and we could have other kinds of augmented trees such as interval trees.

Working out exactly what these layers should look like is not easy,
but I think it's worth doing in order to broaden the applicability.

Regards,  Phil.