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".
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk