add subtree-ish sources for 12.0.3

[ceph.git] / ceph / src / boost / libs / container / doc / container.qbk

[/
 / Copyright (c) 2009-2013 Ion Gazta\u00F1aga
 /
 / 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)
 /]

[library Boost.Container
    [quickbook 1.5]
    [authors [Gaztanaga, Ion]]
    [copyright 2009-2015 Ion Gaztanaga]
    [id container]
    [dirname container]
    [purpose Containers library]
    [license
        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])
    ]
]

[template super[x]'''<superscript>'''[x]'''</superscript>''']
[template sub[x]'''<subscript>'''[x]'''</subscript>''']

[section:intro Introduction]

[*Boost.Container] library implements several well-known containers, including
STL containers. The aim of the library is to offers advanced features not present
in standard containers or to offer the latest standard draft features for compilers
that don't comply with the latest C++ standard.

In short, what does [*Boost.Container] offer?

* Move semantics are implemented, including move emulation for pre-C++11 compilers.
* New advanced features (e.g. placement insertion, recursive containers) are present.
* Containers support stateful allocators and are compatible with [*Boost.Interprocess]
  (they can be safely placed in shared memory).
* The library offers new useful containers:
  * [classref boost::container::flat_map flat_map],
    [classref boost::container::flat_set flat_set],
    [classref boost::container::flat_multimap flat_multimap] and
    [classref boost::container::flat_multiset flat_multiset]: drop-in
    replacements for standard associative containers but more memory friendly and with faster
    searches.
  * [classref boost::container::stable_vector stable_vector]: a std::list and std::vector hybrid
    container: vector-like random-access iterators and list-like iterator stability in insertions and erasures.
  * [classref boost::container::slist slist]: the classic pre-standard singly linked list implementation
    offering constant-time `size()`. Note that C++11 `forward_list` has no `size()`.

[section:introduction_building_container Building Boost.Container]

There is no need to compile [*Boost.Container], since it's a header-only library,
just include your Boost header directory in your compiler include path *except if you use*:

*  [link container.extended_functionality.extended_allocators Extended Allocators]
*  Some [link container.extended_functionality.polymorphic_memory_resources Polymorphic Memory Resources] classes.
   
