Proposal: Vector-like container, which takes O(log(N)) for insert/erase
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 would like to name it alex_kupriianov_array (after myself) and add it to boost. Please tell me who is the coordinator of containers and what is the procedure of adding something to boost. If the community finds it useful, I'll add more features. Among them: 1) non-intrusive version of the container; 2) shallow/partial/lazy copying; if you copy an array and then modify small part of it (for example, beginning), it will keep different beginnings and common end; 3) bookmarks - sort of sticky iterators, which are sticky to a certain element, no matter if there are insertions/deletions before them. Contact me: alexkupri at gmail dot com
On 17:01 Mon 31 Mar , Alexander Kuprijanov wrote:
I would like to name it alex_kupriianov_array (after myself) and add it to boost.
What a handy name!
Please tell me who is the coordinator of containers and what is the procedure of adding something to boost.
Your code needs to go through review[1] first, so it would help if you could post a link to your source repository first. Cheers -Andreas [1] http://www.boost.org/community/reviews.html -- ========================================================== Andreas Schäfer HPC and Grid Computing Chair of Computer Science 3 Friedrich-Alexander-Universität Erlangen-Nürnberg, Germany +49 9131 85-27910 PGP/GPG key via keyserver http://www.libgeodecomp.org ========================================================== (\___/) (+'.'+) (")_(") This is Bunny. Copy and paste Bunny into your signature to help him gain world domination!
Hi Alexander, Alexander Kuprijanov 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 would like to name it alex_kupriianov_array (after myself) and add it to boost.
Why not alex_kupriianov_btrees_rope? ;) But seriously, wouldn't it be more convenient to have separate B-tree and rope data structures implementations?
Please tell me who is the coordinator of containers and what is the procedure of adding something to boost.
www.boost.org/development/submissions.html Regards, Adam
On Mon, Mar 31, 2014 at 7:01 AM, Alexander Kuprijanov
I would like to name it alex_kupriianov_array (after myself) and add it to boost.
I don't think it's really in the style of Boost to have names like that. -- -Matt Calabrese
On Mon, Mar 31, 2014 at 7:01 AM, Alexander Kuprijanov wrote:
Hi, everybody! I've implemented a container, which has interface similar to vector and takes O(log(N)) for inserting/erasing.
HiAlexander, Can you provide some additional details? It would be a good idea to upload the code and documentation in a location that can be easily reviewed online. http://github.com could host both for you. Aside from describing the complexity of each operation, some performance measurements (and comparisons to other containers like std::deque) would also be worthwhile.
Please tell me who is the coordinator of containers and what is the procedure of adding something to boost.
Ion is the maintainer for that library; you can find his contact details at: http://github.com/boostorg/boost/blob/master/libs/maintainers.txt A typical sequence for contributing to Boost is: 1. Soliciting feedback on this mailing list 2. Submission (see http://www.boost.org/development/submissions.html for details) 3. Formal review (see http://www.boost.org/community/reviews.html for details)
I would like to name it alex_kupriianov_array (after myself) and add it to boost.
Identifiers in Boost Libraries don't contain the names of their inventors. :) (see http://www.boost.org/development/requirements.html for additional guidelines) Best, Glen
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
participants (6)
-
Adam Wulkiewicz -
Alexander Kuprijanov -
Andreas Schäfer -
Glen Fernandes -
Matt Calabrese -
Vadim Stadnik