New library ( countertree: Binary trees with access by position like the vectors)
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 Thanks Francisco Tapia fjtapia@gmail.com
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
Francisco José Tapia 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).
How does this differ from Boost.MultiIndex which can provide random access plus ordered, key-based indices in a single container?
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.
A sorted vector, with map-like functionality, is certainly a useful data structure for occasions when it is mostly populated one time and accessed many times thereafter. Indeed, Meyers discussed it years ago in one of his books. The question is whether your vector_tree is better than what Boost.MultiIndex can do.
You can find the documentation, the code and the test programs in:
I haven't read your documentation yet, but may do so, based upon your response. _____ Rob Stewart robert.stewart@sig.com Software Engineer, Core Software using std::disclaimer; Susquehanna International Group, LLP http://www.sig.com IMPORTANT: The information contained in this email and/or its attachments is confidential. If you are not the intended recipient, please notify the sender immediately by reply and immediately delete this message and all its attachments. Any review, use, reproduction, disclosure or dissemination of this message or any attachment by an unintended recipient is strictly prohibited. Neither this message nor any attachment is intended as or should be construed as an offer, solicitation or recommendation to buy or sell any security or other financial instrument. Neither the sender, his or her employer nor any of their respective affiliates makes any warranties as to the completeness or accuracy of any of the information contained herein or that this message or any of its attachments is free of viruses.
On 28/09/10 11:49, Stewart, Robert wrote:
Francisco José Tapia 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).
How does this differ from Boost.MultiIndex which can provide random access plus ordered, key-based indices in a single container?
AFAIK, in that case Boost.MultiIndex stores the data and an index separately as two distinct structures. Counter trees provide both features in the same data structure; which might be a good idea or not.
On 28 September 2010 01:09, Francisco José Tapia <fjtapia@gmail.com> 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 :
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
On 9/27/2010 4:09 PM, Francisco José Tapia 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).
You might want to search this list for "ranktree" as there was discussions related to that a few years ago. There's also work in progress on a comprehensive tree library in the sandbox <https://svn.boost.org/svn/boost/sandbox/SOC/2006/tree/>. -- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org (msn) - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim,yahoo,skype,efnet,gmail
Several thinks : vector_tree is a data structure with the interface of a vector or a deque. The logic is like a vector. The information stored is unordered, like in a vector. The utility of this data structure is when you need insert or delete many elements in positions which are not the beginning or the end. In the vector, you must move the elements. If the vector is big, you spend many time moving the elements. In the documentation, in countertree.html you can see the test done with vector_tree and deque. Of course, the iterators of vector_tree are random access. You can know the position of the element pointed by an iterator with the function pos( ). If the information stored in the data structure is ordered, it is like the STL set , map …. but with access by position and random access iterators. Over the vector_tree, I had built the classes set, multiset, map and multimap. They have the same functionality than the STL set, multiset , map and multimap. The performance is similar to the STL data structures, and you have , too, access to the elements by position, and random access iterators which permit to know the position of the element pointed by an iterator with the function pos( ). The utility : Imagine you are working in a multicore system. You make a find with upper_bound ( ) and lower_ bound ( ). You want to know the number of elements selected for to divide the range and assign to the cores in a easy way. Remember, in STL set the function count ( ) is O(N) You have a multiset with the age of the employees of a company, and other with the weight. You need to select the employees within a range of age and within a range of weight. In the multiset of age, you obtain 10000 employees. In the multiset of weight you obtain 100 employees. It is faster to every element selected in the weight multiset, check the age, than to every element selected in the multiset of age, check the weight, If you know the size of the ranges , you can select the best option In the search you can use the position, by example: You have in a multimap the results of the last New York Marathon, sorted by the time spent , and now you need to know how many runners between the first 1000 spent less than 2 hours and half. But perhaps the idea is : you can do the same than the STL set, multiset, map and multimap, with a similar performance, but you have more things like the access by position and random access iterators In the documentation you have a test folder with examples and test programs of all the cklasses involved. I encourage you to see and test, it is very easy. And if you have any problem , please, contact me. Best regards Francisco José Tapia fjtapia@gmail.com 2010/9/28 Rene Rivera <grafikrobot@gmail.com>
On 9/27/2010 4:09 PM, Francisco José Tapia 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).
You might want to search this list for "ranktree" as there was discussions related to that a few years ago. There's also work in progress on a comprehensive tree library in the sandbox < https://svn.boost.org/svn/boost/sandbox/SOC/2006/tree/>.
-- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org (msn) - grafik/redshift-software.com -- 102708583/icq - grafikrobot/aim,yahoo,skype,efnet,gmail
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
participants (6)
-
Francisco José Tapia -
Krzysztof Czainski -
Mathias Gaunard -
Rene Rivera -
Stewart, Robert -
Игорь Микушкин