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