|
|
| (3 intermediate revisions by 3 users not shown) |
| Line 20: |
Line 20: |
| | {{dsc inc|cpp/container/dsc array}} | | {{dsc inc|cpp/container/dsc array}} |
| | {{dsc inc|cpp/container/dsc vector}} | | {{dsc inc|cpp/container/dsc vector}} |
| | + | {{dsc inc|cpp/container/dsc inplace_vector}} |
| | {{dsc inc|cpp/container/dsc deque}} | | {{dsc inc|cpp/container/dsc deque}} |
| | {{dsc inc|cpp/container/dsc forward_list}} | | {{dsc inc|cpp/container/dsc forward_list}} |
| Line 150: |
Line 151: |
| | |} | | |} |
| | | | |
| − | {{todo|iterators from C++23 adaptors}} | + | {{todo|add iterator invalidation for C++23 "flat" adaptors ({{lc|std::flat_set}} etc)}} |
| | + | {{todo|add iterator invalidation for C++26 {{lc|std::inplace_vector}}}} |
| | | | |
| | Here, '''insertion''' refers to any method which adds one or more elements to the container and '''erasure''' refers to any method which removes one or more elements from the container. | | Here, '''insertion''' refers to any method which adds one or more elements to the container and '''erasure''' refers to any method which removes one or more elements from the container. |
| Line 184: |
Line 186: |
| | |- | | |- |
| | |style="width:4em; background:#bcbcff;"| | | |style="width:4em; background:#bcbcff;"| |
| − | |- functions present in C++03 | + | | - functions present in C++03 |
| | |- | | |- |
| | |style="width:4em; background:#bcffbc;"| | | |style="width:4em; background:#bcffbc;"| |
| − | |- functions present since C++11 | + | | - functions present since C++11 |
| | |- | | |- |
| | |style="width:4em; background:#ffeebc;"| | | |style="width:4em; background:#ffeebc;"| |
| − | |- functions present since C++17 | + | | - functions present since C++17 |
| | |- | | |- |
| | |style="width:4em; background:#ffdb99;"| | | |style="width:4em; background:#ffdb99;"| |
| − | |- functions present since C++20 | + | | - functions present since C++20 |
| | |- | | |- |
| | |style="width:4em; background:#ff9966;"| | | |style="width:4em; background:#ff9966;"| |
| − | |- functions present since C++23 | + | | - functions present since C++23 |
| | |} | | |} |
| | + | {{todo|Add C++26 "color" and fill member/non-member function table for {{lc|std::inplace_vector}}}} |
| | | | |
| | ====Member function table==== | | ====Member function table==== |
| − | <div style="display: inline-block;"> | + | <div style="max-width: 100%; max-height: 80vh; overflow: scroll;"> |
| − | <div style="display: inline-block;">
| + | |
| | {|class="wikitable" style="font-size:0.8em; line-height:1em; text-align: center;" | | {|class="wikitable" style="font-size:0.8em; line-height:1em; text-align: center;" |
| | |- | | |- |
| Line 2,015: |
Line 2,017: |
| | !colspan="2"| | | !colspan="2"| |
| | |} | | |} |
| − | </div>
| |
| | </div> | | </div> |
| | | | |
| Line 2,022: |
Line 2,023: |
| | | | |
| | ====Non-member function table==== | | ====Non-member function table==== |
| − | <div style="display: inline-block;"> | + | <div style="max-width: 100%; max-height: 80vh; overflow: scroll;"> |
| | {|class="wikitable" style="font-size:0.8em; line-height:1em; text-align: center;" | | {|class="wikitable" style="font-size:0.8em; line-height:1em; text-align: center;" |
| | |- | | |- |
The Containers library is a generic collection of class templates and algorithms that allow programmers to easily implement common data structures like queues, lists and stacks. There are two(until C++11)three(since C++11) classes of containers:
The container manages the storage space that is allocated for its elements and provides member functions to access them, either directly or through iterators (objects with properties similar to pointers).
Most containers have at least several member functions in common, and share functionalities. Which container is the best for the particular application depends not only on the offered functionality, but also on its efficiency for different workloads.
Sequence containers implement data structures which can be accessed sequentially.
Associative containers implement sorted data structures that can be quickly searched (O(log n) complexity).
Unordered associative containers implement unsorted (hashed) data structures that can be quickly searched (O(1) average, O(n) worst-case complexity).
Views provide flexible facilities for interacting with one- or multi-dimensional views over a non-owning array of elements.
Unless otherwise specified (either explicitly or by defining a function in terms of other functions), passing a container as an argument to a library function never invalidate iterators to, or change the values of, objects within that container.
The past-the-end iterator deserves particular mention. In general this iterator is invalidated as though it were a normal iterator to a non-erased element. So std::set::end is never invalidated, std::unordered_set::end is invalidated only on rehash(since C++11), std::vector::end is always invalidated (since it is always after the modified elements), and so on.
Thread safety
- All container functions can be called concurrently by different threads on different containers. More generally, the C++ standard library functions do not read objects accessible by other threads unless those objects are directly or indirectly accessible via the function arguments, including the this pointer.
- All const member functions can be called concurrently by different threads on the same container. In addition, the member functions
begin(), end(), rbegin(), rend(), front(), back(), data(), find(), lower_bound(), upper_bound(), equal_range(), at(), and, except in associative containers, operator[], behave as const for the purposes of thread safety (that is, they can also be called concurrently by different threads on the same container). More generally, the C++ standard library functions do not modify objects unless those objects are accessible, directly or indirectly, via the function's non-const arguments, including the this pointer.
- Different elements in the same container can be modified concurrently by different threads, except for the elements of std::vector<bool> (for example, a vector of std::future objects can be receiving values from multiple threads).
- Iterator operations (e.g. incrementing an iterator) read, but do not modify the underlying container, and may be executed concurrently with operations on other iterators on the same container, with the const member functions, or reads from the elements. Container operations that invalidate any iterators modify the container and cannot be executed concurrently with any operations on existing iterators even if those iterators are not invalidated.
- Elements of the same container can be modified concurrently with those member functions that are not specified to access these elements. More generally, the C++ standard library functions do not read objects indirectly accessible through their arguments (including other elements of a container) except when required by its specification.
- In any case, container operations (as well as algorithms, or any other C++ standard library functions) may be parallelized internally as long as this does not change the user-visible results (e.g. std::transform may be parallelized, but not std::for_each which is specified to visit each element of a sequence in order).
|
(since C++11) |
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
