]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | [/ |
2 | / Copyright (c) 2009-2013 Ion Gazta\u00F1aga | |
3 | / | |
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) | |
6 | /] | |
7 | ||
8 | [library Boost.Container | |
9 | [quickbook 1.5] | |
10 | [authors [Gaztanaga, Ion]] | |
11 | [copyright 2009-2015 Ion Gaztanaga] | |
12 | [id container] | |
13 | [dirname container] | |
14 | [purpose Containers library] | |
15 | [license | |
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]) | |
19 | ] | |
20 | ] | |
21 | ||
22 | [template super[x]'''<superscript>'''[x]'''</superscript>'''] | |
23 | [template sub[x]'''<subscript>'''[x]'''</subscript>'''] | |
24 | ||
25 | [section:intro Introduction] | |
26 | ||
27 | [*Boost.Container] library implements several well-known containers, including | |
28 | STL containers. The aim of the library is to offers 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. | |
31 | ||
32 | In short, what does [*Boost.Container] offer? | |
33 | ||
34 | * Move semantics are implemented, including move emulation for pre-C++11 compilers. | |
35 | * New advanced features (e.g. placement insertion, recursive containers) are present. | |
36 | * Containers support stateful allocators and are compatible with [*Boost.Interprocess] | |
37 | (they can be safely placed in shared memory). | |
38 | * The library offers new useful containers: | |
39 | * [classref boost::container::flat_map flat_map], | |
40 | [classref boost::container::flat_set flat_set], | |
41 | [classref boost::container::flat_multimap flat_multimap] and | |
42 | [classref boost::container::flat_multiset flat_multiset]: drop-in | |
43 | replacements for standard associative containers but more memory friendly and with faster | |
44 | searches. | |
45 | * [classref boost::container::stable_vector stable_vector]: a std::list and std::vector hybrid | |
46 | container: vector-like random-access iterators and list-like iterator stability in insertions and erasures. | |
47 | * [classref boost::container::slist slist]: the classic pre-standard singly linked list implementation | |
48 | offering constant-time `size()`. Note that C++11 `forward_list` has no `size()`. | |
49 | ||
50 | [section:introduction_building_container Building Boost.Container] | |
51 | ||
52 | There is no need to compile [*Boost.Container], since it's a header-only library, | |
53 | just include your Boost header directory in your compiler include path *except if you use*: | |
54 | ||
55 | * [link container.extended_functionality.extended_allocators Extended Allocators] | |
56 | * Some [link container.extended_functionality.polymorphic_memory_resources Polymorphic Memory Resources] classes. | |
57 | ||
58 | Those exceptions are are implemented as a separately compiled library, so in those cases you must install binaries | |
59 | in a location that can be found by your linker. | |
60 | If you followed the [@http://www.boost.org/doc/libs/release/more/getting_started/index.html Boost Getting Started] | |
61 | instructions, that's already been done for you. | |
62 | ||
63 | [endsect] | |
64 | ||
65 | [section:tested_compilers Tested compilers] | |
66 | ||
67 | [*Boost.Container] requires a decent C++98 compatibility. Some compilers known to work are: | |
68 | ||
69 | * Visual C++ >= 7.1. | |
70 | * GCC >= 4.1. | |
71 | * Intel C++ >= 9.0 | |
72 | ||
73 | [endsect] | |
74 | ||
75 | [endsect] | |
76 | ||
77 | [section:main_features Main features] | |
78 | ||
79 | [section:move_emplace Efficient insertion] | |
80 | ||
81 | Move semantics and placement insertion are two features brought by C++11 containers | |
82 | that can have a very positive impact in your C++ applications. Boost.Container implements | |
83 | both techniques both for C++11 and C++03 compilers. | |
84 | ||
85 | [section:move_containers Move-aware containers] | |
86 | ||
87 | All containers offered by [*Boost.Container] can store movable-only types | |
88 | and actual requirements for `value_type` depend on each container operations. | |
89 | Following C++11 requirements even for C++03 compilers, many operations now require | |
90 | movable or default constructible types instead of just copy constructible types. | |
91 | ||
92 | Containers themselves are also movable, with no-throw guarantee if allocator | |
93 | or predicate (if present) copy operations are no-throw. This allows | |
94 | high performance operations when transferring data between vectors. | |
95 | Let's see an example: | |
96 | ||
97 | [import ../example/doc_move_containers.cpp] | |
98 | [doc_move_containers] | |
99 | ||
100 | [endsect] | |
101 | ||
102 | [section:emplace Emplace: Placement insertion] | |
103 | ||
104 | All containers offered by [*Boost.Container] implement placement insertion, | |
105 | which means that objects can be built directly into the container from user arguments | |
106 | without creating any temporary object. For compilers without variadic templates support | |
107 | placement insertion is emulated up to a finite (10) number of arguments. | |
108 | ||
109 | Expensive to move types are perfect candidates emplace functions and in case of node containers | |
110 | ([classref boost::container::list list], [classref boost::container::set set], ...) | |
111 | emplace allows storing non-movable and non-copyable types in containers! Let's | |
112 | see an example: | |
113 | ||
114 | [import ../example/doc_emplace.cpp] | |
115 | [doc_emplace] | |
116 | ||
117 | [endsect] | |
118 | ||
119 | [endsect] | |
120 | ||
121 | ||
122 | [section:containers_of_incomplete_types Containers of Incomplete Types] | |
123 | ||
124 | Incomplete types allow | |
125 | [@http://en.wikipedia.org/wiki/Type_erasure [*type erasure ]] and | |
126 | [@http://en.wikipedia.org/wiki/Recursive_data_type [*recursive data types]], and | |
127 | C and C++ programmers have been using it for years to build complex data structures, like | |
128 | tree structures where a node may have an arbitrary number of children. | |
129 | ||
130 | What about standard containers? Containers of incomplete types have been under discussion for a long time, | |
131 | as explained in Matt Austern's great article ([@http://drdobbs.com/184403814 [*The Standard Librarian: Containers of Incomplete Types]]): | |
132 | ||
133 | ["['Unlike most of my columns, this one is about something you can't do with the C++ Standard library: | |
134 | put incomplete types in one of the standard containers. This column explains why you might want to | |
135 | do this, why the standardization committee banned it even though they knew it was useful, and what | |
136 | you might be able to do to get around the restriction.]] | |
137 | ||
138 | ["['In 1997, shortly before the C++ Standard was completed, the standardization committee received a | |
139 | query: Is it possible to create standard containers with incomplete types? It took a while for the | |
140 | committee to understand the question. What would such a thing even mean, and why on earth would you | |
141 | ever want to do it? The committee eventually worked it out and came up with an answer to the question. | |
142 | (Just so you don't have to skip ahead to the end, the answer is "no.") But the question is much more | |
143 | interesting than the answer: it points to a useful, and insufficiently discussed, programming technique. | |
144 | The standard library doesn't directly support that technique, but the two can be made to coexist.]] | |
145 | ||
146 | ["['In a future revision of C++, it might make sense to relax the restriction on instantiating | |
147 | standard library templates with incomplete types. Clearly, the general prohibition should stay | |
148 | in place - instantiating templates with incomplete types is a delicate business, and there are | |
149 | too many classes in the standard library where it would make no sense. But perhaps it should be | |
150 | relaxed on a case-by-case basis, and `vector` looks like a good candidate for such special-case | |
151 | treatment: it's the one standard container class where there are good reasons to instantiate | |
152 | it with an incomplete type and where Standard Library implementors want to make it work. As of | |
153 | today, in fact, implementors would have to go out of their way to prohibit it!]] | |
154 | ||
155 | C++11 standard is also cautious about incomplete types and STL: ["['17.6.4.8 Other functions (...) 2. | |
156 | the effects are undefined in the following cases: (...) In particular - if an incomplete type (3.9) | |
157 | is used as a template argument when instantiating a template component, | |
158 | unless specifically allowed for that component]]. | |
159 | ||
160 | Fortunately all [*Boost.Container] containers except | |
161 | [classref boost::container::static_vector static_vector] and | |
162 | [classref boost::container::basic_string basic_string] are designed to support incomplete types. | |
163 | [classref boost::container::static_vector static_vector] is special because | |
164 | it statically allocates memory for `value_type` and this requires complete types and | |
165 | [classref boost::container::basic_string basic_string] implements Small String Optimization which | |
166 | also requires complete types. | |
167 | ||
168 | [*Boost.Container] containers supporting incomplete types also support instantiating iterators to | |
169 | those incomplete elements. | |
170 | ||
171 | [section:recursive_containers Recursive containers] | |
172 | ||
173 | Most [*Boost.Container] containers can be used to define recursive containers: | |
174 | ||
175 | [import ../example/doc_recursive_containers.cpp] | |
176 | [doc_recursive_containers] | |
177 | ||
178 | [endsect] | |
179 | ||
180 | [section:type_erasure Type Erasure] | |
181 | ||
182 | Containers of incomplete types are useful to break header file dependencies and improve | |
183 | compilation types. With Boost.Container, you can write a header file defining a class | |
184 | with containers of incomplete types as data members, if you carefully put all the | |
185 | implementation details that require knowing the size of the `value_type` in your | |
186 | implementation file: | |
187 | ||
188 | [import ../example/doc_type_erasure.cpp] | |
189 | ||
190 | In this header file we define a class (`MyClassHolder)` that holds a `vector` of an | |
191 | incomplete type (`MyClass`) that it's only forward declared. | |
192 | ||
193 | [doc_type_erasure_MyClassHolder_h] | |
194 | ||
195 | Then we can define `MyClass` in its own header file. | |
196 | ||
197 | [doc_type_erasure_MyClass_h] | |
198 | ||
199 | And include it only in the implementation file of `MyClassHolder` | |
200 | ||
201 | [doc_type_erasure_MyClassHolder_cpp] | |
202 | ||
203 | Finally, we can just compile, link, and run! | |
204 | ||
205 | [doc_type_erasure_main_cpp] | |
206 | ||
207 | [endsect] | |
208 | ||
209 | [endsect] | |
210 | ||
211 | [section:scary_iterators SCARY iterators] | |
212 | ||
213 | The paper N2913, titled [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2913.pdf, | |
214 | SCARY Iterator Assignment and Initialization], proposed a requirement that a standard container's | |
215 | iterator types have no dependency on any type argument apart from the container's `value_type`, | |
216 | `difference_type`, `pointer type`, and `const_pointer` type. In particular, according to the proposal, | |
217 | the types of a standard container's iterators should not depend on the container's `key_compare`, | |
218 | `hasher`, `key_equal`, or `allocator` types. | |
219 | ||
220 | That paper demonstrated that SCARY operations were crucial to the performant implementation of common | |
221 | design patterns using STL components. It showed that implementations that support SCARY operations reduce | |
222 | object code bloat by eliminating redundant specializations of iterator and algorithm templates. | |
223 | ||
224 | [*Boost.Container] containers implement SCARY iterators so the iterator type of a container is only dependent | |
225 | on the `allocator_traits<allocator_type>::pointer` type (the pointer type of the `value_type` to be inserted | |
226 | in the container). Reference types and all other typedefs are deduced from the pointer type using the | |
227 | C++11 `pointer_traits` utility. This leads to lower code bloat in algorithms and classes templated on | |
228 | iterators. | |
229 | ||
230 | [endsect] | |
231 | ||
232 | [section:other_features Other features] | |
233 | ||
234 | * Default constructors don't allocate memory which improves performance and | |
235 | usually implies a no-throw guarantee (if predicate's or allocator's default constructor doesn't throw). | |
236 | ||
237 | * Small string optimization for [classref boost::container::basic_string basic_string], | |
238 | with an internal buffer of 11/23 bytes (32/64 bit systems) | |
239 | [*without] increasing the usual `sizeof` of the string (3 words). | |
240 | ||
241 | * `[multi]set/map` containers are size optimized embedding the color bit of the red-black tree nodes | |
242 | in the parent pointer. | |
243 | ||
244 | * `[multi]set/map` containers use no recursive functions so stack problems are avoided. | |
245 | ||
246 | [endsect] | |
247 | ||
248 | [endsect] | |
249 | ||
250 | [section:exception_handling Boost.Container and C++ exceptions] | |
251 | ||
252 | In some environments, such as game development or embedded systems, C++ exceptions are disabled or a customized error handling is needed. | |
253 | According to document [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html N2271 EASTL -- Electronic Arts Standard Template Library] | |
254 | exceptions can be disabled for several reasons: | |
255 | ||
256 | * ["['Exception handling incurs some kind of cost in all compiler implementations, including those that avoid | |
257 | the cost during normal execution. However, in some cases this cost may arguably offset the cost of the code that it is replacing.]] | |
258 | * ["['Exception handling is often agreed to be a superior solution for handling a large range of function return values. However, | |
259 | avoiding the creation of functions that need large ranges of return values is superior to using exception handling to handle such values.]] | |
260 | * ["['Using exception handling correctly can be difficult in the case of complex software.]] | |
261 | * ["['The execution of throw and catch can be significantly expensive with some implementations.]] | |
262 | * ["['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 | |
263 | has destructible stack objects regardless of whether they use exception handling.]] | |
264 | * ["['The approach that game software usually takes is to avoid the need for exception handling where possible; avoid the possibility | |
265 | of circumstances that may lead to exceptions. For example, verify up front that there is enough memory for a subsystem to do its job | |
266 | instead of trying to deal with the problem via exception handling or any other means after it occurs.]] | |
267 | * ["['However, some game libraries may nevertheless benefit from the use of exception handling. It's best, however, | |
268 | if such libraries keep the exception handling internal lest they force their usage of exception handling on the rest of the application.]] | |
269 | ||
270 | In order to support environments without C++ exception support or environments with special error handling needs, | |
271 | [*Boost.Container] changes error signalling behaviour when `BOOST_CONTAINER_USER_DEFINED_THROW_CALLBACKS` or `BOOST_NO_EXCEPTIONS` | |
272 | 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] | |
273 | when the compiler has been invoked with the appropriate flag (like `-fno-exceptions` in GCC). | |
274 | ||
275 | When dealing with user-defined classes, (e.g. when constructing user-defined classes): | |
276 | ||
277 | * If `BOOST_NO_EXCEPTIONS` is defined, the library avoids using `try`/`catch`/`throw` statements. The class writer must handle and | |
278 | propagate error situations internally as no error will be propagated through [*Boost.Container]. | |
279 | * If `BOOST_NO_EXCEPTIONS` is *not* defined, the library propagates exceptions offering the exception guarantees detailed in the documentation. | |
280 | ||
281 | 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 | |
282 | a throw-callback declared in [headerref boost/container/throw_exception.hpp]: | |
283 | ||
284 | * If `BOOST_CONTAINER_USER_DEFINED_THROW_CALLBACKS` is defined, then the programmer must provide its own definition for all | |
285 | `throw_xxx` functions. Those functions can't return, they must throw an exception or call `std::exit` or `std::abort`. | |
286 | * Else if `BOOST_NO_EXCEPTIONS` is defined, a `BOOST_ASSERT_MSG` assertion is triggered | |
287 | (see [@http://www.boost.org/libs/utility/assert.html Boost.Assert] for more information). | |
288 | If this assertion returns, then `std::abort` is called. | |
289 | * Else, an appropriate standard library exception is thrown (like `std::out_of_range`). | |
290 | ||
291 | [endsect] | |
292 | ||
293 | [section:non_standard_containers Non-standard containers] | |
294 | ||
295 | [section:stable_vector ['stable_vector]] | |
296 | ||
297 | 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] | |
298 | is an hybrid between `vector` and `list`, providing most of | |
299 | the features of `vector` except [@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#69 element contiguity]. | |
300 | ||
301 | Extremely convenient as they are, `vector`s have a limitation that many novice C++ programmers frequently stumble upon: | |
302 | iterators and references to an element of an `vector` are invalidated when a preceding element is erased or when the | |
303 | vector expands and needs to migrate its internal storage to a wider memory region (i.e. when the required size exceeds | |
304 | the vector's capacity). We say then that `vector`s are unstable: by contrast, stable containers are those for which | |
305 | references and iterators to a given element remain valid as long as the element is not erased: examples of stable containers | |
306 | within the C++ standard library are `list` and the standard associative containers (`set`, `map`, etc.). | |
307 | ||
308 | Sometimes stability is too precious a feature to live without, but one particular property of `vector`s, element contiguity, | |
309 | makes it impossible to add stability to this container. So, provided we sacrifice element contiguity, how much | |
310 | can a stable design approach the behavior of `vector` (random access iterators, amortized constant time end | |
311 | insertion/deletion, minimal memory overhead, etc.)? | |
312 | The following image describes the layout of a possible data structure upon which to base the design of a stable vector: | |
313 | ||
314 | [$../../libs/container/doc/html/images/stable_vector.png [width 50%] [align center] ] | |
315 | ||
316 | Each element is stored in its own separate node. All the nodes are referenced from a contiguous array of pointers, but | |
317 | also every node contains an "up" pointer referring back to the associated array cell. This up pointer is the key element | |
318 | to implementing stability and random accessibility: | |
319 | ||
320 | Iterators point to the nodes rather than to the pointer array. This ensures stability, as it is only the pointer array | |
321 | that needs to be shifted or relocated upon insertion or deletion. Random access operations can be implemented by using | |
322 | the pointer array as a convenient intermediate zone. For instance, if the iterator it holds a node pointer `it.p` and we | |
323 | want to advance it by n positions, we simply do: | |
324 | ||
325 | [c++] | |
326 | ||
327 | it.p = *(it.p->up+n); | |
328 | ||
329 | That is, we go "up" to the pointer array, add n there and then go "down" to the resulting node. | |
330 | ||
331 | [*General properties]. `stable_vector` satisfies all the requirements of a container, a reversible container and a sequence | |
332 | and provides all the optional operations present in vector. Like vector, iterators are random access. `stable_vector` | |
333 | does not provide element contiguity; in exchange for this absence, the container is stable, i.e. references and iterators | |
334 | to an element of a `stable_vector` remain valid as long as the element is not erased, and an iterator that has been | |
335 | assigned the return value of end() always remain valid until the destruction of the associated `stable_vector`. | |
336 | ||
337 | [*Operation complexity]. The big-O complexities of `stable_vector` operations match exactly those of vector. In general, | |
338 | insertion/deletion is constant time at the end of the sequence and linear elsewhere. Unlike vector, `stable_vector` | |
339 | does not internally perform any value_type destruction, copy/move construction/assignment operations other than those exactly | |
340 | corresponding to the insertion of new elements or deletion of stored elements, which can sometimes compensate in terms of | |
341 | performance for the extra burden of doing more pointer manipulation and an additional allocation per element. | |
342 | ||
343 | [*Exception safety]. (according to [@http://www.boost.org/community/exception_safety.html Abrahams' terminology]) | |
344 | As `stable_vector` does not internally copy/move elements around, some | |
345 | operations provide stronger exception safety guarantees than in vector: | |
346 | ||
347 | [table:stable_vector_req Exception safety | |
348 | [[operation] [exception safety for `vector<T>`] [exception safety for `stable_vector<T>`]] | |
349 | [[insert] [strong unless copy/move construction/assignment of `T` throw (basic)] [strong]] | |
350 | [[erase] [no-throw unless copy/move construction/assignment of `T` throw (basic)] [no-throw]] | |
351 | ] | |
352 | ||
353 | [*Memory overhead]. The C++ standard does not specifiy requirements on memory consumption, but virtually any implementation | |
354 | of `vector` has the same behavior wih respect to memory usage: the memory allocated by a `vector` v with n elements of type T | |
355 | is | |
356 | ||
357 | m[sub v] = c\u2219e, | |
358 | ||
359 | 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 | |
360 | required; otherwise, the average value c for a growing `vector` oscillates between 1.25\u2219n and 1.5\u2219n for typical resizing | |
361 | policies. For `stable_vector`, the memory usage is | |
362 | ||
363 | m[sub sv] = (c + 1)p + (n + 1)(e + p), | |
364 | ||
365 | 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 | |
366 | the sequence. If we call f the capacity to size ratio c/n and assume that n is large enough, we have that | |
367 | ||
368 | m[sub sv]/m[sub v] \u2243 (fp + e + p)/fe. | |
369 | ||
370 | So, `stable_vector` uses less memory than `vector` only when e > p and the capacity to size ratio exceeds a given threshold: | |
371 | ||
372 | m[sub sv] < m[sub v] <-> f > (e + p)/(e - p). (provided e > p) | |
373 | ||
374 | This threshold approaches typical values of f below 1.5 when e > 5p; in a 32-bit architecture, when e > 20 bytes. | |
375 | ||
376 | [*Summary]. `stable_vector` is a drop-in replacement for `vector` providing stability of references and iterators, in exchange | |
377 | for missing element contiguity and also some performance and memory overhead. When the element objects are expensive to | |
378 | move around, the performance overhead can turn into a net performance gain for `stable_vector` if many middle insertions | |
379 | or deletions are performed or if resizing is very frequent. Similarly, if the elements are large there are situations when | |
380 | the memory used by `stable_vector` can actually be less than required by vector. | |
381 | ||
382 | ['Note: Text and explanations taken from [@http://bannalia.blogspot.com/2008/09/introducing-stablevector.html Joaqu\u00EDn's blog]] | |
383 | ||
384 | [endsect] | |
385 | ||
386 | [section:flat_xxx ['flat_(multi)map/set] associative containers] | |
387 | ||
388 | Using sorted vectors instead of tree-based associative containers is a well-known technique in | |
389 | C++ world. Matt Austern's classic article | |
390 | [@http://lafstern.org/matt/col1.pdf Why You Shouldn't Use set, and What You Should Use Instead] | |
391 | (C++ Report 12:4, April 2000) was enlightening: | |
392 | ||
393 | ["['Red-black trees aren't the only way to organize data that permits lookup in logarithmic time. One of the basic | |
394 | algorithms of computer science is binary search, which works by successively dividing a range in half. Binary | |
395 | search is log N and it doesn't require any fancy data structures, just a sorted collection of elements. | |
396 | (...) You can use whatever data structure is convenient, so long as it provides STL iterator; | |
397 | usually it's easiest to use a C array, or a vector.]] | |
398 | ||
399 | ["['Both std::lower_bound and set::find take time proportional to log N, but the constants of proportionality | |
400 | are very different. Using g++ (...) it takes X seconds to perform a million lookups in a | |
401 | sorted vector<double> of a million elements, and almost twice as long (...) using a set. Moreover, | |
402 | the set uses almost three times as much memory (48 million bytes) as the vector (16.8 million).]] | |
403 | ||
404 | ["['Using a sorted vector instead of a set gives you faster lookup and much faster iteration, | |
405 | but at the cost of slower insertion. Insertion into a set, using set::insert, is proportional | |
406 | to log N, but insertion into a sorted vector, (...) | |
407 | , is proportional to N. Whenever you insert something into a vector, | |
408 | vector::insert has to make room by shifting all of the elements that follow it. On average, if you're equally | |
409 | likely to insert a new element anywhere, you'll be shifting N/2 elements.]] | |
410 | ||
411 | ["['It may sometimes be convenient to bundle all of this together into a small container adaptor. | |
412 | This class does not satisfy the requirements of a Standard Associative Container, since the complexity of insert is | |
413 | O(N) rather than O(log N), but otherwise it is almost a drop-in replacement for set.]] | |
414 | ||
415 | Following Matt Austern's indications, Andrei Alexandrescu's | |
416 | [@http://www.bestwebbuys.com/Modern-C-Design-Generic-Programming-and-Design-Patterns-Applied-ISBN-9780201704310?isrc=-rd Modern C++ Design] | |
417 | showed `AssocVector`, a `std::map` drop-in | |
418 | replacement designed in his [@http://loki-lib.sourceforge.net/ Loki] library: | |
419 | ||
420 | ["['It seems as if we're better off with a sorted vector. The disadvantages of a sorted | |
421 | vector are linear-time insertions and linear-time deletions (...). In exchange, a vector | |
422 | offers about twice the lookup speed and a much smaller working set (...). | |
423 | Loki saves the trouble of maintaining a sorted vector by hand by defining an AssocVector class | |
424 | template. AssocVector is a drop-in replacement for std::map (it supports the same set of member | |
425 | functions), implemented on top of std::vector. AssocVector differs from a map in the behavior of | |
426 | its erase functions (AssocVector::erase invalidates all iterators into the object) and in the | |
427 | complexity guarantees of insert and erase (linear as opposed to constant). ]] | |
428 | ||
429 | [*Boost.Container] `flat_[multi]map/set` containers are ordered-vector based associative containers | |
430 | based on Austern's and Alexandrescu's guidelines. These ordered vector containers have also | |
431 | benefited recently with the addition of `move semantics` to C++, speeding up insertion | |
432 | and erasure times considerably. Flat associative containers have the following | |
433 | attributes: | |
434 | ||
435 | * Faster lookup than standard associative containers | |
436 | * Much faster iteration than standard associative containers. | |
437 | Random-access iterators instead of bidirectional iterators. | |
438 | * Less memory consumption for small objects (and for big objects if `shrink_to_fit` is used) | |
439 | * Improved cache performance (data is stored in contiguous memory) | |
440 | * Non-stable iterators (iterators are invalidated when inserting and erasing elements) | |
441 | * Non-copyable and non-movable values types can't be stored | |
442 | * Weaker exception safety than standard associative containers | |
443 | (copy/move constructors can throw when shifting values in erasures and insertions) | |
444 | * Slower insertion and erasure than standard associative containers (specially for non-movable types) | |
445 | ||
446 | [endsect] | |
447 | ||
448 | [section:slist ['slist]] | |
449 | ||
450 | When the standard template library was designed, it contained a singly linked list called `slist`. | |
451 | Unfortunately, this container was not standardized and remained as an extension for many standard | |
452 | library implementations until C++11 introduced `forward_list`, which is a bit different from the | |
453 | the original SGI `slist`. According to [@http://www.sgi.com/tech/stl/Slist.html SGI STL documentation]: | |
454 | ||
455 | ["['An `slist` is a singly linked list: a list where each element is linked to the next element, but | |
456 | not to the previous element. That is, it is a Sequence that supports forward but not backward traversal, | |
457 | and (amortized) constant time insertion and removal of elements. Slists, like lists, have the important | |
458 | property that insertion and splicing do not invalidate iterators to list elements, and that even removal | |
459 | invalidates only the iterators that point to the elements that are removed. The ordering of iterators | |
460 | may be changed (that is, slist<T>::iterator might have a different predecessor or successor after a list | |
461 | operation than it did before), but the iterators themselves will not be invalidated or made to point to | |
462 | different elements unless that invalidation or mutation is explicit.]] | |
463 | ||
464 | ["['The main difference between `slist` and list is that list's iterators are bidirectional iterators, | |
465 | while slist's iterators are forward iterators. This means that `slist` is less versatile than list; | |
466 | frequently, however, bidirectional iterators are unnecessary. You should usually use `slist` unless | |
467 | you actually need the extra functionality of list, because singly linked lists are smaller and faster | |
468 | than double linked lists.]] | |
469 | ||
470 | ["['Important performance note: like every other Sequence, `slist` defines the member functions insert and erase. | |
471 | Using these member functions carelessly, however, can result in disastrously slow programs. The problem is that | |
472 | insert's first argument is an iterator pos, and that it inserts the new element(s) before pos. This means that | |
473 | insert must find the iterator just before pos; this is a constant-time operation for list, since list has | |
474 | bidirectional iterators, but for `slist` it must find that iterator by traversing the list from the beginning | |
475 | up to pos. In other words: insert and erase are slow operations anywhere but near the beginning of the slist.]] | |
476 | ||
477 | ["['Slist provides the member functions insert_after and erase_after, which are constant time operations: you should | |
478 | always use insert_after and erase_after whenever possible. If you find that insert_after and erase_after aren't | |
479 | adequate for your needs, and that you often need to use insert and erase in the middle of the list, then you | |
480 | should probably use list instead of slist.]] | |
481 | ||
482 | [*Boost.Container] updates the classic `slist` container with C++11 features like move semantics and placement | |
483 | insertion and implements it a bit differently than the standard C++ `forward_list`. `forward_list` has no `size()` | |
484 | method, so it's been designed to allow (or in practice, encourage) implementations without tracking list size | |
485 | with every insertion/erasure, allowing constant-time | |
486 | `splice_after(iterator, forward_list &, iterator, iterator)`-based list merging. On the other hand `slist` offers | |
487 | constant-time `size()` for those that don't care about linear-time `splice_after(iterator, slist &, iterator, iterator)` | |
488 | `size()` and offers an additional `splice_after(iterator, slist &, iterator, iterator, size_type)` method that | |
489 | can speed up `slist` merging when the programmer already knows the size. `slist` and `forward_list` are therefore | |
490 | complementary. | |
491 | ||
492 | [endsect] | |
493 | ||
494 | [section:static_vector ['static_vector]] | |
495 | ||
496 | `static_vector` is an hybrid between `vector` and `array`: like `vector`, it's a sequence container | |
497 | with contiguous storage that can change in size, along with the static allocation, low overhead, | |
498 | and fixed capacity of `array`. `static_vector` is based on Adam Wulkiewicz and Andrew Hundt's | |
499 | high-performance [@https://svn.boost.org/svn/boost/sandbox/varray/doc/html/index.html varray] | |
500 | class. | |
501 | ||
502 | The number of elements in a `static_vector` may vary dynamically up to a fixed capacity | |
503 | because elements are stored within the object itself similarly to an array. However, objects are | |
504 | initialized as they are inserted into `static_vector` unlike C arrays or `std::array` which must construct | |
505 | all elements on instantiation. The behavior of `static_vector` enables the use of statically allocated | |
506 | elements in cases with complex object lifetime requirements that would otherwise not be trivially | |
507 | possible. Some other properties: | |
508 | ||
509 | * Random access to elements | |
510 | * Constant time insertion and removal of elements at the end | |
511 | * Linear time insertion and removal of elements at the beginning or in the middle. | |
512 | ||
513 | `static_vector` is well suited for use in a buffer, the internal implementation of other | |
514 | classes, or use cases where there is a fixed limit to the number of elements that must be stored. | |
515 | Embedded and realtime applications where allocation either may not be available or acceptable | |
516 | are a particular case where `static_vector` can be beneficial. | |
517 | ||
518 | [endsect] | |
519 | ||
520 | [section:small_vector ['small_vector]] | |
521 | ||
522 | `small_vector` is a vector-like container optimized for the case when it contains few elements. | |
523 | It contains some preallocated elements in-place, which allows it to avoid the use of dynamic storage allocation | |
524 | when the actual number of elements is below that preallocated threshold. `small_vector` is inspired by | |
525 | [@http://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h LLVM's `SmallVector`] container. | |
526 | Unlike `static_vector`, `small_vector`'s capacity can grow beyond the initial preallocated capacity. | |
527 | ||
528 | `small_vector<T, N, Allocator>` is convertible to `small_vector_base<T, Allocator>`, a type that is independent | |
529 | from the preallocated element count, allowing client code that does not need to be templated on that N argument. | |
530 | `small_vector` inherits all `vector`'s member functions so it supports all standard features like emplacement, | |
531 | stateful allocators, etc. | |
532 | ||
533 | [endsect] | |
534 | ||
535 | [endsect] | |
536 | ||
537 | [section:extended_functionality Extended functionality] | |
538 | ||
539 | [section:default_initialialization Default initialization for vector-like containers] | |
540 | ||
541 | STL and most other containers value initialize new elements in common operations like | |
542 | `vector::resize(size_type n)` or `explicit vector::vector(size_type n)`. | |
543 | ||
544 | In some performance-sensitive environments, where vectors are used as a replacement for | |
545 | variable-size buffers for file or network operations, | |
546 | [@http://en.cppreference.com/w/cpp/language/value_initialization value initialization] | |
547 | is a cost that is not negligible as elements are going to be overwritten by an external source | |
548 | shortly after new elements are added to the container. | |
549 | ||
550 | [*Boost.Container] offers two new members for `vector`, `static_vector` and `stable_vector`: | |
551 | `explicit container::container(size_type n, default_init_t)` and | |
552 | `explicit container::resize(size_type n, default_init_t)`, where new elements are constructed | |
553 | using [@http://en.cppreference.com/w/cpp/language/default_initialization default initialization]. | |
554 | ||
555 | [endsect] | |
556 | ||
557 | [section:ordered_range_insertion Ordered range insertion for associative containers (['ordered_unique_range], ['ordered_range]) ] | |
558 | ||
559 | When filling associative containers big performance gains can be achieved if the input range to be inserted | |
560 | is guaranteed by the user to be ordered according to the predicate. This can happen when inserting values from a `set` to | |
561 | a `multiset` or between different associative container families (`[multi]set/map` vs. `flat_[multi]set/map`). | |
562 | ||
563 | [*Boost.Container] has some overloads for constructors and insertions taking an `ordered_unique_range_t` or | |
564 | an `ordered_range_t` tag parameters as the first argument. When an `ordered_unique_range_t` overload is used, the | |
565 | user notifies the container that the input range is ordered according to the container predicate and has no | |
566 | duplicates. When an `ordered_range_t` overload is used, the | |
567 | user notifies the container that the input range is ordered according to the container predicate but it might | |
568 | have duplicates. With this information, the container can avoid multiple predicate calls and improve insertion | |
569 | times. | |
570 | ||
571 | [endsect] | |
572 | ||
573 | [section:configurable_tree_based_associative_containers Configurable tree-based associative ordered containers] | |
574 | ||
575 | [classref boost::container::set set], [classref boost::container::multiset multiset], | |
576 | [classref boost::container::map map] and [classref boost::container::multimap multimap] associative containers | |
577 | are implemented as binary search trees which offer the needed complexity and stability guarantees required by the | |
578 | C++ standard for associative containers. | |
579 | ||
580 | [*Boost.Container] offers the possibility to configure at compile time some parameters of the binary search tree | |
581 | implementation. This configuration is passed as the last template parameter and defined using the utility class | |
582 | [classref boost::container::tree_assoc_options tree_assoc_options]. | |
583 | ||
584 | The following parameters can be configured: | |
585 | ||
586 | * The underlying [*tree implementation] type ([classref boost::container::tree_type tree_type]). | |
587 | By default these containers use a red-black tree but the user can use other tree types: | |
588 | * [@http://en.wikipedia.org/wiki/Red%E2%80%93black_tree Red-Black Tree] | |
589 | * [@http://en.wikipedia.org/wiki/Avl_trees AVL tree] | |
590 | * [@http://en.wikipedia.org/wiki/Scapegoat_tree Scapegoat tree]. In this case Insertion and Deletion | |
591 | are amortized O(log n) instead of O(log n). | |
592 | * [@http://en.wikipedia.org/wiki/Splay_tree Splay tree]. In this case Searches, Insertions and Deletions | |
593 | are amortized O(log n) instead of O(log n). | |
594 | ||
595 | * Whether the [*size saving] mechanisms are used to implement the tree nodes | |
596 | ([classref boost::container::optimize_size optimize_size]). By default this option is activated and is only | |
597 | meaningful to red-black and avl trees (in other cases, this option will be ignored). | |
598 | This option will try to put rebalancing metadata inside the "parent" pointer of the node if the pointer | |
599 | type has enough alignment. Usually, due to alignment issues, the metadata uses the size of a pointer yielding | |
600 | to four pointer size overhead per node, whereas activating this option usually leads to 3 pointer size overhead. | |
601 | Although some mask operations must be performed to extract | |
602 | data from this special "parent" pointer, in several systems this option also improves performance due to the | |
603 | improved cache usage produced by the node size reduction. | |
604 | ||
605 | See the following example to see how [classref boost::container::tree_assoc_options tree_assoc_options] can be | |
606 | used to customize these containers: | |
607 | ||
608 | [import ../example/doc_custom_tree.cpp] | |
609 | [doc_custom_tree] | |
610 | ||
611 | [endsect] | |
612 | ||
613 | [section:constant_time_range_splice Constant-time range splice for `(s)list`] | |
614 | ||
615 | In the first C++ standard `list::size()` was not required to be constant-time, | |
616 | and that caused some controversy in the C++ community. Quoting Howard Hinnant's | |
617 | [@http://howardhinnant.github.io/On_list_size.html ['On List Size]] paper: | |
618 | ||
619 | [: ['There is a considerable debate on whether `std::list<T>::size()` should be O(1) or O(N). | |
620 | The usual argument notes that it is a tradeoff with:] | |
621 | ||
622 | `splice(iterator position, list& x, iterator first, iterator last);` | |
623 | ||
624 | ['If size() is O(1) and this != &x, then this method must perform a linear operation so that it | |
625 | can adjust the size member in each list]] | |
626 | ||
627 | C++11 definitely required `size()` to be O(1), so range splice became O(N). However, | |
628 | Howard Hinnant's paper proposed a new `splice` overload so that even O(1) `list:size()` | |
629 | implementations could achieve O(1) range splice when the range size was known to the caller: | |
630 | ||
631 | [: `void splice(iterator position, list& x, iterator first, iterator last, size_type n);` | |
632 | ||
633 | [*Effects]: Inserts elements in the range [first, last) before position and removes the elements from x. | |
634 | ||
635 | [*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). | |
636 | ||
637 | [*Throws]: Nothing. | |
638 | ||
639 | [*Complexity]: Constant time. | |
640 | ] | |
641 | ||
642 | This new splice signature allows the client to pass the distance of the input range in. | |
643 | This information is often available at the call site. If it is passed in, | |
644 | then the operation is constant time, even with an O(1) size. | |
645 | ||
646 | [*Boost.Container] implements this overload for `list` and a modified version of it for `slist` | |
647 | (as `slist::size()` is also `O(1)`). | |
648 | ||
649 | [endsect] | |
650 | ||
651 | [section:extended_allocators Extended allocators] | |
652 | ||
653 | Many C++ programmers have ever wondered where does good old realloc fit in C++. And that's a good question. | |
654 | Could we improve [classref boost::container::vector vector] performance using memory expansion mechanisms | |
655 | to avoid too many copies? But [classref boost::container::vector vector] is not the only container that | |
656 | could benefit from an improved allocator interface: we could take advantage of the insertion of multiple | |
657 | elements in [classref boost::container::list list] using a burst allocation mechanism that could amortize | |
658 | costs (mutex locks, free memory searches...) that can't be amortized when using single node allocation | |
659 | strategies. | |
660 | ||
661 | These improvements require extending the STL allocator interface and use make use of a new | |
662 | general purpose allocator since new and delete don't offer expansion and burst capabilities. | |
663 | ||
664 | * [*Boost.Container] containers support an extended allocator interface based on an evolution of proposals | |
665 | [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1953.html N1953: Upgrading the Interface of Allocators using API Versioning], | |
666 | [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html N2045: Improving STL allocators] | |
667 | and the article | |
668 | [@http://www.drivehq.com/web/igaztanaga/allocplus/ Applying classic memory allocation strategies to C++ containers]. | |
669 | The extended allocator interface is implemented by [classref boost::container::allocator allocator], | |
670 | [classref boost::container::adaptive_pool adaptive_pool] and [classref boost::container::node_allocator node_allocator] | |
671 | classes. | |
672 | ||
673 | * Extended allocators use a modified [@http://g.oswego.edu/dl/html/malloc.html Doug Lea Malloc (DLMalloc)] low-level | |
674 | allocator and offers an C API to implement memory expansion and burst allocations. DLmalloc is known to be very size | |
675 | and speed efficient, and this allocator is used as the basis of many malloc implementations, including multithreaded | |
676 | allocators built above DLmalloc (See [@http://www.malloc.de/en/ ptmalloc2, ptmalloc3] or | |
677 | [@http://www.nedprod.com/programs/portable/nedmalloc/ nedmalloc]). This low-level allocator is implemented as | |
678 | a separately compiled library and the following extended allocators depend on the library: | |
679 | ||
680 | * [classref boost::container::allocator allocator]: This extended allocator offers expansion, shrink-in place | |
681 | and burst allocation capabilities implemented as a thin wrapper around the modified DLMalloc. | |
682 | It can be used with all containers and it should be the default choice when the programmer wants to use | |
683 | extended allocator capabilities. | |
684 | ||
685 | * [classref boost::container::node_allocator node_allocator]: It's a | |
686 | [@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] | |
687 | allocator, similar to [*Boost.Pool] that takes advantage of the modified DLMalloc burst interface. It does not return | |
688 | memory to the DLMalloc allocator (and thus, to the system), unless explicitly requested. It does offer a very small | |
689 | memory overhead so it's suitable for node containers ([boost::container::list list], [boost::container::slist slist] | |
690 | [boost::container::set set]...) that allocate very small `value_type`s and it offers improved node allocation times | |
691 | for single node allocations with respecto to [classref boost::container::allocator allocator]. | |
692 | ||
693 | * [classref boost::container::adaptive_pool adaptive_pool]: It's a low-overhead node allocator that can return memory | |
694 | 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]. | |
695 | It's also suitable for node containers. | |
696 | ||
697 | Use them simply specifying the new allocator in the corresponding template argument of your favourite container: | |
698 | ||
699 | [import ../example/doc_extended_allocators.cpp] | |
700 | [doc_extended_allocators] | |
701 | ||
702 | [endsect] | |
703 | ||
704 | [section:polymorphic_memory_resources Polymorphic Memory Resources ] | |
705 | ||
706 | The document | |
707 | [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4480.html C++ Extensions for Library Fundamentals (Final draft: N4480)] | |
708 | includes classes that provide allocator type erasure and runtime polymorphism. As Pablo Halpern, the author of the proposal, | |
709 | explains in the paper ([@https://isocpp.org/files/papers/N3916.pdf N3916 Polymorphic Memory Resources (r2)]): | |
710 | ||
711 | ["['A significant impediment to effective memory management in C++ has been the | |
712 | inability to use allocators in non-generic contexts. In large software systems, | |
713 | most of the application program consists of non-generic procedural or | |
714 | object-oriented code that is compiled once and linked many times.]] | |
715 | ||
716 | ["['Allocators in C++, however, have historically relied solely on | |
717 | compile-time polymorphism, and therefore have not been suitable for use in vocabulary | |
718 | types, which are passed through interfaces between separately-compiled modules, | |
719 | because the allocator type necessarily affects the type of the object that uses it. | |
720 | This proposal builds upon the improvements made to allocators in | |
721 | C++11 and describes a set of facilities for runtime polymorphic memory | |
722 | resources that interoperate with the existing compile-time polymorphic | |
723 | allocators.]] | |
724 | ||
725 | [*Boost.Container] implements nearly all classes of the proposal under | |
726 | the namespace `boost::container::pmr`. There are two groups, | |
727 | ||
728 | * Header only utilities (these don't require the separately compiled library): | |
729 | * [classref boost::container::pmr::memory_resource memory_resource]. | |
730 | * [classref boost::container::pmr::resource_adaptor resource_adaptor]. | |
731 | ||
732 | * Utilities that require the the separately compiled library: | |
733 | * [classref boost::container::pmr::polymorphic_allocator polymorphic_allocator]. | |
734 | * [classref boost::container::pmr::monotonic_buffer_resource monotonic_buffer_resource]. | |
735 | * [classref boost::container::pmr::unsynchronized_pool_resource unsynchronized_pool_resource]. | |
736 | * [classref boost::container::pmr::synchronized_pool_resource synchronized_pool_resource]. | |
737 | * Global resource functions: [funcref boost::container::pmr::get_default_resource get_default_resource]/ | |
738 | [funcref boost::container::pmr::set_default_resource set_default_resource]/ | |
739 | [funcref boost::container::pmr::new_delete_resource new_delete_resource]/ | |
740 | [funcref boost::container::pmr::null_memory_resource null_memory_resource] | |
741 | * Aliases for boost containers using the polymorphic allocator | |
742 | (like [classref boost::container::pmr::vector pmr::vector], etc.) | |
743 | ||
744 | [*Boost.Container]'s polymorphic resource library is usable from C++03 containers, | |
745 | and offers some alternative utilities if the required C++11 features of the | |
746 | ['Library Fundamentals] specification are not available. | |
747 | ||
748 | [import ../example/doc_pmr.cpp] | |
749 | ||
750 | Let's review the usage example given in | |
751 | [@https://isocpp.org/files/papers/N3916.pdf N3916] and see how it can be implemented | |
752 | using [*Boost.Container]: ['Suppose we are processing a series of shopping lists, where a shopping list is a | |
753 | container of strings, and storing them in a collection (a list) of shopping lists. | |
754 | Each shopping list being processed uses a bounded amount of memory that is needed for | |
755 | a short period of time, while the collection of shopping lists uses an unbounded | |
756 | amount of memory and will exist for a longer period of time. For efficiency, we can | |
757 | use a more time-efficient memory allocator based on a finite buffer for the temporary | |
758 | shopping lists.] | |
759 | ||
760 | Let's see how `ShoppingList` can be defined to support an polymorphic memory resource | |
761 | that can allocate memory from different underlying mechanisms. The most important | |
762 | details are: | |
763 | ||
764 | * It should declare that supports an allocator defining an `allocator_type` typedef. | |
765 | This `allocator_type` will be of type [classref boost::container::pmr::memory_resource memory_resource *], | |
766 | which is a base class for polymorphic resources. | |
767 | * It must define constructors that take the | |
768 | the allocator as argument. It can be implemented in two ways: | |
769 | * `ShoppingList` has constructors taking | |
770 | [classref boost::container::pmr::memory_resource memory_resource*] as the last argument. | |
771 | * `ShoppingList` has constructors taking | |
772 | [classref boost::container::allocator_arg_t allocator_arg_t] as the first argument | |
773 | and [classref boost::container::pmr::memory_resource memory_resource*] as the second argument. | |
774 | ||
775 | [*Note:] ['In C++03 compilers, it is required that the programmer specializes as `true` | |
776 | [classref boost::container::constructible_with_allocator_suffix constructible_with_allocator_suffix] or | |
777 | [classref boost::container::constructible_with_allocator_prefix constructible_with_allocator_prefix] | |
778 | as in C++03 there is no way to automatically detect the chosen option at compile time. If | |
779 | no specialization is done, [*Boost.Container] assumes the suffix option]. | |
780 | ||
781 | [doc_pmr_ShoppingList_hpp] | |
782 | ||
783 | ['However, this time-efficient allocator is not appropriate for the longer | |
784 | lived collection of shopping lists. This example shows how those temporary shopping | |
785 | lists, using a time-efficient allocator, can be used to populate the long lived collection | |
786 | of shopping lists, using a general purpose allocator, something that would be | |
787 | annoyingly difficult without the polymorphic allocators.] | |
788 | ||
789 | In [*Boost.Container] for the time-efficient allocation we can use | |
790 | [classref boost::container::pmr::monotonic_buffer_resource monotonic_buffer_resource], | |
791 | providing an external buffer that will be used until it's exhausted. In the default | |
792 | configuration, when the buffer is exhausted, the default memory resource will be used | |
793 | instead. | |
794 | ||
795 | [doc_pmr_main_cpp] | |
796 | ||
797 | ['Notice that the shopping lists within `folder` use the default allocator resource | |
798 | whereas the shopping list `temporaryShoppingList` uses the short-lived but very fast | |
799 | `buf_rsrc`. Despite using different allocators, you can insert | |
800 | `temporaryShoppingList` into folder because they have the same `ShoppingList` | |
801 | type. Also, while `ShoppingList` uses memory_resource directly, | |
802 | [classref boost::container::pmr::list pmr::list], | |
803 | [classref boost::container::pmr::vector pmr::vector] | |
804 | and [classref boost::container::pmr::string pmr::string] all use | |
805 | [classref boost::container::pmr::polymorphic_allocator polymorphic_allocator].] | |
806 | ||
807 | ['The resource passed to the `ShoppingList` constructor is propagated to the vector and | |
808 | each string within that `ShoppingList`. Similarly, the resource used to construct | |
809 | `folder` is propagated to the constructors of the ShoppingLists that are inserted into | |
810 | the list (and to the strings within those `ShoppingLists`). The | |
811 | [classref boost::container::pmr::polymorphic_allocator polymorphic_allocator] | |
812 | template is designed to be almost interchangeable with a pointer to | |
813 | [classref boost::container::pmr::memory_resource memory_resource], | |
814 | thus producing a ['bridge] between the template-policy | |
815 | style of allocator and the polymorphic-base-class style of allocator.] | |
816 | ||
817 | This example actually shows how easy is to use [*Boost.Container] to write | |
818 | type-erasured allocator-capable classes even in C++03 compilers. | |
819 | ||
820 | [endsect] | |
821 | ||
822 | [/ | |
823 | /a__section:previous_element_slist Previous element for slist__a | |
824 | / | |
825 | /The C++11 `std::forward_list` class implement a singly linked list, similar to `slist`, and these | |
826 | /containers only offer forward iterators and implement insertions and splice operations that operate with ranges | |
827 | /to be inserted ['after] that position. In those cases, sometimes it's interesting to obtain an iterator pointing | |
828 | /to the previous element of another element. This operation can be implemented | |
829 | / | |
830 | /a__endsect__a | |
831 | ] | |
832 | ||
833 | [/ | |
834 | /a__section:get_stored_allocator Obtain stored allocator__a | |
835 | / | |
836 | /STL containers offer a `get_allocator()` member to obtain a copy of the allocator that | |
837 | /the container is using to allocate and construct elements. For performance reasons, some | |
838 | /applications need o | |
839 | / | |
840 | /http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html | |
841 | / | |
842 | /a__endsect__a | |
843 | /] | |
844 | ||
845 | [endsect] | |
846 | ||
847 | [section:Cpp11_conformance C++11/C++14 Conformance] | |
848 | ||
849 | [*Boost.Container] aims for full C++11 conformance except reasoned deviations, | |
850 | backporting as much as possible for C++03. Obviously, this conformance is a work | |
851 | in progress so this section explains what C++11 features are implemented and which of them | |
852 | have been backported to C++03 compilers. | |
853 | ||
854 | [section:move_emplace Move and Emplace] | |
855 | ||
856 | For compilers with rvalue references and for those C++03 types that use | |
857 | [@http://www.boost.org/libs/move Boost.Move] rvalue reference emulation | |
858 | [*Boost.Container] supports all C++11 features related to move semantics: containers | |
859 | are movable, requirements for `value_type` are those specified for C++11 containers. | |
860 | ||
861 | For compilers with variadic templates, [*Boost.Container] supports placement insertion | |
862 | (`emplace`, ...) functions from C++11. For those compilers without variadic templates | |
863 | support [*Boost.Container] uses the preprocessor to create a set of overloads up to | |
864 | a finite number of parameters. | |
865 | ||
866 | [endsect] | |
867 | ||
868 | [section:alloc_traits_move_traits Stateful allocators] | |
869 | ||
870 | C++03 was not stateful-allocator friendly. For compactness of container objects and for | |
871 | simplicity, it did not require containers to support allocators with state: Allocator objects | |
872 | need not be stored in container objects. It was not possible to store an allocator with state, | |
873 | say an allocator that holds a pointer to an arena from which to allocate. C++03 allowed implementors | |
874 | to suppose two allocators of the same type always compare equal (that means that memory allocated | |
875 | by one allocator object could be deallocated by another instance of the same type) and | |
876 | allocators were not swapped when the container was swapped. | |
877 | ||
878 | C++11 further improves stateful allocator support through | |
879 | [@http://en.cppreference.com/w/cpp/memory/allocator_traits `std::allocator_traits`]. | |
880 | `std::allocator_traits` is the protocol between a container and an allocator, and | |
881 | an allocator writer can customize its behaviour (should the container propagate it in | |
882 | move constructor, swap, etc.?) following `allocator_traits` requirements. [*Boost.Container] | |
883 | not only supports this model with C++11 but also [*backports it to C++03] via | |
884 | [classref boost::container::allocator_traits boost::container::allocator_traits] including some | |
885 | C++17 changes. This class | |
886 | offers some workarounds for C++03 compilers to achieve the same allocator guarantees as | |
887 | `std::allocator_traits`. | |
888 | ||
889 | In [Boost.Container] containers, if possible, a single allocator is hold to construct | |
890 | `value_type`s. If the container needs an auxiliary | |
891 | allocator (e.g. an array allocator used by `deque` or `stable_vector`), that allocator is also | |
892 | stored in the container and initialized from the user-supplied allocator when the | |
893 | container is constructed (i.e. it's not constructed on the fly when auxiliary memory is needed). | |
894 | ||
895 | [endsect] | |
896 | ||
897 | [section:scoped_allocator Scoped allocators] | |
898 | ||
899 | C++11 improves stateful allocators with the introduction of | |
900 | [@http://en.cppreference.com/w/cpp/memory/scoped_allocator_adaptor `std::scoped_allocator_adaptor`] | |
901 | class template. `scoped_allocator_adaptor` is instantiated with one outer allocator and zero or more inner | |
902 | allocators. | |
903 | ||
904 | A scoped allocator is a mechanism to automatically propagate the state of the allocator to the subobjects | |
905 | of a container in a controlled way. If instantiated with only one allocator type, the inner allocator | |
906 | becomes the `scoped_allocator_adaptor` itself, thus using the same allocator | |
907 | resource for the container and every element within the container and, if the elements themselves are | |
908 | containers, each of their elements recursively. If instantiated with more than one allocator, the first allocator | |
909 | is the outer allocator for use by the container, the second allocator is passed to the constructors of the | |
910 | container's elements, and, if the elements themselves are containers, the third allocator is passed to the | |
911 | elements' elements, and so on. | |
912 | ||
913 | [*Boost.Container] implements its own [classref boost::container::scoped_allocator_adaptor scoped_allocator_adaptor] | |
914 | class and [*backports this feature also | |
915 | to C++03 compilers]. Due to C++03 limitations, in those compilers | |
916 | the allocator propagation implemented by `scoped_allocator_adaptor::construct` functions | |
917 | will be based on traits ([classref boost::container::constructible_with_allocator_suffix constructible_with_allocator_suffix] | |
918 | and [classref boost::container::constructible_with_allocator_prefix constructible_with_allocator_prefix]) | |
919 | proposed in [@http://www.open-std.org/jtc1/sc22/WG21/docs/papers/2008/n2554.pdf | |
920 | N2554: The Scoped Allocator Model (Rev 2) proposal]. In conforming C++11 compilers or compilers supporting SFINAE | |
921 | expressions (when `BOOST_NO_SFINAE_EXPR` is NOT defined), traits are ignored and C++11 rules | |
922 | (`is_constructible<T, Args..., inner_allocator_type>::value` and | |
923 | `is_constructible<T, allocator_arg_t, inner_allocator_type, Args...>::value`) | |
924 | will be used to detect if the allocator must be propagated with suffix or prefix allocator arguments. | |
925 | ||
926 | [endsect] | |
927 | ||
928 | [section:insertion_hints Insertion hints in associative containers and preserving | |
929 | insertion ordering for elements with equivalent keys] | |
930 | ||
931 | [@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#233 LWG Issue #233] corrected a defect | |
932 | in C++98 and specified how equivalent keys were to be inserted in associative containers. [*Boost.Container] | |
933 | implements the C++11 changes that were specified in [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html N1780 | |
934 | ['Comments on LWG issue 233: Insertion hints in associative containers]]: | |
935 | ||
936 | * `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. | |
937 | * `a_eq.insert(p,t)`: t is inserted as close as possible to the position just prior to p. | |
938 | ||
939 | [endsect] | |
940 | ||
941 | [section:initializer_lists Initializer lists] | |
942 | ||
943 | [*Boost.Container] supports initialization, assignments and insertions from initializer lists | |
944 | in compilers that implement this feature. | |
945 | ||
946 | [endsect] | |
947 | ||
948 | [section:null_iterators Null Forward Iterators] | |
949 | ||
950 | [*Boost.Container] implements | |
951 | [@http://www.open-std.org/JTC1/sc22/WG21/docs/papers/2013/n3644.pdf C++14 Null Forward Iterators], | |
952 | which means that value-initialized iterators may be compared and compare equal | |
953 | to other value-initialized iterators of the same type. Value initialized iterators behave as if they refer | |
954 | past the end of the same empty sequence (example taken from N3644): | |
955 | ||
956 | [c++] | |
957 | ||
958 | vector<int> v = { ... }; | |
959 | auto ni = vector<int>::iterator(); | |
960 | auto nd = vector<double>::iterator(); | |
961 | ni == ni; // True. | |
962 | nd != nd; // False. | |
963 | v.begin() == ni; // ??? (likely false in practice). | |
964 | v.end() == ni; // ??? (likely false in practice). | |
965 | ni == nd; // Won't compile. | |
966 | ||
967 | [endsect] | |
968 | ||
969 | [section:forward_list `forward_list<T>`] | |
970 | ||
971 | [*Boost.Container] does not offer C++11 `forward_list` container yet, but it will be available in future | |
972 | versions. | |
973 | ||
974 | [endsect] | |
975 | ||
976 | [section:vector_exception_guarantees `vector` vs. `std::vector` exception guarantees] | |
977 | ||
978 | [classref boost::container::vector vector] does not support the strong exception guarantees | |
979 | given by `std::vector` in functions like `insert`, `push_back`, `emplace`, `emplace_back`, | |
980 | `resize`, `reserve` or `shrink_to_fit` for either copyable or no-throw moveable classes. | |
981 | In C++11 [@http://en.cppreference.com/w/cpp/utility/move_if_noexcept move_if_noexcept] is used | |
982 | to maintain C++03 exception safety guarantees combined with C++11 move semantics. | |
983 | This strong exception guarantee degrades the insertion performance of copyable and throwing-moveable types, | |
984 | degrading moves to copies when such types are inserted in the vector using the aforementioned | |
985 | members. | |
986 | ||
987 | This strong exception guarantee also precludes the possibility of using some type of | |
988 | in-place reallocations that can further improve the insertion performance of `vector` See | |
989 | [link container.extended_functionality.extended_allocators Extended Allocators] to know more | |
990 | about these optimizations. | |
991 | ||
992 | [classref boost::container::vector vector] always uses move constructors/assignments | |
993 | to rearrange elements in the vector and uses memory expansion mechanisms if the allocator supports them, | |
994 | while offering only basic safety guarantees. It trades off exception guarantees for an improved performance. | |
995 | ||
996 | [endsect] | |
997 | ||
998 | [section:container_const_reference_parameters Parameter taken by const reference that can be changed] | |
999 | ||
1000 | Several container operations use a parameter taken by const reference that can be changed during execution of the function. | |
1001 | [@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#526 LWG Issue 526 | |
1002 | (['Is it undefined if a function in the standard changes in parameters?])] | |
1003 | discusses them: | |
1004 | ||
1005 | [c++] | |
1006 | ||
1007 | //Given std::vector<int> v | |
1008 | v.insert(v.begin(), v[2]); | |
1009 | //v[2] can be changed by moving elements of vector | |
1010 | ||
1011 | //Given std::list<int> l: | |
1012 | l.remove(*l.begin()) | |
1013 | //The operation could delete the first element, and then continue trying to access it. | |
1014 | ||
1015 | The adopted resolution, NAD (Not A Defect), implies that previous operations must be well-defined. This requires code | |
1016 | to detect a reference to an inserted element and an additional copy in that case, impacting performance even when | |
1017 | references to already inserted objects are not used. Note that equivalent functions taking rvalue references or | |
1018 | iterator ranges require elements not already inserted in the container. | |
1019 | ||
1020 | [*Boost.Container] prioritizes performance and has not implemented the NAD resolution: | |
1021 | in functions that might modify the argument, the library requires references to elements not stored | |
1022 | in the container. Using references to inserted elements yields to undefined behaviour (although in debug mode, this | |
1023 | precondition violation could be notified via BOOST_ASSERT). | |
1024 | ||
1025 | [endsect] | |
1026 | ||
1027 | [section:Vector_bool `vector<bool>` specialization] | |
1028 | ||
1029 | `vector<bool>` specialization has been quite problematic, and there have been several | |
1030 | unsuccessful tries to deprecate or remove it from the standard. [*Boost.Container] does not implement it | |
1031 | as there is a superior [@http://www.boost.org/libs/dynamic_bitset/ Boost.DynamicBitset] | |
1032 | solution. For issues with `vector<bool>` see the following papers: | |
1033 | ||
1034 | * [@http://howardhinnant.github.io/onvectorbool.html On `vector<bool>`] | |
1035 | * [@http://www.gotw.ca/publications/N1211.pdf vector<bool>: N1211: More Problems, Better Solutions], | |
1036 | * [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2160.html N2160: Library Issue 96: Fixing vector<bool>], | |
1037 | * [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2204.html N2204 A Specification to deprecate vector<bool>]. | |
1038 | ||
1039 | Quotes: | |
1040 | ||
1041 | * ["['But it is a shame that the C++ committee gave this excellent data structure the name vector<bool> and | |
1042 | that it gives no guidance nor encouragement on the critical generic algorithms that need to be optimized for this | |
1043 | data structure. Consequently, few std::lib implementations go to this trouble.]] | |
1044 | ||
1045 | * ["['In 1998, admitting that the committee made a mistake was controversial. | |
1046 | Since then Java has had to deprecate such significant portions of their libraries | |
1047 | that the idea C++ would be ridiculed for deprecating a single minor template specialization seems quaint.]] | |
1048 | ||
1049 | * ["['`vector<bool>` is not a container and `vector<bool>::iterator` is not a random-access iterator | |
1050 | (or even a forward or bidirectional iterator either, for that matter). This has already broken user code | |
1051 | in the field in mysterious ways.]] | |
1052 | ||
1053 | * ["['`vector<bool>` forces a specific (and potentially bad) optimization choice on all users by enshrining | |
1054 | it in the standard. The optimization is premature; different users have different requirements. This too | |
1055 | has already hurt users who have been forced to implement workarounds to disable the 'optimization' | |
1056 | (e.g., by using a vector<char> and manually casting to/from bool).]] | |
1057 | ||
1058 | So `boost::container::vector<bool>::iterator` returns real `bool` references and works as a fully compliant container. | |
1059 | If you need a memory optimized version of `boost::container::vector<bool>`, please use | |
1060 | [@http://www.boost.org/libs/dynamic_bitset/ Boost.DynamicBitset]. | |
1061 | ||
1062 | [endsect] | |
1063 | ||
1064 | [section:non_standard_memset_initialization Non-standard value initialization using `std::memset`] | |
1065 | ||
1066 | [*Boost.Container] uses `std::memset` with a zero value to initialize some types as in most platforms this | |
1067 | initialization yields to the desired value initialization with improved performance. | |
1068 | ||
1069 | Following the C11 standard, [*Boost.Container] assumes that ['for any integer type, | |
1070 | the object representation where all the bits are zero shall be a representation of the value | |
1071 | zero in that type]. Since `_Bool`/`wchar_t`/`char16_t`/`char32_t` are also integer types in C, it considers | |
1072 | all C++ integral types as initializable via `std::memset`. | |
1073 | ||
1074 | By default, [*Boost.Container] also considers floating point types to be initializable using `std::memset`. | |
1075 | Most platforms are compatible with this initialization, but in case this initialization is not desirable the | |
1076 | user can `#define BOOST_CONTAINER_MEMZEROED_FLOATING_POINT_IS_NOT_ZERO` before including library headers. | |
1077 | ||
1078 | By default, it also considers pointer types (pointer and pointer to function types, excluding | |
1079 | member object and member function pointers) to be initializable using `std::memset`. | |
1080 | Most platforms are compatible with this initialization, but in case this initialization is not desired the | |
1081 | user can `#define BOOST_CONTAINER_MEMZEROED_POINTER_IS_NOT_ZERO` before including library headers. | |
1082 | ||
1083 | If neither `BOOST_CONTAINER_MEMZEROED_FLOATING_POINT_IS_NOT_ZERO` nor | |
1084 | `BOOST_CONTAINER_MEMZEROED_POINTER_IS_NOT_ZERO` is defined [*Boost.Container] also considers POD | |
1085 | types to be value initializable via `std::memset` with value zero. | |
1086 | ||
1087 | [endsect] | |
1088 | ||
1089 | [endsect] | |
1090 | ||
1091 | [section:known_issues Known Issues] | |
1092 | ||
1093 | [section:move_emulation_limitations Move emulation limitations in C++03 compilers] | |
1094 | ||
1095 | [*Boost.Container] uses [*Boost.Move] to implement move semantics both in C++03 and C++11 compilers. | |
1096 | However, as explained in | |
1097 | [@http://www.boost.org/doc/libs/release/doc/html/move/emulation_limitations.html Emulation limitations], | |
1098 | there are some limitations in C++03 compilers that might surprise [*Boost.Container] users. | |
1099 | ||
1100 | The most noticeable problem is when [*Boost.Container] containers are placed in a struct with a | |
1101 | compiler-generated assignment operator: | |
1102 | ||
1103 | [c++] | |
1104 | ||
1105 | class holder | |
1106 | { | |
1107 | boost::container::vector<MyType> vect; | |
1108 | }; | |
1109 | ||
1110 | void func(const holder& h) | |
1111 | { | |
1112 | holder copy_h(h); //<--- ERROR: can't convert 'const holder&' to 'holder&' | |
1113 | //Compiler-generated copy constructor is non-const: | |
1114 | // holder& operator(holder &) | |
1115 | //!!! | |
1116 | } | |
1117 | ||
1118 | This limitation forces the user to define a const version of the copy assignment, in all classes | |
1119 | holding containers, which might be annoying in some cases. | |
1120 | ||
1121 | [endsect] | |
1122 | ||
1123 | [endsect] | |
1124 | ||
1125 | [section:history_and_reasons History and reasons to use Boost.Container] | |
1126 | ||
1127 | [section:boost_container_history Boost.Container history] | |
1128 | ||
1129 | [*Boost.Container] is a product of a long development effort that started | |
1130 | [@http://lists.boost.org/Archives/boost/2004/11/76263.php in 2004 with the experimental Shmem library], | |
1131 | which pioneered the use of standard containers in shared memory. Shmem included modified SGI STL container | |
1132 | code tweaked to support non-raw `allocator::pointer` types and stateful allocators. Once reviewed, | |
1133 | Shmem was accepted as [@http://www.boost.org/libs/interprocess/ Boost.Interprocess] and this library | |
1134 | continued to refine and improve those containers. | |
1135 | ||
1136 | In 2007, container code from node containers (`map`, `list`, `slist`) was rewritten, refactored | |
1137 | and expanded to build the intrusive container library [@http://www.boost.org/libs/intrusive/ Boost.Intrusive]. | |
1138 | [*Boost.Interprocess] containers were refactored to take advantage of [*Boost.Intrusive] containers and | |
1139 | code duplication was minimized. Both libraries continued to gain support and bug fixes for years. | |
1140 | They introduced move semantics, emplacement insertion and more features of then unreleased C++0x | |
1141 | standard. | |
1142 | ||
1143 | [*Boost.Interprocess] containers were always standard compliant, and those containers and new | |
1144 | containers like `stable_vector` and `flat_[multi]set/map` were used outside [*Boost.Interprocess] | |
1145 | with success. As containers were mature enough to get their own library, it was a natural step to | |
1146 | collect them containers and build [*Boost.Container], a library targeted to a wider audience. | |
1147 | ||
1148 | [endsect] | |
1149 | ||
1150 | ||
1151 | [section:Why_boost_container Why Boost.Container?] | |
1152 | ||
1153 | With so many high quality standard library implementations out there, why would you want to | |
1154 | use [*Boost.Container]? There are several reasons for that: | |
1155 | ||
1156 | * If you have a C++03 compiler, you can have access to C++11 features and have an easy | |
1157 | code migration when you change your compiler. | |
1158 | * It's compatible with [*Boost.Interprocess] shared memory allocators. | |
1159 | * You have extremely useful new containers like `stable_vector` and `flat_[multi]set/map`. | |
1160 | * If you work on multiple platforms, you'll have a portable behaviour without depending | |
1161 | on the std-lib implementation conformance of each platform. Some examples: | |
1162 | * Default constructors don't allocate memory at all, which improves performance and | |
1163 | usually implies a no-throw guarantee (if predicate's or allocator's default constructor doesn't throw). | |
1164 | * Small string optimization for [classref boost::container::basic_string basic_string]. | |
1165 | * [link container.extended_functionality Extended functionality] beyond the standard based | |
1166 | on user feedback to improve code performance. | |
1167 | * You need a portable implementation that works when compiling without exceptions support or | |
1168 | you need to customize the error handling when a container needs to signal an exceptional error. | |
1169 | ||
1170 | [endsect] | |
1171 | ||
1172 | [endsect] | |
1173 | ||
1174 | [include auto_index_helpers.qbk] | |
1175 | ||
1176 | [section:index Indexes] | |
1177 | ||
1178 | [named_index class_name Class Index] | |
1179 | [named_index typedef_name Typedef Index] | |
1180 | [named_index function_name Function Index] | |
1181 | [/named_index macro_name Macro Index] | |
1182 | [/index] | |
1183 | ||
1184 | [endsect] | |
1185 | ||
1186 | [xinclude autodoc.xml] | |
1187 | ||
1188 | [section:acknowledgements_notes Acknowledgements, notes and links] | |
1189 | ||
1190 | * Original standard container code comes from [@http://www.sgi.com/tech/stl/ SGI STL library], | |
1191 | which enhanced the original HP STL code. Code was rewritten for | |
1192 | [*Boost.Interprocess] and moved to [*Boost.Intrusive]. Many thanks to Alexander Stepanov, Meng Lee, David Musser, | |
1193 | Matt Austern... and all HP and SGI STL developers. | |
1194 | ||
1195 | * `flat_[multi]_map/set` containers were originally based on [@http://en.wikipedia.org/wiki/Loki_%28C%2B%2B%29 Loki's] | |
1196 | AssocVector class. Code was rewritten and expanded for [*Boost.Interprocess], so thanks to Andrei Alexandrescu. | |
1197 | ||
1198 | * `stable_vector` was invented and coded by | |
1199 | [@http://bannalia.blogspot.com/2008/09/introducing-stablevector.html Joaqu\u00EDn M. L\u00F3pez Mu\u00F1oz], | |
1200 | then adapted for [*Boost.Interprocess]. Thanks for such a great container. | |
1201 | ||
1202 | * `static_vector` was based on Andrew Hundt's and Adam Wulkiewicz's high-performance `varray` class. | |
1203 | Many performance improvements of `vector` were also inspired by their implementation. Thanks! | |
1204 | ||
1205 | * Howard Hinnant's help and advices were essential when implementing move semantics, | |
1206 | improving allocator support or implementing small string optimization. Thanks Howard | |
1207 | for your wonderful standard library implementations. | |
1208 | ||
1209 | * And finally thanks to all Boosters who helped all these years, improving, fixing and | |
1210 | reviewing all my libraries. | |
1211 | ||
1212 | [endsect] | |
1213 | ||
1214 | [section:release_notes Release Notes] | |
1215 | ||
1216 | [section:release_notes_boost_1_62_00 Boost 1.62 Release] | |
1217 | ||
1218 | * Fixed bugs: | |
1219 | * [@https://svn.boost.org/trac/boost/ticket/9481 Trac #9481: ['"Minor comment typo in Boost.Container"]]. | |
1220 | * [@https://svn.boost.org/trac/boost/ticket/9689 Trac #9689: ['"Add piecewise_construct to boost::container"]]. | |
1221 | * [@https://svn.boost.org/trac/boost/ticket/11170 Trac #11170: ['"Doc slip for index_of"]]. | |
1222 | * [@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"]]. | |
1223 | * [@https://svn.boost.org/trac/boost/ticket/12117 Trac #12117: ['"flat_set constructor with ordered_unique_range"]]. | |
1224 | * [@https://svn.boost.org/trac/boost/ticket/12177 Trac #12177: ['"vector::priv_merge uses unqualified uintptr_t"]]. | |
1225 | * [@https://svn.boost.org/trac/boost/ticket/12183 Trac #12183: ['"GCC 6.1 thinks boost::container::string violates strict aliasing"]]. | |
1226 | * [@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"]]. | |
1227 | * [@https://svn.boost.org/trac/boost/ticket/12273 Trac #12273: ['"static_vector max_size() and capacity() should be constant expressions"]]. | |
1228 | Added constant `static_vector<>::static_capacity` to use the configured capacity in constant expressions. | |
1229 | * [@https://svn.boost.org/trac/boost/ticket/12286 Trac #12286: ['"PMR flat_map from Boost Container does not compile"]]. | |
1230 | * [@https://svn.boost.org/trac/boost/ticket/12296 Trac #12296: ['"{deque,string} combine for a memory leak"]]. | |
1231 | * [@https://svn.boost.org/trac/boost/ticket/12319 Trac #12319: ['"flat_set` should be nothrow move constructible"]]. | |
1232 | ||
1233 | * Revised noexcept expressions of default and move constructors in all containers. | |
1234 | * Implemented C++17's `insert_or_assign`/`try_emplace` for [classref boost::container::map map] and [classref boost::container::flat_map flat_map]. | |
1235 | * Implemented C++17's [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0083r3.pdf ['Splicing Maps and Sets (Revision 5)]] | |
1236 | for [classref boost::container::map map], [classref boost::container::multimap multimap], | |
1237 | [classref boost::container::set set], [classref boost::container::multiset multiset]. | |
1238 | * Implemented C++17's [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0084r2.pdf ['P0084R2 Emplace Return Type]] | |
1239 | in `deque`, `vector`, `stable_vector`, `small_vector`, `static_vector`, `list` and `slist`. | |
1240 | ||
1241 | [endsect] | |
1242 | ||
1243 | [section:release_notes_boost_1_61_00 Boost 1.61 Release] | |
1244 | ||
1245 | * [classref boost::container::small_vector] supports more constructors and assignments. | |
1246 | * Fixed bugs: | |
1247 | * [@https://svn.boost.org/trac/boost/ticket/11820 Trac #11820: ['"compiler error when using operator[] of map"]]. | |
1248 | * [@https://svn.boost.org/trac/boost/ticket/11856 Trac #11856: ['"pool_resource.cpp error: declaration changes meaning"]]. | |
1249 | * [@https://svn.boost.org/trac/boost/ticket/11866 Trac #11866: ['"small_vector does not have range constructor"]]. | |
1250 | * [@https://svn.boost.org/trac/boost/ticket/11867 Trac #11867: ['"small_vector should have constructor and assignment operator taking other small_vector"]]. | |
1251 | * [@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"]]. | |
1252 | * [@https://svn.boost.org/trac/boost/ticket/11957 Trac #11957: ['"static_vector::max_size() is higher than the capacity"]]. | |
1253 | * [@https://svn.boost.org/trac/boost/ticket/12014 Trac #12014: ['"boost::container::set can not insert const (ref) range"]]. | |
1254 | * [@https://github.com/boostorg/container/pull/33 GitHub #33: ['Make sure std::string constructor is available]]. | |
1255 | ||
1256 | [endsect] | |
1257 | ||
1258 | [section:release_notes_boost_1_60_00 Boost 1.60 Release] | |
1259 | ||
1260 | * Implemented [link container.extended_functionality.polymorphic_memory_resources Polymorphic Memory Resources]. | |
1261 | * Add more BOOST_ASSERT checks to test preconditions in some operations (like `pop_back`, `pop_front`, `back`, `front`, etc.) | |
1262 | * Added C++11 `back`/`front` operations to [classref boost::container::basic_string basic_string]. | |
1263 | * Fixed bugs: | |
1264 | * [@https://svn.boost.org/trac/boost/ticket/11627 Trac #11627: ['"small_vector<T,n>::swap() appears to be broken"]]. | |
1265 | * [@https://svn.boost.org/trac/boost/ticket/11628 Trac #11628: ['"small_vector<int,n> iterates over elements in destructor"]]. | |
1266 | * [@https://svn.boost.org/trac/boost/ticket/11697 Trac #11697: ['"Wrong initialization order in tuple copy-constructor"]]. | |
1267 | * [@https://svn.boost.org/trac/boost/ticket/11698 Trac #11698: ['"Missing return statement in static_storage_allocator"]]. | |
1268 | * [@https://github.com/boostorg/container/pull/29 GitHub #29: ['Doc fixes for flap_map complexity requirements]]. | |
1269 | * [@https://github.com/boostorg/container/pull/31 GitHub #31: ['DL_SIZE_IMPL also dereference addr]]. | |
1270 | ||
1271 | [endsect] | |
1272 | ||
1273 | [section:release_notes_boost_1_59_00 Boost 1.59 Release] | |
1274 | ||
1275 | * [@https://github.com/boostorg/container/pull/26 GitHub #26: ['Fix bug in stable_vector::capacity()]]. Thanks to timsong-cpp/Arindam Mukerjee. | |
1276 | * [@https://github.com/boostorg/container/pull/27 GitHub #27: ['fix stable_vector's index_of's doxygen comment]]. Thanks to kariya-mitsuru. | |
1277 | * [@https://svn.boost.org/trac/boost/ticket/11380 Trac #11380: ['"Container library std forward declarations incorrect in std_fwd.hpp on libc++ with gcc"]]. | |
1278 | * [@https://svn.boost.org/trac/boost/ticket/11388 Trac #11388: ['"boost::container::list::emplace_back broken on Visual Studio 2010"]]. | |
1279 | * [@https://svn.boost.org/trac/boost/ticket/11339 Trac #11339: ['"VC12 LNK2005 error with boost::container::adaptive_pool"]]. | |
1280 | ||
1281 | [endsect] | |
1282 | ||
1283 | [section:release_notes_boost_1_58_00 Boost 1.58 Release] | |
1284 | * Experimental [classref boost::container::small_vector small_vector] container. | |
1285 | * Massive dependency reorganization. Now [*Boost.Container] depends on very basic utilities like Boost.Core | |
1286 | and [*Boost.Intrusive]. Preprocessed code size have decreased considerably and compilation times have improved. | |
1287 | * Added `nth` and `index_of` functions to containers with random-access iterators (except `basic_string`). | |
1288 | * Added C++17's `allocator_traits<Allocator>::is_always_equal`. | |
1289 | * Updated containers to implement new constructors as specified in | |
1290 | [@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#2210 2210. Missing allocator-extended constructor for allocator-aware containers]. | |
1291 | * Fixed bugs: | |
1292 | * [@https://svn.boost.org/trac/boost/ticket/9931 Trac #9931: ['"flat_map::insert(ordered_unique_range_t...) fails with move_iterators"]] (reopened). | |
1293 | * [@https://svn.boost.org/trac/boost/ticket/11076 Trac #11076: ['"Unqualified calls to memmove/memcpy in container/detail/copy_move_algo.hpp"]]. | |
1294 | * [@https://svn.boost.org/trac/boost/ticket/10790 Trac #10790 (['"long long errors from container"])]. | |
1295 | * [@https://svn.boost.org/trac/boost/ticket/10808 Trac #10808 (['"compare equal operator of vector is broken"])]. | |
1296 | * [@https://svn.boost.org/trac/boost/ticket/10930 Trac #10930 (['"container std_fwd.hpp neglects custom std namespaces"])]. | |
1297 | * [@https://svn.boost.org/trac/boost/ticket/11139 Trac #11139 (['"boost::container::vector<std::shared_ptr<const T>...>::const_iterator allows changing dereferenced elements"])]. | |
1298 | * [*Source Breaking]: [classref boost::container::scoped_allocator_adaptor scoped_allocator_adaptor]'s | |
1299 | `propagate_on_container_copy_assignment`, `propagate_on_container_move_assignment` and `propagate_on_container_swap` | |
1300 | are no longer `::boost::integral_constant<bool, true/false>` types. The dependency reorganization needed to break | |
1301 | with those classes to avoid MPL dependencies, and interoperability with `std::integral_constant` was not guaranteed. | |
1302 | Code assumming `boost::true_type/boost::false_type` on this will not compile. As a workaround, use the guaranteed internal | |
1303 | `::value` constant: `::boost::integral_constant<bool, scoped_allocator_adaptor<Allocator>::propagate_on_container_move_assignment::value>`. | |
1304 | ||
1305 | [endsect] | |
1306 | ||
1307 | [section:release_notes_boost_1_57_00 Boost 1.57 Release] | |
1308 | * Added support for `initializer_list`. Contributed by Robert Matusewicz. | |
1309 | * Fixed double destruction bugs in vector and backward expansion capable allocators. | |
1310 | * Fixed bugs: | |
1311 | * [@https://svn.boost.org/trac/boost/ticket/10263 Trac #10263 (['"AIX 6.1 bug with sched_yield() function out of scope"])]. | |
1312 | * [@https://github.com/boostorg/container/pull/16 GitHub #16: ['Fix iterators of incomplete type containers]]. Thanks to Mikael Persson. | |
1313 | ||
1314 | [endsect] | |
1315 | ||
1316 | [section:release_notes_boost_1_56_00 Boost 1.56 Release] | |
1317 | ||
1318 | * Added DlMalloc-based [link container.extended_functionality.extended_allocators Extended Allocators]. | |
1319 | ||
1320 | * [link container.extended_functionality.configurable_tree_based_associative_containers Improved configurability] | |
1321 | of tree-based ordered associative containers. AVL, Scapegoat and Splay trees are now available | |
1322 | to implement [classref boost::container::set set], [classref boost::container::multiset multiset], | |
1323 | [classref boost::container::map map] and [classref boost::container::multimap multimap]. | |
1324 | ||
1325 | * Fixed bugs: | |
1326 | * [@https://svn.boost.org/trac/boost/ticket/9338 #9338: ['"VS2005 compiler errors in swap() definition after including container/memory_util.hpp"]]. | |
1327 | * [@https://svn.boost.org/trac/boost/ticket/9637 #9637: ['"Boost.Container vector::resize() performance issue"]]. | |
1328 | * [@https://svn.boost.org/trac/boost/ticket/9648 #9648: ['"string construction optimization - char_traits::copy could be used ..."]]. | |
1329 | * [@https://svn.boost.org/trac/boost/ticket/9801 #9801: ['"I can no longer create and iterator_range from a stable_vector"]]. | |
1330 | * [@https://svn.boost.org/trac/boost/ticket/9915 #9915: ['"Documentation issues regarding vector constructors and resize methods - value/default initialization"]]. | |
1331 | * [@https://svn.boost.org/trac/boost/ticket/9916 #9916: ['"Allocator propagation incorrect in the assignment operator of most"]]. | |
1332 | * [@https://svn.boost.org/trac/boost/ticket/9931 #9931: ['"flat_map::insert(ordered_unique_range_t...) fails with move_iterators"]]. | |
1333 | * [@https://svn.boost.org/trac/boost/ticket/9955 #9955: ['"Using memcpy with overlapped buffers in vector"]]. | |
1334 | ||
1335 | [endsect] | |
1336 | ||
1337 | [section:release_notes_boost_1_55_00 Boost 1.55 Release] | |
1338 | ||
1339 | * Implemented [link container.main_features.scary_iterators SCARY iterators]. | |
1340 | ||
1341 | * Fixed bugs [@https://svn.boost.org/trac/boost/ticket/8269 #8269], | |
1342 | [@https://svn.boost.org/trac/boost/ticket/8473 #8473], | |
1343 | [@https://svn.boost.org/trac/boost/ticket/8892 #8892], | |
1344 | [@https://svn.boost.org/trac/boost/ticket/9009 #9009], | |
1345 | [@https://svn.boost.org/trac/boost/ticket/9064 #9064], | |
1346 | [@https://svn.boost.org/trac/boost/ticket/9092 #9092], | |
1347 | [@https://svn.boost.org/trac/boost/ticket/9108 #9108], | |
1348 | [@https://svn.boost.org/trac/boost/ticket/9166 #9166]. | |
1349 | ||
1350 | * Added `default initialization` insertion functions to vector-like containers | |
1351 | with new overloads taking `default_init_t` as an argument instead of `const value_type &`. | |
1352 | ||
1353 | [endsect] | |
1354 | ||
1355 | [section:release_notes_boost_1_54_00 Boost 1.54 Release] | |
1356 | ||
1357 | * Added experimental `static_vector` class, based on Andrew Hundt's and Adam Wulkiewicz's | |
1358 | high performance `varray` class. | |
1359 | * Speed improvements in `vector` constructors/copy/move/swap, dispatching to memcpy when possible. | |
1360 | * Support for `BOOST_NO_EXCEPTIONS` [@https://svn.boost.org/trac/boost/ticket/7227 #7227]. | |
1361 | * Fixed bugs [@https://svn.boost.org/trac/boost/ticket/7921 #7921], | |
1362 | [@https://svn.boost.org/trac/boost/ticket/7969 #7969], | |
1363 | [@https://svn.boost.org/trac/boost/ticket/8118 #8118], | |
1364 | [@https://svn.boost.org/trac/boost/ticket/8294 #8294], | |
1365 | [@https://svn.boost.org/trac/boost/ticket/8553 #8553], | |
1366 | [@https://svn.boost.org/trac/boost/ticket/8724 #8724]. | |
1367 | ||
1368 | [endsect] | |
1369 | ||
1370 | [section:release_notes_boost_1_53_00 Boost 1.53 Release] | |
1371 | ||
1372 | * Fixed bug [@https://svn.boost.org/trac/boost/ticket/7650 #7650]. | |
1373 | * Improved `vector`'s insertion performance. | |
1374 | * Changed again experimental multiallocation interface for better performance (still experimental). | |
1375 | * Added no exception support for those willing to disable exceptions in their compilers. | |
1376 | * Fixed GCC -Wshadow warnings. | |
1377 | * Replaced deprecated BOOST_NO_XXXX with newer BOOST_NO_CXX11_XXX macros. | |
1378 | ||
1379 | [endsect] | |
1380 | ||
1381 | [section:release_notes_boost_1_52_00 Boost 1.52 Release] | |
1382 | ||
1383 | * Improved `stable_vector`'s template code bloat and type safety. | |
1384 | * Changed typedefs and reordered functions of sequence containers to improve doxygen documentation. | |
1385 | * Fixed bugs | |
1386 | [@https://svn.boost.org/trac/boost/ticket/6615 #6615], | |
1387 | [@https://svn.boost.org/trac/boost/ticket/7139 #7139], | |
1388 | [@https://svn.boost.org/trac/boost/ticket/7215 #7215], | |
1389 | [@https://svn.boost.org/trac/boost/ticket/7232 #7232], | |
1390 | [@https://svn.boost.org/trac/boost/ticket/7269 #7269], | |
1391 | [@https://svn.boost.org/trac/boost/ticket/7439 #7439]. | |
1392 | * Implemented LWG Issue #149 (range insertion now returns an iterator) & cleaned up insertion code in most containers | |
1393 | * Corrected aliasing errors. | |
1394 | ||
1395 | [endsect] | |
1396 | ||
1397 | [section:release_notes_boost_1_51_00 Boost 1.51 Release] | |
1398 | ||
1399 | * Fixed bugs | |
1400 | [@https://svn.boost.org/trac/boost/ticket/6763 #6763], | |
1401 | [@https://svn.boost.org/trac/boost/ticket/6803 #6803], | |
1402 | [@https://svn.boost.org/trac/boost/ticket/7114 #7114], | |
1403 | [@https://svn.boost.org/trac/boost/ticket/7103 #7103]. | |
1404 | [@https://svn.boost.org/trac/boost/ticket/7123 #7123], | |
1405 | ||
1406 | [endsect] | |
1407 | ||
1408 | [section:release_notes_boost_1_50_00 Boost 1.50 Release] | |
1409 | ||
1410 | * Added Scoped Allocator Model support. | |
1411 | ||
1412 | * Fixed bugs | |
1413 | [@https://svn.boost.org/trac/boost/ticket/6606 #6606], | |
1414 | [@https://svn.boost.org/trac/boost/ticket/6533 #6533], | |
1415 | [@https://svn.boost.org/trac/boost/ticket/6536 #6536], | |
1416 | [@https://svn.boost.org/trac/boost/ticket/6566 #6566], | |
1417 | [@https://svn.boost.org/trac/boost/ticket/6575 #6575], | |
1418 | ||
1419 | [endsect] | |
1420 | ||
1421 | ||
1422 | [section:release_notes_boost_1_49_00 Boost 1.49 Release] | |
1423 | ||
1424 | * Fixed bugs | |
1425 | [@https://svn.boost.org/trac/boost/ticket/6540 #6540], | |
1426 | [@https://svn.boost.org/trac/boost/ticket/6499 #6499], | |
1427 | [@https://svn.boost.org/trac/boost/ticket/6336 #6336], | |
1428 | [@https://svn.boost.org/trac/boost/ticket/6335 #6335], | |
1429 | [@https://svn.boost.org/trac/boost/ticket/6287 #6287], | |
1430 | [@https://svn.boost.org/trac/boost/ticket/6205 #6205], | |
1431 | [@https://svn.boost.org/trac/boost/ticket/4383 #4383]. | |
1432 | ||
1433 | * Added `allocator_traits` support for both C++11 and C++03 | |
1434 | compilers through an internal `allocator_traits` clone. | |
1435 | ||
1436 | [endsect] | |
1437 | ||
1438 | [section:release_notes_boost_1_48_00 Boost 1.48 Release] | |
1439 | ||
1440 | * First release. Container code from [*Boost.Interprocess] was deleted | |
1441 | and redirected to [*Boost.Container ] via using directives. | |
1442 | ||
1443 | [endsect] | |
1444 | ||
1445 | [endsect] |