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,
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.
(C++11)
fixed-sized inplace contiguous array
(class template)
resizable contiguous array
(class template)
(C++26)
resizable, fixed capacity, inplace contiguous array
(class template)
(C++26)
collection that reuses erased elements' memory
(class template)
double-ended queue
(class template)
(C++11)
singly-linked list
(class template)
doubly-linked 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
(class template)
collection of key-value pairs, sorted by keys, keys are unique
(class template)
collection of keys, sorted by keys
(class template)
collection of key-value pairs, sorted by keys
(class template)
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).
Container adaptors
Container adaptors provide a different interface for sequential containers.
adapts a container to provide stack (LIFO data structure)
(class template)
adapts a container to provide queue (FIFO data structure)
(class template)
adapts a container to provide priority queue
(class template)
(C++23)
adapts a container to provide a collection of unique keys, sorted by keys
(class template)
(C++23)
adapts two containers to provide a collection of key-value pairs, sorted by unique keys
(class template)
(C++23)
adapts a container to provide a collection of keys, sorted by keys
(class template)
(C++23)
adapts two containers to provide a collection of key-value pairs, sorted by keys
(class template)
Views (since C++20)
Views provide flexible facilities for interacting with one- or multi-dimensional views over a non-owning array of elements.
(C++20)
a non-owning view over a contiguous sequence of objects
(class template)
(C++23)
a multi-dimensional non-owning array view
(class template)
Iterator invalidation
Read-only methods never
iterators or references. Methods which modify the contents of a container may invalidate iterators and/or references, as summarized in this table.
Category Container After insertion, are... After erasure, are... Conditionally iterators valid? references valid? iterators valid? references valid? Sequence containers
N/AN/A
No N/AInsertion changed capacity Yes Yes Before modified element(s)
(for insertion only if capacity didn't change) No No At or after modified element(s)
No Yes Yes, except erased element(s) Modified first or last element No No Modified middle only
Yes Yes, except erased element(s)
Yes Yes, except erased element(s) Associative containers
Yes Yes, except erased element(s) Unordered associative containers
No Yes N/AInsertion caused rehash Yes Yes, except erased element(s) No rehash 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
,
,
, and
.
Examples of erasure methods are
,
,
, and
. 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
is never invalidated,
is invalidated only on rehash(since C++11),
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
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
iterators, the net result is that the only modifying operation which does not invalidate
is an erasure which deletes the first element, but not the last.
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
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.
may be parallelized, but not
which is specified to visit each element of a sequence in order).
(since C++11)Function table
Note:
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 Member function table
Pseudo container Sequence containers Associative containers Unordered associative containers Container adaptors Header
Header Container
Container (constructor)
(implicit)
(constructor)(destructor)
(implicit)
(destructor)operator=
(implicit)
operator=assign
assignassign_range
assign_rangeIterators begincbegin
begincbeginIterators endcend
endcendrbegincrbegin
rbegincrbeginrendcrend
rendcrendElement
access at
atElement
access operator[]
operator[]data
datafront
frontback
backCapacity empty
emptyCapacity size
sizemax_size
max_sizeresize
resizecapacity
capacityreserve
reserveshrink_to_fit
shrink_to_fitModifiers clear
clearModifiers insert
insertinsert_range
insert_rangeinsert_or_assign
insert_or_assignemplace
emplaceemplace_hint
emplace_hinttry_emplace
try_emplaceerase
erasepush_front
push_frontprepend_range
prepend_rangeemplace_front
emplace_frontpop_front
pop_frontpush_back
push_backappend_range
append_rangeemplace_back
emplace_backpop_back
pop_backswap
swapmerge
mergeextract
extractList operations splice
spliceList operations remove
removeremove_if
remove_ifreverse
reverseunique
uniquesort
sortBucket and Hash begin(size_type)cbegin(size_type)
begin(size_type) cbegin(size_type)
begin(size_type) cbegin(size_type)
begin(size_type) cbegin(size_type)
begin(size_type) cbegin(size_type)
begin(size_type)cbegin(size_type)Bucket and Hash end(size_type)cend(size_type)
end(size_type) cend(size_type)
end(size_type) cend(size_type)
end(size_type) cend(size_type)
end(size_type) cend(size_type)
end(size_type)cend(size_type)bucket_count
bucket_countmax_bucket_count
max_bucket_countbucket_size
bucket_sizebucket
bucketload_factor
load_factormax_load_factor
max_load_factorrehash
rehashLookup count
countLookup find
findcontains
containslower_bound
lower_boundupper_bound
upper_boundequal_range
equal_rangeObservers key_comp
key_compObservers value_comp
value_comphash_function
hash_functionkey_eq
key_eqAllocator get_allocator
get_allocatorAllocator Adaptors extract
extractAdaptors replace
replaceContainer
Container Header
Header Pseudo container Sequence containers Associative containers Unordered associative containers Container adaptors Note: functions in two different extract lines have different meanings and syntax:
e.g., node_typeextract(const_iterator) or node_typeextract(Key&)
e.g., container_typeextract()&&
Non-member function table
Pseudo container Sequence containers Associative containers Unordered associative containers Container adaptors Header
Header Container
Container Non-member function operator==
operator==Non-member function operator!= (removed in C++20)
operator!= (removed in C++20)operator< (removed in C++20)
operator< (removed in C++20)operator<= (removed in C++20)
operator<= (removed in C++20)operator> (removed in C++20)
operator> (removed in C++20)operator>= (removed in C++20)
operator>= (removed in C++20)operator<=>
operator<=>swap
swaperase
eraseerase_if
erase_ifContainer
Container Header
Header Pseudo container Sequence containers Associative containers Unordered associative containers Container adaptors The <, <=, >, >=, and != operators are
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
C++98 container iterators might be invalidated
by arbitrary library operation they are only invalidated
when specified See also
C++ named requirements: