14/10/2024, 15:12 Containers library - cppreference.
com
Containers library
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:
sequence containers,
associative containers, and
unordered associative containers, (since C++11)
each of which is designed to support a different set of operations.
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
Sequence containers implement data structures which can be accessed sequentially.
fixed-sized inplace contiguous array
array (C++11)
(class template)
dynamic contiguous array
vector
(class template)
dynamically-resizable, fixed capacity, inplace contiguous array
inplace_vector (C++26)
(class template)
double-ended queue
deque
(class template)
singly-linked list
forward_list (C++11)
(class template)
doubly-linked list
list
(class template)
Associative containers
Associative containers implement sorted data structures that can be quickly searched (O(log n) complexity).
collection of unique keys, sorted by keys
set
(class template)
collection of key-value pairs, sorted by keys, keys are unique
map
(class template)
collection of keys, sorted by keys
multiset
(class template)
collection of key-value pairs, sorted by keys
multimap
(class template)
[Link] 1/7
14/10/2024, 15:12 Containers library - [Link]
Unordered associative containers (since C++11)
Unordered associative containers implement unsorted (hashed) data structures that can be quickly searched (O(1) average, O(n) worst-case complexity).
collection of unique keys, hashed by keys
unordered_set (C++11) (class template)
collection of key-value pairs, hashed by keys, keys are unique
unordered_map (C++11)
(class template)
collection of keys, hashed by keys
unordered_multiset (C++11)
(class template)
collection of key-value pairs, hashed by keys
unordered_multimap (C++11)
(class template)
Container adaptors
Container adaptors provide a different interface for sequential containers.
adapts a container to provide stack (LIFO data structure)
stack
(class template)
adapts a container to provide queue (FIFO data structure)
queue
(class template)
adapts a container to provide priority queue
priority_queue
(class template)
adapts a container to provide a collection of unique keys, sorted by keys
flat_set (C++23)
(class template)
adapts two containers to provide a collection of key-value pairs, sorted by unique keys
flat_map (C++23)
(class template)
adapts a container to provide a collection of keys, sorted by keys
flat_multiset (C++23)
(class template)
adapts two containers to provide a collection of key-value pairs, sorted by keys
flat_multimap (C++23)
(class template)
Views
Views provide flexible facilities for interacting with one- or multi-dimensional views over a non-owning array of elements.
a non-owning view over a contiguous sequence of objects
span (C++20)
(class template)
a multi-dimensional non-owning array view
mdspan (C++23)
(class template)
Iterator invalidation
Read-only methods never invalidate iterators or references. Methods which modify the contents of a container may invalidate iterators and/or references, as summarized in
this table.
[Link] 2/7
14/10/2024, 15:12 Containers library - [Link]
After insertion, are... After erasure, are...
Category Container Conditionally
iterators valid? references valid? iterators valid? references valid?
array N/A N/A
No N/A Insertion changed capacity
vector Yes Yes Before modified element(s)
(for insertion only if capacity didn't change)
Sequence containers No No At or after modified element(s)
Yes Yes, except erased element(s) Modified first or last element
deque No
No No Modified middle only
list Yes Yes, except erased element(s)
forward_list Yes Yes, except erased element(s)
set
Associative containers multiset Yes Yes, except erased element(s)
map
multimap
unordered_set No N/A Insertion caused rehash
unordered_multiset
Unordered associative containers unordered_map Yes
unordered_multimap Yes Yes, except erased element(s) No rehash
This section is incomplete
Reason: add iterator invalidation for C++23 "flat" adaptors (std::flat_set etc)
This section is incomplete
Reason: add iterator invalidation for C++26 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.
Examples of insertion methods are std::set::insert, std::map::emplace, std::vector::push_back, and std::deque::push_front.
Note that std::unordered_map::operator[] also counts, as it may insert an element into the map. (since C++11)
Examples of erasure methods are std::set::erase, std::vector::pop_back, std::deque::pop_front, and std::map::clear.
clear invalidates all iterators and references. Because it erases all elements, this technically complies with the rules above.
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.
There is one exception: an erasure which deletes the last element of a std::deque does invalidate the past-the-end iterator, even though it is not an erased element of the
container (or an element at all). Combined with the general rules for std::deque iterators, the net result is that the only modifying operation which does not invalidate
std::deque::end is an erasure which deletes the first element, but not the last.
(since C++11)
Thread safety
1. 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.
[Link] 3/7
14/10/2024, 15:12 Containers library - [Link]
2. 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.
3. 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).
4. 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.
5. 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.
6. 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).
Function table
Note: std::basic_string is not treated as a container by the standard but behaves much like one due to its similarity. It is listed as 'Pseudo container' here for convenience.
- functions present in C++03
- functions present since C++11
- functions present since C++17
- functions present since C++20
- functions present since C++23
This section is incomplete
Reason: Add C++26 "color" and fill member/non-member function table for
std::inplace_vector
[Link] 4/7
14/10/2024, 15:12 Containers library - [Link]
Member function table
Pseudo
container Sequence containers Associative containers Unor
Header <string> <array> <vector> <deque> <forward_list> <list> <set> <map> <unordered_se
Container basic_string array vector deque forward_list list set multiset map multimap unordered_set unorder
(constructor) basic_string (implicit) vector deque forward_list list set multiset map multimap unordered_set unorder
(destructor) ~basic_string (implicit) ~vector ~deque ~forward_list ~list ~set ~multiset ~map ~multimap ~unordered_set ~unorde
operator= operator= (implicit) operator= operator= operator= operator= operator= operator= operator= operator= operator= op
assign assign assign assign assign assign
assign_range assign_range assign_range assign_range assign_range assign_range
begin begin begin begin begin begin begin begin begin begin begin begin
cbegin cbegin cbegin cbegin cbegin cbegin cbegin cbegin cbegin cbegin cbegin cbegin c
end end end end end end end end end end end end
cend cend cend cend cend cend cend cend cend cend cend cend
Iterators
rbegin rbegin rbegin rbegin rbegin rbegin rbegin rbegin rbegin rbegin
crbegin crbegin crbegin crbegin crbegin crbegin crbegin crbegin crbegin crbegin
rend rend rend rend rend rend rend rend rend rend
crend crend crend crend crend crend crend crend crend crend
at at at at at at
operator[] operator[] operator[] operator[] operator[] operator[]
Element data data data data
access
front front front front front front front
back back back back back back
empty empty empty empty empty empty empty empty empty empty empty empty
size size size size size size size size size size size
max_size max_size max_size max_size max_size max_size max_size max_size max_size max_size max_size max_size ma
Capacity resize resize resize resize resize resize
capacity capacity capacity
reserve reserve reserve reserve r
shrink_to_fit shrink_to_fit shrink_to_fit shrink_to_fit
clear clear clear clear clear clear clear clear clear clear clear
insert insert insert insert insert_after insert insert insert insert insert insert i
insert_range insert_range insert_range insert_range insert_range_after insert_range insert_range insert_range insert_range insert_range insert_range inse
insert_or_assign insert_or_assign
emplace emplace emplace emplace_after emplace emplace emplace emplace emplace emplace e
emplace_hint emplace_hint emplace_hint emplace_hint emplace_hint emplace_hint empl
try_emplace try_emplace
erase erase erase erase erase_after erase erase erase erase erase erase
push_front push_front push_front push_front
Modifiers prepend_range prepend_range prepend_range prepend_range
emplace_front emplace_front emplace_front emplace_front
pop_front pop_front pop_front pop_front
push_back push_back push_back push_back push_back
Note: functions in two different extract lines have different meanings and syntax:
1. ↑ e.g., node_type extract(const_iterator) or node_type extract(Key&)
2. ↑ e.g., container_type extract() &&
[Link] 5/7
14/10/2024, 15:12 Containers library - [Link]
Non-member function table
Pseudo
container Sequence containers Associative containers Unordered associative containers
Header <string> <array> <vector> <deque> <forward_list> <list> <set> <map> <unordered_set> <unorde
Container basic_string array vector deque forward_list list set multiset map multimap unordered_set unordered_multiset unordered_map un
operator== operator== operator== operator== operator== operator== operator== operator== operator== operator== operator== operator== operator== operator==
operator!=
(removed in operator!= operator!= operator!= operator!= operator!= operator!= operator!= operator!= operator!= operator!= operator!= operator!= operator!=
C++20)
operator<
(removed in operator< operator< operator< operator< operator< operator< operator< operator< operator< operator<
C++20)
operator<=
(removed in operator<= operator<= operator<= operator<= operator<= operator<= operator<= operator<= operator<= operator<=
Non- C++20)
member operator>
function (removed in operator> operator> operator> operator> operator> operator> operator> operator> operator> operator>
C++20)
operator>=
(removed in operator>= operator>= operator>= operator>= operator>= operator>= operator>= operator>= operator>= operator>=
C++20)
operator<=> operator<=> operator<=> operator<=> operator<=> operator<=> operator<=> operator<=> operator<=> operator<=> operator<=>
swap swap swap swap swap swap swap swap swap swap swap swap swap swap
erase erase erase erase erase erase
erase_if erase_if erase_if erase_if erase_if erase_if erase_if erase_if erase_if erase_if erase_if erase_if erase_if
Container basic_string array vector deque forward_list list set multiset map multimap unordered_set unordered_multiset unordered_map un
Header <string> <array> <vector> <deque> <forward_list> <list> <set> <map> <unordered_set> <unorde
Pseudo Sequence containers Associative containers Unordered associative containers
container
The <, <=, >, >=, and != operators are synthesized from operator<=> and operator== respectively. (since C++20)
Defect reports
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
DR Applied to Behavior as published Correct behavior
container iterators might be invalidated they are only invalidated
LWG 51 ([Link] C++98
by arbitrary library operation when specified
See also
C++ named requirements:
Container
SequenceContainer
ContiguousContainer
ReversibleContainer
AssociativeContainer
AllocatorAwareContainer
[Link] 6/7
14/10/2024, 15:12 Containers library - [Link]
UnorderedAssociativeContainer
numeric arrays, array masks and array slices
valarray
(class template)
stores and manipulates sequences of characters
basic_string
(class template)
read-only string view
basic_string_view (C++17)
(class template)
Retrieved from "[Link]
[Link] 7/7