On Wed, Feb 27, 2013 at 1:08 AM, Vadim Stadnik <vadimstdk@gmail.com> wrote:
Hi all,
At present, neither Boost library nor STL provides containers using augmented data structures. I suggest that the Boost community consider solving the challenging problem – how to extend STL by integrating advanced data structures.
[...] Augmented red-black trees could have been included in the very first version of STL.
Why is it difficult and has not been done yet?
The major obstacle for the integration is the C++ standard specification of computational complexities of single operations for containers and iterators.
I totally agree.
[...] There are two libraries in the Boost review schedule:
http://www.boost.org/community/review_schedule.html
"STL Extensions" and "Countertree". None of them has as yet a review manager. The order of the reviews may not be significant. It is more important that at least one library pass the review. This would help integrating other advanced data structures.
Are there Boost experts who could volunteer to take responsibility of review manager for any of these two libraries?
I really hope that some expert jumps in. In the meantime, I would like to point out some previous proposals of similar containers (including mine): 2004 (The oldest mention I could find. I don't know if it got implemented): http://lists.boost.org/Archives/boost/2004/03/62823.php 2006: "Hierarchical Data Structures" http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2101.html#tr.hierar... 2006: "AVL Array" (terrible name, I know) http://sourceforge.net/projects/avl-array Renamed as "Rank List" after some debate when proposed for Boost: http://boost.cvs.sourceforge.net/viewvc/boost-sandbox/boost-sandbox/libs/ran... This last version is probably outdated with respect to "AVL Array". And finally... 2012: Countertree http://dl.dropbox.com/u/8437476/works/countertree/doc/index.html I think that there are very interesting ideas in some of them. The "Hierarchical Data Structures" proposed "cursors" in addition to the ordinary iterators, to let the user traverse the tree at will ---not necessarily in-order---. In my proposal (AVL Array / Rank List), I decided to hide the internal structure of the tree, offering only iterators. As a result, I had to offer some additional methods, like a binary search (provided that the sequence is sorted). Later I found myself hacking into the tree structure to make some other experiments! I proposed augmenting the tree with an integer counting nodes in each subtree ---like all others--- but I also proposed augmenting the tree with a user-defined type. In the normal view of a sequence, every element occupies a unit of space. In what I called "Non-Proportional Sequence View" the user can decide the "virtual space" occupied by every element, and then jump to any position in that "virtual scale" in O(log N) time. I made some design decisions favouring functionality and low computational complexity over space. Every node contained pointers to the next and previous nodes in-order. Between this and the NPSV, they used a lot of space. At some point I increased their size even further, and the shocking result was that my experiments run faster. This leads me to think that a specific allocator ---like the one proposed in Countertree--- might help a lot. I also played with this concept of sequence ---with O(log N) random access and O(log N) insertion/removal--- in permanent storage. See "Shiftable Files" in the project "AVL Array". It is a toy implementation, but it works. I will love to discuss these ideas if anybody is interested. I would have said all this before, but I was disconnected from the Boost list for a long while and I didn't know that augmented trees had been proposed again. Sorry. Best regards, Martín Knoblauch Revuelta