[/
- / Copyright (c) 2009-2012 Ion Gazta\u00F1aga
+ / Copyright (c) 2009-2013 Ion Gazta\u00F1aga
/
/ Distributed under the Boost Software License, Version 1.0. (See accompanying
/ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
[library Boost.Container
[quickbook 1.5]
[authors [Gaztanaga, Ion]]
- [copyright 2009-2012 Ion Gaztanaga]
+ [copyright 2009-2013 Ion Gaztanaga]
[id container]
[dirname container]
[purpose Containers library]
* The library offers new useful containers:
* [classref boost::container::flat_map flat_map],
[classref boost::container::flat_set flat_set],
- [classref boost::container::flat_multiset flat_multiset] and
+ [classref boost::container::flat_multimap flat_multimap] and
[classref boost::container::flat_multiset flat_multiset]: drop-in
replacements for standard associative containers but more memory friendly and with faster
searches.
[section:introduction_building_container Building Boost.Container]
-There is no need to compile [*Boost.Container], since it's
-a header only library. Just include your Boost header directory in your
-compiler include path.
+There is no need to compile [*Boost.Container] if you don't use [link container.extended_functionality.extended_allocators Extended Allocators]
+since in that case it's a header-only library. Just include your Boost header directory in your compiler include path.
+
+[link container.extended_functionality.extended_allocators Extended Allocators] are
+implemented as a separately compiled library, so you must install binaries in a location that can be found by your linker
+when using these classes. If you followed the [@http://www.boost.org/doc/libs/release/more/getting_started/index.html Boost Getting Started] instructions,
+that's already been done for you.
[endsect]
[endsect]
+[section:main_features Main features]
+
[section:move_emplace Efficient insertion]
Move semantics and placement insertion are two features brought by C++11 containers
C++11 standard is also cautious about incomplete types and STL: ["['17.6.4.8 Other functions (...) 2.
the effects are undefined in the following cases: (...) In particular - if an incomplete type (3.9)
is used as a template argument when instantiating a template component,
-unless specifically allowed for that component]]. Fortunately [*Boost.Container] containers are designed
-to support type erasure and recursive types, so let's see some examples:
+unless specifically allowed for that component]].
+
+Fortunately all [*Boost.Container] containers except
+[classref boost::container::static_vector static_vector] and
+[classref boost::container::basic_string basic_string] are designed to support incomplete types.
+[classref boost::container::static_vector static_vector] is special because
+it statically allocates memory for `value_type` and this requires complete types and
+[classref boost::container::basic_string basic_string] implements Small String Optimization which
+also requires complete types.
+
+[*Boost.Container] containers supporting incomplete types also support instantiating iterators to
+those incomplete elements.
[section:recursive_containers Recursive containers]
-All containers offered by [*Boost.Container] can be used to define recursive containers:
+Most [*Boost.Container] containers can be used to define recursive containers:
[import ../example/doc_recursive_containers.cpp]
[doc_recursive_containers]
[endsect]
+[section:scary_iterators SCARY iterators]
+
+The paper N2913, titled [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2913.pdf,
+SCARY Iterator Assignment and Initialization], proposed a requirement that a standard container's
+iterator types have no dependency on any type argument apart from the container's `value_type`,
+`difference_type`, `pointer type`, and `const_pointer` type. In particular, according to the proposal,
+the types of a standard container's iterators should not depend on the container's `key_compare`,
+`hasher`, `key_equal`, or `allocator` types.
+
+That paper demonstrated that SCARY operations were crucial to the performant implementation of common
+design patterns using STL components. It showed that implementations that support SCARY operations reduce
+object code bloat by eliminating redundant specializations of iterator and algorithm templates.
+
+[*Boost.Container] containers implement SCARY iterators so the iterator type of a container is only dependent
+on the `allocator_traits<allocator_type>::pointer` type (the pointer type of the `value_type` to be inserted
+in the container). Reference types and all other typedefs are deduced from the pointer type using the
+C++11 `pointer_traits` utility. This leads to lower code bloat in algorithms and classes templated on
+iterators.
+
+[endsect]
+
+[section:other_features Other features]
+
+* Default constructors don't allocate memory which improves performance and
+ usually implies a no-throw guarantee (if predicate's or allocator's default constructor doesn't throw).
+
+* Small string optimization for [classref boost::container::basic_string basic_string],
+ with an internal buffer of 11/23 bytes (32/64 bit systems)
+ [*without] increasing the usual `sizeof` of the string (3 words).
+
+* `[multi]set/map` containers are size optimized embedding the color bit of the red-black tree nodes
+ in the parent pointer.
+
+* `[multi]set/map` containers use no recursive functions so stack problems are avoided.
+
+[endsect]
+
+[endsect]
+
+[section:exception_handling Boost.Container and C++ exceptions]
+
+In some environments, such as game development or embedded systems, C++ exceptions are disabled or a customized error handling is needed.
+According to document [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html N2271 EASTL -- Electronic Arts Standard Template Library]
+exceptions can be disabled for several reasons:
+
+* ["['Exception handling incurs some kind of cost in all compiler implementations, including those that avoid
+ the cost during normal execution. However, in some cases this cost may arguably offset the cost of the code that it is replacing.]]
+* ["['Exception handling is often agreed to be a superior solution for handling a large range of function return values. However,
+ avoiding the creation of functions that need large ranges of return values is superior to using exception handling to handle such values.]]
+* ["['Using exception handling correctly can be difficult in the case of complex software.]]
+* ["['The execution of throw and catch can be significantly expensive with some implementations.]]
+* ["['Exception handling violates the don't-pay-for-what-you-don't-use design of C++, as it incurs overhead in any non-leaf function that
+ has destructible stack objects regardless of whether they use exception handling.]]
+* ["['The approach that game software usually takes is to avoid the need for exception handling where possible; avoid the possibility
+ of circumstances that may lead to exceptions. For example, verify up front that there is enough memory for a subsystem to do its job
+ instead of trying to deal with the problem via exception handling or any other means after it occurs.]]
+* ["['However, some game libraries may nevertheless benefit from the use of exception handling. It's best, however,
+ if such libraries keep the exception handling internal lest they force their usage of exception handling on the rest of the application.]]
+
+In order to support environments without C++ exception support or environments with special error handling needs,
+[*Boost.Container] changes error signalling behaviour when `BOOST_CONTAINER_USER_DEFINED_THROW_CALLBACKS` or `BOOST_NO_EXCEPTIONS`
+is defined. The former shall be defined by the user and the latter can be either defined by the user or implicitly defined by [*Boost.Confg]
+when the compiler has been invoked with the appropriate flag (like `-fno-exceptions` in GCC).
+
+When dealing with user-defined classes, (e.g. when constructing user-defined classes):
+
+* If `BOOST_NO_EXCEPTIONS` is defined, the library avoids using `try`/`catch`/`throw` statements. The class writer must handle and
+ propagate error situations internally as no error will be propagated through [*Boost.Container].
+* If `BOOST_NO_EXCEPTIONS` is *not* defined, the library propagates exceptions offering the exception guarantees detailed in the documentation.
+
+When the library needs to throw an exception (such as `out_of_range` when an incorrect index is used in `vector::at`), the library calls
+a throw-callback declared in [headerref boost/container/throw_exception.hpp]:
+
+* If `BOOST_CONTAINER_USER_DEFINED_THROW_CALLBACKS` is defined, then the programmer must provide its own definition for all
+ `throw_xxx` functions. Those functions can't return, they must throw an exception or call `std::exit` or `std::abort`.
+* Else if `BOOST_NO_EXCEPTIONS` is defined, a `BOOST_ASSERT_MSG` assertion is triggered
+ (see [@http://www.boost.org/libs/utility/assert.html Boost.Assert] for more information).
+ If this assertion returns, then `std::abort` is called.
+* Else, an appropriate standard library exception is thrown (like `std::out_of_range`).
+
+[endsect]
+
[section:non_standard_containers Non-standard containers]
[section:stable_vector ['stable_vector]]
-This useful, fully STL-compliant stable container [@http://bannalia.blogspot.com/2008/09/introducing-stablevector.html designed by by Joaqu\u00EDn M. L\u00F3pez Mu\u00F1oz]
+This useful, fully STL-compliant stable container [@http://bannalia.blogspot.com/2008/09/introducing-stablevector.html designed by Joaqu\u00EDn M. L\u00F3pez Mu\u00F1oz]
is an hybrid between `vector` and `list`, providing most of
the features of `vector` except [@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#69 element contiguity].
insertion/deletion, minimal memory overhead, etc.)?
The following image describes the layout of a possible data structure upon which to base the design of a stable vector:
-[$images/stable_vector.png [width 50%] [align center] ]
+[$../../libs/container/doc/html/images/stable_vector.png [width 50%] [align center] ]
Each element is stored in its own separate node. All the nodes are referenced from a contiguous array of pointers, but
also every node contains an "up" pointer referring back to the associated array cell. This up pointer is the key element
attributes:
* Faster lookup than standard associative containers
-* Much faster iteration than standard associative containers
+* Much faster iteration than standard associative containers.
+ Random-access iterators instead of bidirectional iterators.
* Less memory consumption for small objects (and for big objects if `shrink_to_fit` is used)
* Improved cache performance (data is stored in contiguous memory)
* Non-stable iterators (iterators are invalidated when inserting and erasing elements)
[endsect]
+[section:static_vector ['static_vector]]
+
+`static_vector` is an hybrid between `vector` and `array`: like `vector`, it's a sequence container
+with contiguous storage that can change in size, along with the static allocation, low overhead,
+and fixed capacity of `array`. `static_vector` is based on Adam Wulkiewicz and Andrew Hundt's
+high-performance [@https://svn.boost.org/svn/boost/sandbox/varray/doc/html/index.html varray]
+class.
+
+The number of elements in a `static_vector` may vary dynamically up to a fixed capacity
+because elements are stored within the object itself similarly to an array. However, objects are
+initialized as they are inserted into `static_vector` unlike C arrays or `std::array` which must construct
+all elements on instantiation. The behavior of `static_vector` enables the use of statically allocated
+elements in cases with complex object lifetime requirements that would otherwise not be trivially
+possible. Some other properties:
+
+* Random access to elements
+* Constant time insertion and removal of elements at the end
+* Linear time insertion and removal of elements at the beginning or in the middle.
+
+`static_vector` is well suited for use in a buffer, the internal implementation of other
+classes, or use cases where there is a fixed limit to the number of elements that must be stored.
+Embedded and realtime applications where allocation either may not be available or acceptable
+are a particular case where `static_vector` can be beneficial.
+
+[endsect]
+
+[endsect]
+
+[section:extended_functionality Extended functionality]
+
+[section:default_initialialization Default initialization for vector-like containers]
+
+STL and most other containers value initialize new elements in common operations like
+`vector::resize(size_type n)` or `explicit vector::vector(size_type n)`.
+
+In some performance-sensitive environments, where vectors are used as a replacement for
+variable-size buffers for file or network operations,
+[@http://en.cppreference.com/w/cpp/language/value_initialization value initialization]
+is a cost that is not negligible as elements are going to be overwritten by an external source
+shortly after new elements are added to the container.
+
+[*Boost.Container] offers two new members for `vector`, `static_vector` and `stable_vector`:
+`explicit container::container(size_type n, default_init_t)` and
+`explicit container::resize(size_type n, default_init_t)`, where new elements are constructed
+using [@http://en.cppreference.com/w/cpp/language/default_initialization default initialization].
+
+[endsect]
+
+[section:ordered_range_insertion Ordered range insertion for associative containers (['ordered_unique_range], ['ordered_range]) ]
+
+When filling associative containers big performance gains can be achieved if the input range to be inserted
+is guaranteed by the user to be ordered according to the predicate. This can happen when inserting values from a `set` to
+a `multiset` or between different associative container families (`[multi]set/map` vs. `flat_[multi]set/map`).
+
+[*Boost.Container] has some overloads for constructors and insertions taking an `ordered_unique_range_t` or
+an `ordered_range_t` tag parameters as the first argument. When an `ordered_unique_range_t` overload is used, the
+user notifies the container that the input range is ordered according to the container predicate and has no
+duplicates. When an `ordered_range_t` overload is used, the
+user notifies the container that the input range is ordered according to the container predicate but it might
+have duplicates. With this information, the container can avoid multiple predicate calls and improve insertion
+times.
+
+[endsect]
+
+[section:configurable_tree_based_associative_containers Configurable tree-based associative ordered containers]
+
+[classref boost::container::set set], [classref boost::container::multiset multiset],
+[classref boost::container::map map] and [classref boost::container::multimap multimap] associative containers
+are implemented as binary search trees which offer the needed complexity and stability guarantees required by the
+C++ standard for associative containers.
+
+[*Boost.Container] offers the possibility to configure at compile time some parameters of the binary search tree
+implementation. This configuration is passed as the last template parameter and defined using the utility class
+[classref boost::container::tree_assoc_options tree_assoc_options].
+
+The following parameters can be configured:
+
+* The underlying [*tree implementation] type ([classref boost::container::tree_type tree_type]).
+ By default these containers use a red-black tree but the user can use other tree types:
+ * [@http://en.wikipedia.org/wiki/Red%E2%80%93black_tree Red-Black Tree]
+ * [@http://en.wikipedia.org/wiki/Avl_trees AVL tree]
+ * [@http://en.wikipedia.org/wiki/Scapegoat_tree Scapegoat tree]. In this case Insertion and Deletion
+ are amortized O(log n) instead of O(log n).
+ * [@http://en.wikipedia.org/wiki/Splay_tree Splay tree]. In this case Searches, Insertions and Deletions
+ are amortized O(log n) instead of O(log n).
+
+* Whether the [*size saving] mechanisms are used to implement the tree nodes
+ ([classref boost::container::optimize_size optimize_size]). By default this option is activated and is only
+ meaningful to red-black and avl trees (in other cases, this option will be ignored).
+ This option will try to put rebalancing metadata inside the "parent" pointer of the node if the pointer
+ type has enough alignment. Usually, due to alignment issues, the metadata uses the size of a pointer yielding
+ to four pointer size overhead per node, whereas activating this option usually leads to 3 pointer size overhead.
+ Although some mask operations must be performed to extract
+ data from this special "parent" pointer, in several systems this option also improves performance due to the
+ improved cache usage produced by the node size reduction.
+
+See the following example to see how [classref boost::container::tree_assoc_options tree_assoc_options] can be
+used to customize these containers:
+
+[import ../example/doc_custom_tree.cpp]
+[doc_custom_tree]
+
+[endsect]
+
+[section:constant_time_range_splice Constant-time range splice for `(s)list`]
+
+In the first C++ standard `list::size()` was not required to be constant-time,
+and that caused some controversy in the C++ community. Quoting Howard Hinnant's
+[@http://home.roadrunner.com/~hinnant/On_list_size.html ['On List Size]] paper:
+
+[: ['There is a considerable debate on whether `std::list<T>::size()` should be O(1) or O(N).
+The usual argument notes that it is a tradeoff with:]
+
+`splice(iterator position, list& x, iterator first, iterator last);`
+
+['If size() is O(1) and this != &x, then this method must perform a linear operation so that it
+can adjust the size member in each list]]
+
+C++11 definitely required `size()` to be O(1), so range splice became O(N). However,
+Howard Hinnant's paper proposed a new `splice` overload so that even O(1) `list:size()`
+implementations could achieve O(1) range splice when the range size was known to the caller:
+
+[: `void splice(iterator position, list& x, iterator first, iterator last, size_type n);`
+
+ [*Effects]: Inserts elements in the range [first, last) before position and removes the elements from x.
+
+ [*Requires]: [first, last) is a valid range in x. The result is undefined if position is an iterator in the range [first, last). Invalidates only the iterators and references to the spliced elements. n == distance(first, last).
+
+ [*Throws]: Nothing.
+
+ [*Complexity]: Constant time.
+]
+
+This new splice signature allows the client to pass the distance of the input range in.
+This information is often available at the call site. If it is passed in,
+then the operation is constant time, even with an O(1) size.
+
+[*Boost.Container] implements this overload for `list` and a modified version of it for `slist`
+(as `slist::size()` is also `O(1)`).
+
+[endsect]
+
+[section:extended_allocators Extended allocators]
+
+Many C++ programmers have ever wondered where does good old realloc fit in C++. And that's a good question.
+Could we improve [classref boost::container::vector vector] performance using memory expansion mechanisms
+to avoid too many copies? But [classref boost::container::vector vector] is not the only container that
+could benefit from an improved allocator interface: we could take advantage of the insertion of multiple
+elements in [classref boost::container::list list] using a burst allocation mechanism that could amortize
+costs (mutex locks, free memory searches...) that can't be amortized when using single node allocation
+strategies.
+
+These improvements require extending the STL allocator interface and use make use of a new
+general purpose allocator since new and delete don't offer expansion and burst capabilities.
+
+* [*Boost.Container] containers support an extended allocator interface based on an evolution of proposals
+[@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n1953.html N1953: Upgrading the Interface of Allocators using API Versioning],
+[@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2045.html N2045: Improving STL allocators]
+and the article
+[@http://www.drivehq.com/web/igaztanaga/allocplus/ Applying classic memory allocation strategies to C++ containers].
+The extended allocator interface is implemented by [classref boost::container::allocator allocator],
+[classref boost::container::adaptive_pool adaptive_pool] and [classref boost::container::node_allocator node_allocator]
+classes.
+
+* Extended allocators use a modified [@http://g.oswego.edu/dl/html/malloc.html Doug Lea Malloc (DLMalloc)] low-level
+allocator and offers an C API to implement memory expansion and burst allocations. DLmalloc is known to be very size
+and speed efficient, and this allocator is used as the basis of many malloc implementations, including multithreaded
+allocators built above DLmalloc (See [@http://www.malloc.de/en/ ptmalloc2, ptmalloc3] or
+[@http://www.nedprod.com/programs/portable/nedmalloc/ nedmalloc]). This low-level allocator is implemented as
+a separately compiled library whereas [classref boost::container::allocator allocator],
+[classref boost::container::adaptive_pool adaptive_pool] and [classref boost::container::node_allocator node_allocator]
+are header-only classes.
+
+The following extended allocators are provided:
+
+* [classref boost::container::allocator allocator]: This extended allocator offers expansion, shrink-in place
+ and burst allocation capabilities implemented as a thin wrapper around the modified DLMalloc.
+ It can be used with all containers and it should be the default choice when the programmer wants to use
+ extended allocator capabilities.
+
+* [classref boost::container::node_allocator node_allocator]: It's a
+ [@http://www.boost.org/doc/libs/1_55_0/libs/pool/doc/html/boost_pool/pool/pooling.html#boost_pool.pool.pooling.simple Simple Segregated Storage]
+ allocator, similar to [*Boost.Pool] that takes advantage of the modified DLMalloc burst interface. It does not return
+ memory to the DLMalloc allocator (and thus, to the system), unless explicitly requested. It does offer a very small
+ memory overhead so it's suitable for node containers ([boost::container::list list], [boost::container::slist slist]
+ [boost::container::set set]...) that allocate very small `value_type`s and it offers improved node allocation times
+ for single node allocations with respecto to [classref boost::container::allocator allocator].
+
+* [classref boost::container::adaptive_pool adaptive_pool]: It's a low-overhead node allocator that can return memory
+ to the system. The overhead can be very low (< 5% for small nodes) and it's nearly as fast as [classref boost::container::node_allocator node_allocator].
+ It's also suitable for node containers.
+
+Use them simply specifying the new allocator in the corresponding template argument of your favourite container:
+
+[import ../example/doc_extended_allocators.cpp]
+[doc_extended_allocators]
+
[endsect]
-[section:Cpp11_conformance C++11 Conformance]
+[/
+/a__section:previous_element_slist Previous element for slist__a
+/
+/The C++11 `std::forward_list` class implement a singly linked list, similar to `slist`, and these
+/containers only offer forward iterators and implement insertions and splice operations that operate with ranges
+/to be inserted ['after] that position. In those cases, sometimes it's interesting to obtain an iterator pointing
+/to the previous element of another element. This operation can be implemented
+/
+/a__endsect__a
+]
+
+[/
+/a__section:get_stored_allocator Obtain stored allocator__a
+/
+/STL containers offer a `get_allocator()` member to obtain a copy of the allocator that
+/the container is using to allocate and construct elements. For performance reasons, some
+/applications need o
+/
+/http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html
+/
+/a__endsect__a
+/]
+
+[endsect]
+
+[section:Cpp11_conformance C++11/C++14 Conformance]
[*Boost.Container] aims for full C++11 conformance except reasoned deviations,
backporting as much as possible for C++03. Obviously, this conformance is a work
`std::allocator_traits` is the protocol between a container and an allocator, and
an allocator writer can customize its behaviour (should the container propagate it in
move constructor, swap, etc.?) following `allocator_traits` requirements. [*Boost.Container]
-not only supports this model with C++11 but also [*backports it to C++03].
+not only supports this model with C++11 but also [*backports it to C++03] via
+[classref boost::container::allocator_traits boost::container::allocator_traits]. This class
+offers some workarounds for C++03 compilers to achieve the same allocator guarantees as
+`std::allocator_traits`.
-If possible, a single allocator is hold to construct `value_type`. If the container needs an auxiliary
-allocator (e.g. a array allocator used by `deque` or `stable_vector`), that allocator is also
-constructed from the user-supplied allocator when the container is constructed (i.e. it's
-not constructed on the fly when auxiliary memory is needed).
+In [Boost.Container] containers, if possible, a single allocator is hold to construct
+`value_type`s. If the container needs an auxiliary
+allocator (e.g. an array allocator used by `deque` or `stable_vector`), that allocator is also
+stored in the container and initialized from the user-supplied allocator when the
+container is constructed (i.e. it's not constructed on the fly when auxiliary memory is needed).
[endsect]
[*Boost.Container] implements its own `scoped_allocator_adaptor` class and [*backports this feature also
to C++03 compilers]. Due to C++03 limitations, in those compilers
the allocator propagation implemented by `scoped_allocator_adaptor::construct` functions
-will be based on traits([classref boost::container::constructible_with_allocator_suffix constructible_with_allocator_suffix]
+will be based on traits ([classref boost::container::constructible_with_allocator_suffix constructible_with_allocator_suffix]
and [classref boost::container::constructible_with_allocator_prefix constructible_with_allocator_prefix])
proposed in [@http://www.open-std.org/jtc1/sc22/WG21/docs/papers/2008/n2554.pdf
N2554: The Scoped Allocator Model (Rev 2) proposal]. In conforming C++11 compilers or compilers supporting SFINAE
[endsect]
+[section:insertion_hints Insertion hints in associative containers and preserving
+ insertion ordering for elements with equivalent keys]
+
+[@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#233 LWG Issue #233] corrected a defect
+in C++98 and specified how equivalent keys were to be inserted in associative containers. [*Boost.Container]
+implements the C++11 changes that were specified in [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html N1780
+['Comments on LWG issue 233: Insertion hints in associative containers]]:
+
+* `a_eq.insert(t)`: If a range containing elements equivalent to t exists in a_eq, t is inserted at the end of that range.
+* `a_eq.insert(p,t)`: t is inserted as close as possible to the position just prior to p.
+
+[endsect]
+
[section:initializer_lists Initializer lists]
-[*Boost.Container] does not support initializer lists when constructing or assigning containers
-but it will support it for compilers with initialized-list support. This feature won't be backported
-to C++03 compilers.
+[*Boost.Container] supports initialization, assignments and insertions from initializer lists
+in compilers that implement this feature.
+
+[endsect]
+
+[section:null_iterators Null Forward Iterators]
+
+[*Boost.Container] implements
+[@http://www.open-std.org/JTC1/sc22/WG21/docs/papers/2013/n3644.pdf C++14 Null Forward Iterators],
+which means that value-initialized iterators may be compared and compare equal
+to other value-initialized iterators of the same type. Value initialized iterators behave as if they refer
+past the end of the same empty sequence (example taken from N3644):
+
+[c++]
+
+ vector<int> v = { ... };
+ auto ni = vector<int>::iterator();
+ auto nd = vector<double>::iterator();
+ ni == ni; // True.
+ nd != nd; // False.
+ v.begin() == ni; // ??? (likely false in practice).
+ v.end() == ni; // ??? (likely false in practice).
+ ni == nd; // Won't compile.
[endsect]
[endsect]
-[section:Vector_bool `vector<bool>`]
+[section:vector_exception_guarantees `vector` vs. `std::vector` exception guarantees]
+
+[classref boost::container::vector vector] does not support the strong exception guarantees
+given by `std::vector` in functions like `insert`, `push_back`, `emplace`, `emplace_back`,
+`resize`, `reserve` or `shrink_to_fit` for either copyable or no-throw moveable classes.
+In C++11 [@http://en.cppreference.com/w/cpp/utility/move_if_noexcept move_if_noexcept] is used
+to maintain C++03 exception safety guarantees combined with C++11 move semantics.
+This strong exception guarantee degrades the insertion performance of copyable and throwing-moveable types,
+degrading moves to copies when such types are inserted in the vector using the aforementioned
+members.
+
+This strong exception guarantee also precludes the possibility of using some type of
+in-place reallocations that can further improve the insertion performance of `vector` See
+[link container.extended_functionality.extended_allocators Extended Allocators] to know more
+about these optimizations.
+
+[classref boost::container::vector vector] always uses move constructors/assignments
+to rearrange elements in the vector and uses memory expansion mechanisms if the allocator supports them,
+while offering only basic safety guarantees. It trades off exception guarantees for an improved performance.
+
+[endsect]
+
+[section:container_const_reference_parameters Parameter taken by const reference that can be changed]
+
+Several container operations use a parameter taken by const reference that can be changed during execution of the function.
+[@http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-closed.html#526 LWG Issue 526
+ (['Is it undefined if a function in the standard changes in parameters?])]
+discusses them:
+
+[c++]
+
+ //Given std::vector<int> v
+ v.insert(v.begin(), v[2]);
+ //v[2] can be changed by moving elements of vector
+
+ //Given std::list<int> l:
+ l.remove(*l.begin())
+ //The operation could delete the first element, and then continue trying to access it.
+
+The adopted resolution, NAD (Not A Defect), implies that previous operations must be well-defined. This requires code
+to detect a reference to an inserted element and an additional copy in that case, impacting performance even when
+references to already inserted objects are not used. Note that equivalent functions taking rvalue references or
+iterator ranges require elements not already inserted in the container.
+
+[*Boost.Container] prioritizes performance and has not implemented the NAD resolution:
+in functions that might modify the argument, the library requires references to elements not stored
+in the container. Using references to inserted elements yields to undefined behaviour (although in debug mode, this
+precondition violation could be notified via BOOST_ASSERT).
+
+[endsect]
+
+[section:Vector_bool `vector<bool>` specialization]
`vector<bool>` specialization has been quite problematic, and there have been several
unsuccessful tries to deprecate or remove it from the standard. [*Boost.Container] does not implement it
as there is a superior [@http://www.boost.org/libs/dynamic_bitset/ Boost.DynamicBitset]
-solution. For issues with `vector<bool>` see papers
-[@http://www.gotw.ca/publications/N1211.pdf vector<bool>: N1211: More Problems, Better Solutions],
-[@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2160.html N2160: Library Issue 96: Fixing vector<bool>],
-[@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2204.html N2204 A Specification to deprecate vector<bool>].
+solution. For issues with `vector<bool>` see the following papers:
+
+* [@http://home.roadrunner.com/~hinnant/onvectorbool.html On `vector<bool>`]
+* [@http://www.gotw.ca/publications/N1211.pdf vector<bool>: N1211: More Problems, Better Solutions],
+* [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2160.html N2160: Library Issue 96: Fixing vector<bool>],
+* [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2204.html N2204 A Specification to deprecate vector<bool>].
+
+Quotes:
+
+* ["['But it is a shame that the C++ committee gave this excellent data structure the name vector<bool> and
+ that it gives no guidance nor encouragement on the critical generic algorithms that need to be optimized for this
+ data structure. Consequently, few std::lib implementations go to this trouble.]]
* ["['In 1998, admitting that the committee made a mistake was controversial.
Since then Java has had to deprecate such significant portions of their libraries
(e.g., by using a vector<char> and manually casting to/from bool).]]
So `boost::container::vector<bool>::iterator` returns real `bool` references and works as a fully compliant container.
-If you need a memory optimized version of `boost::container::vector<bool>` functionalities, please use
+If you need a memory optimized version of `boost::container::vector<bool>`, please use
[@http://www.boost.org/libs/dynamic_bitset/ Boost.DynamicBitset].
[endsect]
+[section:non_standard_memset_initialization Non-standard value initialization using `std::memset`]
+
+[*Boost.Container] uses `std::memset` with a zero value to initialize some types as in most platforms this
+initialization yields to the desired value initialization with improved performance.
+
+Following the C11 standard, [*Boost.Container] assumes that ['for any integer type,
+the object representation where all the bits are zero shall be a representation of the value
+zero in that type]. Since `_Bool`/`wchar_t`/`char16_t`/`char32_t` are also integer types in C, it considers
+all C++ integral types as initializable via `std::memset`.
+
+By default, [*Boost.Container] also considers floating point types to be initializable using `std::memset`.
+Most platforms are compatible with this initialization, but in case this initialization is not desirable the
+user can `#define BOOST_CONTAINER_MEMZEROED_FLOATING_POINT_IS_NOT_ZERO` before including library headers.
+
+By default, it also considers pointer types (pointer and pointer to function types, excluding
+member object and member function pointers) to be initializable using `std::memset`.
+Most platforms are compatible with this initialization, but in case this initialization is not desired the
+user can `#define BOOST_CONTAINER_MEMZEROED_POINTER_IS_NOT_ZERO` before including library headers.
+
+If neither `BOOST_CONTAINER_MEMZEROED_FLOATING_POINT_IS_NOT_ZERO` nor
+`BOOST_CONTAINER_MEMZEROED_POINTER_IS_NOT_ZERO` is defined [*Boost.Container] also considers POD
+types to be value initializable via `std::memset` with value zero.
+
[endsect]
-[section:other_features Other features]
+[endsect]
-* Default constructors don't allocate memory which improves performance and
- usually implies a no-throw guarantee (if predicate's or allocator's default constructor doesn't throw).
+[section:known_issues Known Issues]
-* Small string optimization for [classref boost::container::basic_string basic_string],
- with an internal buffer of 11/23 bytes (32/64 bit systems)
- [*without] increasing the usual `sizeof` of the string (3 words).
+[section:move_emulation_limitations Move emulation limitations in C++03 compilers]
-* `[multi]set/map` containers are size optimized embedding the color bit of the red-black tree nodes
- in the parent pointer.
+[*Boost.Container] uses [*Boost.Move] to implement move semantics both in C++03 and C++11 compilers.
+However, as explained in
+[@http://www.boost.org/doc/libs/release/doc/html/move/emulation_limitations.html Emulation limitations],
+there are some limitations in C++03 compilers that might surprise [*Boost.Container] users.
-* `[multi]set/map` containers use no recursive functions so stack problems are avoided.
+The most noticeable problem is when [*Boost.Container] containers are placed in a struct with a
+compiler-generated assignment operator:
+
+[c++]
+
+ class holder
+ {
+ boost::container::vector<MyType> vect;
+ };
+
+ void func(const holder& h)
+ {
+ holder copy_h(h); //<--- ERROR: can't convert 'const holder&' to 'holder&'
+ //Compiler-generated copy constructor is non-const:
+ // holder& operator(holder &)
+ //!!!
+ }
+
+This limitation forces the user to define a const version of the copy assignment, in all classes
+holding containers, which might be annoying in some cases.
+
+[endsect]
[endsect]
* Default constructors don't allocate memory at all, which improves performance and
usually implies a no-throw guarantee (if predicate's or allocator's default constructor doesn't throw).
* Small string optimization for [classref boost::container::basic_string basic_string].
-* New extensions beyond the standard based on user feedback to improve code performance.
+* [link container.extended_functionality Extended functionality] beyond the standard based
+ on user feedback to improve code performance.
+* You need a portable implementation that works when compiling without exceptions support or
+ you need to customize the error handling when a container needs to signal an exceptional error.
[endsect]
[section:acknowledgements_notes Acknowledgements, notes and links]
* Original standard container code comes from [@http://www.sgi.com/tech/stl/ SGI STL library],
- which enhanced the original HP STL code. Most of this code was rewritten for
- [*Boost.Interprocess] and moved to [*Boost.Intrusive]. `deque` and `string` containers still
- have fragments of the original SGI code. Many thanks to Alexander Stepanov, Meng Lee, David Musser,
+ which enhanced the original HP STL code. Code was rewritten for
+ [*Boost.Interprocess] and moved to [*Boost.Intrusive]. Many thanks to Alexander Stepanov, Meng Lee, David Musser,
Matt Austern... and all HP and SGI STL developers.
* `flat_[multi]_map/set` containers were originally based on [@http://en.wikipedia.org/wiki/Loki_%28C%2B%2B%29 Loki's]
[@http://bannalia.blogspot.com/2008/09/introducing-stablevector.html Joaqu\u00EDn M. L\u00F3pez Mu\u00F1oz],
then adapted for [*Boost.Interprocess]. Thanks for such a great container.
+* `static_vector` was based on Andrew Hundt's and Adam Wulkiewicz's high-performance `varray` class.
+ Many performance improvements of `vector` were also inspired in their implementation. Thanks!
+
* Howard Hinnant's help and advices were essential when implementing move semantics,
improving allocator support or implementing small string optimization. Thanks Howard
for your wonderful standard library implementations.
[section:release_notes Release Notes]
+[section:release_notes_boost_1_57_00 Boost 1.57 Release]
+* Added support for `initializer_list`. Contributed by Robert Matusewicz.
+* Fixed double destruction bugs in vector and backward expansion capable allocators.
+* Fixed bugs:
+ * [@https://svn.boost.org/trac/boost/ticket/10263 Trac #10263 (['"AIX 6.1 bug with sched_yield() function out of scope"])].
+ * [@https://github.com/boostorg/container/pull/16 GitHub #16: ['Fix iterators of incomplete type containers]]. Thanks to Mikael Persson.
+
+[endsect]
+
+[section:release_notes_boost_1_56_00 Boost 1.56 Release]
+
+* Added DlMalloc-based [link container.extended_functionality.extended_allocators Extended Allocators].
+
+* [link container.extended_functionality.configurable_tree_based_associative_containers Improved configurability]
+ of tree-based ordered associative containers. AVL, Scapegoat and Splay trees are now available
+ to implement [classref boost::container::set set], [classref boost::container::multiset multiset],
+ [classref boost::container::map map] and [classref boost::container::multimap multimap].
+
+* Fixed bugs:
+ * [@https://svn.boost.org/trac/boost/ticket/9338 #9338: ['"VS2005 compiler errors in swap() definition after including container/memory_util.hpp"]].
+ * [@https://svn.boost.org/trac/boost/ticket/9637 #9637: ['"Boost.Container vector::resize() performance issue"]].
+ * [@https://svn.boost.org/trac/boost/ticket/9648 #9648: ['"string construction optimization - char_traits::copy could be used ..."]].
+ * [@https://svn.boost.org/trac/boost/ticket/9801 #9801: ['"I can no longer create and iterator_range from a stable_vector"]].
+ * [@https://svn.boost.org/trac/boost/ticket/9915 #9915: ['"Documentation issues regarding vector constructors and resize methods - value/default initialization"]].
+ * [@https://svn.boost.org/trac/boost/ticket/9916 #9916: ['"Allocator propagation incorrect in the assignment operator of most"]].
+ * [@https://svn.boost.org/trac/boost/ticket/9931 #9931: ['"flat_map::insert(ordered_unique_range_t...) fails with move_iterators"]].
+ * [@https://svn.boost.org/trac/boost/ticket/9955 #9955: ['"Using memcpy with overlapped buffers in vector"]].
+
+[endsect]
+
+[section:release_notes_boost_1_55_00 Boost 1.55 Release]
+
+* Implemented [link container.main_features.scary_iterators SCARY iterators].
+
+* Fixed bugs [@https://svn.boost.org/trac/boost/ticket/8269 #8269],
+ [@https://svn.boost.org/trac/boost/ticket/8473 #8473],
+ [@https://svn.boost.org/trac/boost/ticket/8892 #8892],
+ [@https://svn.boost.org/trac/boost/ticket/9009 #9009],
+ [@https://svn.boost.org/trac/boost/ticket/9064 #9064],
+ [@https://svn.boost.org/trac/boost/ticket/9092 #9092],
+ [@https://svn.boost.org/trac/boost/ticket/9108 #9108],
+ [@https://svn.boost.org/trac/boost/ticket/9166 #9166].
+
+* Added `default initialization` insertion functions to vector-like containers
+ with new overloads taking `default_init_t` as an argument instead of `const value_type &`.
+
+[endsect]
+
+[section:release_notes_boost_1_54_00 Boost 1.54 Release]
+
+* Added experimental `static_vector` class, based on Andrew Hundt's and Adam Wulkiewicz's
+ high performance `varray` class.
+* Speed improvements in `vector` constructors/copy/move/swap, dispatching to memcpy when possible.
+* Support for `BOOST_NO_EXCEPTIONS` [@https://svn.boost.org/trac/boost/ticket/7227 #7227].
+* Fixed bugs [@https://svn.boost.org/trac/boost/ticket/7921 #7921],
+ [@https://svn.boost.org/trac/boost/ticket/7969 #7969],
+ [@https://svn.boost.org/trac/boost/ticket/8118 #8118],
+ [@https://svn.boost.org/trac/boost/ticket/8294 #8294],
+ [@https://svn.boost.org/trac/boost/ticket/8553 #8553],
+ [@https://svn.boost.org/trac/boost/ticket/8724 #8724].
+
+[endsect]
+
+[section:release_notes_boost_1_53_00 Boost 1.53 Release]
+
+* Fixed bug [@https://svn.boost.org/trac/boost/ticket/7650 #7650].
+* Improved `vector`'s insertion performance.
+* Changed again experimental multiallocation interface for better performance (still experimental).
+* Added no exception support for those willing to disable exceptions in their compilers.
+* Fixed GCC -Wshadow warnings.
+* Replaced deprecated BOOST_NO_XXXX with newer BOOST_NO_CXX11_XXX macros.
+
+[endsect]
+
+[section:release_notes_boost_1_52_00 Boost 1.52 Release]
+
+* Improved `stable_vector`'s template code bloat and type safety.
+* Changed typedefs and reordered functions of sequence containers to improve doxygen documentation.
+* Fixed bugs
+ [@https://svn.boost.org/trac/boost/ticket/6615 #6615],
+ [@https://svn.boost.org/trac/boost/ticket/7139 #7139],
+ [@https://svn.boost.org/trac/boost/ticket/7215 #7215],
+ [@https://svn.boost.org/trac/boost/ticket/7232 #7232],
+ [@https://svn.boost.org/trac/boost/ticket/7269 #7269],
+ [@https://svn.boost.org/trac/boost/ticket/7439 #7439].
+* Implemented LWG Issue #149 (range insertion now returns an iterator) & cleaned up insertion code in most containers
+* Corrected aliasing errors.
+
+[endsect]
+
[section:release_notes_boost_1_51_00 Boost 1.51 Release]
* Fixed bugs
[@https://svn.boost.org/trac/boost/ticket/7103 #7103].
[@https://svn.boost.org/trac/boost/ticket/7123 #7123],
-
[endsect]
[section:release_notes_boost_1_50_00 Boost 1.50 Release]
* Added Scoped Allocator Model support.
* Fixed bugs
+ [@https://svn.boost.org/trac/boost/ticket/6606 #6606],
[@https://svn.boost.org/trac/boost/ticket/6533 #6533],
[@https://svn.boost.org/trac/boost/ticket/6536 #6536],
[@https://svn.boost.org/trac/boost/ticket/6566 #6566],
[@https://svn.boost.org/trac/boost/ticket/6575 #6575],
- [@https://svn.boost.org/trac/boost/ticket/6606 #6606],
- [@https://svn.boost.org/trac/boost/ticket/6615 #6615],
-
+
[endsect]
projects / platform / upstream / boost.git / blobdiff