Re: [boost] new proposal: order statistics tree

Subject: Re: [boost] new proposal: order statistics tree
From: Szymon Wojciechowski (sw10_at_[hidden])
Date: 2013-01-15 15:43:43

"Vadim Stadnik" <vadimstdk_at_[hidden]> pisze:

> The performance of your trees looks quite promising.
> What are the sizes of the data sets used in the tests?

I forgot to add this. The data sets had 30 000 elements.

> 
>
> The support of these operations with logarithmic running time would be
> quite beneficial for your variant of augmented trees.
> 
> The augmented trees can support not only STL associative containers, but
> also STL sequences, such as std::vector and std::list. String algorithms
> can also take advantage of these efficient operations. The split operation
> is general. The join and splice operations are general for STL sequences.
> For associative containers they can be used only in special cases. You can
> find more details in documentation to augmented B+ trees.
> 
> The CGAL library
> http://www.cgal.org/Manual/latest/doc_html/cgal_manual/STL_Extension_ref/Class_Multiset.html
> 
> implements split and join (as function catenate()) operations for
> Multiset. However, these trees are not augmented, this is why container
> sizes must be re-counted in linear time, which creates a performance
> problem for STL variants of containers. Note also that this is a problem of
> all dynamically allocated data structures that can support bidirectional
> iterators only, including std::list.
> 
> With augmented red-black trees the cost of these operations and
> corresponding member functions of STL containers should be logarithmic.

If it is possible as you said, it is worth to consider and do. However, now I would rather publish the code, so I am preparing it.