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
> 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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk