2 / Copyright (c) 2009-2018 Ion Gazta\u00F1aga
4 / Distributed under the Boost Software License, Version 1.0. (See accompanying
5 / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
8 [library Boost.Container
10 [authors [Gaztanaga, Ion]]
11 [copyright 2009-2018 Ion Gaztanaga]
14 [purpose Containers library]
16 Distributed under the Boost Software License, Version 1.0.
17 (See accompanying file LICENSE_1_0.txt or copy at
18 [@http://www.boost.org/LICENSE_1_0.txt])
22 [template super[x]'''<superscript>'''[x]'''</superscript>''']
23 [template sub[x]'''<subscript>'''[x]'''</subscript>''']
25 [section:intro Introduction]
27 [*Boost.Container] library implements several well-known containers, including
28 STL containers. The aim of the library is to offer advanced features not present
29 in standard containers or to offer the latest standard draft features for compilers
30 that don't comply with the latest C++ standard.
32 In short, what does [*Boost.Container] offer?
34 * Emplacement and move semantics are implemented, including emulation for pre-C++11 compilers.
35 * Polymorphic allocators and memory resources, including implementation and emulation for pre-C++17 compilers
36 * New advanced features (e.g. recursive containers) and configurability options [link container.configurable_containers] for containers.
37 * Containers support stateful allocators and are compatible with [*Boost.Interprocess]
38 (they can be safely placed in shared memory).
39 * Users obtain a more uniform performance across all plataforms,
40 including [link container.main_features.scary_iterators SCARY iterators].
41 * The library offers new useful containers:
42 * [classref boost::container::flat_map flat_map],
43 [classref boost::container::flat_set flat_set],
44 [classref boost::container::flat_multimap flat_multimap] and
45 [classref boost::container::flat_multiset flat_multiset]: drop-in
46 replacements for standard associative containers but more memory friendly and with faster
48 * [classref boost::container::stable_vector stable_vector]: a std::list and std::vector hybrid
49 container: vector-like random-access iterators and list-like iterator stability in insertions and erasures.
50 * [classref boost::container::static_vector static_vector ]: a vector-like container that internally embeds
51 (statically allocates) all needed memory up to the maximum capacity. Maximum capacity can't be increased and
52 it's specified at compile time.
53 * [classref boost::container::small_vector small_vector ]: a vector-like container that internally embeds
54 (statically allocates) a minimum amount of memory, but dynamically allocates elements when capacity
55 has to be increased. This minimum capacity is specified at compile time.
56 * [classref boost::container::slist slist]: the classic pre-standard singly linked list implementation
57 offering constant-time `size()`. Note that C++11 `forward_list` has no `size()`.
59 [section:introduction_building_container Building Boost.Container]
61 There is no need to compile [*Boost.Container], since it's a header-only library,
62 just include your Boost header directory in your compiler include path *except if you use*:
64 * [link container.extended_allocators Extended Allocators]
65 * Some [link container.cpp_conformance.polymorphic_memory_resources Polymorphic Memory Resources] classes.
67 Those exceptions are are implemented as a separately compiled library, so in those cases you must install binaries
68 in a location that can be found by your linker.
69 If you followed the [@http://www.boost.org/doc/libs/release/more/getting_started/index.html Boost Getting Started]
70 instructions, that's already been done for you.
74 [section:tested_compilers Tested compilers]
76 [*Boost.Container] requires a decent C++98 compatibility. Some compilers known to work are:
81 [warning GCC < 4.3 and MSVC < 9.0 are deprecated and will be removed in the next version.]
87 [section:main_features Main features]
89 [section:move_emplace Efficient insertion]
91 Move semantics and placement insertion are two features brought by C++11 containers
92 that can have a very positive impact in your C++ applications. Boost.Container implements
93 both techniques both for C++11 and C++03 compilers.
95 [section:move_containers Move-aware containers]
97 All containers offered by [*Boost.Container] can store movable-only types
98 and actual requirements for `value_type` depend on each container operations.
99 Following C++11 requirements even for C++03 compilers, many operations now require
100 movable or default constructible types instead of just copy constructible types.
102 Containers themselves are also movable, with no-throw guarantee if allocator
103 or predicate (if present) copy operations are no-throw. This allows
104 high performance operations when transferring data between vectors.
105 Let's see an example:
107 [import ../example/doc_move_containers.cpp]
108 [doc_move_containers]
112 [section:emplace Emplace: Placement insertion]
114 All containers offered by [*Boost.Container] implement placement insertion,
115 which means that objects can be built directly into the container from user arguments
116 without creating any temporary object. For compilers without variadic templates support
117 placement insertion is emulated up to a finite (10) number of arguments.
119 Expensive to move types are perfect candidates emplace functions and in case of node containers
120 ([classref boost::container::list list], [classref boost::container::set set], ...)
121 emplace allows storing non-movable and non-copyable types in containers! Let's
124 [import ../example/doc_emplace.cpp]
132 [section:containers_of_incomplete_types Containers of Incomplete Types]
134 Incomplete types allow
135 [@http://en.wikipedia.org/wiki/Type_erasure [*type erasure ]] and
136 [@http://en.wikipedia.org/wiki/Recursive_data_type [*recursive data types]], and
137 C and C++ programmers have been using it for years to build complex data structures, like
138 tree structures where a node may have an arbitrary number of children.
140 What about standard containers? Containers of incomplete types have been under discussion for a long time,
141 as explained in Matt Austern's great article ([@http://drdobbs.com/184403814 [*The Standard Librarian: Containers of Incomplete Types]]):
143 ["['Unlike most of my columns, this one is about something you can't do with the C++ Standard library:
144 put incomplete types in one of the standard containers. This column explains why you might want to
145 do this, why the standardization committee banned it even though they knew it was useful, and what
146 you might be able to do to get around the restriction.]]
148 ["['In 1997, shortly before the C++ Standard was completed, the standardization committee received a
149 query: Is it possible to create standard containers with incomplete types? It took a while for the
150 committee to understand the question. What would such a thing even mean, and why on earth would you
151 ever want to do it? The committee eventually worked it out and came up with an answer to the question.
152 (Just so you don't have to skip ahead to the end, the answer is "no.") But the question is much more
153 interesting than the answer: it points to a useful, and insufficiently discussed, programming technique.
154 The standard library doesn't directly support that technique, but the two can be made to coexist.]]
156 ["['In a future revision of C++, it might make sense to relax the restriction on instantiating
157 standard library templates with incomplete types. Clearly, the general prohibition should stay
158 in place - instantiating templates with incomplete types is a delicate business, and there are
159 too many classes in the standard library where it would make no sense. But perhaps it should be
160 relaxed on a case-by-case basis, and `vector` looks like a good candidate for such special-case
161 treatment: it's the one standard container class where there are good reasons to instantiate
162 it with an incomplete type and where Standard Library implementors want to make it work. As of
163 today, in fact, implementors would have to go out of their way to prohibit it!]]
165 C++11 standard is also cautious about incomplete types and STL: ["['17.6.4.8 Other functions (...) 2.
166 the effects are undefined in the following cases: (...) In particular - if an incomplete type (3.9)
167 is used as a template argument when instantiating a template component,
168 unless specifically allowed for that component]].
170 Finally C++17 added support for incomplete types in `std::vector`, `std::list` and `std::forward_list`
171 (see [@https://wg21.link/n4569 ['N4569: Minimal incomplete type support for standard containers, revision 4]]
172 for details), but no other containers like `std::set/map/unordered_set/unordered_map`,
174 Fortunately all [*Boost.Container] containers except
175 [classref boost::container::static_vector static_vector] and
176 [classref boost::container::small_vector small_vector] and
177 [classref boost::container::basic_string basic_string] are designed to support incomplete types.
178 [classref boost::container::static_vector static_vector] and
179 [classref boost::container::small_vector small_vector] are special because
180 they statically allocates memory for `value_type` and this requires complete types.
181 [classref boost::container::basic_string basic_string] implements Small String Optimization which
182 also requires complete types.
184 [*Boost.Container] containers supporting incomplete types also support instantiating iterators to
185 those incomplete elements.
187 [section:recursive_containers Recursive containers]
189 Most [*Boost.Container] containers can be used to define recursive containers:
191 [import ../example/doc_recursive_containers.cpp]
192 [doc_recursive_containers]
196 [section:type_erasure Type Erasure]
198 Containers of incomplete types are useful to break header file dependencies and improve
199 compilation types. With Boost.Container, you can write a header file defining a class
200 with containers of incomplete types as data members, if you carefully put all the
201 implementation details that require knowing the size of the `value_type` in your
204 [import ../example/doc_type_erasure.cpp]
206 In this header file we define a class (`MyClassHolder)` that holds a `vector` of an
207 incomplete type (`MyClass`) that it's only forward declared.
209 [doc_type_erasure_MyClassHolder_h]
211 Then we can define `MyClass` in its own header file.
213 [doc_type_erasure_MyClass_h]
215 And include it only in the implementation file of `MyClassHolder`
217 [doc_type_erasure_MyClassHolder_cpp]
219 Finally, we can just compile, link, and run!
221 [doc_type_erasure_main_cpp]
227 [section:scary_iterators SCARY iterators]
229 The paper N2913, titled [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2913.pdf
230 SCARY Iterator Assignment and Initialization], proposed a requirement that a standard container's
231 iterator types have no dependency on any type argument apart from the container's `value_type`,
232 `difference_type`, `pointer type`, and `const_pointer` type. In particular, according to the proposal,
233 the types of a standard container's iterators should not depend on the container's `key_compare`,
234 `hasher`, `key_equal`, or `allocator` types.
236 That paper demonstrated that SCARY operations were crucial to the performant implementation of common
237 design patterns using STL components. It showed that implementations that support SCARY operations reduce
238 object code bloat by eliminating redundant specializations of iterator and algorithm templates.
240 [*Boost.Container] containers implement SCARY iterators so the iterator type of a container is only dependent
241 on the `allocator_traits<allocator_type>::pointer` type (the pointer type of the `value_type` to be inserted
242 in the container). Reference types and all other typedefs are deduced from the pointer type using the
243 C++11 `pointer_traits` utility. This leads to lower code bloat in algorithms and classes templated on
248 [section:other_features Other features]
250 * Default constructors don't allocate memory which improves performance and
251 usually implies a no-throw guarantee (if predicate's or allocator's default constructor doesn't throw).
253 * Small string optimization for [classref boost::container::basic_string basic_string],
254 with an internal buffer of 11/23 bytes (32/64 bit systems)
255 [*without] increasing the usual `sizeof` of the string (3 words).
257 * `[multi]set/map` containers are size optimized embedding the color bit of the red-black tree nodes
258 in the parent pointer.
260 * `[multi]set/map` containers use no recursive functions so stack problems are avoided.
266 [section:exception_handling Boost.Container and C++ exceptions]
268 In some environments, such as game development or embedded systems, C++ exceptions are disabled or a customized error handling is needed.
269 According to document [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html N2271 EASTL -- Electronic Arts Standard Template Library]
270 exceptions can be disabled for several reasons:
272 * ["['Exception handling incurs some kind of cost in all compiler implementations, including those that avoid
273 the cost during normal execution. However, in some cases this cost may arguably offset the cost of the code that it is replacing.]]
274 * ["['Exception handling is often agreed to be a superior solution for handling a large range of function return values. However,
275 avoiding the creation of functions that need large ranges of return values is superior to using exception handling to handle such values.]]
276 * ["['Using exception handling correctly can be difficult in the case of complex software.]]
277 * ["['The execution of throw and catch can be significantly expensive with some implementations.]]
278 * ["['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
279 has destructible stack objects regardless of whether they use exception handling.]]
280 * ["['The approach that game software usually takes is to avoid the need for exception handling where possible; avoid the possibility
281 of circumstances that may lead to exceptions. For example, verify up front that there is enough memory for a subsystem to do its job
282 instead of trying to deal with the problem via exception handling or any other means after it occurs.]]
283 * ["['However, some game libraries may nevertheless benefit from the use of exception handling. It's best, however,
284 if such libraries keep the exception handling internal lest they force their usage of exception handling on the rest of the application.]]
286 In order to support environments without C++ exception support or environments with special error handling needs,
287 [*Boost.Container] changes error signalling behaviour when `BOOST_CONTAINER_USER_DEFINED_THROW_CALLBACKS` or `BOOST_NO_EXCEPTIONS`
288 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]
289 when the compiler has been invoked with the appropriate flag (like `-fno-exceptions` in GCC).
291 When dealing with user-defined classes, (e.g. when constructing user-defined classes):
293 * If `BOOST_NO_EXCEPTIONS` is defined, the library avoids using `try`/`catch`/`throw` statements. The class writer must handle and
294 propagate error situations internally as no error will be propagated through [*Boost.Container].
295 * If `BOOST_NO_EXCEPTIONS` is *not* defined, the library propagates exceptions offering the exception guarantees detailed in the documentation.
297 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
298 a throw-callback declared in [headerref boost/container/throw_exception.hpp]:
300 * If `BOOST_CONTAINER_USER_DEFINED_THROW_CALLBACKS` is defined, then the programmer must provide its own definition for all
301 `throw_xxx` functions. Those functions can't return, they must throw an exception or call `std::exit` or `std::abort`.
302 * Else if `BOOST_NO_EXCEPTIONS` is defined, a `BOOST_ASSERT_MSG` assertion is triggered
303 (see [@http://www.boost.org/libs/utility/assert.html Boost.Assert] for more information).
304 If this assertion returns, then `std::abort` is called.
305 * Else, an appropriate standard library exception is thrown (like `std::out_of_range`).
309 [section:non_standard_containers Non-standard containers]
311 [section:stable_vector ['stable_vector]]
313 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]
314 is an hybrid between `vector` and `list`, providing most of
315 the features of `vector` except [@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#69 element contiguity].
317 Extremely convenient as they are, `vector`s have a limitation that many novice C++ programmers frequently stumble upon:
318 iterators and references to an element of an `vector` are invalidated when a preceding element is erased or when the
319 vector expands and needs to migrate its internal storage to a wider memory region (i.e. when the required size exceeds
320 the vector's capacity). We say then that `vector`s are unstable: by contrast, stable containers are those for which
321 references and iterators to a given element remain valid as long as the element is not erased: examples of stable containers
322 within the C++ standard library are `list` and the standard associative containers (`set`, `map`, etc.).
324 Sometimes stability is too precious a feature to live without, but one particular property of `vector`s, element contiguity,
325 makes it impossible to add stability to this container. So, provided we sacrifice element contiguity, how much
326 can a stable design approach the behavior of `vector` (random access iterators, amortized constant time end
327 insertion/deletion, minimal memory overhead, etc.)?
328 The following image describes the layout of a possible data structure upon which to base the design of a stable vector:
330 [$../../libs/container/doc/images/stable_vector.png [width 50%] [align center] ]
332 Each element is stored in its own separate node. All the nodes are referenced from a contiguous array of pointers, but
333 also every node contains an "up" pointer referring back to the associated array cell. This up pointer is the key element
334 to implementing stability and random accessibility:
336 Iterators point to the nodes rather than to the pointer array. This ensures stability, as it is only the pointer array
337 that needs to be shifted or relocated upon insertion or deletion. Random access operations can be implemented by using
338 the pointer array as a convenient intermediate zone. For instance, if the iterator it holds a node pointer `it.p` and we
339 want to advance it by n positions, we simply do:
343 it.p = *(it.p->up+n);
345 That is, we go "up" to the pointer array, add n there and then go "down" to the resulting node.
347 [*General properties]. `stable_vector` satisfies all the requirements of a container, a reversible container and a sequence
348 and provides all the optional operations present in vector. Like vector, iterators are random access. `stable_vector`
349 does not provide element contiguity; in exchange for this absence, the container is stable, i.e. references and iterators
350 to an element of a `stable_vector` remain valid as long as the element is not erased, and an iterator that has been
351 assigned the return value of end() always remain valid until the destruction of the associated `stable_vector`.
353 [*Operation complexity]. The big-O complexities of `stable_vector` operations match exactly those of vector. In general,
354 insertion/deletion is constant time at the end of the sequence and linear elsewhere. Unlike vector, `stable_vector`
355 does not internally perform any value_type destruction, copy/move construction/assignment operations other than those exactly
356 corresponding to the insertion of new elements or deletion of stored elements, which can sometimes compensate in terms of
357 performance for the extra burden of doing more pointer manipulation and an additional allocation per element.
359 [*Exception safety]. (according to [@http://www.boost.org/community/exception_safety.html Abrahams' terminology])
360 As `stable_vector` does not internally copy/move elements around, some
361 operations provide stronger exception safety guarantees than in vector:
363 [table:stable_vector_req Exception safety
364 [[operation] [exception safety for `vector<T>`] [exception safety for `stable_vector<T>`]]
365 [[insert] [strong unless copy/move construction/assignment of `T` throw (basic)] [strong]]
366 [[erase] [no-throw unless copy/move construction/assignment of `T` throw (basic)] [no-throw]]
369 [*Memory overhead]. The C++ standard does not specify requirements on memory consumption, but virtually any implementation
370 of `vector` has the same behavior with respect to memory usage: the memory allocated by a `vector` v with n elements of type T
375 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
376 required; otherwise, the average value c for a growing `vector` oscillates between 1.25\u2219n and 1.5\u2219n for typical resizing
377 policies. For `stable_vector`, the memory usage is
379 m[sub sv] = (c + 1)p + (n + 1)(e + p),
381 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
382 the sequence. If we call f the capacity to size ratio c/n and assume that n is large enough, we have that
384 m[sub sv]/m[sub v] \u2243 (fp + e + p)/fe.
386 So, `stable_vector` uses less memory than `vector` only when e > p and the capacity to size ratio exceeds a given threshold:
388 m[sub sv] < m[sub v] <-> f > (e + p)/(e - p). (provided e > p)
390 This threshold approaches typical values of f below 1.5 when e > 5p; in a 32-bit architecture, when e > 20 bytes.
392 [*Summary]. `stable_vector` is a drop-in replacement for `vector` providing stability of references and iterators, in exchange
393 for missing element contiguity and also some performance and memory overhead. When the element objects are expensive to
394 move around, the performance overhead can turn into a net performance gain for `stable_vector` if many middle insertions
395 or deletions are performed or if resizing is very frequent. Similarly, if the elements are large there are situations when
396 the memory used by `stable_vector` can actually be less than required by vector.
398 ['Note: Text and explanations taken from [@http://bannalia.blogspot.com/2008/09/introducing-stablevector.html Joaqu\u00EDn's blog]]
402 [section:flat_xxx ['flat_(multi)map/set] associative containers]
404 Using sorted vectors instead of tree-based associative containers is a well-known technique in
405 C++ world. Matt Austern's classic article
406 [@http://lafstern.org/matt/col1.pdf Why You Shouldn't Use set, and What You Should Use Instead]
407 (C++ Report 12:4, April 2000) was enlightening:
409 ["['Red-black trees aren't the only way to organize data that permits lookup in logarithmic time. One of the basic
410 algorithms of computer science is binary search, which works by successively dividing a range in half. Binary
411 search is log N and it doesn't require any fancy data structures, just a sorted collection of elements.
412 (...) You can use whatever data structure is convenient, so long as it provides STL iterator;
413 usually it's easiest to use a C array, or a vector.]]
415 ["['Both std::lower_bound and set::find take time proportional to log N, but the constants of proportionality
416 are very different. Using g++ (...) it takes X seconds to perform a million lookups in a
417 sorted vector<double> of a million elements, and almost twice as long (...) using a set. Moreover,
418 the set uses almost three times as much memory (48 million bytes) as the vector (16.8 million).]]
420 ["['Using a sorted vector instead of a set gives you faster lookup and much faster iteration,
421 but at the cost of slower insertion. Insertion into a set, using set::insert, is proportional
422 to log N, but insertion into a sorted vector, (...)
423 , is proportional to N. Whenever you insert something into a vector,
424 vector::insert has to make room by shifting all of the elements that follow it. On average, if you're equally
425 likely to insert a new element anywhere, you'll be shifting N/2 elements.]]
427 ["['It may sometimes be convenient to bundle all of this together into a small container adaptor.
428 This class does not satisfy the requirements of a Standard Associative Container, since the complexity of insert is
429 O(N) rather than O(log N), but otherwise it is almost a drop-in replacement for set.]]
431 Following Matt Austern's indications, Andrei Alexandrescu's
432 [@http://www.bestwebbuys.com/Modern-C-Design-Generic-Programming-and-Design-Patterns-Applied-ISBN-9780201704310?isrc=-rd Modern C++ Design]
433 showed `AssocVector`, a `std::map` drop-in
434 replacement designed in his [@http://loki-lib.sourceforge.net/ Loki] library:
436 ["['It seems as if we're better off with a sorted vector. The disadvantages of a sorted
437 vector are linear-time insertions and linear-time deletions (...). In exchange, a vector
438 offers about twice the lookup speed and a much smaller working set (...).
439 Loki saves the trouble of maintaining a sorted vector by hand by defining an AssocVector class
440 template. AssocVector is a drop-in replacement for std::map (it supports the same set of member
441 functions), implemented on top of std::vector. AssocVector differs from a map in the behavior of
442 its erase functions (AssocVector::erase invalidates all iterators into the object) and in the
443 complexity guarantees of insert and erase (linear as opposed to constant). ]]
445 [*Boost.Container] `flat_[multi]map/set` containers are ordered, vector-like container based, associative
446 containers following Austern's and Alexandrescu's guidelines. These ordered vector containers have also
447 benefited with the addition of `move semantics` to C++11, speeding up insertion and
448 erasure times considerably. Flat associative containers have the following attributes:
450 * Faster lookup than standard associative containers
451 * Much faster iteration than standard associative containers.
452 Random-access iterators instead of bidirectional iterators.
453 * Less memory consumption for small objects (and for big objects if `shrink_to_fit` is used)
454 * Improved cache performance (data is stored in contiguous memory)
455 * Non-stable iterators (iterators are invalidated when inserting and erasing elements)
456 * Non-copyable and non-movable values types can't be stored
457 * Weaker exception safety than standard associative containers
458 (copy/move constructors can throw when shifting values in erasures and insertions)
459 * Slower insertion and erasure than standard associative containers (specially for non-movable types)
463 [section:slist ['slist]]
465 When the standard template library was designed, it contained a singly linked list called `slist`.
466 Unfortunately, this container was not standardized and remained as an extension for many standard
467 library implementations until C++11 introduced `forward_list`, which is a bit different from the
468 the original SGI `slist`. According to [@http://www.sgi.com/tech/stl/Slist.html SGI STL documentation]:
470 ["['An `slist` is a singly linked list: a list where each element is linked to the next element, but
471 not to the previous element. That is, it is a Sequence that supports forward but not backward traversal,
472 and (amortized) constant time insertion and removal of elements. Slists, like lists, have the important
473 property that insertion and splicing do not invalidate iterators to list elements, and that even removal
474 invalidates only the iterators that point to the elements that are removed. The ordering of iterators
475 may be changed (that is, slist<T>::iterator might have a different predecessor or successor after a list
476 operation than it did before), but the iterators themselves will not be invalidated or made to point to
477 different elements unless that invalidation or mutation is explicit.]]
479 ["['The main difference between `slist` and list is that list's iterators are bidirectional iterators,
480 while slist's iterators are forward iterators. This means that `slist` is less versatile than list;
481 frequently, however, bidirectional iterators are unnecessary. You should usually use `slist` unless
482 you actually need the extra functionality of list, because singly linked lists are smaller and faster
483 than double linked lists.]]
485 ["['Important performance note: like every other Sequence, `slist` defines the member functions insert and erase.
486 Using these member functions carelessly, however, can result in disastrously slow programs. The problem is that
487 insert's first argument is an iterator pos, and that it inserts the new element(s) before pos. This means that
488 insert must find the iterator just before pos; this is a constant-time operation for list, since list has
489 bidirectional iterators, but for `slist` it must find that iterator by traversing the list from the beginning
490 up to pos. In other words: insert and erase are slow operations anywhere but near the beginning of the slist.]]
492 ["['Slist provides the member functions insert_after and erase_after, which are constant time operations: you should
493 always use insert_after and erase_after whenever possible. If you find that insert_after and erase_after aren't
494 adequate for your needs, and that you often need to use insert and erase in the middle of the list, then you
495 should probably use list instead of slist.]]
497 [*Boost.Container] updates the classic `slist` container with C++11 features like move semantics and placement
498 insertion and implements it a bit differently than the standard C++ `forward_list`. `forward_list` has no `size()`
499 method, so it's been designed to allow (or in practice, encourage) implementations without tracking list size
500 with every insertion/erasure, allowing constant-time
501 `splice_after(iterator, forward_list &, iterator, iterator)`-based list merging. On the other hand `slist` offers
502 constant-time `size()` for those that don't care about linear-time `splice_after(iterator, slist &, iterator, iterator)`
503 `size()` and offers an additional `splice_after(iterator, slist &, iterator, iterator, size_type)` method that
504 can speed up `slist` merging when the programmer already knows the size. `slist` and `forward_list` are therefore
509 [section:static_vector ['static_vector]]
511 `static_vector` is an hybrid between `vector` and `array`: like `vector`, it's a sequence container
512 with contiguous storage that can change in size, along with the static allocation, low overhead,
513 and fixed capacity of `array`. `static_vector` is based on Adam Wulkiewicz and Andrew Hundt's
514 high-performance [@https://svn.boost.org/svn/boost/sandbox/varray/doc/html/index.html varray]
517 The number of elements in a `static_vector` may vary dynamically up to a fixed capacity
518 because elements are stored within the object itself similarly to an array. However, objects are
519 initialized as they are inserted into `static_vector` unlike C arrays or `std::array` which must construct
520 all elements on instantiation. The behavior of `static_vector` enables the use of statically allocated
521 elements in cases with complex object lifetime requirements that would otherwise not be trivially
522 possible. Some other properties:
524 * Random access to elements
525 * Constant time insertion and removal of elements at the end
526 * Linear time insertion and removal of elements at the beginning or in the middle.
528 `static_vector` is well suited for use in a buffer, the internal implementation of other
529 classes, or use cases where there is a fixed limit to the number of elements that must be stored.
530 Embedded and realtime applications where allocation either may not be available or acceptable
531 are a particular case where `static_vector` can be beneficial.
535 [section:small_vector ['small_vector]]
537 `small_vector` is a vector-like container optimized for the case when it contains few elements.
538 It contains some preallocated elements in-place, which allows it to avoid the use of dynamic storage allocation
539 when the actual number of elements is below that preallocated threshold. `small_vector` is inspired by
540 [@http://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h LLVM's `SmallVector`] container.
541 Unlike `static_vector`, `small_vector`'s capacity can grow beyond the initial preallocated capacity.
543 `small_vector<T, N, Allocator>` is convertible to `small_vector_base<T, Allocator>`, a type that is independent
544 from the preallocated element count, allowing client code that does not need to be templated on that N argument.
545 `small_vector` inherits all `vector`'s member functions so it supports all standard features like emplacement,
546 stateful allocators, etc.
552 [section:extended_functionality Extended functionality: Basic extensions]
554 [section:default_initialialization Default initialization for vector-like containers]
556 STL and most other containers value initialize new elements in common operations like
557 `vector::resize(size_type n)` or `explicit vector::vector(size_type n)`.
559 In some performance-sensitive environments, where vectors are used as a replacement for
560 variable-size buffers for file or network operations,
561 [@http://en.cppreference.com/w/cpp/language/value_initialization value initialization]
562 is a cost that is not negligible as elements are going to be overwritten by an external source
563 shortly after new elements are added to the container.
565 [*Boost.Container] offers two new members for `vector`, `static_vector` and `stable_vector`:
566 `explicit container::container(size_type n, default_init_t)` and
567 `container::resize(size_type n, default_init_t)`, where new elements are constructed
568 using [@http://en.cppreference.com/w/cpp/language/default_initialization default initialization].
572 [section:ordered_range_insertion Ordered range insertion for associative containers (['ordered_unique_range], ['ordered_range]) ]
574 When filling associative containers big performance gains can be achieved if the input range to be inserted
575 is guaranteed by the user to be ordered according to the predicate. This can happen when inserting values from a `set` to
576 a `multiset` or between different associative container families (`[multi]set/map` vs. `flat_[multi]set/map`).
578 [*Boost.Container] has some overloads for constructors and insertions taking an `ordered_unique_range_t` or
579 an `ordered_range_t` tag parameters as the first argument. When an `ordered_unique_range_t` overload is used, the
580 user notifies the container that the input range is ordered according to the container predicate and has no
581 duplicates. When an `ordered_range_t` overload is used, the
582 user notifies the container that the input range is ordered according to the container predicate but it might
583 have duplicates. With this information, the container can avoid multiple predicate calls and improve insertion
588 [section:constant_time_range_splice Constant-time range splice for `(s)list`]
590 In the first C++ standard `list::size()` was not required to be constant-time,
591 and that caused some controversy in the C++ community. Quoting Howard Hinnant's
592 [@http://howardhinnant.github.io/On_list_size.html ['On List Size]] paper:
594 [: ['There is a considerable debate on whether `std::list<T>::size()` should be O(1) or O(N).
595 The usual argument notes that it is a tradeoff with:]
597 `splice(iterator position, list& x, iterator first, iterator last);`
599 ['If size() is O(1) and this != &x, then this method must perform a linear operation so that it
600 can adjust the size member in each list]]
602 C++11 definitely required `size()` to be O(1), so range splice became O(N). However,
603 Howard Hinnant's paper proposed a new `splice` overload so that even O(1) `list:size()`
604 implementations could achieve O(1) range splice when the range size was known to the caller:
606 [: `void splice(iterator position, list& x, iterator first, iterator last, size_type n);`
608 [*Effects]: Inserts elements in the range [first, last) before position and removes the elements from x.
610 [*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).
614 [*Complexity]: Constant time.
617 This new splice signature allows the client to pass the distance of the input range in.
618 This information is often available at the call site. If it is passed in,
619 then the operation is constant time, even with an O(1) size.
621 [*Boost.Container] implements this overload for `list` and a modified version of it for `slist`
622 (as `slist::size()` is also `O(1)`).
628 [section:configurable_containers Extended functionality: Configurable containers]
630 [*Boost.Container] offers the possibility to configure at compile time some parameters of
631 several containers, apart from the stored type and the allocator. This configuration is passed as
632 the last template parameter and defined using the utility classes. The following containers can receive
633 useful configuration options:
635 [section:configurable_tree_based_associative_containers Configurable tree-based associative ordered containers]
637 [classref boost::container::set set], [classref boost::container::multiset multiset],
638 [classref boost::container::map map] and [classref boost::container::multimap multimap] associative containers
639 are implemented as binary search trees which offer the needed complexity and stability guarantees required by the
640 C++ standard for associative containers.
642 [*Boost.Container] offers the possibility to configure at compile time some parameters of the binary search tree
643 implementation. This configuration is passed as the last template parameter and defined using the utility class
644 [classref boost::container::tree_assoc_options tree_assoc_options]. The following parameters can be configured:
646 * The underlying [*tree implementation] type ([classref boost::container::tree_type tree_type]).
647 By default these containers use a red-black tree but the user can use other tree types:
648 * [@http://en.wikipedia.org/wiki/Red%E2%80%93black_tree Red-Black Tree]
649 * [@http://en.wikipedia.org/wiki/Avl_trees AVL tree]
650 * [@http://en.wikipedia.org/wiki/Scapegoat_tree Scapegoat tree]. In this case Insertion and Deletion
651 are amortized O(log n) instead of O(log n).
652 * [@http://en.wikipedia.org/wiki/Splay_tree Splay tree]. In this case Searches, Insertions and Deletions
653 are amortized O(log n) instead of O(log n).
655 * Whether the [*size saving] mechanisms are used to implement the tree nodes
656 ([classref boost::container::optimize_size optimize_size]). By default this option is activated and is only
657 meaningful to red-black and avl trees (in other cases, this option will be ignored).
658 This option will try to put rebalancing metadata inside the "parent" pointer of the node if the pointer
659 type has enough alignment. Usually, due to alignment issues, the metadata uses the size of a pointer yielding
660 to four pointer size overhead per node, whereas activating this option usually leads to 3 pointer size overhead.
661 Although some mask operations must be performed to extract
662 data from this special "parent" pointer, in several systems this option also improves performance due to the
663 improved cache usage produced by the node size reduction.
665 See the following example to see how [classref boost::container::tree_assoc_options tree_assoc_options] can be
666 used to customize these containers:
668 [import ../example/doc_custom_tree.cpp]
673 [section:configurable_vectors Configurable vectors]
675 The configuration for [classref boost::container::vector vector] is passed as
676 the last template parameter and defined using the utility class
677 [classref boost::container::vector_options vector_options]. The following parameters can be configured:
679 * [classref boost::container::growth_factor growth_factor]: the growth policy of the vector.
680 The rate at which the capacity of a vector grows is implementation dependent and
681 implementations choose exponential growth in order to meet the amortized constant time requirement for push_back.
682 A higher growth factor will make it faster as it will require less data movement, but it will have a greater memory
683 impact (on average, more memory will be unused). A user can provide a custom implementation of the growth factor and some
684 predefined policies are available: [classref boost::container::growth_factor_50 growth_factor_50],
685 [classref boost::container::growth_factor_60 growth_factor_60] and
686 [classref boost::container::growth_factor_50 growth_factor_100].
688 * [classref boost::container::stored_size stored_size]: the type that will be used to store size-related
689 parameters inside of the vector. Sometimes, when the maximum capacity to be used is much less than the
690 theoretical maximum that a vector can hold, it's interesting to use smaller unsigned integer types to represent
691 `size()` and `capacity()` inside vector, so that the size of an empty vector is minimized and cache
692 performance might be improved. See [classref boost::container::stored_size stored_size] for more details.
694 See the following example to see how [classref boost::container::vector_options vector_options] can be
695 used to customize `vector` container:
697 [import ../example/doc_custom_vector.cpp]
702 [section:configurable_deques Configurable deques]
704 The configuration for [classref boost::container::deque deque] is passed as
705 the last template parameter and defined using the utility class
706 [classref boost::container::deque_options deque_options]. The following parameters can be configured:
708 Parameters that control the size of deque's 'block' (deque allocates contiguous chunks of elements, called 'blocks').
709 Only one of these paratemers can be specified:
711 * [classref boost::container::block_bytes block_bytes]: the number of bytes deque will allocate for store
712 elements contiguously: `deque::get_block_size()` will return aproximately `block_bytes/sizeof(value_type)`.
713 A value of zero means the default value.
715 * [classref boost::container::block_size block_size]: the number of elements deque will allocate contiguously.
716 If this option is specified, `deque::get_block_size()` will return the specified `block_size`.
717 A value of zero means the default value.
719 See the following example to see how [classref boost::container::deque_options deque_options] can be
720 used to customize `deque` container:
722 [import ../example/doc_custom_deque.cpp]
727 [section:configurable_static_vectors Configurable static vector]
729 The configuration for [classref boost::container::static_vector static_vector] is passed as
730 the last template parameter and defined using the utility class
731 [classref boost::container::static_vector_options static_vector_options]. The following parameters can be configured:
733 * [classref boost::container::inplace_alignment inplace_alignment]: the minimum alignment (in bytes) that the stored value type
734 needs. This option allows static vectors that need non-default alignments, e.g., to be used in SIMD operations.
736 * [classref boost::container::throw_on_overflow throw_on_overflow]: A boolean that specifies if the
737 container should throw an exception when the compile-time capacity is not enough to hold the requesteed number
738 of objects. When "false", if the capacit is overflowd, the implementation calls to BOOST_ASSERT and if that assertion
739 does not throw or abort, undefined behavior is triggered.
741 See the following example to see how [classref boost::container::static_vector_options static_vector_options] can be
742 used to customize `static_vector` container:
744 [import ../example/doc_custom_static_vector.cpp]
745 [doc_custom_static_vector]
749 [section:configurable_small_vectors Configurable small vector]
751 The configuration for [classref boost::container::small_vector small_vector] is passed as
752 the last template parameter and defined using the utility class
753 [classref boost::container::small_vector_options small_vector_options]. The following parameters can be configured:
755 * [classref boost::container::inplace_alignment inplace_alignment]: the minimum alignment (in bytes) for the in-place storage
756 used to build the "small" number of elements. [*The alignment of the dynamic memory must be provided by the allocator
757 and it is not affected by this option].
759 * [classref boost::container::growth_factor growth_factor]: the growth policy of the vector.
760 The rate at which the capacity of a vector grows is implementation dependent and
761 implementations choose exponential growth in order to meet the amortized constant time requirement for push_back.
762 A higher growth factor will make it faster as it will require less data movement, but it will have a greater memory
763 impact (on average, more memory will be unused). A user can provide a custom implementation of the growth factor and some
764 predefined policies are available: [classref boost::container::growth_factor_50 growth_factor_50],
765 [classref boost::container::growth_factor_60 growth_factor_60] and
766 [classref boost::container::growth_factor_50 growth_factor_100].
768 See the following example to see how [classref boost::container::small_vector_options small_vector_options] can be
769 used to customize `small_vector` container:
771 [import ../example/doc_custom_small_vector.cpp]
772 [doc_custom_small_vector]
778 [section:extended_allocators Extended functionality: Extended allocators]
780 Many C++ programmers have ever wondered where does good old realloc fit in C++. And that's a good question.
781 Could we improve [classref boost::container::vector vector] performance using memory expansion mechanisms
782 to avoid too many copies? But [classref boost::container::vector vector] is not the only container that
783 could benefit from an improved allocator interface: we could take advantage of the insertion of multiple
784 elements in [classref boost::container::list list] using a burst allocation mechanism that could amortize
785 costs (mutex locks, free memory searches...) that can't be amortized when using single node allocation
788 These improvements require extending the STL allocator interface and use make use of a new
789 general purpose allocator since new and delete don't offer expansion and burst capabilities.
791 * [*Boost.Container] containers support an extended allocator interface based on an evolution of proposals
792 [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1953.html N1953: Upgrading the Interface of Allocators using API Versioning],
793 [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html N2045: Improving STL allocators]
795 [@http://www.drivehq.com/web/igaztanaga/allocplus/ Applying classic memory allocation strategies to C++ containers].
796 The extended allocator interface is implemented by [classref boost::container::allocator allocator],
797 [classref boost::container::adaptive_pool adaptive_pool] and [classref boost::container::node_allocator node_allocator]
800 * Extended allocators use a modified [@http://g.oswego.edu/dl/html/malloc.html Doug Lea Malloc (DLMalloc)] low-level
801 allocator and offers an C API to implement memory expansion and burst allocations. DLmalloc is known to be very size
802 and speed efficient, and this allocator is used as the basis of many malloc implementations, including multithreaded
803 allocators built above DLmalloc (See [@http://www.malloc.de/en/ ptmalloc2, ptmalloc3] or
804 [@http://www.nedprod.com/programs/portable/nedmalloc/ nedmalloc]). This low-level allocator is implemented as
805 a separately compiled library and the following extended allocators depend on the library:
807 * [classref boost::container::allocator allocator]: This extended allocator offers expansion, shrink-in place
808 and burst allocation capabilities implemented as a thin wrapper around the modified DLMalloc.
809 It can be used with all containers and it should be the default choice when the programmer wants to use
810 extended allocator capabilities.
812 * [classref boost::container::node_allocator node_allocator]: It's a
813 [@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]
814 allocator, similar to [*Boost.Pool] that takes advantage of the modified DLMalloc burst interface. It does not return
815 memory to the DLMalloc allocator (and thus, to the system), unless explicitly requested. It does offer a very small
816 memory overhead so it's suitable for node containers ([boost::container::list list], [boost::container::slist slist]
817 [boost::container::set set]...) that allocate very small `value_type`s and it offers improved node allocation times
818 for single node allocations with respecto to [classref boost::container::allocator allocator].
820 * [classref boost::container::adaptive_pool adaptive_pool]: It's a low-overhead node allocator that can return memory
821 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].
822 It's also suitable for node containers.
824 Use them simply specifying the new allocator in the corresponding template argument of your favourite container:
826 [import ../example/doc_extended_allocators.cpp]
827 [doc_extended_allocators]
831 [section:cpp_conformance C++11/C++14/C++17 Conformance]
833 [*Boost.Container] aims for full C++11 conformance except reasoned deviations,
834 backporting as much as possible for C++03. Obviously, this conformance is a work
835 in progress so this section explains what C++11/C++14/C++17 features are implemented and which
836 of them have been backported to earlier standard conformig compilers.
838 [section:move_emplace Move and Emplace]
840 For compilers with rvalue references and for those C++03 types that use
841 [@http://www.boost.org/libs/move Boost.Move] rvalue reference emulation
842 [*Boost.Container] supports all C++11 features related to move semantics: containers
843 are movable, requirements for `value_type` are those specified for C++11 containers.
845 For compilers with variadic templates, [*Boost.Container] supports placement insertion
846 (`emplace`, ...) functions from C++11. For those compilers without variadic templates
847 support [*Boost.Container] uses the preprocessor to create a set of overloads up to
848 a finite number of parameters.
852 [section:alloc_traits_move_traits Stateful allocators]
854 C++03 was not stateful-allocator friendly. For compactness of container objects and for
855 simplicity, it did not require containers to support allocators with state: Allocator objects
856 need not be stored in container objects. It was not possible to store an allocator with state,
857 say an allocator that holds a pointer to an arena from which to allocate. C++03 allowed implementors
858 to suppose two allocators of the same type always compare equal (that means that memory allocated
859 by one allocator object could be deallocated by another instance of the same type) and
860 allocators were not swapped when the container was swapped.
862 C++11 further improves stateful allocator support through
863 [@http://en.cppreference.com/w/cpp/memory/allocator_traits `std::allocator_traits`].
864 `std::allocator_traits` is the protocol between a container and an allocator, and
865 an allocator writer can customize its behaviour (should the container propagate it in
866 move constructor, swap, etc.?) following `allocator_traits` requirements. [*Boost.Container]
867 not only supports this model with C++11 but also [*backports it to C++03] via
868 [classref boost::container::allocator_traits boost::container::allocator_traits] including some
869 C++17 changes. This class
870 offers some workarounds for C++03 compilers to achieve the same allocator guarantees as
871 `std::allocator_traits`.
873 In [Boost.Container] containers, if possible, a single allocator is hold to construct
874 `value_type`s. If the container needs an auxiliary
875 allocator (e.g. an array allocator used by `deque` or `stable_vector`), that allocator is also
876 stored in the container and initialized from the user-supplied allocator when the
877 container is constructed (i.e. it's not constructed on the fly when auxiliary memory is needed).
881 [section:scoped_allocator Scoped allocators]
883 C++11 improves stateful allocators with the introduction of
884 [@http://en.cppreference.com/w/cpp/memory/scoped_allocator_adaptor `std::scoped_allocator_adaptor`]
885 class template. `scoped_allocator_adaptor` is instantiated with one outer allocator and zero or more inner
888 A scoped allocator is a mechanism to automatically propagate the state of the allocator to the subobjects
889 of a container in a controlled way. If instantiated with only one allocator type, the inner allocator
890 becomes the `scoped_allocator_adaptor` itself, thus using the same allocator
891 resource for the container and every element within the container and, if the elements themselves are
892 containers, each of their elements recursively. If instantiated with more than one allocator, the first allocator
893 is the outer allocator for use by the container, the second allocator is passed to the constructors of the
894 container's elements, and, if the elements themselves are containers, the third allocator is passed to the
895 elements' elements, and so on.
897 [*Boost.Container] implements its own [classref boost::container::scoped_allocator_adaptor scoped_allocator_adaptor]
898 class and [*backports this feature also
899 to C++03 compilers]. Due to C++03 limitations, in those compilers
900 the allocator propagation implemented by `scoped_allocator_adaptor::construct` functions
901 will be based on traits ([classref boost::container::constructible_with_allocator_suffix constructible_with_allocator_suffix]
902 and [classref boost::container::constructible_with_allocator_prefix constructible_with_allocator_prefix])
903 proposed in [@http://www.open-std.org/jtc1/sc22/WG21/docs/papers/2008/n2554.pdf
904 N2554: The Scoped Allocator Model (Rev 2) proposal]. In conforming C++11 compilers or compilers supporting SFINAE
905 expressions (when `BOOST_NO_SFINAE_EXPR` is NOT defined), traits are ignored and C++11 rules
906 (`is_constructible<T, Args..., inner_allocator_type>::value` and
907 `is_constructible<T, allocator_arg_t, inner_allocator_type, Args...>::value`)
908 will be used to detect if the allocator must be propagated with suffix or prefix allocator arguments.
912 [section:insertion_hints Insertion hints in associative containers and preserving
913 insertion ordering for elements with equivalent keys]
915 [@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#233 LWG Issue #233] corrected a defect
916 in C++98 and specified how equivalent keys were to be inserted in associative containers. [*Boost.Container]
917 implements the C++11 changes that were specified in [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html N1780
918 ['Comments on LWG issue 233: Insertion hints in associative containers]]:
920 * `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.
921 * `a_eq.insert(p,t)`: t is inserted as close as possible to the position just prior to p.
925 [section:initializer_lists Initializer lists]
927 [*Boost.Container] supports initialization, assignments and insertions from initializer lists
928 in compilers that implement this feature.
932 [section:null_iterators Null Forward Iterators]
934 [*Boost.Container] implements
935 [@http://www.open-std.org/JTC1/sc22/WG21/docs/papers/2013/n3644.pdf C++14 Null Forward Iterators],
936 which means that value-initialized iterators may be compared and compare equal
937 to other value-initialized iterators of the same type. Value initialized iterators behave as if they refer
938 past the end of the same empty sequence (example taken from N3644):
942 vector<int> v = { ... };
943 auto ni = vector<int>::iterator();
944 auto nd = vector<double>::iterator();
947 v.begin() == ni; // ??? (likely false in practice).
948 v.end() == ni; // ??? (likely false in practice).
949 ni == nd; // Won't compile.
953 [section:polymorphic_memory_resources Polymorphic Memory Resources ]
956 [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4480.html C++ Extensions for Library Fundamentals (final draft)]
957 includes classes that provide allocator type erasure and runtime polymorphism. As Pablo Halpern, the author of the proposal,
958 explains in the paper ([@https://isocpp.org/files/papers/N3916.pdf N3916 Polymorphic Memory Resources (r2)]):
960 ["['A significant impediment to effective memory management in C++ has been the
961 inability to use allocators in non-generic contexts. In large software systems,
962 most of the application program consists of non-generic procedural or
963 object-oriented code that is compiled once and linked many times.]]
965 ["['Allocators in C++, however, have historically relied solely on
966 compile-time polymorphism, and therefore have not been suitable for use in vocabulary
967 types, which are passed through interfaces between separately-compiled modules,
968 because the allocator type necessarily affects the type of the object that uses it.
969 This proposal builds upon the improvements made to allocators in
970 C++11 and describes a set of facilities for runtime polymorphic memory
971 resources that interoperate with the existing compile-time polymorphic
974 Most utilities from the Fundamentals TS were merged into C++17, but
975 [*Boost.Container] offers them for C++03, C++11 and C++14 compilers.
977 [*Boost.Container] implements nearly all classes of the proposal under
978 the namespace `boost::container::pmr`. There are two groups,
980 * Header only utilities (these don't require the separately compiled library):
981 * [classref boost::container::pmr::memory_resource memory_resource].
982 * [classref boost::container::pmr::resource_adaptor resource_adaptor].
984 * Utilities that require the the separately compiled library:
985 * [classref boost::container::pmr::polymorphic_allocator polymorphic_allocator].
986 * [classref boost::container::pmr::monotonic_buffer_resource monotonic_buffer_resource].
987 * [classref boost::container::pmr::unsynchronized_pool_resource unsynchronized_pool_resource].
988 * [classref boost::container::pmr::synchronized_pool_resource synchronized_pool_resource].
989 * Global resource functions: [funcref boost::container::pmr::get_default_resource get_default_resource]/
990 [funcref boost::container::pmr::set_default_resource set_default_resource]/
991 [funcref boost::container::pmr::new_delete_resource new_delete_resource]/
992 [funcref boost::container::pmr::null_memory_resource null_memory_resource]
993 * Aliases for boost containers using the polymorphic allocator
994 (like [classref boost::container::pmr::vector pmr::vector], etc.)
996 [*Boost.Container]'s polymorphic resource library is usable from C++03 containers,
997 and offers some alternative utilities if the required C++11 features of the
998 ['Library Fundamentals] specification are not available.
1000 [import ../example/doc_pmr.cpp]
1002 Let's review the usage example given in
1003 [@https://isocpp.org/files/papers/N3916.pdf N3916] and see how it can be implemented
1004 using [*Boost.Container]: ['Suppose we are processing a series of shopping lists, where a shopping list is a
1005 container of strings, and storing them in a collection (a list) of shopping lists.
1006 Each shopping list being processed uses a bounded amount of memory that is needed for
1007 a short period of time, while the collection of shopping lists uses an unbounded
1008 amount of memory and will exist for a longer period of time. For efficiency, we can
1009 use a more time-efficient memory allocator based on a finite buffer for the temporary
1012 Let's see how `ShoppingList` can be defined to support an polymorphic memory resource
1013 that can allocate memory from different underlying mechanisms. The most important
1016 * It should declare that supports an allocator defining an `allocator_type` typedef.
1017 This `allocator_type` will be of type [classref boost::container::pmr::memory_resource memory_resource *],
1018 which is a base class for polymorphic resources.
1019 * It must define constructors that take the
1020 the allocator as argument. It can be implemented in two ways:
1021 * `ShoppingList` has constructors taking
1022 [classref boost::container::pmr::memory_resource memory_resource*] as the last argument.
1023 * `ShoppingList` has constructors taking
1024 [classref boost::container::allocator_arg_t allocator_arg_t] as the first argument
1025 and [classref boost::container::pmr::memory_resource memory_resource*] as the second argument.
1027 [*Note:] ['In C++03 compilers, it is required that the programmer specializes as `true`
1028 [classref boost::container::constructible_with_allocator_suffix constructible_with_allocator_suffix] or
1029 [classref boost::container::constructible_with_allocator_prefix constructible_with_allocator_prefix]
1030 as in C++03 there is no way to automatically detect the chosen option at compile time. If
1031 no specialization is done, [*Boost.Container] assumes the suffix option].
1033 [doc_pmr_ShoppingList_hpp]
1035 ['However, this time-efficient allocator is not appropriate for the longer
1036 lived collection of shopping lists. This example shows how those temporary shopping
1037 lists, using a time-efficient allocator, can be used to populate the long lived collection
1038 of shopping lists, using a general purpose allocator, something that would be
1039 annoyingly difficult without the polymorphic allocators.]
1041 In [*Boost.Container] for the time-efficient allocation we can use
1042 [classref boost::container::pmr::monotonic_buffer_resource monotonic_buffer_resource],
1043 providing an external buffer that will be used until it's exhausted. In the default
1044 configuration, when the buffer is exhausted, the default memory resource will be used
1049 ['Notice that the shopping lists within `folder` use the default allocator resource
1050 whereas the shopping list `temporaryShoppingList` uses the short-lived but very fast
1051 `buf_rsrc`. Despite using different allocators, you can insert
1052 `temporaryShoppingList` into folder because they have the same `ShoppingList`
1053 type. Also, while `ShoppingList` uses memory_resource directly,
1054 [classref boost::container::pmr::list pmr::list],
1055 [classref boost::container::pmr::vector pmr::vector]
1056 and [classref boost::container::pmr::string pmr::string] all use
1057 [classref boost::container::pmr::polymorphic_allocator polymorphic_allocator].]
1059 ['The resource passed to the `ShoppingList` constructor is propagated to the vector and
1060 each string within that `ShoppingList`. Similarly, the resource used to construct
1061 `folder` is propagated to the constructors of the ShoppingLists that are inserted into
1062 the list (and to the strings within those `ShoppingLists`). The
1063 [classref boost::container::pmr::polymorphic_allocator polymorphic_allocator]
1064 template is designed to be almost interchangeable with a pointer to
1065 [classref boost::container::pmr::memory_resource memory_resource],
1066 thus producing a ['bridge] between the template-policy
1067 style of allocator and the polymorphic-base-class style of allocator.]
1069 This example actually shows how easy is to use [*Boost.Container] to write
1070 type-erasured allocator-capable classes even in C++03 compilers.
1075 [section:forward_list `forward_list<T>`]
1077 [*Boost.Container] does not offer C++11 `forward_list` container yet, but it will be available in future
1082 [section:vector_exception_guarantees `vector` vs. `std::vector` exception guarantees]
1084 [classref boost::container::vector vector] does not support the strong exception guarantees
1085 given by `std::vector` in functions like `insert`, `push_back`, `emplace`, `emplace_back`,
1086 `resize`, `reserve` or `shrink_to_fit` for either copyable or no-throw moveable classes.
1087 In C++11 [@http://en.cppreference.com/w/cpp/utility/move_if_noexcept move_if_noexcept] is used
1088 to maintain C++03 exception safety guarantees combined with C++11 move semantics.
1089 This strong exception guarantee degrades the insertion performance of copyable and throwing-moveable types,
1090 degrading moves to copies when such types are inserted in the vector using the aforementioned
1093 This strong exception guarantee also precludes the possibility of using some type of
1094 in-place reallocations that can further improve the insertion performance of `vector` See
1095 [link container.extended_allocators Extended Allocators] to know more
1096 about these optimizations.
1098 [classref boost::container::vector vector] always uses move constructors/assignments
1099 to rearrange elements in the vector and uses memory expansion mechanisms if the allocator supports them,
1100 while offering only basic safety guarantees. It trades off exception guarantees for an improved performance.
1104 [section:container_const_reference_parameters Parameter taken by const reference that can be changed]
1106 Several container operations use a parameter taken by const reference that can be changed during execution of the function.
1107 [@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#526 LWG Issue 526
1108 (['Is it undefined if a function in the standard changes in parameters?])]
1113 //Given std::vector<int> v
1114 v.insert(v.begin(), v[2]);
1115 //v[2] can be changed by moving elements of vector
1117 //Given std::list<int> l:
1118 l.remove(*l.begin())
1119 //The operation could delete the first element, and then continue trying to access it.
1121 The adopted resolution, NAD (Not A Defect), implies that previous operations must be well-defined. This requires code
1122 to detect a reference to an inserted element and an additional copy in that case, impacting performance even when
1123 references to already inserted objects are not used. Note that equivalent functions taking rvalue references or
1124 iterator ranges require elements not already inserted in the container.
1126 [*Boost.Container] prioritizes performance and has not implemented the NAD resolution:
1127 in functions that might modify the argument, the library requires references to elements not stored
1128 in the container. Using references to inserted elements yields to undefined behaviour (although in debug mode, this
1129 precondition violation could be notified via BOOST_ASSERT).
1133 [section:Vector_bool `vector<bool>` specialization]
1135 `vector<bool>` specialization has been quite problematic, and there have been several
1136 unsuccessful tries to deprecate or remove it from the standard. [*Boost.Container] does not implement it
1137 as there is a superior [@http://www.boost.org/libs/dynamic_bitset/ Boost.DynamicBitset]
1138 solution. For issues with `vector<bool>` see the following papers:
1140 * [@http://howardhinnant.github.io/onvectorbool.html On `vector<bool>`]
1141 * [@http://www.gotw.ca/publications/N1211.pdf vector<bool>: N1211: More Problems, Better Solutions],
1142 * [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2160.html N2160: Library Issue 96: Fixing vector<bool>],
1143 * [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2204.html N2204 A Specification to deprecate vector<bool>].
1147 * ["['But it is a shame that the C++ committee gave this excellent data structure the name vector<bool> and
1148 that it gives no guidance nor encouragement on the critical generic algorithms that need to be optimized for this
1149 data structure. Consequently, few std::lib implementations go to this trouble.]]
1151 * ["['In 1998, admitting that the committee made a mistake was controversial.
1152 Since then Java has had to deprecate such significant portions of their libraries
1153 that the idea C++ would be ridiculed for deprecating a single minor template specialization seems quaint.]]
1155 * ["['`vector<bool>` is not a container and `vector<bool>::iterator` is not a random-access iterator
1156 (or even a forward or bidirectional iterator either, for that matter). This has already broken user code
1157 in the field in mysterious ways.]]
1159 * ["['`vector<bool>` forces a specific (and potentially bad) optimization choice on all users by enshrining
1160 it in the standard. The optimization is premature; different users have different requirements. This too
1161 has already hurt users who have been forced to implement workarounds to disable the 'optimization'
1162 (e.g., by using a vector<char> and manually casting to/from bool).]]
1164 So `boost::container::vector<bool>::iterator` returns real `bool` references and works as a fully compliant container.
1165 If you need a memory optimized version of `boost::container::vector<bool>`, please use
1166 [@http://www.boost.org/libs/dynamic_bitset/ Boost.DynamicBitset].
1170 [section:non_standard_memset_initialization Non-standard value initialization using `std::memset`]
1172 [*Boost.Container] uses `std::memset` with a zero value to initialize some types as in most platforms this
1173 initialization yields to the desired value initialization with improved performance.
1175 Following the C11 standard, [*Boost.Container] assumes that ['for any integer type,
1176 the object representation where all the bits are zero shall be a representation of the value
1177 zero in that type]. Since `_Bool`/`wchar_t`/`char16_t`/`char32_t` are also integer types in C, it considers
1178 all C++ integral types as initializable via `std::memset`.
1180 By default, [*Boost.Container] also considers floating point types to be initializable using `std::memset`.
1181 Most platforms are compatible with this initialization, but in case this initialization is not desirable the
1182 user can `#define BOOST_CONTAINER_MEMZEROED_FLOATING_POINT_IS_NOT_ZERO` before including library headers.
1184 By default, it also considers pointer types (pointer and pointer to function types, excluding
1185 member object and member function pointers) to be initializable using `std::memset`.
1186 Most platforms are compatible with this initialization, but in case this initialization is not desired the
1187 user can `#define BOOST_CONTAINER_MEMZEROED_POINTER_IS_NOT_ZERO` before including library headers.
1189 If neither `BOOST_CONTAINER_MEMZEROED_FLOATING_POINT_IS_NOT_ZERO` nor
1190 `BOOST_CONTAINER_MEMZEROED_POINTER_IS_NOT_ZERO` is defined [*Boost.Container] also considers POD
1191 types to be value initializable via `std::memset` with value zero.
1197 [section:known_issues Known Issues]
1199 [section:move_emulation_limitations Move emulation limitations in C++03 compilers]
1201 [*Boost.Container] uses [*Boost.Move] to implement move semantics both in C++03 and C++11 compilers.
1202 However, as explained in
1203 [@http://www.boost.org/doc/libs/release/doc/html/move/emulation_limitations.html Emulation limitations],
1204 there are some limitations in C++03 compilers that might surprise [*Boost.Container] users.
1206 The most noticeable problem is when [*Boost.Container] containers are placed in a struct with a
1207 compiler-generated assignment operator:
1213 boost::container::vector<MyType> vect;
1216 void func(const holder& h)
1218 holder copy_h(h); //<--- ERROR: can't convert 'const holder&' to 'holder&'
1219 //Compiler-generated copy constructor is non-const:
1220 // holder& operator(holder &)
1224 This limitation forces the user to define a const version of the copy assignment, in all classes
1225 holding containers, which might be annoying in some cases.
1231 [section:history_and_reasons History and reasons to use Boost.Container]
1233 [section:boost_container_history Boost.Container history]
1235 [*Boost.Container] is a product of a long development effort that started
1236 [@http://lists.boost.org/Archives/boost/2004/11/76263.php in 2004 with the experimental Shmem library],
1237 which pioneered the use of standard containers in shared memory. Shmem included modified SGI STL container
1238 code tweaked to support non-raw `allocator::pointer` types and stateful allocators. Once reviewed,
1239 Shmem was accepted as [@http://www.boost.org/libs/interprocess/ Boost.Interprocess] and this library
1240 continued to refine and improve those containers.
1242 In 2007, container code from node containers (`map`, `list`, `slist`) was rewritten, refactored
1243 and expanded to build the intrusive container library [@http://www.boost.org/libs/intrusive/ Boost.Intrusive].
1244 [*Boost.Interprocess] containers were refactored to take advantage of [*Boost.Intrusive] containers and
1245 code duplication was minimized. Both libraries continued to gain support and bug fixes for years.
1246 They introduced move semantics, emplacement insertion and more features of then unreleased C++0x
1249 [*Boost.Interprocess] containers were always standard compliant, and those containers and new
1250 containers like `stable_vector` and `flat_[multi]set/map` were used outside [*Boost.Interprocess]
1251 with success. As containers were mature enough to get their own library, it was a natural step to
1252 collect them containers and build [*Boost.Container], a library targeted to a wider audience.
1257 [section:Why_boost_container Why Boost.Container?]
1259 With so many high quality standard library implementations out there, why would you want to
1260 use [*Boost.Container]? There are several reasons for that:
1262 * Even if you have a earlier standard conforming compiler, you still can have access to many
1263 of the latest C++ standard features and have an easy code migration when you change your compiler.
1264 * It's compatible with [*Boost.Interprocess] shared memory allocators.
1265 * You have extremely useful new containers like `[stable/static/small]_vector` and `flat_[multi]set/map`.
1266 * If you work on multiple platforms, you'll have a portable behaviour without depending
1267 on the std-lib implementation conformance of each platform. Some examples:
1268 * Default constructors don't allocate memory at all, which improves performance and
1269 usually implies a no-throw guarantee (if predicate's or allocator's default constructor doesn't throw).
1270 * Small string optimization for [classref boost::container::basic_string basic_string].
1271 * [link container.extended_functionality Extended functionality] beyond the standard based
1272 on user feedback to improve code performance.
1273 * You need a portable implementation that works when compiling without exceptions support or
1274 you need to customize the error handling when a container needs to signal an exceptional error.
1280 [include auto_index_helpers.qbk]
1282 [section:index Indexes]
1284 [named_index class_name Class Index]
1285 [named_index typedef_name Typedef Index]
1286 [named_index function_name Function Index]
1287 [/named_index macro_name Macro Index]
1292 [xinclude autodoc.xml]
1294 [section:acknowledgements_notes Acknowledgements, notes and links]
1296 * Original standard container code comes from [@http://www.sgi.com/tech/stl/ SGI STL library],
1297 which enhanced the original HP STL code. Code was rewritten for
1298 [*Boost.Interprocess] and moved to [*Boost.Intrusive]. Many thanks to Alexander Stepanov, Meng Lee, David Musser,
1299 Matt Austern... and all HP and SGI STL developers.
1301 * `flat_[multi]_map/set` containers were originally based on [@http://en.wikipedia.org/wiki/Loki_%28C%2B%2B%29 Loki's]
1302 AssocVector class. Code was rewritten and expanded for [*Boost.Interprocess], so thanks to Andrei Alexandrescu.
1304 * `stable_vector` was invented and coded by
1305 [@http://bannalia.blogspot.com/2008/09/introducing-stablevector.html Joaqu\u00EDn M. L\u00F3pez Mu\u00F1oz],
1306 then adapted for [*Boost.Interprocess]. Thanks for such a great container.
1308 * `static_vector` was based on Andrew Hundt's and Adam Wulkiewicz's high-performance `varray` class.
1309 Many performance improvements of `vector` were also inspired by their implementation. Thanks!
1311 * Howard Hinnant's help and advices were essential when implementing move semantics,
1312 improving allocator support or implementing small string optimization. Thanks Howard
1313 for your wonderful standard library implementations.
1315 * And finally thanks to all Boosters who helped all these years, improving, fixing and
1316 reviewing all my libraries.
1320 [section:release_notes Release Notes]
1322 [section:release_notes_boost_1_72_00 Boost 1.72 Release]
1325 * [@https://github.com/boostorg/container/issues/127 GitHub #127: ['"Fix docs for static_vector::max_size() and capacity()"]].
1326 * [@https://github.com/boostorg/container/issues/132 GitHub #132: ['"flat_map::lower_bound and upper_bound have wrong/misleading docs"]].
1327 * [@https://github.com/boostorg/container/issues/133 GitHub #133: ['"basic_string move constructor with allocator argument has incorrect allocator check"]].
1331 [section:release_notes_boost_1_71_00 Boost 1.71 Release]
1334 * [@https://github.com/boostorg/container/pull/47 GitHub #47: ['"added alignment specification for small_vector"]].
1335 * [@https://github.com/boostorg/container/issues/88 GitHub #88: ['"Implement C++17 MoveAssignable requirements for self-move assignments"]].
1336 * [@https://github.com/boostorg/container/issues/107 GitHub #107: ['"Alignment ignored in resource_adaptor"]].
1337 * [@https://github.com/boostorg/container/pull/109 GitHub #109: ['"Get rid of integer overflow in copy_move_algo.hpp (-fsanitize=integer)"]].
1338 * [@https://github.com/boostorg/container/pull/110 GitHub #110: ['"Avoid gcc 9 deprecated copy warnings in new_allocator.hpp"]].
1339 * [@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"]].
1340 * [@https://github.com/boostorg/container/issues/114 GitHub #114: ['"Fix small_vector noexcept specification"]].
1341 * [@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)"]].
1342 * [@https://github.com/boostorg/container/issues/117 GitHub #117: ['"flat_map/map::insert_or_assign with hint has wrong return types"]].
1343 * [@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"]].
1344 * [@https://github.com/boostorg/container/issues/122 GitHub #122: ['"Fix has_trivial_destructor_after_move"]].
1345 * [@https://github.com/boostorg/container/issues/123 GitHub #123: ['"With heterogeneous lookup, `equal_range` can result in a range with length greater than 1"]].
1347 * [classref boost::container::deque deque] can now have options, using [classref boost::container::deque_options deque_options].
1348 The block size/bytes can be be specified.
1350 * [classref boost::container::static_vector static_vector] can now have options, using [classref boost::container::static_vector_options static_vector_options].
1351 Alignment and throwing behaviour can be be specified.
1353 * [classref boost::container::small_vector small_vector] can now have options, using [classref boost::container::small_vector_options small_vector_options].
1354 Alignment and growth factor can be be specified.
1358 [section:release_notes_boost_1_70_00 Boost 1.70 Release]
1360 * Removed support for already deprecated GCC < 4.3 and MSVC < 9.0 (Visual 2008) compilers.
1361 * Default allocator parameter changed form `new_allocator<T>` to `void` to reduce symbol lenghts.
1363 * [@https://github.com/boostorg/container/pull/96 GitHub #96: ['"Workaround: Intel compilers do not offer CTAD yet"]].
1364 * [@https://github.com/boostorg/container/issues/97 GitHub #97: ['"buffer overflow in boost::container::flat_map on FreeBSD"]].
1365 * [@https://github.com/boostorg/container/issues/98 GitHub #98: ['"flat_map: insert_or_assign does not work with hint"]].
1366 * [@https://github.com/boostorg/container/issues/100 GitHub #100: ['"Compile error on Green Hills: container_detail::flat_tree has no member insert"]].
1367 * [@https://github.com/boostorg/container/pull/103 GitHub #103: ['"Fix deallocating never-allocated storage in vector.merge()"]].
1368 * [@https://github.com/boostorg/container/pull/104 GitHub #104: ['"Fix -Wmissing-noreturn clang warnings"]].
1369 * [@https://github.com/boostorg/container/pull/105 GitHub #105: ['"Fix gcc -Wdeprecated-copy"]].
1370 * [@https://github.com/boostorg/container/issues/111 GitHub #111: ['"container::vector of interprocess::offset_ptrs to variants holding incomplete type"]].
1374 [section:release_notes_boost_1_69_00 Boost 1.69 Release]
1376 * Deprecated GCC < 4.3 and MSVC < 9.0 (Visual 2008) compilers.
1378 * Implemented C++20 `contains()` for associative containers as specified in
1379 [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0458r2.html
1380 P0458R2: Checking for Existence of an Element in Associative Containers].
1382 * Fixed serious bug in heterogeneous lookup functions (is_transparent was broken).
1385 * [@https://github.com/boostorg/container/issues/77 GitHub #77: ['"warning: 'sbrk' is deprecated"]].
1386 * [@https://github.com/boostorg/container/issues/79 GitHub #79: ['"Mark small_vector move operations noexcept"]].
1387 * [@https://github.com/boostorg/container/issues/80 GitHub #80: ['"flat_map deduction guides are ambiguous"]].
1388 * [@https://github.com/boostorg/container/issues/81 GitHub #81: ['"Vector with custom allocator does not support value types with operator&"]].
1389 * [@https://github.com/boostorg/container/issues/82 GitHub #82: ['"Function definition in header file"]].
1390 * [@https://github.com/boostorg/container/issues/83 GitHub #83: ['"Iterator zero incrementing leads to assert on empty vector"]].
1391 * [@https://github.com/boostorg/container/pull/84 GitHub #84: ['"Allow vector to be assigned to itself"]].
1392 * [@https://github.com/boostorg/container/pull/85 GitHub #85: ['"container: misc-typos"]].
1393 * [@https://github.com/boostorg/container/pull/86 GitHub #86: ['"Add missing warning re-enabling include"]].
1394 * [@https://github.com/boostorg/container/issues/89 GitHub #89: ['"UBSAN failures detected in preflight CI PR"]].
1395 * [@https://github.com/boostorg/container/issues/90 GitHub #90: ['"Build fails on clang-5 with libstdc++7-dev (C++17 issue)"]].
1396 * [@https://github.com/boostorg/container/issues/93 GitHub #93: ['"vector::erase memory leak"]].
1400 [section:release_notes_boost_1_68_00 Boost 1.68 Release]
1402 * Improved correctness of [classref boost::container::adaptive_pool adaptive_pool] and many parameters are now compile-time
1403 constants instead of runtime constants.
1405 * Implemented C++14's heterogeneous lookup functions for `[multi]map/[multi]set/flat_[multi]map/flat_[multi]set`.
1407 * Added [@https://github.com/boostorg/container/pull/71 GitHub #71: ['"Constructor Template Auto Deduction guides "]].
1410 * [@https://svn.boost.org/trac/boost/ticket/13533 Trac #13533: ['"Boost vector resize causes assert(false)"]].
1411 * [@https://github.com/boostorg/container/issues/73 GitHub #73: ['"triviality of pair"]].
1412 * [@https://github.com/boostorg/container/issues/74 GitHub #74: ['"vector assignment not using memcpy"]].
1413 * [@https://github.com/boostorg/container/issues/75 GitHub #75: ['"flat_set: Heap overflow"]].
1414 * [@https://github.com/boostorg/container/issues/76 GitHub #76: ['"flat_set: undefined behaviour on empty range"]].
1415 * Fixed race condition bug in [classref boost::container::pmr::unsynchronized_pool_resource unsynchronized_pool_resource]
1416 found by Arthur O'Dowyer in his blog post
1417 [@https://quuxplusone.github.io/blog/2018/06/05/libcpp-memory-resource/ <memory_resource> for libc++]
1419 * Implemented proposed resolution for
1420 [@https://cplusplus.github.io/LWG/issue3120 ['"LWG 3120 Unclear behavior of monotonic_buffer_resource::release()"]].
1421 After `release()` the original buffer is recovered for the next allocation.
1425 [section:release_notes_boost_1_67_00 Boost 1.67 Release]
1427 * ['vector] can now have options, using [classref boost::container::vector_options vector_options].
1428 The growth factor and the stored size type can be specified.
1430 * Improved range insertion in ['flat_[multi]map/set] containers overall complexity is reduced to O(NlogN).
1433 * [@https://github.com/boostorg/container/pull/61 GitHub #61: ['"Compile problems on Android ndk r16 beta 1"]].
1434 * [@https://github.com/boostorg/container/pull/64 GitHub #64: ['"Fix splice for slist"]].
1435 * [@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"]].
1436 * [@https://svn.boost.org/trac/boost/ticket/13500 Trac #13500: ['"Memory leak when using erase on string vectors"]].
1440 [section:release_notes_boost_1_66_00 Boost 1.66 Release]
1442 * ['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].
1443 The allocator argument is checked for ['size()] and ['empty()] members. If so, the argument is interpreted as the required underlying container.
1444 This means that ['static_vector], ['stable_vector] and ['small_vector] can be used now with flat associative containers.
1447 * [@https://github.com/boostorg/container/pull/54 GitHub #54: ['"no sbrk() in VxWorks, configure dlmalloc to use only mmap"]].
1448 * [@https://github.com/boostorg/container/issues/58 GitHub #58: ['"Comparing strings does not compile in gcc 7+ in C++17 mode"]].
1449 * [@https://github.com/boostorg/container/issues/59 GitHub #59: ['"basic_string::npos is missing its definition"]].
1453 [section:release_notes_boost_1_65_00 Boost 1.65 Release]
1455 * Implemented `extract_sequence`, `adopt_sequence` functions for flat_[multi]map/set associative containers.
1458 * [@https://github.com/boostorg/container/pull/48 GitHub #48: ['"Replace deprecated/removed C++98 binders"]].
1459 * [@https://github.com/boostorg/container/pull/49 GitHub #49: ['"Remove useless allocator copy in map"]].
1460 * [@https://github.com/boostorg/container/pull/50 GitHub #50: ['"Fixed bug Trac #13038"]].
1461 * [@https://github.com/boostorg/container/pull/51 GitHub #51: ['"Fix integer rollover that triggers clang ubsan when U is unsigned"]].
1465 [section:release_notes_boost_1_64_00 Boost 1.64 Release]
1468 * [@https://svn.boost.org/trac/boost/ticket/11333 Trac #11333: ['"boost::basic_string_ref should interop with boost::container::basic_string"]].
1469 * [@https://svn.boost.org/trac/boost/ticket/12749 Trac #12749: ['"container::pmr::polymorphic_allocator compilation error"]].
1470 * [@https://svn.boost.org/trac/boost/ticket/12915 Trac #12915: ['"Buffer overflow in boost::container::vector (affects flat_set)"]].
1471 * [@https://github.com/boostorg/container/pull/45 GitHub #45: ['"emplace_back must return reference to back(), not to *end()"]].
1472 * [@https://github.com/boostorg/container/pull/46 GitHub #46: ['"Fix use of propagate_on_container_swap"]].
1476 [section:release_notes_boost_1_63_00 Boost 1.63 Release]
1479 * [@https://svn.boost.org/trac/boost/ticket/12534 Trac #12534: ['"flat_map fails to compile if included after type_traits is instantiated under gcc"]].
1480 * [@https://svn.boost.org/trac/boost/ticket/12577 Trac #12577: ['"Null reference in pair.hpp triggers runtime warning with -fsanitize=undefined"]].
1481 * [@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]].
1482 * [@https://github.com/boostorg/container/pull/41 GitHub #41: ['Avoid -Wunreachable-code in do_allocate()]].
1486 [section:release_notes_boost_1_62_00 Boost 1.62 Release]
1489 * [@https://svn.boost.org/trac/boost/ticket/9481 Trac #9481: ['"Minor comment typo in Boost.Container"]].
1490 * [@https://svn.boost.org/trac/boost/ticket/9689 Trac #9689: ['"Add piecewise_construct to boost::container"]].
1491 * [@https://svn.boost.org/trac/boost/ticket/11170 Trac #11170: ['"Doc slip for index_of"]].
1492 * [@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"]].
1493 * [@https://svn.boost.org/trac/boost/ticket/12117 Trac #12117: ['"flat_set constructor with ordered_unique_range"]].
1494 * [@https://svn.boost.org/trac/boost/ticket/12177 Trac #12177: ['"vector::priv_merge uses unqualified uintptr_t"]].
1495 * [@https://svn.boost.org/trac/boost/ticket/12183 Trac #12183: ['"GCC 6.1 thinks boost::container::string violates strict aliasing"]].
1496 * [@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"]].
1497 * [@https://svn.boost.org/trac/boost/ticket/12273 Trac #12273: ['"static_vector max_size() and capacity() should be constant expressions"]].
1498 Added constant `static_vector<>::static_capacity` to use the configured capacity in constant expressions.
1499 * [@https://svn.boost.org/trac/boost/ticket/12286 Trac #12286: ['"PMR flat_map from Boost Container does not compile"]].
1500 * [@https://svn.boost.org/trac/boost/ticket/12296 Trac #12296: ['"{deque,string} combine for a memory leak"]].
1501 * [@https://svn.boost.org/trac/boost/ticket/12319 Trac #12319: ['"flat_set` should be nothrow move constructible"]].
1503 * Revised noexcept expressions of default and move constructors in all containers.
1504 * Implemented C++17's `insert_or_assign`/`try_emplace` for [classref boost::container::map map] and [classref boost::container::flat_map flat_map].
1505 * Implemented C++17's [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0083r3.pdf ['Splicing Maps and Sets (Revision 5)]]
1506 for [classref boost::container::map map], [classref boost::container::multimap multimap],
1507 [classref boost::container::set set], [classref boost::container::multiset multiset].
1508 * Implemented C++17's [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0084r2.pdf ['P0084R2 Emplace Return Type]]
1509 in `deque`, `vector`, `stable_vector`, `small_vector`, `static_vector`, `list` and `slist`.
1513 [section:release_notes_boost_1_61_00 Boost 1.61 Release]
1515 * [classref boost::container::small_vector] supports more constructors and assignments.
1517 * [@https://svn.boost.org/trac/boost/ticket/11820 Trac #11820: ['"compiler error when using operator[] of map"]].
1518 * [@https://svn.boost.org/trac/boost/ticket/11856 Trac #11856: ['"pool_resource.cpp error: declaration changes meaning"]].
1519 * [@https://svn.boost.org/trac/boost/ticket/11866 Trac #11866: ['"small_vector does not have range constructor"]].
1520 * [@https://svn.boost.org/trac/boost/ticket/11867 Trac #11867: ['"small_vector should have constructor and assignment operator taking other small_vector"]].
1521 * [@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"]].
1522 * [@https://svn.boost.org/trac/boost/ticket/11957 Trac #11957: ['"static_vector::max_size() is higher than the capacity"]].
1523 * [@https://svn.boost.org/trac/boost/ticket/12014 Trac #12014: ['"boost::container::set can not insert const (ref) range"]].
1524 * [@https://github.com/boostorg/container/pull/33 GitHub #33: ['Make sure std::string constructor is available]].
1528 [section:release_notes_boost_1_60_00 Boost 1.60 Release]
1530 * Implemented [link container.cpp_conformance.polymorphic_memory_resources Polymorphic Memory Resources].
1531 * Add more BOOST_ASSERT checks to test preconditions in some operations (like `pop_back`, `pop_front`, `back`, `front`, etc.)
1532 * Added C++11 `back`/`front` operations to [classref boost::container::basic_string basic_string].
1534 * [@https://svn.boost.org/trac/boost/ticket/11627 Trac #11627: ['"small_vector<T,n>::swap() appears to be broken"]].
1535 * [@https://svn.boost.org/trac/boost/ticket/11628 Trac #11628: ['"small_vector<int,n> iterates over elements in destructor"]].
1536 * [@https://svn.boost.org/trac/boost/ticket/11697 Trac #11697: ['"Wrong initialization order in tuple copy-constructor"]].
1537 * [@https://svn.boost.org/trac/boost/ticket/11698 Trac #11698: ['"Missing return statement in static_storage_allocator"]].
1538 * [@https://github.com/boostorg/container/pull/29 GitHub #29: ['Doc fixes for flap_map complexity requirements]].
1539 * [@https://github.com/boostorg/container/pull/31 GitHub #31: ['DL_SIZE_IMPL also dereference addr]].
1543 [section:release_notes_boost_1_59_00 Boost 1.59 Release]
1545 * [@https://github.com/boostorg/container/pull/26 GitHub #26: ['Fix bug in stable_vector::capacity()]]. Thanks to timsong-cpp/Arindam Mukerjee.
1546 * [@https://github.com/boostorg/container/pull/27 GitHub #27: ['fix stable_vector's index_of's doxygen comment]]. Thanks to kariya-mitsuru.
1547 * [@https://svn.boost.org/trac/boost/ticket/11380 Trac #11380: ['"Container library std forward declarations incorrect in std_fwd.hpp on libc++ with gcc"]].
1548 * [@https://svn.boost.org/trac/boost/ticket/11388 Trac #11388: ['"boost::container::list::emplace_back broken on Visual Studio 2010"]].
1549 * [@https://svn.boost.org/trac/boost/ticket/11339 Trac #11339: ['"VC12 LNK2005 error with boost::container::adaptive_pool"]].
1553 [section:release_notes_boost_1_58_00 Boost 1.58 Release]
1554 * Experimental [classref boost::container::small_vector small_vector] container.
1555 * Massive dependency reorganization. Now [*Boost.Container] depends on very basic utilities like Boost.Core
1556 and [*Boost.Intrusive]. Preprocessed code size have decreased considerably and compilation times have improved.
1557 * Added `nth` and `index_of` functions to containers with random-access iterators (except `basic_string`).
1558 * Added C++17's `allocator_traits<Allocator>::is_always_equal`.
1559 * Updated containers to implement new constructors as specified in
1560 [@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2210 2210. Missing allocator-extended constructor for allocator-aware containers].
1562 * [@https://svn.boost.org/trac/boost/ticket/9931 Trac #9931: ['"flat_map::insert(ordered_unique_range_t...) fails with move_iterators"]] (reopened).
1563 * [@https://svn.boost.org/trac/boost/ticket/11076 Trac #11076: ['"Unqualified calls to memmove/memcpy in container/detail/copy_move_algo.hpp"]].
1564 * [@https://svn.boost.org/trac/boost/ticket/10790 Trac #10790 (['"long long errors from container"])].
1565 * [@https://svn.boost.org/trac/boost/ticket/10808 Trac #10808 (['"compare equal operator of vector is broken"])].
1566 * [@https://svn.boost.org/trac/boost/ticket/10930 Trac #10930 (['"container std_fwd.hpp neglects custom std namespaces"])].
1567 * [@https://svn.boost.org/trac/boost/ticket/11139 Trac #11139 (['"boost::container::vector<std::shared_ptr<const T>...>::const_iterator allows changing dereferenced elements"])].
1568 * [*Source Breaking]: [classref boost::container::scoped_allocator_adaptor scoped_allocator_adaptor]'s
1569 `propagate_on_container_copy_assignment`, `propagate_on_container_move_assignment` and `propagate_on_container_swap`
1570 are no longer `::boost::integral_constant<bool, true/false>` types. The dependency reorganization needed to break
1571 with those classes to avoid MPL dependencies, and interoperability with `std::integral_constant` was not guaranteed.
1572 Code assumming `boost::true_type/boost::false_type` on this will not compile. As a workaround, use the guaranteed internal
1573 `::value` constant: `::boost::integral_constant<bool, scoped_allocator_adaptor<Allocator>::propagate_on_container_move_assignment::value>`.
1577 [section:release_notes_boost_1_57_00 Boost 1.57 Release]
1578 * Added support for `initializer_list`. Contributed by Robert Matusewicz.
1579 * Fixed double destruction bugs in vector and backward expansion capable allocators.
1581 * [@https://svn.boost.org/trac/boost/ticket/10263 Trac #10263 (['"AIX 6.1 bug with sched_yield() function out of scope"])].
1582 * [@https://github.com/boostorg/container/pull/16 GitHub #16: ['Fix iterators of incomplete type containers]]. Thanks to Mikael Persson.
1586 [section:release_notes_boost_1_56_00 Boost 1.56 Release]
1588 * Added DlMalloc-based [link container.extended_allocators Extended Allocators].
1590 * [link container.configurable_containers.configurable_tree_based_associative_containers Improved configurability]
1591 of tree-based ordered associative containers. AVL, Scapegoat and Splay trees are now available
1592 to implement [classref boost::container::set set], [classref boost::container::multiset multiset],
1593 [classref boost::container::map map] and [classref boost::container::multimap multimap].
1596 * [@https://svn.boost.org/trac/boost/ticket/9338 #9338: ['"VS2005 compiler errors in swap() definition after including container/memory_util.hpp"]].
1597 * [@https://svn.boost.org/trac/boost/ticket/9637 #9637: ['"Boost.Container vector::resize() performance issue"]].
1598 * [@https://svn.boost.org/trac/boost/ticket/9648 #9648: ['"string construction optimization - char_traits::copy could be used ..."]].
1599 * [@https://svn.boost.org/trac/boost/ticket/9801 #9801: ['"I can no longer create and iterator_range from a stable_vector"]].
1600 * [@https://svn.boost.org/trac/boost/ticket/9915 #9915: ['"Documentation issues regarding vector constructors and resize methods - value/default initialization"]].
1601 * [@https://svn.boost.org/trac/boost/ticket/9916 #9916: ['"Allocator propagation incorrect in the assignment operator of most"]].
1602 * [@https://svn.boost.org/trac/boost/ticket/9931 #9931: ['"flat_map::insert(ordered_unique_range_t...) fails with move_iterators"]].
1603 * [@https://svn.boost.org/trac/boost/ticket/9955 #9955: ['"Using memcpy with overlapped buffers in vector"]].
1607 [section:release_notes_boost_1_55_00 Boost 1.55 Release]
1609 * Implemented [link container.main_features.scary_iterators SCARY iterators].
1611 * Fixed bugs [@https://svn.boost.org/trac/boost/ticket/8269 #8269],
1612 [@https://svn.boost.org/trac/boost/ticket/8473 #8473],
1613 [@https://svn.boost.org/trac/boost/ticket/8892 #8892],
1614 [@https://svn.boost.org/trac/boost/ticket/9009 #9009],
1615 [@https://svn.boost.org/trac/boost/ticket/9064 #9064],
1616 [@https://svn.boost.org/trac/boost/ticket/9092 #9092],
1617 [@https://svn.boost.org/trac/boost/ticket/9108 #9108],
1618 [@https://svn.boost.org/trac/boost/ticket/9166 #9166].
1620 * Added `default initialization` insertion functions to vector-like containers
1621 with new overloads taking `default_init_t` as an argument instead of `const value_type &`.
1625 [section:release_notes_boost_1_54_00 Boost 1.54 Release]
1627 * Added experimental `static_vector` class, based on Andrew Hundt's and Adam Wulkiewicz's
1628 high performance `varray` class.
1629 * Speed improvements in `vector` constructors/copy/move/swap, dispatching to memcpy when possible.
1630 * Support for `BOOST_NO_EXCEPTIONS` [@https://svn.boost.org/trac/boost/ticket/7227 #7227].
1631 * Fixed bugs [@https://svn.boost.org/trac/boost/ticket/7921 #7921],
1632 [@https://svn.boost.org/trac/boost/ticket/7969 #7969],
1633 [@https://svn.boost.org/trac/boost/ticket/8118 #8118],
1634 [@https://svn.boost.org/trac/boost/ticket/8294 #8294],
1635 [@https://svn.boost.org/trac/boost/ticket/8553 #8553],
1636 [@https://svn.boost.org/trac/boost/ticket/8724 #8724].
1640 [section:release_notes_boost_1_53_00 Boost 1.53 Release]
1642 * Fixed bug [@https://svn.boost.org/trac/boost/ticket/7650 #7650].
1643 * Improved `vector`'s insertion performance.
1644 * Changed again experimental multiallocation interface for better performance (still experimental).
1645 * Added no exception support for those willing to disable exceptions in their compilers.
1646 * Fixed GCC -Wshadow warnings.
1647 * Replaced deprecated BOOST_NO_XXXX with newer BOOST_NO_CXX11_XXX macros.
1651 [section:release_notes_boost_1_52_00 Boost 1.52 Release]
1653 * Improved `stable_vector`'s template code bloat and type safety.
1654 * Changed typedefs and reordered functions of sequence containers to improve doxygen documentation.
1656 [@https://svn.boost.org/trac/boost/ticket/6615 #6615],
1657 [@https://svn.boost.org/trac/boost/ticket/7139 #7139],
1658 [@https://svn.boost.org/trac/boost/ticket/7215 #7215],
1659 [@https://svn.boost.org/trac/boost/ticket/7232 #7232],
1660 [@https://svn.boost.org/trac/boost/ticket/7269 #7269],
1661 [@https://svn.boost.org/trac/boost/ticket/7439 #7439].
1662 * Implemented LWG Issue #149 (range insertion now returns an iterator) & cleaned up insertion code in most containers
1663 * Corrected aliasing errors.
1667 [section:release_notes_boost_1_51_00 Boost 1.51 Release]
1670 [@https://svn.boost.org/trac/boost/ticket/6763 #6763],
1671 [@https://svn.boost.org/trac/boost/ticket/6803 #6803],
1672 [@https://svn.boost.org/trac/boost/ticket/7114 #7114],
1673 [@https://svn.boost.org/trac/boost/ticket/7103 #7103].
1674 [@https://svn.boost.org/trac/boost/ticket/7123 #7123],
1678 [section:release_notes_boost_1_50_00 Boost 1.50 Release]
1680 * Added Scoped Allocator Model support.
1683 [@https://svn.boost.org/trac/boost/ticket/6606 #6606],
1684 [@https://svn.boost.org/trac/boost/ticket/6533 #6533],
1685 [@https://svn.boost.org/trac/boost/ticket/6536 #6536],
1686 [@https://svn.boost.org/trac/boost/ticket/6566 #6566],
1687 [@https://svn.boost.org/trac/boost/ticket/6575 #6575],
1692 [section:release_notes_boost_1_49_00 Boost 1.49 Release]
1695 [@https://svn.boost.org/trac/boost/ticket/6540 #6540],
1696 [@https://svn.boost.org/trac/boost/ticket/6499 #6499],
1697 [@https://svn.boost.org/trac/boost/ticket/6336 #6336],
1698 [@https://svn.boost.org/trac/boost/ticket/6335 #6335],
1699 [@https://svn.boost.org/trac/boost/ticket/6287 #6287],
1700 [@https://svn.boost.org/trac/boost/ticket/6205 #6205],
1701 [@https://svn.boost.org/trac/boost/ticket/4383 #4383].
1703 * Added `allocator_traits` support for both C++11 and C++03
1704 compilers through an internal `allocator_traits` clone.
1708 [section:release_notes_boost_1_48_00 Boost 1.48 Release]
1710 * First release. Container code from [*Boost.Interprocess] was deleted
1711 and redirected to [*Boost.Container ] via using directives.