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: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2015-09-12 09:12:53

On Fri, Sep 11, 2015 at 8:10 PM, Chris Clearwater <chris_at_[hidden]> wrote:

> Greetings,
>
> 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.
>
> Useful links:
>  - Source code: https://github.com/det/segmented_tree_seq
>  - Documentation: http://det.github.io/segmented_tree_seq/
>  - Benchmarks: https://github.com/det/segmented_tree_seq/tree/benchmarks
>
> Any feedback is greatly appreciated.
>
>
There are many variants of B+ trees. A document with explanation of the
implemented data structure and key algorithms would be quite helpful. It
should provide figures.

Is this a level-linked variant of B+ trees or not?

To make this B+ tree much more useful, it should supports not only
sequences, but also std::set<T>, std::multiset<T>, std::map<T> and
std::multimap<T>. Alternatively, you can implement all of these standard
containers using your B+ tree as underlying data structure.

Regards,
Vadim Stadnik