[boost] [stl_ext_adv] comparison with Boost.Container and string algorithms

Subject: [boost] [stl_ext_adv] comparison with Boost.Container and string algorithms
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2012-11-21 05:54:44

Hi all,

In response to the previously made suggestion, I have added to the
documentation the comparison of new proposed STL containers with
Boost.Container. Please let me know if some of my statements concerning
Boost.Container are incorrect, I will update the documentation.

>From a user perspective an augmented array based B+ tree of the new
library can be regarded as a segmented vector that offers several more
efficient operations than std::vector: logarithmic time insertion, erasure,
splice and split. One such data structure can support interfaces of all
C++03 standard sequences and associative containers. This is why new
containers offer a higher level of uniformity and generalization of the C++
standard containers. Unlike std::vector, the new array based containers do
not have the problem of exponential storage growth and manual shrinking
storage to the optimal capacity.

The comparison section  also includes simple tests of performance. One test
shows the advantage of the wide set of efficient operations of new
containers. None of the C++ standard and Boost containers can outperform
new containers in the test with just two operations: move an iterator to a
specified position and then insert a new element. The other test shows that
new containers have good locality of reference. In sequential processing
they perform much better than containers using dynamically allocated data
structures.

String algorithms

The new sequence container that implements the union of interfaces of
std::vector, std::list and std::deque is particularly beneficial for string
algorithms. A container, such as std_ext_adv::sequence<char>, efficiently
supports all main editing string operations: cut, copy, paste, delete,
find, replace, etc. In terms of computational complexity this new container
provides general and equally efficient support for both copy and move
semantics operations. The move semantics functions splice() and split() can
be used to replace inefficient copy semantics functions insert() and
erase() to achieve significant performance improvements.

The examples section and code shows how to concatenate two strings and
extract a sub-string in logarithmic time using the move semantics
functions. These operations do not require that user algorithms count moved
characters. This functionality and efficiency are not possible with linked
lists and basic search trees.

The efficient calculation of statistical parameters and numerical
integration in logarithmic time are the other practically important
applications of the new containers. They are discussed in the examples
section.

Project (source code and documentation):

https://github.com/vstadnik/stl_ext_adv_review

Documentation:
http://dl.dropbox.com/u/51041088/stl_ext_adv_review/doc/index.html

Regards,
Vadim Stadnik