Containers

This section documents C++23 (ISO/IEC 14882:2024), as published by ISO/IEC JTC1/SC22/WG21 (wg21), verified against the freely available working draft N5046 (eel.is/c++draft) and cppreference.com.

This content was generated with the assistance of AI and should be verified against the working draft and cppreference.com before being relied on in production.

This section’s bibliography lists the reference material consulted while preparing these pages.

Sequence Containers

#include <vector>
#include <array>
#include <deque>
#include <list>
#include <forward_list>

std::vector<int> v = {1, 2, 3};          // contiguous, growable -- the default choice for almost everything
std::array<int, 3> a = {1, 2, 3};         // fixed-size, contiguous, stack-allocated -- a "safe C array"
std::deque<int> d = {1, 2, 3};             // double-ended queue: fast push/pop at both ends, NOT contiguous
std::list<int> l = {1, 2, 3};               // doubly-linked list: O(1) insert/erase anywhere, no random access
std::forward_list<int> fl = {1, 2, 3};       // singly-linked list: smaller than list, forward iteration only

Associative Containers

Ordered by key (typically a red-black tree), giving O(log n) lookup/insert/erase and in-order iteration:

#include <map>
#include <set>

std::map<std::string, int> ages = {{"Ada", 36}};            // unique keys, sorted
std::multimap<std::string, int> scores;                       // duplicate keys allowed, sorted
scores.insert({"Ada", 90});
scores.insert({"Ada", 85});                                    // both entries kept

std::set<int> unique = {3, 1, 2};                              // sorted, unique elements: {1, 2, 3}
std::multiset<int> withDupes = {3, 1, 2, 1};                    // sorted, duplicates allowed: {1, 1, 2, 3}

Unordered Containers

Hash-table based, giving average O(1) lookup/insert/erase but no ordering guarantee — needs std::hash<Key> for a custom key type (see Standard Library Overview):

#include <unordered_map>
#include <unordered_set>

std::unordered_map<std::string, int> fastAges = {{"Ada", 36}};
std::unordered_set<int> fastUnique = {3, 1, 2};                 // no ordering guarantee when iterated

flat_map/flat_set (C++23)

std::flat_map/std::flat_set store keys and values in sorted, contiguous vectors rather than a tree — much better cache locality and lower memory overhead for read-heavy workloads, at the cost of O(n) insertion (shifting elements) instead of a tree’s O(log n):

#include <flat_map>

std::flat_map<std::string, int> config = {{"retries", 3}, {"timeout", 30}};
config["retries"] = 5;             // same interface as std::map for lookup/insert
// internally: two sorted vectors (keys, values), not a tree -- far fewer allocations, better cache behavior
<flat_map>/<flat_set> are standard-conformant C++23 (verified against cppreference and the working draft) but are not yet shipped by this environment’s libstdc++ 13 — they need GCC 14+, a recent libc++, or MSVC (see Getting Started); every other container on this page does compile locally.

Container Adaptors

An adaptor restricts a sequence container’s interface to a specific access pattern, rather than implementing storage itself:

#include <stack>
#include <queue>

std::stack<int> s;              // LIFO, backed by std::deque by default
s.push(1); s.push(2);
s.pop();                          // removes 2

std::queue<int> q;               // FIFO, backed by std::deque by default
q.push(1); q.push(2);
q.pop();                           // removes 1

std::priority_queue<int> pq;      // max-heap, backed by std::vector by default
pq.push(3); pq.push(1); pq.push(2);
pq.top();                          // 3 -- the largest

std::span and std::mdspan

std::span<T> (C++20) is a non-owning (pointer, length) view over a contiguous sequence — the array/vector analogue of std::string_view:

#include <span>
#include <vector>
#include <array>

void printAll(std::span<const int> values) {   // accepts a C array, std::array, or std::vector -- no copy
    for (int v : values) { (void)v; }
}

int carr[3] = {1, 2, 3};
std::vector<int> vec = {4, 5, 6};
std::array<int, 3> arr = {7, 8, 9};
// printAll(carr); printAll(vec); printAll(arr);   // all three bind without any conversion overhead

std::mdspan<T, Extents> (C++23) generalizes std::span to multiple dimensions over one flat buffer, with a customizable layout (row-major, column-major, or a custom stride) — useful for numeric/matrix code that would otherwise hand-roll index arithmetic:

#include <mdspan>
#include <vector>

std::vector<double> buffer(6, 0.0);
std::mdspan<double, std::extents<std::size_t, 2, 3>> matrix(buffer.data());
matrix[1, 2] = 5.0;    // row 1, column 2 -- no manual "row * cols + col" arithmetic
<mdspan> is standard-conformant C++23 syntax (verified against cppreference and the working draft) but is not yet shipped by this environment’s libstdc++ 13 — see the note on flat_map above; std::span itself does compile locally.

std::bitset and vector<bool>

std::bitset<N> was covered in Numbers and Math. std::vector<bool> is a notorious special case: it’s specialized to pack bits (8 per byte) rather than storing one bool per element, so operator[] returns a proxy object, not bool& — code generic over vector<T> that assumes T& from operator[] breaks for T = bool:

#include <vector>

std::vector<bool> flags = {true, false, true};
// bool& ref = flags[0];         // error: vector<bool>::reference is a proxy, not bool&
auto ref = flags[0];              // fine: deduces the proxy type
bool copy = flags[0];              // fine: converts to a real bool

For a genuine array-of-bool with real references, prefer std::vector<char>, std::array<bool, N>, or std::deque<bool> (which is not specialized this way).

Choosing the Right Container

Decision chart: contiguous + random access → vector; fixed size known at compile time → array; frequent front/back push → deque; frequent middle insert/erase → list; sorted unique keys → map/set; O(1) average lookup

Iterator/Reference Invalidation

Modifying a container can invalidate existing iterators/references/pointers into it — the exact rule differs per container and operation, and using an invalidated iterator is undefined behavior:

Container Invalidation on insert/erase

vector

push_back beyond capacity invalidates everything; erase invalidates from the erased point onward.

deque

Insert/erase at either end rarely invalidates; insert/erase in the middle invalidates everything.

list/forward_list

Erase invalidates only the erased element’s iterator; insert never invalidates any.

map/set

Erase invalidates only the erased element’s iterator; insert never invalidates any.

std::erase_if (covered in Iterators and Algorithms) sidesteps hand-writing an erase-in-a-loop that must reason about which iterators survive each step.

See Also

  • C: Arrays and Strings — raw arrays and pointer/length pairs — the starting point std::vector, std::array and std::span improve on.

References