Copyright Vadim Stadnik 2011-2012. Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

SUMMARY

The proposed library stl_ext_adv offers augmented array based B+ trees and STL containers that support the interfaces of the C++03 sequences and associative containers. The library offers a number of extensions and performance improvements that are not available in C++03 and C++11 standard containers.

OVERVIEW

Both sequences and associative containers support:

• random access iterators;
• logarithmic time insert and erase operations for a single element anywhere within a container;

Sequences support:

• the union of interfaces of the C++03 sequence containers: std::list, std::deque and std::vector;
• complete set of move semantics functions splice() and split() that guarantee logarithmic complexity in the worst case;

Associative containers support:

• equally efficient access to elements by their keys and positions;
• logarithmic time search operations using keys of the container elements;
• logarithmic time split operations in the general case and logarithmic time merge operations in special cases.

One basic container implements the efficient algorithm accumulate(), which sums up any consecutive elements of a container in logarithmic time. The algorithm is fundamental to many important applications, such as the numerical integration and statistics.

The array based data structures improve locality of reference and offer more efficient algorithms against equivalent dynamically allocated data structures. The wide set of the efficient member functions provided by the new containers makes them useful to improve the performance of algorithms using the standard containers with at least one relatively inefficient operation or a bidirectional iterator.

EXAMPLES

Simple examples of uses of the containers and algorithms are available in the test code of this project, see files in the folder "test".

Examples in the folder "example" demonstrate how to improve the computational complexity from O(N) to O(log N) in the following applications and problems:

• numerical integration;
• calculation of mean value and standard deviation;
• calculation of weighted mean value;
• testing if any number of consecutive elements are equal;
• counting intersections of one interval with a sequence of intervals;
• string concatenation and replacement;

COMPILERS

• MSVC++ 9/10 (Visual Studio 2008/2010, including Express editions) ;
• GCC 4.5.2 (tested using MinGW) ;
• GCC 4.6, GCC 4.7 using Android NDK and ADT Eclipse ;