2010/9/27 Francisco José Tapia <fjtapia@gmail.com>
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 :
The compilers used for to check are GCC 4.5 ( 32 and 64 bits) and Visual Studio 2008
I have been looking for something just like the described library. I haven't had the time to look at the code yet, but I am definitely interested. Regards, Krzysztof Czaiński