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:39:12

On 09/11/2015 08:16 AM, Rene Rivera wrote:
> First.. You are going to need to add some documentation as to how your
> container works with regards to complexity order. Second.. Your
> implementation is rather hard to follow (but this is not a necessarily a
> bad thing). I say that because I was trying to figure out how your
> container attains the O9log n) you claim. And AFAICT, because of this <
> https://github.com/det/segmented_tree_seq/blob/master/include/boost/container/segmented_tree_seq.hpp#L1278>,
> that your container is just another implementation of an order statistic
> tree <https://en.wikipedia.org/wiki/Order_statistic_tree>. Which is a data
> structure that has been proposed for Boost (and standardization) at various
> times.

The complexity of all operations in my container are already documented 
in the link I provided.

I've most often heard this data structure refered to as a counted tree, 
my implementation in particular is a counted B+Tree, the elements it 
contains are not ordered.