1716 lines
100 KiB
Plaintext
1716 lines
100 KiB
Plaintext
[/
|
|
/ Copyright (c) 2009-2018 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-2018 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 offer 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?
|
|
|
|
* Emplacement and move semantics are implemented, including emulation for pre-C++11 compilers.
|
|
* Polymorphic allocators and memory resources, including implementation and emulation for pre-C++17 compilers
|
|
* New advanced features (e.g. recursive containers) and configurability options [link container.configurable_containers] for containers.
|
|
* Containers support stateful allocators and are compatible with [*Boost.Interprocess]
|
|
(they can be safely placed in shared memory).
|
|
* Users obtain a more uniform performance across all plataforms,
|
|
including [link container.main_features.scary_iterators SCARY iterators].
|
|
* 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::static_vector static_vector ]: a vector-like container that internally embeds
|
|
(statically allocates) all needed memory up to the maximum capacity. Maximum capacity can't be increased and
|
|
it's specified at compile time.
|
|
* [classref boost::container::small_vector small_vector ]: a vector-like container that internally embeds
|
|
(statically allocates) a minimum amount of memory, but dynamically allocates elements when capacity
|
|
has to be increased. This minimum capacity is specified at compile time.
|
|
* [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_allocators Extended Allocators]
|
|
* Some [link container.cpp_conformance.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.
|
|
|
|
[warning GCC < 4.3 and MSVC < 9.0 are deprecated and will be removed in the next version.]
|
|
|
|
[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]].
|
|
|
|
Finally C++17 added support for incomplete types in `std::vector`, `std::list` and `std::forward_list`
|
|
(see [@https://wg21.link/n4569 ['N4569: Minimal incomplete type support for standard containers, revision 4]]
|
|
for details), but no other containers like `std::set/map/unordered_set/unordered_map`,
|
|
|
|
Fortunately all [*Boost.Container] containers except
|
|
[classref boost::container::static_vector static_vector] and
|
|
[classref boost::container::small_vector small_vector] and
|
|
[classref boost::container::basic_string basic_string] are designed to support incomplete types.
|
|
[classref boost::container::static_vector static_vector] and
|
|
[classref boost::container::small_vector small_vector] are special because
|
|
they statically allocates memory for `value_type` and this requires complete types.
|
|
[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/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 specify requirements on memory consumption, but virtually any implementation
|
|
of `vector` has the same behavior with 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-like container based, associative
|
|
containers following Austern's and Alexandrescu's guidelines. These ordered vector containers have also
|
|
benefited with the addition of `move semantics` to C++11, 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: Basic extensions]
|
|
|
|
[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
|
|
`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: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]
|
|
|
|
[endsect]
|
|
|
|
[section:configurable_containers Extended functionality: Configurable containers]
|
|
|
|
[*Boost.Container] offers the possibility to configure at compile time some parameters of
|
|
several containers, apart from the stored type and the allocator. This configuration is passed as
|
|
the last template parameter and defined using the utility classes. The following containers can receive
|
|
useful configuration options:
|
|
|
|
[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:configurable_vectors Configurable vectors]
|
|
|
|
The configuration for [classref boost::container::vector vector] is passed as
|
|
the last template parameter and defined using the utility class
|
|
[classref boost::container::vector_options vector_options]. The following parameters can be configured:
|
|
|
|
* [classref boost::container::growth_factor growth_factor]: the growth policy of the vector.
|
|
The rate at which the capacity of a vector grows is implementation dependent and
|
|
implementations choose exponential growth in order to meet the amortized constant time requirement for push_back.
|
|
A higher growth factor will make it faster as it will require less data movement, but it will have a greater memory
|
|
impact (on average, more memory will be unused). A user can provide a custom implementation of the growth factor and some
|
|
predefined policies are available: [classref boost::container::growth_factor_50 growth_factor_50],
|
|
[classref boost::container::growth_factor_60 growth_factor_60] and
|
|
[classref boost::container::growth_factor_50 growth_factor_100].
|
|
|
|
* [classref boost::container::stored_size stored_size]: the type that will be used to store size-related
|
|
parameters inside of the vector. Sometimes, when the maximum capacity to be used is much less than the
|
|
theoretical maximum that a vector can hold, it's interesting to use smaller unsigned integer types to represent
|
|
`size()` and `capacity()` inside vector, so that the size of an empty vector is minimized and cache
|
|
performance might be improved. See [classref boost::container::stored_size stored_size] for more details.
|
|
|
|
See the following example to see how [classref boost::container::vector_options vector_options] can be
|
|
used to customize `vector` container:
|
|
|
|
[import ../example/doc_custom_vector.cpp]
|
|
[doc_custom_vector]
|
|
|
|
[endsect]
|
|
|
|
[section:configurable_deques Configurable deques]
|
|
|
|
The configuration for [classref boost::container::deque deque] is passed as
|
|
the last template parameter and defined using the utility class
|
|
[classref boost::container::deque_options deque_options]. The following parameters can be configured:
|
|
|
|
Parameters that control the size of deque's 'block' (deque allocates contiguous chunks of elements, called 'blocks').
|
|
Only one of these paratemers can be specified:
|
|
|
|
* [classref boost::container::block_bytes block_bytes]: the number of bytes deque will allocate for store
|
|
elements contiguously: `deque::get_block_size()` will return aproximately `block_bytes/sizeof(value_type)`.
|
|
A value of zero means the default value.
|
|
|
|
* [classref boost::container::block_size block_size]: the number of elements deque will allocate contiguously.
|
|
If this option is specified, `deque::get_block_size()` will return the specified `block_size`.
|
|
A value of zero means the default value.
|
|
|
|
See the following example to see how [classref boost::container::deque_options deque_options] can be
|
|
used to customize `deque` container:
|
|
|
|
[import ../example/doc_custom_deque.cpp]
|
|
[doc_custom_deque]
|
|
|
|
[endsect]
|
|
|
|
[section:configurable_static_vectors Configurable static vector]
|
|
|
|
The configuration for [classref boost::container::static_vector static_vector] is passed as
|
|
the last template parameter and defined using the utility class
|
|
[classref boost::container::static_vector_options static_vector_options]. The following parameters can be configured:
|
|
|
|
* [classref boost::container::inplace_alignment inplace_alignment]: the minimum alignment (in bytes) that the stored value type
|
|
needs. This option allows static vectors that need non-default alignments, e.g., to be used in SIMD operations.
|
|
|
|
* [classref boost::container::throw_on_overflow throw_on_overflow]: A boolean that specifies if the
|
|
container should throw an exception when the compile-time capacity is not enough to hold the requesteed number
|
|
of objects. When "false", if the capacit is overflowd, the implementation calls to BOOST_ASSERT and if that assertion
|
|
does not throw or abort, undefined behavior is triggered.
|
|
|
|
See the following example to see how [classref boost::container::static_vector_options static_vector_options] can be
|
|
used to customize `static_vector` container:
|
|
|
|
[import ../example/doc_custom_static_vector.cpp]
|
|
[doc_custom_static_vector]
|
|
|
|
[endsect]
|
|
|
|
[section:configurable_small_vectors Configurable small vector]
|
|
|
|
The configuration for [classref boost::container::small_vector small_vector] is passed as
|
|
the last template parameter and defined using the utility class
|
|
[classref boost::container::small_vector_options small_vector_options]. The following parameters can be configured:
|
|
|
|
* [classref boost::container::inplace_alignment inplace_alignment]: the minimum alignment (in bytes) for the in-place storage
|
|
used to build the "small" number of elements. [*The alignment of the dynamic memory must be provided by the allocator
|
|
and it is not affected by this option].
|
|
|
|
* [classref boost::container::growth_factor growth_factor]: the growth policy of the vector.
|
|
The rate at which the capacity of a vector grows is implementation dependent and
|
|
implementations choose exponential growth in order to meet the amortized constant time requirement for push_back.
|
|
A higher growth factor will make it faster as it will require less data movement, but it will have a greater memory
|
|
impact (on average, more memory will be unused). A user can provide a custom implementation of the growth factor and some
|
|
predefined policies are available: [classref boost::container::growth_factor_50 growth_factor_50],
|
|
[classref boost::container::growth_factor_60 growth_factor_60] and
|
|
[classref boost::container::growth_factor_50 growth_factor_100].
|
|
|
|
See the following example to see how [classref boost::container::small_vector_options small_vector_options] can be
|
|
used to customize `small_vector` container:
|
|
|
|
[import ../example/doc_custom_small_vector.cpp]
|
|
[doc_custom_small_vector]
|
|
|
|
[endsect]
|
|
|
|
[endsect]
|
|
|
|
[section:extended_allocators Extended functionality: 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:cpp_conformance C++11/C++14/C++17 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/C++14/C++17 features are implemented and which
|
|
of them have been backported to earlier standard conformig 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: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)]
|
|
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.]]
|
|
|
|
Most utilities from the Fundamentals TS were merged into C++17, but
|
|
[*Boost.Container] offers them for C++03, C++11 and C++14 compilers.
|
|
|
|
[*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]
|
|
|
|
|
|
[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_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:
|
|
|
|
* Even if you have a earlier standard conforming compiler, you still can have access to many
|
|
of the latest C++ standard 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/static/small]_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_72_00 Boost 1.72 Release]
|
|
|
|
* Fixed bugs:
|
|
* [@https://github.com/boostorg/container/issues/127 GitHub #127: ['"Fix docs for static_vector::max_size() and capacity()"]].
|
|
* [@https://github.com/boostorg/container/issues/132 GitHub #132: ['"flat_map::lower_bound and upper_bound have wrong/misleading docs"]].
|
|
* [@https://github.com/boostorg/container/issues/133 GitHub #133: ['"basic_string move constructor with allocator argument has incorrect allocator check"]].
|
|
|
|
[endsect]
|
|
|
|
[section:release_notes_boost_1_71_00 Boost 1.71 Release]
|
|
|
|
* Fixed bugs:
|
|
* [@https://github.com/boostorg/container/pull/47 GitHub #47: ['"added alignment specification for small_vector"]].
|
|
* [@https://github.com/boostorg/container/issues/88 GitHub #88: ['"Implement C++17 MoveAssignable requirements for self-move assignments"]].
|
|
* [@https://github.com/boostorg/container/issues/107 GitHub #107: ['"Alignment ignored in resource_adaptor"]].
|
|
* [@https://github.com/boostorg/container/pull/109 GitHub #109: ['"Get rid of integer overflow in copy_move_algo.hpp (-fsanitize=integer)"]].
|
|
* [@https://github.com/boostorg/container/pull/110 GitHub #110: ['"Avoid gcc 9 deprecated copy warnings in new_allocator.hpp"]].
|
|
* [@https://github.com/boostorg/container/issues/112 GitHub #112: ['"vector::resize() compilation error with msvc-10..12: data is not a member of boost::detail::aligned_storage"]].
|
|
* [@https://github.com/boostorg/container/issues/114 GitHub #114: ['"Fix small_vector noexcept specification"]].
|
|
* [@https://github.com/boostorg/container/issues/116 GitHub #116: ['"MSVC + boost 1.70 compilation error when windows.h is already included (detail/thread_mutex.hpp)"]].
|
|
* [@https://github.com/boostorg/container/issues/117 GitHub #117: ['"flat_map/map::insert_or_assign with hint has wrong return types"]].
|
|
* [@https://github.com/boostorg/container/issues/118 GitHub #118: ['"Non-unique inplace_set_difference used in in flat_tree_merge_unique and iterator invalidation in insert_unique"]].
|
|
* [@https://github.com/boostorg/container/issues/122 GitHub #122: ['"Fix has_trivial_destructor_after_move"]].
|
|
* [@https://github.com/boostorg/container/issues/123 GitHub #123: ['"With heterogeneous lookup, `equal_range` can result in a range with length greater than 1"]].
|
|
|
|
* [classref boost::container::deque deque] can now have options, using [classref boost::container::deque_options deque_options].
|
|
The block size/bytes can be be specified.
|
|
|
|
* [classref boost::container::static_vector static_vector] can now have options, using [classref boost::container::static_vector_options static_vector_options].
|
|
Alignment and throwing behaviour can be be specified.
|
|
|
|
* [classref boost::container::small_vector small_vector] can now have options, using [classref boost::container::small_vector_options small_vector_options].
|
|
Alignment and growth factor can be be specified.
|
|
|
|
[endsect]
|
|
|
|
[section:release_notes_boost_1_70_00 Boost 1.70 Release]
|
|
|
|
* Removed support for already deprecated GCC < 4.3 and MSVC < 9.0 (Visual 2008) compilers.
|
|
* Default allocator parameter changed form `new_allocator<T>` to `void` to reduce symbol lenghts.
|
|
* Fixed bugs:
|
|
* [@https://github.com/boostorg/container/pull/96 GitHub #96: ['"Workaround: Intel compilers do not offer CTAD yet"]].
|
|
* [@https://github.com/boostorg/container/issues/97 GitHub #97: ['"buffer overflow in boost::container::flat_map on FreeBSD"]].
|
|
* [@https://github.com/boostorg/container/issues/98 GitHub #98: ['"flat_map: insert_or_assign does not work with hint"]].
|
|
* [@https://github.com/boostorg/container/issues/100 GitHub #100: ['"Compile error on Green Hills: container_detail::flat_tree has no member insert"]].
|
|
* [@https://github.com/boostorg/container/pull/103 GitHub #103: ['"Fix deallocating never-allocated storage in vector.merge()"]].
|
|
* [@https://github.com/boostorg/container/pull/104 GitHub #104: ['"Fix -Wmissing-noreturn clang warnings"]].
|
|
* [@https://github.com/boostorg/container/pull/105 GitHub #105: ['"Fix gcc -Wdeprecated-copy"]].
|
|
* [@https://github.com/boostorg/container/issues/111 GitHub #111: ['"container::vector of interprocess::offset_ptrs to variants holding incomplete type"]].
|
|
|
|
[endsect]
|
|
|
|
[section:release_notes_boost_1_69_00 Boost 1.69 Release]
|
|
|
|
* Deprecated GCC < 4.3 and MSVC < 9.0 (Visual 2008) compilers.
|
|
|
|
* Implemented C++20 `contains()` for associative containers as specified in
|
|
[@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0458r2.html
|
|
P0458R2: Checking for Existence of an Element in Associative Containers].
|
|
|
|
* Fixed serious bug in heterogeneous lookup functions (is_transparent was broken).
|
|
|
|
* Fixed bugs:
|
|
* [@https://github.com/boostorg/container/issues/77 GitHub #77: ['"warning: 'sbrk' is deprecated"]].
|
|
* [@https://github.com/boostorg/container/issues/79 GitHub #79: ['"Mark small_vector move operations noexcept"]].
|
|
* [@https://github.com/boostorg/container/issues/80 GitHub #80: ['"flat_map deduction guides are ambiguous"]].
|
|
* [@https://github.com/boostorg/container/issues/81 GitHub #81: ['"Vector with custom allocator does not support value types with operator&"]].
|
|
* [@https://github.com/boostorg/container/issues/82 GitHub #82: ['"Function definition in header file"]].
|
|
* [@https://github.com/boostorg/container/issues/83 GitHub #83: ['"Iterator zero incrementing leads to assert on empty vector"]].
|
|
* [@https://github.com/boostorg/container/pull/84 GitHub #84: ['"Allow vector to be assigned to itself"]].
|
|
* [@https://github.com/boostorg/container/pull/85 GitHub #85: ['"container: misc-typos"]].
|
|
* [@https://github.com/boostorg/container/pull/86 GitHub #86: ['"Add missing warning re-enabling include"]].
|
|
* [@https://github.com/boostorg/container/issues/89 GitHub #89: ['"UBSAN failures detected in preflight CI PR"]].
|
|
* [@https://github.com/boostorg/container/issues/90 GitHub #90: ['"Build fails on clang-5 with libstdc++7-dev (C++17 issue)"]].
|
|
* [@https://github.com/boostorg/container/issues/93 GitHub #93: ['"vector::erase memory leak"]].
|
|
|
|
[endsect]
|
|
|
|
[section:release_notes_boost_1_68_00 Boost 1.68 Release]
|
|
|
|
* Improved correctness of [classref boost::container::adaptive_pool adaptive_pool] and many parameters are now compile-time
|
|
constants instead of runtime constants.
|
|
|
|
* Implemented C++14's heterogeneous lookup functions for `[multi]map/[multi]set/flat_[multi]map/flat_[multi]set`.
|
|
|
|
* Added [@https://github.com/boostorg/container/pull/71 GitHub #71: ['"Constructor Template Auto Deduction guides "]].
|
|
|
|
* Fixed bugs:
|
|
* [@https://svn.boost.org/trac/boost/ticket/13533 Trac #13533: ['"Boost vector resize causes assert(false)"]].
|
|
* [@https://github.com/boostorg/container/issues/73 GitHub #73: ['"triviality of pair"]].
|
|
* [@https://github.com/boostorg/container/issues/74 GitHub #74: ['"vector assignment not using memcpy"]].
|
|
* [@https://github.com/boostorg/container/issues/75 GitHub #75: ['"flat_set: Heap overflow"]].
|
|
* [@https://github.com/boostorg/container/issues/76 GitHub #76: ['"flat_set: undefined behaviour on empty range"]].
|
|
* Fixed race condition bug in [classref boost::container::pmr::unsynchronized_pool_resource unsynchronized_pool_resource]
|
|
found by Arthur O'Dowyer in his blog post
|
|
[@https://quuxplusone.github.io/blog/2018/06/05/libcpp-memory-resource/ <memory_resource> for libc++]
|
|
|
|
* Implemented proposed resolution for
|
|
[@https://cplusplus.github.io/LWG/issue3120 ['"LWG 3120 Unclear behavior of monotonic_buffer_resource::release()"]].
|
|
After `release()` the original buffer is recovered for the next allocation.
|
|
|
|
[endsect]
|
|
|
|
[section:release_notes_boost_1_67_00 Boost 1.67 Release]
|
|
|
|
* ['vector] can now have options, using [classref boost::container::vector_options vector_options].
|
|
The growth factor and the stored size type can be specified.
|
|
|
|
* Improved range insertion in ['flat_[multi]map/set] containers overall complexity is reduced to O(NlogN).
|
|
|
|
* Fixed bugs:
|
|
* [@https://github.com/boostorg/container/pull/61 GitHub #61: ['"Compile problems on Android ndk r16 beta 1"]].
|
|
* [@https://github.com/boostorg/container/pull/64 GitHub #64: ['"Fix splice for slist"]].
|
|
* [@https://github.com/boostorg/container/issues/58 GitHub #65: ['"`pmr::monotonic_buffer_resource::allocate()` can return a pointer to freed memory after `release()` is called"]].
|
|
* [@https://svn.boost.org/trac/boost/ticket/13500 Trac #13500: ['"Memory leak when using erase on string vectors"]].
|
|
|
|
[endsect]
|
|
|
|
[section:release_notes_boost_1_66_00 Boost 1.66 Release]
|
|
|
|
* ['flat_[multi]map/set] can now work as container adaptors, as proposed in [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0429r1.pdf P0429R1].
|
|
The allocator argument is checked for ['size()] and ['empty()] members. If so, the argument is interpreted as the required underlying container.
|
|
This means that ['static_vector], ['stable_vector] and ['small_vector] can be used now with flat associative containers.
|
|
|
|
* Fixed bugs:
|
|
* [@https://github.com/boostorg/container/pull/54 GitHub #54: ['"no sbrk() in VxWorks, configure dlmalloc to use only mmap"]].
|
|
* [@https://github.com/boostorg/container/issues/58 GitHub #58: ['"Comparing strings does not compile in gcc 7+ in C++17 mode"]].
|
|
* [@https://github.com/boostorg/container/issues/59 GitHub #59: ['"basic_string::npos is missing its definition"]].
|
|
|
|
[endsect]
|
|
|
|
[section:release_notes_boost_1_65_00 Boost 1.65 Release]
|
|
|
|
* Implemented `extract_sequence`, `adopt_sequence` functions for flat_[multi]map/set associative containers.
|
|
|
|
* Fixed bugs:
|
|
* [@https://github.com/boostorg/container/pull/48 GitHub #48: ['"Replace deprecated/removed C++98 binders"]].
|
|
* [@https://github.com/boostorg/container/pull/49 GitHub #49: ['"Remove useless allocator copy in map"]].
|
|
* [@https://github.com/boostorg/container/pull/50 GitHub #50: ['"Fixed bug Trac #13038"]].
|
|
* [@https://github.com/boostorg/container/pull/51 GitHub #51: ['"Fix integer rollover that triggers clang ubsan when U is unsigned"]].
|
|
|
|
[endsect]
|
|
|
|
[section:release_notes_boost_1_64_00 Boost 1.64 Release]
|
|
|
|
* Fixed bugs:
|
|
* [@https://svn.boost.org/trac/boost/ticket/11333 Trac #11333: ['"boost::basic_string_ref should interop with boost::container::basic_string"]].
|
|
* [@https://svn.boost.org/trac/boost/ticket/12749 Trac #12749: ['"container::pmr::polymorphic_allocator compilation error"]].
|
|
* [@https://svn.boost.org/trac/boost/ticket/12915 Trac #12915: ['"Buffer overflow in boost::container::vector (affects flat_set)"]].
|
|
* [@https://github.com/boostorg/container/pull/45 GitHub #45: ['"emplace_back must return reference to back(), not to *end()"]].
|
|
* [@https://github.com/boostorg/container/pull/46 GitHub #46: ['"Fix use of propagate_on_container_swap"]].
|
|
|
|
[endsect]
|
|
|
|
[section:release_notes_boost_1_63_00 Boost 1.63 Release]
|
|
|
|
* Fixed bugs:
|
|
* [@https://svn.boost.org/trac/boost/ticket/12534 Trac #12534: ['"flat_map fails to compile if included after type_traits is instantiated under gcc"]].
|
|
* [@https://svn.boost.org/trac/boost/ticket/12577 Trac #12577: ['"Null reference in pair.hpp triggers runtime warning with -fsanitize=undefined"]].
|
|
* [@https://github.com/boostorg/container/pull/41 GitHub #40: ['Fix parameter types in copy_move_algo.hpp: iterator_traits::difference_type -> allocator_traits::size_type]].
|
|
* [@https://github.com/boostorg/container/pull/41 GitHub #41: ['Avoid -Wunreachable-code in do_allocate()]].
|
|
|
|
[endsect]
|
|
|
|
[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.cpp_conformance.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_allocators Extended Allocators].
|
|
|
|
* [link container.configurable_containers.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]
|