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: Andrey Semashev (andrey.semashev_at_[hidden])
Date: 2015-09-11 11:00:15

On 11.09.2015 13:10, 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.

Could you provide more details on your container special features and 
advantages/weaknesses? E.g. how is it better than, for instance, 
Boost.MultiIndex with random access and binary lookup indices?

O(log n) random access is an unusual trait; random access containers are 
usually able to provide O(1) complexity for accessing an element by 
index. It seems there is a key-value lookup instead of a true random 
access. Am I correct?