Subject: [boost] New library ( countertree: Binary trees with access by position like the vectors)
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2010-09-27 17:09:50
Is there any interest in a library implementing counter trees, which permit
us to access to the elements by the position, as in the same way than a
vector.The insertion, deletion and access to elements are operations O(log
The iterator and const_iterator are random access iterators in the same way
than the STL vector::iterator and STL vector::const_iterator. These
iterators and const_iterators have a function pos() which provide the
position in the tree.
The first class implemented is vector_tree wich has the full interface of
the STL vector and STL deque.
When the information stored in the vector_tree is sorted, we can build the
new classes boost::set, boost::multiset, boost::map and boost::multimap.
These clases have the full interface of the STL set , multiset, map and
multimap, plus a function which permit to access to the elements of the set,
map... by the position. The iterators of this data stuctures are random
access, and have a function to take the position of the element pointed by
The performance of these data stuctures is similar to the STL set, multiset,
map and multimap
You can find the documentation, the code and the test programs in :
The compilers used for to check are GCC 4.5 ( 32 and 64 bits) and Visual
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk