Re: [boost] Proposal: Vector-like container, which takes O(log(N)) for insert/erase

Subject: Re: [boost] Proposal: Vector-like container, which takes O(log(N)) for insert/erase
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2014-04-01 05:30:00

On Tue, Apr 1, 2014 at 1:01 AM, Alexander Kuprijanov <alexkupri_at_[hidden]>wrote:

> Hi, everybody!
> I've implemented a container, which has interface similar to vector and
> takes O(log(N)) for inserting/erasing.
> Shortly speaking, it has BTrees inside and intrusive leaves, and exploits
> idea of so-called "rope".
>

Hi Alexander,

I also suggest providing results of some performance tests.

Any data structure that performs better than std::vector is very important
in practical applications. High linear computational cost of insertion and
erasure operations of this default STL container often leads to performance
bottlenecks in user algorithms. A comparison with std::vector is essential
to convince Boost users in the usefulness of your data structures.

The design method you used looks similar to augmenting a data structure.
There are two projects in Boost review queue that implement STL containers
based on two types of augmented trees: "STL Extensions" and "Countertree",
for more details see http://www.boost.org/community/review_schedule.html . It
would be helpful and interesting to see comparison of performance of your
data structures with the data structures waiting for review.

Regards,

Vadim Stadnik