On Tue, Apr 1, 2014 at 1:01 AM, Alexander Kuprijanov
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