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: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2010-09-28 11:33:21

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_at_[hidden]

2010/9/28 Rene Rivera <grafikrobot_at_[hidden]>

> 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
>