"Vadim Stadnik" <vadimstdk@gmail.com> 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/Cla...
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.