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: Chris Clearwater (chris_at_[hidden])
Date: 2015-09-11 12:17:13

On 09/11/2015 08:00 AM, Andrey Semashev wrote:
> 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?

My segmented_tree_seq container provides the same interface as 
std::vector/std::deque (excepting reserve and shrink_to_fit) while 
Boost.MultiIndex has an interface of its own. Also, given that 
Boost.MultiIndex provides stable iterators, I'd expect it allocates each 
element individually. This makes it completely unsuitable for many 
applications such as storing a buffer of 8bit characters. It probably 
also means that it's performance would be similar to avl_array which I 
outperform by as much as 10x in many benchmarks. My container does not 
provide stable iterators and as a consequence is able to be implemented 
in a very cache efficient way.

Much like you should prefer vector when you are doing insert/erase near 
the end, and you should prefer deque when you are doing insert/erase 
near both ends, you should prefer my container when you are doing 
insert/erase at any index.
>
> 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?

As the name suggest, segmented_tree_seq is a tree. It maintains an 
B+Tree index into chunks of data similar to how deque maintains a vector 
index into chunks of data.