Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
72 lines (51 sloc) 2.61 KB
Copyright Vadim Stadnik 2011-2012.
Distributed under the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or copy at
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.
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
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;
- 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 ;