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: Christian N. (cn00_at_[hidden])
Date: 2015-09-11 11:02:56

On 2015-09-11 12:10 +0200, Chris Clearwater 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.

Since I haven't found documentation on how this is implemented I have to 
ask: Is this "segmented tree" a rope[1, 2]? Usabele for text editor and 
log(n) inserts and erase seem to fit that guess :-).

[1]: https://en.wikipedia.org/wiki/Rope_%28data_structure%29
[2]: 
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.14.9450&rep=rep1&type=pdf

Regards,

Christian