Boost logo

Boost :

Subject: [boost] Formal Review Request [stl_ext_adv]
From: Vadim Stadnik (vadimstdk_at_[hidden])
Date: 2012-09-26 06:35:06

Hi all,

I would like to request a formal review of the library “STL extensions
based on advanced data structures” [stl_ext_adv].

Project location:

Quick view of documentation:

The previous version of this library is based on dynamically allocated data
structures. It was discussed by Boost community in this thread:

The new version has two major improvements. It offers more efficient array
based data structures and extensions of move semantics functions of STL

I am looking for the review manager. I would really appreciate if someone
interested in advanced data structures could take this role.

Early comments are welcome!


Vadim Stadnik


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


Boost list run by bdawes at, gregod at, cpdaniel at, john at