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.