Those exceptions are are implemented as a separately compiled library, so in those cases you must install binaries
in a location that can be found by your linker.
If you followed the [@http://www.boost.org/doc/libs/release/more/getting_started/index.html Boost Getting Started]
instructions, that's already been done for you.

[endsect]

[section:tested_compilers Tested compilers]

[*Boost.Container] requires a decent C++98 compatibility. Some compilers known to work are:

*  Visual C++ >= 7.1.
*  GCC >= 4.1.
*  Intel C++ >= 9.0

[endsect]

[endsect]

[section:main_features Main features]

[section:move_emplace Efficient insertion]

Move semantics and placement insertion are two features brought by C++11 containers
that can have a very positive impact in your C++ applications. Boost.Container implements
both techniques both for C++11 and C++03 compilers.

[section:move_containers Move-aware containers]

All containers offered by [*Boost.Container] can store movable-only types
and actual requirements for `value_type` depend on each container operations.
Following C++11 requirements even for C++03 compilers, many operations now require
movable or default constructible types instead of just copy constructible types.

Containers themselves are also movable, with no-throw guarantee if allocator
or predicate (if present) copy operations are no-throw. This allows
high performance operations when transferring data between vectors.
Let's see an example:

[import ../example/doc_move_containers.cpp]
[doc_move_containers]

[endsect]

[section:emplace Emplace: Placement insertion]

All containers offered by [*Boost.Container] implement placement insertion,
which means that  objects can be built directly into the container from user arguments
without creating any temporary object. For compilers without variadic templates support
placement insertion is emulated up to a finite (10) number of arguments.

Expensive to move types are perfect candidates emplace functions and in case of node containers
([classref boost::container::list list], [classref boost::container::set set], ...)
emplace allows storing non-movable and non-copyable types in containers! Let's
see an example:

[import ../example/doc_emplace.cpp]
[doc_emplace]

[endsect]

[endsect]


[section:containers_of_incomplete_types Containers of Incomplete Types]

Incomplete types allow
[@http://en.wikipedia.org/wiki/Type_erasure [*type erasure ]] and
[@http://en.wikipedia.org/wiki/Recursive_data_type [*recursive data types]], and
C and C++ programmers have been using it for years to build complex data structures, like
tree structures where a node may have an arbitrary number of children.

What about standard containers? Containers of incomplete types have been under discussion for a long time,
as explained in Matt Austern's great article ([@http://drdobbs.com/184403814 [*The Standard Librarian: Containers of Incomplete Types]]):

["['Unlike most of my columns, this one is about something you can't do with the C++ Standard library:
put incomplete types in one of the standard containers. This column explains why you might want to
do this, why the standardization committee banned it even though they knew it was useful, and what
you might be able to do to get around the restriction.]]

["['In 1997, shortly before the C++ Standard was completed, the standardization committee received a
query: Is it possible to create standard containers with incomplete types? It took a while for the
committee to understand the question. What would such a thing even mean, and why on earth would you
ever want to do it? The committee eventually worked it out and came up with an answer to the question.
(Just so you don't have to skip ahead to the end, the answer is "no.") But the question is much more
interesting than the answer: it points to a useful, and insufficiently discussed, programming technique.
The standard library doesn't directly support that technique, but the two can be made to coexist.]]

["['In a future revision of C++, it might make sense to relax the restriction on instantiating
standard library templates with incomplete types. Clearly, the general prohibition should stay
in place - instantiating templates with incomplete types is a delicate business, and there are
too many classes in the standard library where it would make no sense. But perhaps it should be
relaxed on a case-by-case basis, and `vector` looks like a good candidate for such special-case
treatment: it's the one standard container class where there are good reasons to instantiate
it with an incomplete type and where Standard Library implementors want to make it work. As of
today, in fact, implementors would have to go out of their way to prohibit it!]]

C++11 standard is also cautious about incomplete types and STL: ["['17.6.4.8 Other functions (...) 2.
the effects are undefined in the following cases: (...) In particular - if an incomplete type (3.9)
is used as a template argument when instantiating a template component,
unless specifically allowed for that component]].

Fortunately all [*Boost.Container] containers except
[classref boost::container::static_vector static_vector] and
[classref boost::container::basic_string basic_string] are designed to support incomplete types.
[classref boost::container::static_vector static_vector] is special because
it statically allocates memory for `value_type` and this requires complete types and
[classref boost::container::basic_string basic_string] implements Small String Optimization which
also requires complete types.

[*Boost.Container] containers supporting incomplete types also support instantiating iterators to
those incomplete elements.

[section:recursive_containers Recursive containers]

Most [*Boost.Container] containers can be used to define recursive containers:

[import ../example/doc_recursive_containers.cpp]
[doc_recursive_containers]

[endsect]

[section:type_erasure Type Erasure]

Containers of incomplete types are useful to break header file dependencies and improve
compilation types. With Boost.Container, you can write a header file defining a class
with containers of incomplete types as data members, if you carefully put all the
implementation details that require knowing the size of the `value_type` in your
implementation file:

[import ../example/doc_type_erasure.cpp]

In this header file we define a class (`MyClassHolder)` that holds a `vector` of an
incomplete type (`MyClass`) that it's only forward declared.

[doc_type_erasure_MyClassHolder_h]

Then we can define `MyClass` in its own header file.

[doc_type_erasure_MyClass_h]

And include it only in the implementation file of `MyClassHolder`

[doc_type_erasure_MyClassHolder_cpp]

Finally, we can just compile, link, and run!

[doc_type_erasure_main_cpp]

[endsect]

[endsect]

[section:scary_iterators SCARY iterators]

The paper N2913, titled [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2913.pdf,
SCARY Iterator Assignment and Initialization], proposed a requirement that a standard container's
iterator types have no dependency on any type argument apart from the container's `value_type`,
`difference_type`, `pointer type`, and `const_pointer` type. In particular, according to the proposal,
the types of a standard container's iterators should not depend on the container's `key_compare`,
`hasher`, `key_equal`, or `allocator` types.

That paper demonstrated that SCARY operations were crucial to the performant implementation of common
design patterns using STL components. It showed that implementations that support SCARY operations reduce
object code bloat by eliminating redundant specializations of iterator and algorithm templates.

[*Boost.Container] containers implement SCARY iterators so the iterator type of a container is only dependent
on the `allocator_traits<allocator_type>::pointer` type (the pointer type of the `value_type` to be inserted
in the container). Reference types and all other typedefs are deduced from the pointer type using the
C++11 `pointer_traits` utility. This leads to lower code bloat in algorithms and classes templated on
iterators.

[endsect]

[section:other_features Other features]

* Default constructors don't allocate memory which improves performance and
  usually implies a no-throw guarantee (if predicate's or allocator's default constructor doesn't throw).

* Small string optimization for [classref boost::container::basic_string basic_string],
  with an internal buffer of 11/23 bytes (32/64 bit systems)
  [*without] increasing the usual `sizeof` of the string (3 words).

* `[multi]set/map` containers are size optimized embedding the color bit of the red-black tree nodes
   in the parent pointer.

* `[multi]set/map` containers use no recursive functions so stack problems are avoided.

[endsect]

[endsect]

[section:exception_handling Boost.Container and C++ exceptions]

In some environments, such as game development or embedded systems, C++ exceptions are disabled or a customized error handling is needed.
According to document [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html N2271 EASTL -- Electronic Arts Standard Template Library]
exceptions can be disabled for several reasons:

*  ["['Exception handling incurs some kind of cost in all compiler implementations, including those that avoid
   the cost during normal execution. However, in some cases this cost may arguably offset the cost of the code that it is replacing.]]
*  ["['Exception handling is often agreed to be a superior solution for handling a large range of function return values. However,
   avoiding the creation of functions that need large ranges of return values is superior to using exception handling to handle such values.]]
*  ["['Using exception handling correctly can be difficult in the case of complex software.]]
*  ["['The execution of throw and catch can be significantly expensive with some implementations.]]
*  ["['Exception handling violates the don't-pay-for-what-you-don't-use design of C++, as it incurs overhead in any non-leaf function that
   has destructible stack objects regardless of whether they use exception handling.]]
*  ["['The approach that game software usually takes is to avoid the need for exception handling where possible; avoid the possibility
   of circumstances that may lead to exceptions. For example, verify up front that there is enough memory for a subsystem to do its job
   instead of trying to deal with the problem via exception handling or any other means after it occurs.]]
*  ["['However, some game libraries may nevertheless benefit from the use of exception handling. It's best, however,
   if such libraries keep the exception handling internal lest they force their usage of exception handling on the rest of the application.]]

In order to support environments without C++ exception support or environments with special error handling needs,
[*Boost.Container] changes error signalling behaviour when `BOOST_CONTAINER_USER_DEFINED_THROW_CALLBACKS` or `BOOST_NO_EXCEPTIONS`
is defined. The former shall be defined by the user and the latter can be either defined by the user or implicitly defined by [*Boost.Confg]
when the compiler has been invoked with the appropriate flag (like `-fno-exceptions` in GCC).

When dealing with user-defined classes, (e.g. when constructing user-defined classes):

*  If `BOOST_NO_EXCEPTIONS` is defined, the library avoids using `try`/`catch`/`throw` statements. The class writer must handle and
   propagate error situations internally as no error will be propagated through [*Boost.Container].
*  If `BOOST_NO_EXCEPTIONS` is *not* defined, the library propagates exceptions offering the exception guarantees detailed in the documentation.

When the library needs to throw an exception (such as `out_of_range` when an incorrect index is used in `vector::at`), the library calls
a throw-callback declared in [headerref boost/container/throw_exception.hpp]:

*  If `BOOST_CONTAINER_USER_DEFINED_THROW_CALLBACKS` is defined, then the programmer must provide its own definition for all
   `throw_xxx` functions. Those functions can't return, they must throw an exception or call `std::exit` or `std::abort`.
*  Else if `BOOST_NO_EXCEPTIONS` is defined, a `BOOST_ASSERT_MSG` assertion is triggered
   (see [@http://www.boost.org/libs/utility/assert.html Boost.Assert] for more information).
   If this assertion returns, then `std::abort` is called.
*  Else, an appropriate standard library exception is thrown (like `std::out_of_range`).

[endsect]

[section:non_standard_containers Non-standard containers]

[section:stable_vector ['stable_vector]]

This useful, fully STL-compliant stable container [@http://bannalia.blogspot.com/2008/09/introducing-stablevector.html designed by Joaqu\u00EDn M. L\u00F3pez Mu\u00F1oz]
is an hybrid between `vector` and `list`, providing most of
the features of `vector` except [@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#69 element contiguity].

Extremely convenient as they are, `vector`s have a limitation that many novice C++ programmers frequently stumble upon:
iterators and references to an element of an `vector` are invalidated when a preceding element is erased or when the
vector expands and needs to migrate its internal storage to a wider memory region (i.e. when the required size exceeds
the vector's capacity). We say then that `vector`s are unstable: by contrast, stable containers are those for which
references and iterators to a given element remain valid as long as the element is not erased: examples of stable containers
within the C++ standard library are `list` and the standard associative containers (`set`, `map`, etc.).

Sometimes stability is too precious a feature to live without, but one particular property of `vector`s, element contiguity,
makes it impossible to add stability to this container. So, provided we sacrifice element contiguity, how much
can a stable design approach the behavior of `vector` (random access iterators, amortized constant time end
insertion/deletion, minimal memory overhead, etc.)?
The following image describes the layout of a possible data structure upon which to base the design of a stable vector:

[$../../libs/container/doc/html/images/stable_vector.png  [width 50%] [align center] ]

Each element is stored in its own separate node. All the nodes are referenced from a contiguous array of pointers, but
also every node contains an "up" pointer referring back to the associated array cell. This up pointer is the key element
to implementing stability and random accessibility:

Iterators point to the nodes rather than to the pointer array. This ensures stability, as it is only the pointer array
that needs to be shifted or relocated upon insertion or deletion. Random access operations can be implemented by using
the pointer array as a convenient intermediate zone. For instance, if the iterator it holds a node pointer `it.p` and we
want to advance it by n positions, we simply do:

[c++]

   it.p = *(it.p->up+n);

That is, we go "up" to the pointer array, add n there and then go "down" to the resulting node.

[*General properties]. `stable_vector` satisfies all the requirements of a container, a reversible container and a sequence
and provides all the optional operations present in vector. Like vector, iterators are random access. `stable_vector`
does not provide element contiguity; in exchange for this absence, the container is stable, i.e. references and iterators
to an element of a `stable_vector` remain valid as long as the element is not erased, and an iterator that has been
assigned the return value of end() always remain valid until the destruction of the associated `stable_vector`.

[*Operation complexity]. The big-O complexities of `stable_vector` operations match exactly those of vector. In general,
insertion/deletion is constant time at the end of the sequence and linear elsewhere. Unlike vector, `stable_vector`
does not internally perform any value_type destruction, copy/move construction/assignment operations other than those exactly
corresponding to the insertion of new elements or deletion of stored elements, which can sometimes compensate in terms of
performance for the extra burden of doing more pointer manipulation and an additional allocation per element.

[*Exception safety]. (according to [@http://www.boost.org/community/exception_safety.html Abrahams' terminology])
As `stable_vector` does not internally copy/move elements around, some
operations provide stronger exception safety guarantees than in vector:

[table:stable_vector_req Exception safety
    [[operation] [exception safety for `vector<T>`] [exception safety for `stable_vector<T>`]]
    [[insert]    [strong unless copy/move construction/assignment of `T` throw (basic)]     [strong]]
    [[erase]     [no-throw unless copy/move construction/assignment  of `T` throw (basic)]     [no-throw]]
]

[*Memory overhead]. The C++ standard does not specifiy requirements on memory consumption, but virtually any implementation
of `vector` has the same behavior wih respect to memory usage: the memory allocated by a `vector` v with n elements of type T
is

m[sub v] = c\u2219e,

where c is `v.capacity()` and e is `sizeof(T)`. c can be as low as n if the user has explicitly reserved the exact capacity
required; otherwise, the average value c for a growing `vector` oscillates between 1.25\u2219n and 1.5\u2219n for typical resizing
policies. For `stable_vector`, the memory usage is

m[sub sv] = (c + 1)p + (n + 1)(e + p),

where p is the size of a pointer. We have c + 1 and n + 1 rather than c and n because a dummy node is needed at the end of
the sequence. If we call f the capacity to size ratio c/n and assume that n is large enough, we have that

m[sub sv]/m[sub v] \u2243 (fp + e + p)/fe.

So, `stable_vector` uses less memory than `vector` only when e > p and the capacity to size ratio exceeds a given threshold:

m[sub sv] < m[sub v] <-> f > (e + p)/(e - p). (provided e > p)

This threshold approaches typical values of f below 1.5 when e > 5p; in a 32-bit architecture, when e > 20 bytes.

[*Summary]. `stable_vector` is a drop-in replacement for `vector` providing stability of references and iterators, in exchange
for missing element contiguity and also some performance and memory overhead. When the element objects are expensive to
move around, the performance overhead can turn into a net performance gain for `stable_vector` if many middle insertions
or deletions are performed or if resizing is very frequent. Similarly, if the elements are large there are situations when
the memory used by `stable_vector` can actually be less than required by vector.

['Note: Text and explanations taken from [@http://bannalia.blogspot.com/2008/09/introducing-stablevector.html Joaqu\u00EDn's blog]]

[endsect]

[section:flat_xxx ['flat_(multi)map/set] associative containers]

Using sorted vectors instead of tree-based associative containers is a well-known technique in
C++ world. Matt Austern's  classic article
[@http://lafstern.org/matt/col1.pdf Why You Shouldn't Use set, and What You Should Use Instead]
(C++ Report 12:4, April 2000) was enlightening:

["['Red-black trees aren't the only way to organize data that permits lookup in logarithmic time.  One of the basic
algorithms of computer science is binary search, which works by successively dividing a range in half. Binary
search is log N and it doesn't require any fancy data structures, just a sorted collection of elements.
(...) You can use whatever data structure is convenient, so long as it provides STL iterator;
usually it's easiest to use a C array, or a vector.]]

["['Both std::lower_bound and set::find take time proportional to log N, but the constants of proportionality
are very different.  Using g++ (...) it takes X seconds to perform a million lookups in a
sorted vector<double> of a million elements, and almost twice as long (...) using a set. Moreover,
the set uses almost three times as much memory (48 million bytes) as the vector (16.8 million).]]

["['Using a sorted vector instead of a set gives you faster lookup and much faster iteration,
but at the cost of slower insertion.  Insertion into a set, using set::insert, is proportional
to log N, but insertion into a sorted vector, (...)
, is proportional to N. Whenever you insert something into a vector,
vector::insert has to make room by shifting all of the elements that follow it.  On average, if you're equally
likely to insert a new element anywhere, you'll be shifting N/2 elements.]]

["['It may sometimes be convenient to bundle all of this together into a small container adaptor.
This class does not satisfy the requirements of a Standard Associative Container, since the complexity of insert is
O(N) rather than O(log N), but otherwise it is almost a drop-in replacement for set.]]

Following Matt Austern's indications, Andrei Alexandrescu's
[@http://www.bestwebbuys.com/Modern-C-Design-Generic-Programming-and-Design-Patterns-Applied-ISBN-9780201704310?isrc=-rd Modern C++ Design]
showed `AssocVector`, a `std::map` drop-in
replacement designed in his [@http://loki-lib.sourceforge.net/ Loki] library:

["['It seems as if we're better off with a sorted vector. The disadvantages of a sorted
vector are linear-time insertions and linear-time deletions (...). In exchange, a vector
offers about twice the lookup speed and a much smaller working set (...).
Loki saves the trouble of maintaining a sorted vector by hand by defining an AssocVector class
template. AssocVector is a drop-in replacement for std::map (it supports the same set of member
functions), implemented on top of std::vector. AssocVector differs from a map in the behavior of
its erase functions (AssocVector::erase invalidates all iterators into the object) and in the
complexity guarantees of insert and erase (linear as opposed to constant). ]]

[*Boost.Container] `flat_[multi]map/set` containers are ordered-vector based associative containers
based on Austern's and Alexandrescu's guidelines. These ordered vector containers have also
benefited recently with the addition of `move semantics` to C++, speeding up insertion
and erasure times considerably. Flat associative containers have the following
attributes:

* Faster lookup than standard associative containers
* Much faster iteration than standard associative containers.
   Random-access iterators instead of bidirectional iterators.
* Less memory consumption for small objects (and for big objects if `shrink_to_fit` is used)
* Improved cache performance (data is stored in contiguous memory)
* Non-stable iterators (iterators are invalidated when inserting and erasing elements)
* Non-copyable and non-movable values types can't be stored
* Weaker exception safety than standard associative containers
(copy/move constructors can throw when shifting values in erasures and insertions)
* Slower insertion and erasure than standard associative containers (specially for non-movable types)

[endsect]

[section:slist ['slist]]

When the standard template library was designed, it contained a singly linked list called `slist`.
Unfortunately, this container was not standardized and remained as an extension for many standard
library implementations until C++11 introduced `forward_list`, which is a bit different from the
the original SGI `slist`. According to [@http://www.sgi.com/tech/stl/Slist.html SGI STL documentation]:

["['An `slist` is a singly linked list: a list where each element is linked to the next element, but
not to the previous element. That is, it is a Sequence that supports forward but not backward traversal,
and (amortized) constant time insertion and removal of elements. Slists, like lists, have the important
property that insertion and splicing do not invalidate iterators to list elements, and that even removal
invalidates only the iterators that point to the elements that are removed. The ordering of iterators
may be changed (that is, slist<T>::iterator might have a different predecessor or successor after a list
operation than it did before), but the iterators themselves will not be invalidated or made to point to
different elements unless that invalidation or mutation is explicit.]]

["['The main difference between `slist` and list is that list's iterators are bidirectional iterators,
while slist's iterators are forward iterators. This means that `slist` is less versatile than list;
frequently, however, bidirectional iterators are unnecessary. You should usually use `slist` unless
you actually need the extra functionality of list, because singly linked lists are smaller and faster
than double linked lists.]]

["['Important performance note: like every other Sequence, `slist` defines the member functions insert and erase.
Using these member functions carelessly, however, can result in disastrously slow programs. The problem is that
insert's first argument is an iterator pos, and that it inserts the new element(s) before pos. This means that
insert must find the iterator just before pos; this is a constant-time operation for list, since list has
bidirectional iterators, but for `slist` it must find that iterator by traversing the list from the beginning
up to pos. In other words: insert and erase are slow operations anywhere but near the beginning of the slist.]]

["['Slist provides the member functions insert_after and erase_after, which are constant time operations: you should
always use insert_after and erase_after whenever possible. If you find that insert_after and erase_after aren't
adequate for your needs, and that you often need to use insert and erase in the middle of the list, then you
should probably use list instead of slist.]]

[*Boost.Container] updates the classic `slist` container with C++11 features like move semantics and placement
insertion and implements it a bit differently than the standard C++ `forward_list`. `forward_list` has no `size()`
method, so it's been designed to allow (or in practice, encourage) implementations without tracking list size
with every insertion/erasure, allowing constant-time
`splice_after(iterator, forward_list &, iterator, iterator)`-based list merging. On the other hand `slist` offers
constant-time `size()` for those that don't care about linear-time `splice_after(iterator, slist &, iterator, iterator)`
`size()` and offers an additional `splice_after(iterator, slist &, iterator, iterator, size_type)` method that
can speed up `slist` merging when the programmer already knows the size. `slist` and `forward_list` are therefore
complementary.

[endsect]

[section:static_vector ['static_vector]]

`static_vector` is an hybrid between `vector` and `array`: like `vector`, it's a sequence container
with contiguous storage that can change in size, along with the static allocation, low overhead,
and fixed capacity of `array`. `static_vector` is based on Adam Wulkiewicz and Andrew Hundt's
high-performance [@https://svn.boost.org/svn/boost/sandbox/varray/doc/html/index.html varray]
class.

The number of elements in a `static_vector` may vary dynamically up to a fixed capacity
because elements are stored within the object itself similarly to an array. However, objects are
initialized as they are inserted into `static_vector` unlike C arrays or `std::array` which must construct
all elements on instantiation. The behavior of `static_vector` enables the use of statically allocated
elements in cases with complex object lifetime requirements that would otherwise not be trivially
possible. Some other properties:

* Random access to elements
* Constant time insertion and removal of elements at the end
* Linear time insertion and removal of elements at the beginning or in the middle.

`static_vector` is well suited for use in a buffer, the internal implementation of other
classes, or use cases where there is a fixed limit to the number of elements that must be stored.
Embedded and realtime applications where allocation either may not be available or acceptable
are a particular case where `static_vector` can be beneficial.

[endsect]

[section:small_vector ['small_vector]]

`small_vector` is a vector-like container optimized for the case when it contains few elements.
It contains some preallocated elements in-place, which allows it to avoid the use of dynamic storage allocation
when the actual number of elements is below that preallocated threshold. `small_vector` is inspired by
[@http://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h LLVM's `SmallVector`] container.
Unlike `static_vector`, `small_vector`'s capacity can grow beyond the initial preallocated capacity.

`small_vector<T, N, Allocator>` is convertible to `small_vector_base<T, Allocator>`, a type that is independent
from the preallocated element count, allowing client code that does not need to be templated on that N argument.
`small_vector` inherits all `vector`'s member functions so it supports all standard features like emplacement,
stateful allocators, etc.

[endsect]

[endsect]

[section:extended_functionality Extended functionality]

[section:default_initialialization Default initialization for vector-like containers]

STL and most other containers value initialize new elements in common operations like
`vector::resize(size_type n)` or `explicit vector::vector(size_type n)`.

In some performance-sensitive environments, where vectors are used as a replacement for
variable-size buffers for file or network operations,
[@http://en.cppreference.com/w/cpp/language/value_initialization value initialization]
is a cost that is not negligible as elements are going to be overwritten by an external source
shortly after new elements are added to the container.

[*Boost.Container] offers two new members for `vector`, `static_vector` and `stable_vector`:
`explicit container::container(size_type n, default_init_t)` and
`explicit container::resize(size_type n, default_init_t)`, where new elements are constructed
using [@http://en.cppreference.com/w/cpp/language/default_initialization default initialization].

[endsect]

[section:ordered_range_insertion Ordered range insertion for associative containers (['ordered_unique_range], ['ordered_range]) ]

When filling associative containers big performance gains can be achieved if the input range to be inserted
is guaranteed by the user to be ordered according to the predicate. This can happen when inserting values from a `set` to
a `multiset` or between different associative container families (`[multi]set/map` vs. `flat_[multi]set/map`).

[*Boost.Container] has some overloads for constructors and insertions taking an `ordered_unique_range_t` or
an `ordered_range_t` tag parameters as the first argument. When an `ordered_unique_range_t` overload is used, the
user notifies the container that the input range is ordered according to the container predicate and has no
duplicates. When an `ordered_range_t` overload is used, the
user notifies the container that the input range is ordered according to the container predicate but it might
have duplicates. With this information, the container can avoid multiple predicate calls and improve insertion
times.

[endsect]

[section:configurable_tree_based_associative_containers Configurable tree-based associative ordered containers]

[classref boost::container::set set], [classref boost::container::multiset multiset],
[classref boost::container::map map] and [classref boost::container::multimap multimap] associative containers
are implemented as binary search trees which offer the needed complexity and stability guarantees required by the
C++ standard for associative containers.

[*Boost.Container] offers the possibility to configure at compile time some parameters of the binary search tree
implementation. This configuration is passed as the last template parameter and defined using the utility class
[classref boost::container::tree_assoc_options tree_assoc_options].

The following parameters can be configured:

*  The underlying [*tree implementation] type ([classref boost::container::tree_type tree_type]).
   By default these containers use a red-black tree but the user can use other tree types:
   *  [@http://en.wikipedia.org/wiki/Red%E2%80%93black_tree Red-Black Tree]
   *  [@http://en.wikipedia.org/wiki/Avl_trees AVL tree]
   *  [@http://en.wikipedia.org/wiki/Scapegoat_tree Scapegoat tree]. In this case Insertion and Deletion
      are amortized O(log n) instead of O(log n).
   *  [@http://en.wikipedia.org/wiki/Splay_tree Splay tree]. In this case Searches, Insertions and Deletions
      are amortized O(log n) instead of O(log n).

*  Whether the [*size saving] mechanisms are used to implement the tree nodes
   ([classref boost::container::optimize_size optimize_size]). By default this option is activated and is only
   meaningful to red-black and avl trees (in other cases, this option will be ignored).
   This option will try to put rebalancing metadata inside the "parent" pointer of the node if the pointer
   type has enough alignment. Usually, due to alignment issues, the metadata uses the size of a pointer yielding
   to four pointer size overhead per node, whereas activating this option usually leads to 3 pointer size overhead.
   Although some mask operations must be performed to extract
   data from this special "parent" pointer, in several systems this option also improves performance due to the
   improved cache usage produced by the node size reduction.

See the following example to see how [classref boost::container::tree_assoc_options tree_assoc_options] can be
used to customize these containers:

[import ../example/doc_custom_tree.cpp]
[doc_custom_tree]

[endsect]

[section:constant_time_range_splice Constant-time range splice for `(s)list`]

In the first C++ standard `list::size()` was not required to be constant-time,
and that caused some controversy in the C++ community. Quoting Howard Hinnant's
[@http://howardhinnant.github.io/On_list_size.html ['On List Size]] paper:

[: ['There is a considerable debate on whether `std::list<T>::size()` should be O(1) or O(N).
The usual argument notes that it is a tradeoff with:]

`splice(iterator position, list& x, iterator first, iterator last);`

['If size() is O(1) and this != &x, then this method must perform a linear operation so that it
can adjust the size member in each list]]

C++11 definitely required `size()` to be O(1), so range splice became O(N). However,
Howard Hinnant's paper proposed a new `splice` overload so that even O(1) `list:size()`
implementations could achieve O(1) range splice when the range size was known to the caller:

[: `void splice(iterator position, list& x, iterator first, iterator last, size_type n);`

   [*Effects]: Inserts elements in the range [first, last) before position and removes the elements from x.

   [*Requires]: [first, last) is a valid range in x. The result is undefined if position is an iterator in the range [first, last). Invalidates only the iterators and references to the spliced elements. n == distance(first, last).

   [*Throws]: Nothing.

   [*Complexity]: Constant time.
]

This new splice signature allows the client to pass the distance of the input range in.
This information is often available at the call site. If it is passed in,
then the operation is constant time, even with an O(1) size.

[*Boost.Container] implements this overload for `list` and a modified version of it for `slist`
(as `slist::size()` is also `O(1)`).

[endsect]

[section:extended_allocators Extended allocators]

Many C++ programmers have ever wondered where does good old realloc fit in C++. And that's a good question.
Could we improve [classref boost::container::vector vector] performance using memory expansion mechanisms
to avoid too many copies? But [classref boost::container::vector vector] is not the only container that
could benefit from an improved allocator interface: we could take advantage of the insertion of multiple
elements in [classref boost::container::list list] using a burst allocation mechanism that could amortize
costs (mutex locks, free memory searches...) that can't be amortized when using single node allocation
strategies.

These improvements require extending the STL allocator interface and use make use of a new
general purpose allocator since new and delete don't offer expansion and burst capabilities.

*  [*Boost.Container] containers support an extended allocator interface based on an evolution of proposals
[@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1953.html N1953: Upgrading the Interface of Allocators using API Versioning],
[@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html N2045: Improving STL allocators]
and the article
[@http://www.drivehq.com/web/igaztanaga/allocplus/ Applying classic memory allocation strategies to C++ containers].
The extended allocator interface is implemented by [classref boost::container::allocator allocator],
[classref boost::container::adaptive_pool adaptive_pool] and [classref boost::container::node_allocator node_allocator]
classes.

*  Extended allocators use a modified [@http://g.oswego.edu/dl/html/malloc.html Doug Lea Malloc (DLMalloc)] low-level
allocator and offers an C API to implement memory expansion and burst allocations. DLmalloc is known to be very size
and speed efficient, and this allocator is used as the basis of many malloc implementations, including multithreaded
allocators built above DLmalloc (See [@http://www.malloc.de/en/ ptmalloc2, ptmalloc3] or
[@http://www.nedprod.com/programs/portable/nedmalloc/ nedmalloc]). This low-level allocator is implemented as
a separately compiled library and the following extended allocators depend on the library:

*  [classref boost::container::allocator allocator]: This extended allocator offers expansion, shrink-in place
   and burst allocation capabilities implemented as a thin wrapper around the modified DLMalloc.
   It can be used with all containers and it should be the default choice when the programmer wants to use
   extended allocator capabilities.

*  [classref boost::container::node_allocator node_allocator]: It's a
   [@http://www.boost.org/doc/libs/1_55_0/libs/pool/doc/html/boost_pool/pool/pooling.html#boost_pool.pool.pooling.simple Simple Segregated Storage]
   allocator, similar to [*Boost.Pool] that takes advantage of the modified DLMalloc burst interface. It does not return
   memory to the DLMalloc allocator (and thus, to the system), unless explicitly requested. It does offer a very small
   memory overhead so it's suitable for node containers ([boost::container::list list], [boost::container::slist slist]
   [boost::container::set set]...) that allocate very small `value_type`s and it offers improved node allocation times
   for single node allocations with respecto to [classref boost::container::allocator allocator].

*  [classref boost::container::adaptive_pool adaptive_pool]: It's a low-overhead node allocator that can return memory
   to the system. The overhead can be very low (< 5% for small nodes) and it's nearly as fast as [classref boost::container::node_allocator node_allocator].
   It's also suitable for node containers.

Use them simply specifying the new allocator in the corresponding template argument of your favourite container:

[import ../example/doc_extended_allocators.cpp]
[doc_extended_allocators]

[endsect]

[section:polymorphic_memory_resources Polymorphic Memory Resources ]

The document
[@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4480.html C++ Extensions for Library Fundamentals (Final draft: N4480)]
includes classes that provide allocator type erasure and runtime polymorphism. As Pablo Halpern, the author of the proposal,
explains in the paper ([@https://isocpp.org/files/papers/N3916.pdf N3916 Polymorphic Memory Resources (r2)]):

["['A significant impediment to effective memory management in C++ has been the 
inability to use allocators in non-generic contexts.  In large software systems,
most of  the application program consists of non-generic procedural or
object-oriented code that is compiled once and linked many times.]]

["['Allocators in C++, however, have historically relied solely on
compile-time polymorphism, and therefore have not been suitable for use in vocabulary
types, which are passed through interfaces between separately-compiled modules,
because the allocator type necessarily affects the type of the object that uses it.
This proposal builds upon the improvements made to allocators in 
C++11 and describes a set of facilities for runtime polymorphic memory 
resources that interoperate with the existing compile-time polymorphic 
allocators.]]

[*Boost.Container] implements nearly all classes of the proposal under
the namespace `boost::container::pmr`. There are two groups,

*  Header only utilities (these don't require the separately compiled library): 
   *    [classref boost::container::pmr::memory_resource memory_resource].
   *    [classref boost::container::pmr::resource_adaptor resource_adaptor].

*  Utilities that require the the separately compiled library: 
   *    [classref boost::container::pmr::polymorphic_allocator polymorphic_allocator].
   *    [classref boost::container::pmr::monotonic_buffer_resource monotonic_buffer_resource].
   *    [classref boost::container::pmr::unsynchronized_pool_resource unsynchronized_pool_resource].
   *    [classref boost::container::pmr::synchronized_pool_resource synchronized_pool_resource].
   *  Global resource functions: [funcref  boost::container::pmr::get_default_resource get_default_resource]/
      [funcref  boost::container::pmr::set_default_resource set_default_resource]/
      [funcref  boost::container::pmr::new_delete_resource  new_delete_resource]/
      [funcref  boost::container::pmr::null_memory_resource null_memory_resource]
   *  Aliases for boost containers using the polymorphic allocator
      (like [classref boost::container::pmr::vector pmr::vector], etc.)

[*Boost.Container]'s polymorphic resource library is usable from C++03 containers,
and offers some alternative utilities if the required C++11 features of the
['Library Fundamentals] specification are not available.

[import ../example/doc_pmr.cpp]

Let's review the usage example given in
[@https://isocpp.org/files/papers/N3916.pdf N3916] and see how it can be implemented
using [*Boost.Container]: ['Suppose we are processing a series of shopping lists, where a shopping list is a
container of strings, and storing them in a collection (a list) of shopping lists.
Each shopping list being processed uses a bounded amount of memory that is needed for
a short period of time, while the collection of shopping lists uses an unbounded
amount of memory and will exist for a longer period of time. For efficiency, we can
use a more time-efficient memory allocator based on a finite buffer for the temporary
shopping lists.]

Let's see how `ShoppingList` can be defined to support an polymorphic memory resource
that can allocate memory from different underlying mechanisms. The most important
details are:

* It should declare that supports an allocator defining an `allocator_type` typedef.
  This `allocator_type` will be of type [classref boost::container::pmr::memory_resource memory_resource *],
  which is a base class for polymorphic resources.
* It must define constructors that take the 
  the allocator as argument. It can be implemented in two ways:
   * `ShoppingList` has constructors taking
      [classref boost::container::pmr::memory_resource memory_resource*] as the last argument.
   * `ShoppingList` has constructors taking
      [classref boost::container::allocator_arg_t allocator_arg_t] as the first argument
     and [classref boost::container::pmr::memory_resource memory_resource*] as the second argument.

[*Note:] ['In C++03 compilers, it is required that the programmer specializes as `true`
[classref boost::container::constructible_with_allocator_suffix constructible_with_allocator_suffix] or
[classref boost::container::constructible_with_allocator_prefix constructible_with_allocator_prefix]
as in C++03 there is no way to automatically detect the chosen option at compile time. If
no specialization is done, [*Boost.Container] assumes the suffix option].

[doc_pmr_ShoppingList_hpp]

['However, this time-efficient allocator is not appropriate for the longer
lived collection of shopping lists. This example shows how those temporary shopping
lists, using a time-efficient allocator, can be used to populate the long lived collection
of shopping lists, using a general purpose allocator, something that would be
annoyingly difficult without the polymorphic allocators.]

In [*Boost.Container] for the time-efficient allocation we can use
[classref boost::container::pmr::monotonic_buffer_resource monotonic_buffer_resource],
providing an external buffer that will be used until it's exhausted. In the default
configuration, when the buffer is exhausted, the default memory resource will be used
instead.

[doc_pmr_main_cpp]

['Notice that the shopping lists within `folder` use the default allocator resource
whereas the shopping list `temporaryShoppingList` uses the short-lived but very fast
`buf_rsrc`. Despite using different allocators, you can insert
`temporaryShoppingList` into folder because they have the same `ShoppingList`
type. Also, while `ShoppingList` uses memory_resource directly,
[classref boost::container::pmr::list pmr::list],
[classref boost::container::pmr::vector pmr::vector]
and [classref boost::container::pmr::string pmr::string] all use 
[classref boost::container::pmr::polymorphic_allocator polymorphic_allocator].]

['The resource passed to the `ShoppingList` constructor is propagated to the vector and
each string within that `ShoppingList`. Similarly, the resource used to construct
`folder` is propagated to the constructors of the ShoppingLists that are inserted into
the list (and to the strings within those `ShoppingLists`). The
[classref boost::container::pmr::polymorphic_allocator polymorphic_allocator]
template is designed to be almost interchangeable with a pointer to
[classref boost::container::pmr::memory_resource memory_resource],
thus producing a ['bridge] between the template-policy
style of allocator and the polymorphic-base-class style of allocator.]

This example actually shows how easy is to use [*Boost.Container] to write
type-erasured allocator-capable classes even in C++03 compilers.

[endsect]

[/
/a__section:previous_element_slist Previous element for slist__a
/
/The C++11 `std::forward_list` class implement a singly linked list, similar to `slist`, and these
/containers only offer forward iterators and implement insertions and splice operations that operate with ranges
/to be inserted ['after] that position. In those cases, sometimes it's interesting to obtain an iterator pointing
/to the previous element of another element. This operation can be implemented
/
/a__endsect__a
]

[/
/a__section:get_stored_allocator Obtain stored allocator__a
/
/STL containers offer a `get_allocator()` member to obtain a copy of the allocator that
/the container is using to allocate and construct elements. For performance reasons, some
/applications need o
/
/http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html
/
/a__endsect__a
/]

[endsect]

[section:Cpp11_conformance C++11/C++14 Conformance]

[*Boost.Container] aims for full C++11 conformance except reasoned deviations,
backporting as much as possible for C++03. Obviously, this conformance is a work
in progress so this section explains what C++11 features are implemented and which of them
have been backported to C++03 compilers.

[section:move_emplace Move and Emplace]

For compilers with rvalue references and for those C++03 types that use
[@http://www.boost.org/libs/move Boost.Move] rvalue reference emulation
[*Boost.Container] supports all C++11 features related to move semantics: containers
are movable, requirements for `value_type` are those specified for C++11 containers.

For compilers with variadic templates, [*Boost.Container] supports placement insertion
(`emplace`, ...) functions from C++11. For those compilers without variadic templates
support [*Boost.Container] uses the preprocessor to create a set of overloads up to
a finite number of parameters.

[endsect]

[section:alloc_traits_move_traits Stateful allocators]

C++03 was not stateful-allocator friendly. For compactness of container objects and for
simplicity, it did not require containers to support allocators with state: Allocator objects
need not be stored in container objects. It was not possible to store an allocator with state,
say an allocator that holds a pointer to an arena from which to allocate. C++03 allowed implementors
to suppose two allocators of the same type always compare equal (that means that memory allocated
by one allocator object could be deallocated by another instance of the same type) and
allocators were not swapped when the container was swapped.

C++11 further improves stateful allocator support through
[@http://en.cppreference.com/w/cpp/memory/allocator_traits `std::allocator_traits`].
`std::allocator_traits` is the protocol between a container and an allocator, and
an allocator writer can customize its behaviour (should the container propagate it in
move constructor, swap, etc.?) following `allocator_traits` requirements. [*Boost.Container]
not only supports this model with C++11 but also [*backports it to C++03] via
[classref boost::container::allocator_traits boost::container::allocator_traits] including some
C++17 changes. This class
offers some workarounds for C++03 compilers to achieve the same allocator guarantees as
`std::allocator_traits`.

In [Boost.Container] containers, if possible, a single allocator is hold to construct
`value_type`s. If the container needs an auxiliary
allocator (e.g. an array allocator used by `deque` or `stable_vector`), that allocator is also
stored in the container and initialized from the user-supplied allocator when the
container is constructed (i.e. it's not constructed on the fly when auxiliary memory is needed).

[endsect]

[section:scoped_allocator Scoped allocators]

C++11 improves stateful allocators with the introduction of
[@http://en.cppreference.com/w/cpp/memory/scoped_allocator_adaptor `std::scoped_allocator_adaptor`]
class template. `scoped_allocator_adaptor` is instantiated with one outer allocator and zero or more inner
allocators.

A scoped allocator is a mechanism to automatically propagate the state of the allocator to the subobjects
of a container in a controlled way. If instantiated with only one allocator type, the inner allocator
becomes the `scoped_allocator_adaptor` itself, thus using the same allocator
resource for the container and every element within the container and, if the elements themselves are
containers, each of their elements recursively. If instantiated with more than one allocator, the first allocator
is the outer allocator for use by the container, the second allocator is passed to the constructors of the
container's elements, and, if the elements themselves are containers, the third allocator is passed to the
elements' elements, and so on.

[*Boost.Container] implements its own [classref boost::container::scoped_allocator_adaptor scoped_allocator_adaptor]
class and [*backports this feature also
to C++03 compilers]. Due to C++03 limitations, in those compilers
the allocator propagation implemented by `scoped_allocator_adaptor::construct` functions
will be based on traits ([classref boost::container::constructible_with_allocator_suffix constructible_with_allocator_suffix]
and [classref boost::container::constructible_with_allocator_prefix constructible_with_allocator_prefix])
proposed in [@http://www.open-std.org/jtc1/sc22/WG21/docs/papers/2008/n2554.pdf
N2554: The Scoped Allocator Model (Rev 2) proposal]. In conforming C++11 compilers or compilers supporting SFINAE
expressions (when `BOOST_NO_SFINAE_EXPR` is NOT defined), traits are ignored and C++11 rules
(`is_constructible<T, Args..., inner_allocator_type>::value` and
`is_constructible<T, allocator_arg_t, inner_allocator_type, Args...>::value`)
will be used to detect if the allocator must be propagated with suffix or prefix allocator arguments.

[endsect]

[section:insertion_hints Insertion hints in associative containers and preserving
 insertion ordering for elements with equivalent keys]

[@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#233 LWG Issue #233] corrected a defect
in C++98 and specified how equivalent keys were to be inserted in associative containers. [*Boost.Container]
implements the C++11 changes that were specified in [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html N1780
['Comments on LWG issue 233: Insertion hints in associative containers]]:

* `a_eq.insert(t)`: If a range containing elements equivalent to t exists in a_eq, t is inserted at the end of that range.
* `a_eq.insert(p,t)`: t is inserted as close as possible to the position just prior to p.

[endsect]

[section:initializer_lists Initializer lists]

[*Boost.Container] supports initialization, assignments and insertions from initializer lists
in compilers that implement this feature.

[endsect]

[section:null_iterators Null Forward Iterators]

[*Boost.Container] implements
[@http://www.open-std.org/JTC1/sc22/WG21/docs/papers/2013/n3644.pdf C++14 Null Forward Iterators],
which means that value-initialized iterators may be compared and compare equal
to other value-initialized iterators of the same type. Value initialized iterators behave as if they refer
past the end of the same empty sequence (example taken from N3644):

[c++]

   vector<int> v = { ... };
   auto ni = vector<int>::iterator();
   auto nd = vector<double>::iterator();
   ni == ni; // True.
   nd != nd; // False.
   v.begin() == ni; // ??? (likely false in practice).
   v.end() == ni;   // ??? (likely false in practice).
   ni == nd; // Won't compile.

[endsect]

[section:forward_list `forward_list<T>`]

[*Boost.Container] does not offer C++11 `forward_list` container yet, but it will be available in future
versions.

[endsect]

[section:vector_exception_guarantees `vector` vs. `std::vector` exception guarantees]

[classref boost::container::vector vector] does not support the strong exception guarantees
given by `std::vector` in functions like `insert`, `push_back`, `emplace`, `emplace_back`,
`resize`, `reserve` or `shrink_to_fit` for either copyable or no-throw moveable classes.
In C++11 [@http://en.cppreference.com/w/cpp/utility/move_if_noexcept move_if_noexcept] is used
to maintain C++03 exception safety guarantees combined with C++11 move semantics.
This strong exception guarantee degrades the insertion performance of copyable and throwing-moveable types,
degrading moves to copies when such types are inserted in the vector using the aforementioned
members.

This strong exception guarantee also precludes the possibility of using some type of
in-place reallocations that can further improve the insertion performance of `vector` See
[link container.extended_functionality.extended_allocators Extended Allocators] to know more
about these optimizations.

[classref boost::container::vector vector] always uses move constructors/assignments
to rearrange elements in the vector and uses memory expansion mechanisms if the allocator supports them,
while offering only basic safety guarantees. It trades off exception guarantees for an improved performance.

[endsect]

[section:container_const_reference_parameters Parameter taken by const reference that can be changed]

Several container operations use a parameter taken by const reference that can be changed during execution of the function.
[@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#526 LWG Issue 526
   (['Is it undefined if a function in the standard changes in parameters?])]
discusses them:

[c++]

   //Given std::vector<int> v
   v.insert(v.begin(), v[2]);
   //v[2] can be changed by moving elements of vector

   //Given std::list<int> l:
   l.remove(*l.begin())
   //The operation could delete the first element, and then continue trying to access it.

The adopted resolution, NAD (Not A Defect), implies that previous operations must be well-defined. This requires code
to detect a reference to an inserted element and an additional copy in that case, impacting performance even when
references to already inserted objects are not used. Note that equivalent functions taking rvalue references or
iterator ranges require elements not already inserted in the container.

[*Boost.Container] prioritizes performance and has not implemented the NAD resolution:
in functions that might modify the argument, the library requires references to elements not stored
in the container. Using references to inserted elements yields to undefined behaviour (although in debug mode, this
precondition violation could be notified via BOOST_ASSERT).

[endsect]

[section:Vector_bool `vector<bool>` specialization]

`vector<bool>` specialization has been quite problematic, and there have been several
unsuccessful tries to deprecate or remove it from the standard. [*Boost.Container] does not implement it
as there is a superior [@http://www.boost.org/libs/dynamic_bitset/ Boost.DynamicBitset]
solution. For issues with `vector<bool>` see the following papers:

* [@http://howardhinnant.github.io/onvectorbool.html On `vector<bool>`]
* [@http://www.gotw.ca/publications/N1211.pdf vector<bool>: N1211: More Problems, Better Solutions],
* [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2160.html N2160: Library Issue 96: Fixing vector<bool>],
* [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2204.html N2204 A Specification to deprecate vector<bool>].

Quotes:

* ["['But it is a shame that the C++ committee gave this excellent data structure the name vector<bool> and
  that it gives no guidance nor encouragement on the critical generic algorithms that need to be optimized for this
  data structure. Consequently, few std::lib implementations go to this trouble.]]

* ["['In 1998, admitting that the committee made a mistake was controversial.
  Since then Java has had to deprecate such significant portions of their libraries
  that the idea C++ would be ridiculed for deprecating a single minor template specialization seems quaint.]]

* ["['`vector<bool>` is not a container and `vector<bool>::iterator` is not a random-access iterator
(or even a forward or bidirectional iterator either, for that matter). This has already broken user code
in the field in mysterious ways.]]

* ["['`vector<bool>` forces a specific (and potentially bad) optimization choice on all users by enshrining
it in the standard. The optimization is premature; different users have different requirements. This too
has already hurt users who have been forced to implement workarounds to disable the 'optimization'
(e.g., by using a vector<char> and manually casting to/from bool).]]

So `boost::container::vector<bool>::iterator` returns real `bool` references and works as a fully compliant container.
If you need a memory optimized version of `boost::container::vector<bool>`, please use
[@http://www.boost.org/libs/dynamic_bitset/ Boost.DynamicBitset].

[endsect]

[section:non_standard_memset_initialization Non-standard value initialization using `std::memset`]

[*Boost.Container] uses `std::memset` with a zero value to initialize some types as in most platforms this
initialization yields to the desired value initialization with improved performance.

Following the C11 standard, [*Boost.Container] assumes that ['for any integer type,
the object representation where all the bits are zero shall be a representation of the value
zero in that type]. Since `_Bool`/`wchar_t`/`char16_t`/`char32_t` are also integer types in C, it considers
all C++ integral types as initializable via `std::memset`.

By default, [*Boost.Container] also considers floating point types to be initializable using `std::memset`.
Most platforms are compatible with this initialization, but in case this initialization is not desirable the
user can `#define BOOST_CONTAINER_MEMZEROED_FLOATING_POINT_IS_NOT_ZERO` before including library headers.

By default, it also considers pointer types (pointer and pointer to function types, excluding
member object and member function pointers) to be initializable using `std::memset`.
Most platforms are compatible with this initialization, but in case this initialization is not desired the
user can `#define BOOST_CONTAINER_MEMZEROED_POINTER_IS_NOT_ZERO` before including library headers.

If neither `BOOST_CONTAINER_MEMZEROED_FLOATING_POINT_IS_NOT_ZERO` nor
`BOOST_CONTAINER_MEMZEROED_POINTER_IS_NOT_ZERO` is defined [*Boost.Container] also considers POD
types to be value initializable via `std::memset` with value zero.

[endsect]

[endsect]

[section:known_issues Known Issues]

[section:move_emulation_limitations Move emulation limitations in C++03 compilers]

[*Boost.Container] uses [*Boost.Move] to implement move semantics both in C++03 and C++11 compilers.
However, as explained in
[@http://www.boost.org/doc/libs/release/doc/html/move/emulation_limitations.html Emulation limitations],
there are some limitations in C++03 compilers that might surprise [*Boost.Container] users.

The most noticeable problem is when [*Boost.Container] containers are placed in a struct with a
compiler-generated assignment operator:

[c++]

   class holder
   {
      boost::container::vector<MyType> vect;
   };

   void func(const holder& h)
   {
      holder copy_h(h); //<--- ERROR: can't convert 'const holder&' to 'holder&'
      //Compiler-generated copy constructor is non-const:
      // holder& operator(holder &)
      //!!!
   }

This limitation forces the user to define a const version of the copy assignment, in all classes
holding containers, which might be annoying in some cases.

[endsect]

[endsect]

[section:history_and_reasons History and reasons to use Boost.Container]

[section:boost_container_history Boost.Container history]

[*Boost.Container] is a product of a long development effort that started
[@http://lists.boost.org/Archives/boost/2004/11/76263.php in 2004 with the experimental Shmem library],
which pioneered the use of standard containers in shared memory. Shmem included modified SGI STL container
code tweaked to support non-raw `allocator::pointer` types and stateful allocators. Once reviewed,
Shmem was accepted as [@http://www.boost.org/libs/interprocess/ Boost.Interprocess] and this library
continued to refine and improve those containers.

In 2007, container code from node containers (`map`, `list`, `slist`) was rewritten, refactored
and expanded to build the intrusive container library [@http://www.boost.org/libs/intrusive/ Boost.Intrusive].
[*Boost.Interprocess] containers were refactored to take advantage of [*Boost.Intrusive] containers and
code duplication was minimized. Both libraries continued to gain support and bug fixes for years.
They introduced move semantics, emplacement insertion and more features of then unreleased C++0x
standard.

[*Boost.Interprocess] containers were always standard compliant, and those containers and new
containers like `stable_vector` and `flat_[multi]set/map` were used outside [*Boost.Interprocess]
with success. As containers were mature enough to get their own library, it was a natural step to
collect them containers and build [*Boost.Container], a library targeted to a wider audience.

[endsect]


[section:Why_boost_container Why Boost.Container?]

With so many high quality standard library implementations out there, why would you want to
use [*Boost.Container]? There are several reasons for that:

* If you have a C++03 compiler, you can have access to C++11 features and have an easy
  code migration when you change your compiler.
* It's compatible with [*Boost.Interprocess] shared memory allocators.
* You have extremely useful new containers like `stable_vector` and `flat_[multi]set/map`.
* If you work on multiple platforms, you'll have a portable behaviour without depending
  on the std-lib implementation conformance of each platform. Some examples:
   * Default constructors don't allocate memory at all, which improves performance and
   usually implies a no-throw guarantee (if predicate's or allocator's default constructor doesn't throw).
   * Small string optimization for [classref boost::container::basic_string basic_string].
* [link container.extended_functionality Extended functionality] beyond the standard based
   on user feedback to improve code performance.
* You need a portable implementation that works when compiling without exceptions support or
  you need to customize the error handling when a container needs to signal an exceptional error.

[endsect]

[endsect]

[include auto_index_helpers.qbk]

[section:index Indexes]

[named_index class_name Class Index]
[named_index typedef_name Typedef Index]
[named_index function_name Function Index]
[/named_index macro_name Macro Index]
[/index]

[endsect]

[xinclude autodoc.xml]

[section:acknowledgements_notes Acknowledgements, notes and links]

*  Original standard container code comes from [@http://www.sgi.com/tech/stl/ SGI STL library],
   which enhanced the original HP STL code. Code was rewritten for
   [*Boost.Interprocess] and moved to [*Boost.Intrusive]. Many thanks to Alexander Stepanov, Meng Lee, David Musser,
   Matt Austern... and all HP and SGI STL developers.

*  `flat_[multi]_map/set` containers were originally based on [@http://en.wikipedia.org/wiki/Loki_%28C%2B%2B%29 Loki's]
   AssocVector class. Code was rewritten and expanded for [*Boost.Interprocess], so thanks to Andrei Alexandrescu.

*  `stable_vector` was invented and coded by
   [@http://bannalia.blogspot.com/2008/09/introducing-stablevector.html Joaqu\u00EDn M. L\u00F3pez Mu\u00F1oz],
   then adapted for [*Boost.Interprocess]. Thanks for such a great container.

*  `static_vector` was based on Andrew Hundt's and Adam Wulkiewicz's high-performance `varray` class.
   Many performance improvements of `vector` were also inspired by their implementation. Thanks!

*  Howard Hinnant's help and advices were essential when implementing move semantics,
   improving allocator support or implementing small string optimization. Thanks Howard
   for your wonderful standard library implementations.

*  And finally thanks to all Boosters who helped all these years, improving, fixing and
   reviewing all my libraries.

[endsect]

[section:release_notes Release Notes]

[section:release_notes_boost_1_62_00 Boost 1.62 Release]

* Fixed bugs:
   * [@https://svn.boost.org/trac/boost/ticket/9481  Trac #9481:  ['"Minor comment typo in Boost.Container"]].
   * [@https://svn.boost.org/trac/boost/ticket/9689  Trac #9689:  ['"Add piecewise_construct to boost::container"]].
   * [@https://svn.boost.org/trac/boost/ticket/11170 Trac #11170: ['"Doc slip for index_of"]].
   * [@https://svn.boost.org/trac/boost/ticket/11802 Trac #11802: ['"Incorrect ordering after using insert() with ordered_range_t on a flat_multiset with a non-default sort order"]].
   * [@https://svn.boost.org/trac/boost/ticket/12117 Trac #12117: ['"flat_set constructor with ordered_unique_range"]].
   * [@https://svn.boost.org/trac/boost/ticket/12177 Trac #12177: ['"vector::priv_merge uses unqualified uintptr_t"]].
   * [@https://svn.boost.org/trac/boost/ticket/12183 Trac #12183: ['"GCC 6.1 thinks boost::container::string violates strict aliasing"]].
   * [@https://svn.boost.org/trac/boost/ticket/12256 Trac #12256: ['"set<std::pair<int,int>>::insert cause compilation error in debug configuration in Visual Studio 2012"]].
   * [@https://svn.boost.org/trac/boost/ticket/12273 Trac #12273: ['"static_vector max_size() and capacity() should be constant expressions"]].
     Added constant `static_vector<>::static_capacity` to use the configured capacity in constant expressions.
   * [@https://svn.boost.org/trac/boost/ticket/12286 Trac #12286: ['"PMR flat_map from Boost Container does not compile"]].
   * [@https://svn.boost.org/trac/boost/ticket/12296 Trac #12296: ['"{deque,string} combine for a memory leak"]].
   * [@https://svn.boost.org/trac/boost/ticket/12319 Trac #12319: ['"flat_set` should be nothrow move constructible"]].

* Revised noexcept expressions of default and move constructors in all containers.
* Implemented C++17's `insert_or_assign`/`try_emplace` for [classref boost::container::map map] and [classref boost::container::flat_map flat_map].
* Implemented C++17's [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0083r3.pdf ['Splicing Maps and Sets (Revision 5)]]
   for [classref boost::container::map map], [classref boost::container::multimap multimap],
   [classref boost::container::set set], [classref boost::container::multiset multiset].
* Implemented C++17's [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0084r2.pdf ['P0084R2 Emplace Return Type]]
  in `deque`, `vector`, `stable_vector`, `small_vector`, `static_vector`, `list` and `slist`.

[endsect]

[section:release_notes_boost_1_61_00 Boost 1.61 Release]

* [classref boost::container::small_vector] supports more constructors and assignments.
* Fixed bugs:
   * [@https://svn.boost.org/trac/boost/ticket/11820 Trac #11820: ['"compiler error when using operator[] of map"]].
   * [@https://svn.boost.org/trac/boost/ticket/11856 Trac #11856: ['"pool_resource.cpp error: declaration changes meaning"]].
   * [@https://svn.boost.org/trac/boost/ticket/11866 Trac #11866: ['"small_vector does not have range constructor"]].
   * [@https://svn.boost.org/trac/boost/ticket/11867 Trac #11867: ['"small_vector should have constructor and assignment operator taking other small_vector"]].
   * [@https://svn.boost.org/trac/boost/ticket/11912 Trac #11912: ['"flat_map use of vector::priv_forward_range_insert_expand_backwards may cause move with same source"]].
   * [@https://svn.boost.org/trac/boost/ticket/11957 Trac #11957: ['"static_vector::max_size() is higher than the capacity"]].
   * [@https://svn.boost.org/trac/boost/ticket/12014 Trac #12014: ['"boost::container::set can not insert const (ref) range"]].
   * [@https://github.com/boostorg/container/pull/33 GitHub #33: ['Make sure std::string constructor is available]].

[endsect]

[section:release_notes_boost_1_60_00 Boost 1.60 Release]

* Implemented [link container.extended_functionality.polymorphic_memory_resources Polymorphic Memory Resources].
* Add more BOOST_ASSERT checks to test preconditions in some operations (like `pop_back`, `pop_front`, `back`, `front`, etc.)
* Added C++11 `back`/`front` operations to [classref boost::container::basic_string basic_string].
* Fixed bugs:
   * [@https://svn.boost.org/trac/boost/ticket/11627 Trac #11627: ['"small_vector<T,n>::swap() appears to be broken"]].
   * [@https://svn.boost.org/trac/boost/ticket/11628 Trac #11628: ['"small_vector<int,n> iterates over elements in destructor"]].
   * [@https://svn.boost.org/trac/boost/ticket/11697 Trac #11697: ['"Wrong initialization order in tuple copy-constructor"]].
   * [@https://svn.boost.org/trac/boost/ticket/11698 Trac #11698: ['"Missing return statement in static_storage_allocator"]].
   * [@https://github.com/boostorg/container/pull/29 GitHub #29: ['Doc fixes for flap_map complexity requirements]].
   * [@https://github.com/boostorg/container/pull/31 GitHub #31: ['DL_SIZE_IMPL also dereference addr]].

[endsect]

[section:release_notes_boost_1_59_00 Boost 1.59 Release]

* [@https://github.com/boostorg/container/pull/26 GitHub #26: ['Fix bug in stable_vector::capacity()]]. Thanks to timsong-cpp/Arindam Mukerjee.
* [@https://github.com/boostorg/container/pull/27 GitHub #27: ['fix stable_vector's index_of's doxygen comment]]. Thanks to kariya-mitsuru.
* [@https://svn.boost.org/trac/boost/ticket/11380 Trac #11380: ['"Container library std forward declarations incorrect in std_fwd.hpp on libc++ with gcc"]].
* [@https://svn.boost.org/trac/boost/ticket/11388 Trac #11388: ['"boost::container::list::emplace_back broken on Visual Studio 2010"]].
* [@https://svn.boost.org/trac/boost/ticket/11339 Trac #11339: ['"VC12 LNK2005 error with boost::container::adaptive_pool"]].

[endsect]

[section:release_notes_boost_1_58_00 Boost 1.58 Release]
*  Experimental [classref boost::container::small_vector small_vector] container.
*  Massive dependency reorganization. Now [*Boost.Container] depends on very basic utilities like Boost.Core
   and [*Boost.Intrusive]. Preprocessed code size have decreased considerably and compilation times have improved.
*  Added `nth` and `index_of` functions to containers with random-access iterators (except `basic_string`).
*  Added C++17's `allocator_traits<Allocator>::is_always_equal`.
*  Updated containers to implement new constructors as specified in
   [@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2210 2210. Missing allocator-extended constructor for allocator-aware containers].
*  Fixed bugs:
   * [@https://svn.boost.org/trac/boost/ticket/9931  Trac #9931: ['"flat_map::insert(ordered_unique_range_t...) fails with move_iterators"]] (reopened).
   * [@https://svn.boost.org/trac/boost/ticket/11076 Trac #11076: ['"Unqualified calls to memmove/memcpy in container/detail/copy_move_algo.hpp"]].
   * [@https://svn.boost.org/trac/boost/ticket/10790 Trac #10790 (['"long long errors from container"])].
   * [@https://svn.boost.org/trac/boost/ticket/10808 Trac #10808 (['"compare equal operator of vector is broken"])].
   * [@https://svn.boost.org/trac/boost/ticket/10930 Trac #10930 (['"container std_fwd.hpp neglects custom std namespaces"])].
   * [@https://svn.boost.org/trac/boost/ticket/11139 Trac #11139 (['"boost::container::vector<std::shared_ptr<const T>...>::const_iterator allows changing dereferenced elements"])].
* [*Source Breaking]: [classref boost::container::scoped_allocator_adaptor scoped_allocator_adaptor]'s
   `propagate_on_container_copy_assignment`, `propagate_on_container_move_assignment` and `propagate_on_container_swap`
   are no longer `::boost::integral_constant<bool, true/false>` types. The dependency reorganization needed to break
   with those classes to avoid MPL dependencies, and interoperability with `std::integral_constant` was not guaranteed.
   Code assumming `boost::true_type/boost::false_type` on this will not compile. As a workaround, use the guaranteed internal
   `::value` constant: `::boost::integral_constant<bool, scoped_allocator_adaptor<Allocator>::propagate_on_container_move_assignment::value>`.

[endsect]

[section:release_notes_boost_1_57_00 Boost 1.57 Release]
*  Added support for `initializer_list`. Contributed by Robert Matusewicz.
*  Fixed double destruction bugs in vector and backward expansion capable allocators.
*  Fixed bugs:
   * [@https://svn.boost.org/trac/boost/ticket/10263 Trac #10263 (['"AIX 6.1 bug with sched_yield() function out of scope"])].
   * [@https://github.com/boostorg/container/pull/16 GitHub #16: ['Fix iterators of incomplete type containers]]. Thanks to Mikael Persson.

[endsect]

[section:release_notes_boost_1_56_00 Boost 1.56 Release]

* Added DlMalloc-based [link container.extended_functionality.extended_allocators Extended Allocators].

* [link container.extended_functionality.configurable_tree_based_associative_containers Improved configurability]
   of tree-based ordered associative containers. AVL, Scapegoat and Splay trees are now available
   to implement [classref boost::container::set set], [classref boost::container::multiset multiset],
   [classref boost::container::map map] and [classref boost::container::multimap multimap].

* Fixed bugs:
   *  [@https://svn.boost.org/trac/boost/ticket/9338 #9338: ['"VS2005 compiler errors in swap() definition after including container/memory_util.hpp"]].
   *  [@https://svn.boost.org/trac/boost/ticket/9637 #9637: ['"Boost.Container vector::resize() performance issue"]].
   *  [@https://svn.boost.org/trac/boost/ticket/9648 #9648: ['"string construction optimization - char_traits::copy could be used ..."]].
   *  [@https://svn.boost.org/trac/boost/ticket/9801 #9801: ['"I can no longer create and iterator_range from a stable_vector"]].
   *  [@https://svn.boost.org/trac/boost/ticket/9915 #9915: ['"Documentation issues regarding vector constructors and resize methods - value/default initialization"]].
   *  [@https://svn.boost.org/trac/boost/ticket/9916 #9916: ['"Allocator propagation incorrect in the assignment operator of most"]].
   *  [@https://svn.boost.org/trac/boost/ticket/9931 #9931: ['"flat_map::insert(ordered_unique_range_t...) fails with move_iterators"]].
   *  [@https://svn.boost.org/trac/boost/ticket/9955 #9955: ['"Using memcpy with overlapped buffers in vector"]].

[endsect]

[section:release_notes_boost_1_55_00 Boost 1.55 Release]

*  Implemented [link container.main_features.scary_iterators SCARY iterators].

*  Fixed bugs [@https://svn.boost.org/trac/boost/ticket/8269 #8269],
              [@https://svn.boost.org/trac/boost/ticket/8473 #8473],
              [@https://svn.boost.org/trac/boost/ticket/8892 #8892],
              [@https://svn.boost.org/trac/boost/ticket/9009 #9009],
              [@https://svn.boost.org/trac/boost/ticket/9064 #9064],
              [@https://svn.boost.org/trac/boost/ticket/9092 #9092],
              [@https://svn.boost.org/trac/boost/ticket/9108 #9108],
              [@https://svn.boost.org/trac/boost/ticket/9166 #9166].

* Added `default initialization` insertion functions to vector-like containers
   with new overloads taking `default_init_t` as an argument instead of `const value_type &`.

[endsect]

[section:release_notes_boost_1_54_00 Boost 1.54 Release]

*  Added experimental `static_vector` class, based on Andrew Hundt's and Adam Wulkiewicz's
   high performance `varray` class.
*  Speed improvements in `vector` constructors/copy/move/swap, dispatching to memcpy when possible.
*  Support for `BOOST_NO_EXCEPTIONS` [@https://svn.boost.org/trac/boost/ticket/7227 #7227].
*  Fixed bugs [@https://svn.boost.org/trac/boost/ticket/7921 #7921],
              [@https://svn.boost.org/trac/boost/ticket/7969 #7969],
              [@https://svn.boost.org/trac/boost/ticket/8118 #8118],
              [@https://svn.boost.org/trac/boost/ticket/8294 #8294],
              [@https://svn.boost.org/trac/boost/ticket/8553 #8553],
              [@https://svn.boost.org/trac/boost/ticket/8724 #8724].

[endsect]

[section:release_notes_boost_1_53_00 Boost 1.53 Release]

*  Fixed bug [@https://svn.boost.org/trac/boost/ticket/7650 #7650].
*  Improved `vector`'s insertion performance.
*  Changed again experimental multiallocation interface for better performance (still experimental).
*  Added no exception support for those willing to disable exceptions in their compilers.
*  Fixed GCC -Wshadow warnings.
*  Replaced deprecated BOOST_NO_XXXX with newer BOOST_NO_CXX11_XXX macros.

[endsect]

[section:release_notes_boost_1_52_00 Boost 1.52 Release]

*  Improved `stable_vector`'s template code bloat and type safety.
*  Changed typedefs and reordered functions of sequence containers to improve doxygen documentation.
*  Fixed bugs
  [@https://svn.boost.org/trac/boost/ticket/6615 #6615],
  [@https://svn.boost.org/trac/boost/ticket/7139 #7139],
  [@https://svn.boost.org/trac/boost/ticket/7215 #7215],
  [@https://svn.boost.org/trac/boost/ticket/7232 #7232],
  [@https://svn.boost.org/trac/boost/ticket/7269 #7269],
  [@https://svn.boost.org/trac/boost/ticket/7439 #7439].
*  Implemented LWG Issue #149 (range insertion now returns an iterator) & cleaned up insertion code in most containers
*  Corrected aliasing errors.

[endsect]

[section:release_notes_boost_1_51_00 Boost 1.51 Release]

*  Fixed bugs
  [@https://svn.boost.org/trac/boost/ticket/6763 #6763],
  [@https://svn.boost.org/trac/boost/ticket/6803 #6803],
  [@https://svn.boost.org/trac/boost/ticket/7114 #7114],
  [@https://svn.boost.org/trac/boost/ticket/7103 #7103].
  [@https://svn.boost.org/trac/boost/ticket/7123 #7123],

[endsect]

[section:release_notes_boost_1_50_00 Boost 1.50 Release]

*  Added Scoped Allocator Model support.

*  Fixed bugs
  [@https://svn.boost.org/trac/boost/ticket/6606 #6606],
  [@https://svn.boost.org/trac/boost/ticket/6533 #6533],
  [@https://svn.boost.org/trac/boost/ticket/6536 #6536],
  [@https://svn.boost.org/trac/boost/ticket/6566 #6566],
  [@https://svn.boost.org/trac/boost/ticket/6575 #6575],

[endsect]


[section:release_notes_boost_1_49_00 Boost 1.49 Release]

*  Fixed bugs
  [@https://svn.boost.org/trac/boost/ticket/6540 #6540],
  [@https://svn.boost.org/trac/boost/ticket/6499 #6499],
  [@https://svn.boost.org/trac/boost/ticket/6336 #6336],
  [@https://svn.boost.org/trac/boost/ticket/6335 #6335],
  [@https://svn.boost.org/trac/boost/ticket/6287 #6287],
  [@https://svn.boost.org/trac/boost/ticket/6205 #6205],
  [@https://svn.boost.org/trac/boost/ticket/4383 #4383].

*  Added `allocator_traits` support for both C++11 and C++03
   compilers through an internal `allocator_traits` clone.

[endsect]

[section:release_notes_boost_1_48_00 Boost 1.48 Release]

*  First release. Container code from [*Boost.Interprocess] was deleted
   and redirected to [*Boost.Container ] via using directives.

[endsect]

[endsect]