Re: [boost] New library ( countertree: Binary trees with access by position like the vectors)

Subject: Re: [boost] New library ( countertree: Binary trees with access by position like the vectors)
From: Игорь Микушкин (igor.mikushkin_at_[hidden])
Date: 2010-09-28 07:16:33

On 28 September 2010 01:09, Francisco José Tapia <fjtapia_at_[hidden]> wrote:
> 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
> N).
>
> 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 iterator.
>
> 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 :
>
> http://www.boostpro.com/vault/index.php?action=downloadfile&filename=countertree.zip&directory=Containers&
>
> The compilers used for to check are GCC 4.5 ( 32 and 64 bits) and Visual
> Studio 2008
>

This is very interesting.
I needed such structure recently.
Could you please briefly describe algorithm.

Thanks,
Igor