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 ;