C++ § data-structures

Data structures

C++‘s standard library provides the Standard Template Library — a coordinated suite of containers, iterators, and algorithms designed to compose generically. The containers cover the conventional shapes: contiguous arrays (std::array, std::vector, std::deque), linked structures (std::list, std::forward_list), associative collections in both ordered (std::map, std::set) and unordered (std::unordered_map, std::unordered_set) forms, and the adaptors (std::stack, std::queue, std::priority_queue). The library is the single largest practical advantage of C++ over C; nearly every non-trivial C++ program uses it heavily, and the conventions for choosing among the containers are part of the language’s idiom.

The STL design

The STL has three components:

Containers — types that hold collections of elements.
Iterators — types that designate positions within containers and admit traversal.
Algorithms — generic functions that operate on iterator ranges.

The components compose generically: any container that exposes an iterator of the appropriate category can be passed to any algorithm requiring that iterator category. The decoupling lets the standard library provide a single std::sort that works on std::vector, std::deque, plain arrays, and any user-defined type that satisfies the random-access iterator concept.

#include <algorithm>
#include <vector>

std::vector<int> values = {3, 1, 4, 1, 5, 9, 2, 6};
std::sort(values.begin(), values.end());
auto it = std::find(values.begin(), values.end(), 5);

C++20 introduced the ranges library (<ranges>), which adds a more direct interface and admits composition into pipelines. The ranges library is treated in Functional and ranges.

Sequence containers

Sequence containers store elements in a defined order, accessed by position.

`std::array<T, N>`

A fixed-size, contiguous array. The size is part of the type and known at compile time:

#include <array>

std::array<int, 5> a = {1, 2, 3, 4, 5};
a[0] = 10;
auto size = a.size();        // 5

The container is a thin wrapper around a C array. It admits the conventional iterator interface, may be copied and assigned by value, and does not decay to a pointer. It is the conventional choice for small fixed-size collections (vector components, RGB triples, fixed-size buffers).

`std::vector<T>`

A dynamic-size, contiguous array. The conventional default container in modern C++:

#include <vector>

std::vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);

v.reserve(100);              // pre-allocate without growing the size
v.resize(50);                // grow or shrink the size

The container maintains:

A pointer to a heap-allocated buffer.
The current size (number of elements).
The current capacity (allocated buffer length).

When size reaches capacity, growth (typically doubling) reallocates the buffer; element insertion at the end is amortised constant time. Insertion or removal at any other position is linear in the distance from the operation to the end.

The principal operations:

Operation	Effect	Complexity
`v.push_back(x)`	Append.	Amortised O(1)
`v.emplace_back(args...)`	Construct in place at end.	Amortised O(1)
`v.pop_back()`	Remove last.	O(1)
`v.insert(pos, x)`	Insert at position.	O(n)
`v.erase(pos)`	Remove at position.	O(n)
`v[i]` / `v.at(i)`	Element access.	O(1)
`v.size()` / `v.empty()`	Size queries.	O(1)
`v.reserve(n)`	Ensure capacity for n elements.	O(n)
`v.shrink_to_fit()`	Release excess capacity.	Up to O(n)

std::vector<int> is the conventional choice for any sequence with no specific requirement that argues for another container.

`std::deque<T>`

A double-ended queue. Constant-time insertion and removal at both ends; constant-time random access; non-contiguous storage:

#include <deque>

std::deque<int> dq;
dq.push_back(1);
dq.push_front(0);            // also constant time, unlike vector

The container is implemented as a sequence of fixed-size blocks; element addresses are stable across push_back/push_front operations on either end (but not across insert in the middle). The construction is the conventional choice when both ends need fast modification; for one-end-only use, vector is typically more efficient.

`std::list<T>` and `std::forward_list<T>`

Doubly- and singly-linked lists. Constant-time insertion and removal at any position given an iterator, but no random access:

#include <list>

std::list<int> lst = {1, 2, 3, 4, 5};
auto it = std::find(lst.begin(), lst.end(), 3);
lst.insert(it, 99);          // O(1) given the iterator
lst.erase(it);               // O(1)

Linked lists are rarely the right choice in modern C++. Cache-unfriendliness, allocation per node, and the overhead of pointer chasing usually make vector (or deque) faster for typical workloads, even when the asymptotic complexity favours the list. The list is appropriate only when:

Iterator stability across modifications is required (insertions and removals must not invalidate other iterators).
Splicing — moving a sublist from one container to another in constant time — is needed.
Constant-time middle-insertion is critical and the iterator is already known.

forward_list saves the back-pointer and one cache line per node at the cost of unidirectional iteration; it is rare in practice.

Associative containers

Associative containers store keyed elements.

`std::map<K, V>` and `std::set<K>`

Ordered associative containers. Implemented as balanced binary search trees (typically red-black). O(log n) lookup, insertion, and removal; iteration in sorted-by-key order:

#include <map>
#include <set>

std::map<std::string, int> ages;
ages["alice"] = 30;
ages.emplace("bob", 28);
ages.try_emplace("carol", 35);    // inserts only if key is absent

if (auto it = ages.find("alice"); it != ages.end()) {
    std::cout << it->second << '\n';
}

std::set<int> primes = {2, 3, 5, 7, 11};
primes.insert(13);
bool has_5 = primes.contains(5);  // C++20

The containers maintain elements sorted by key (using std::less<K> by default). Iteration produces elements in ascending key order. Range-based operations on a sub-range of keys are admissible:

auto lower = ages.lower_bound("a");
auto upper = ages.upper_bound("c");
for (auto it = lower; it != upper; ++it) {
    std::cout << it->first << ": " << it->second << '\n';
}

std::multimap and std::multiset admit duplicate keys.

`std::unordered_map<K, V>` and `std::unordered_set<K>`

Hash-based associative containers. Implemented as hash tables with separate chaining. Average O(1) lookup, insertion, and removal; iteration in unspecified order:

#include <unordered_map>

std::unordered_map<std::string, int> word_counts;
for (const auto &w : words) ++word_counts[w];

The hash function is std::hash<K> by default; for user-defined types, a hash function must be provided either through specialisation of std::hash<MyType> or as a constructor argument:

struct PointHash {
    std::size_t operator()(const Point &p) const noexcept {
        return std::hash<double>{}(p.x) ^ (std::hash<double>{}(p.y) << 1);
    }
};

std::unordered_map<Point, int, PointHash> point_indices;

The unordered_* containers are typically faster than std::map/std::set for lookup-heavy workloads (the constant factor on the hash dominates only for small N), but they consume more memory per element and offer no ordered traversal.

The conventional choice between map and unordered_map:

unordered_map for performance on large data with frequent lookups.
map when ordered iteration, range queries, or stable iteration order is needed.
map for small data where the difference is dominated by overhead.

Container adaptors

Container adaptors wrap an underlying container, exposing a restricted interface:

Adaptor	Underlying	Interface
`std::stack<T>`	`std::deque<T>` (default)	`push`, `pop`, `top` — LIFO
`std::queue<T>`	`std::deque<T>` (default)	`push`, `pop`, `front`, `back` — FIFO
`std::priority_queue<T>`	`std::vector<T>` (default)	Max-heap by default; `push`, `pop`, `top`

#include <stack>
#include <queue>

std::stack<int> s;
s.push(1); s.push(2); s.push(3);
while (!s.empty()) {
    std::cout << s.top() << ' ';
    s.pop();
}
// 3 2 1

std::priority_queue<int> pq;        // max-heap
pq.push(3); pq.push(1); pq.push(4); pq.push(1); pq.push(5);
while (!pq.empty()) {
    std::cout << pq.top() << ' ';   // 5 4 3 1 1
    pq.pop();
}

std::priority_queue admits a custom comparator for min-heap or arbitrary ordering:

std::priority_queue<int, std::vector<int>, std::greater<>> min_heap;

Views

C++20 introduced std::span, a non-owning view over a contiguous range:

#include <span>

void print_all(std::span<const int> values) {
    for (int v : values) std::cout << v << ' ';
}

int arr[] = {1, 2, 3, 4, 5};
std::vector<int> v = {6, 7, 8};

print_all(arr);              // span over the array
print_all(v);                // span over the vector
print_all({arr + 1, 3});     // span over a sub-range

std::span<T> carries a pointer and a length; it is constant-time to construct and copy. The conventional use is as a parameter type for functions that operate on a contiguous range without owning it: std::span<const int> accepts arrays, vectors, and any contiguous range without forcing an allocation.

C++23 added std::mdspan — a multi-dimensional version with explicit extents and layout — for numerical work over multidimensional arrays.

Iterators

An iterator is a position within a container; it admits traversal through ++, comparison through == and !=, and access through * and ->. The standard distinguishes six iterator categories, in increasing capability:

Category	Capabilities	Examples
Input	Single-pass forward; read-only access	`std::istream_iterator`
Output	Single-pass forward; write-only access	`std::back_inserter`
Forward	Multi-pass forward	`std::forward_list::iterator`
Bidirectional	Forward and backward	`std::list::iterator`, `std::map::iterator`
Random-access	Constant-time arbitrary jumps	`std::vector::iterator`, `std::deque::iterator`
Contiguous (C++20)	Random-access plus contiguous storage	`std::vector::iterator`, `std::array::iterator`, raw pointers

Algorithms specify the minimum iterator category they require: std::find requires Input, std::sort requires Random-access. A container’s iterators may satisfy a stronger category than the minimum.

The conventional iterator usage:

for (auto it = c.begin(); it != c.end(); ++it) { /* ... */ }
for (auto it = c.cbegin(); it != c.cend(); ++it) { /* read-only */ }
for (auto it = c.rbegin(); it != c.rend(); ++it) { /* reverse */ }

For most cases, range-based for is preferable; explicit iterators are needed only when the position is needed (insertions, erasures) or when a non-trivial step pattern is required.

C++20 added the sentinel model: an iterator pair may use a sentinel (a type that compares equal to the end iterator without itself being an iterator) to denote the end. The model admits more efficient end-of-range tests for some range types and is used by the ranges library.

Choice of container

The conventional decision tree:

Need	Container
Default sequence	`std::vector<T>`
Fixed-size sequence	`std::array<T, N>`
Frequent insertion at both ends	`std::deque<T>`
Iterator stability across modifications	`std::list<T>`
Lookup by key, ordered	`std::map<K, V>`
Lookup by key, fast	`std::unordered_map<K, V>`
Set membership	`std::set<K>` or `std::unordered_set<K>`
LIFO	`std::stack<T>`
FIFO	`std::queue<T>`
Max element	`std::priority_queue<T>`
View over a contiguous range	`std::span<T>`

The default for “I need a collection” is std::vector<T>; the burden is on the alternative to justify itself.

Iterator invalidation

Modifications to a container may invalidate iterators that reference the container. The rules vary by container; the principal cases:

Container	Operation	Invalidates
`vector`	`push_back` / `insert` causing reallocation	All iterators
`vector`	`erase`	Iterators at and after the erased position
`deque`	`push_back`/`push_front`	All iterators (but not pointers/references to elements)
`list`, `forward_list`	`insert`	None
`list`, `forward_list`	`erase`	The erased iterator only
`map`, `set`, `unordered_*`	`insert`	None for ordered; pointers/references stable. Unordered: rehash invalidates iterators (and pointers, since C++23 it does not re-allocate elements).
`map`, `set`, `unordered_*`	`erase`	The erased iterator only

The rules are detailed; the conventional defence is to avoid holding iterators across container modifications when possible, and to consult the rules when not.

Common idioms

Erase-remove

Removing all elements satisfying a predicate from a sequence:

auto it = std::remove_if(v.begin(), v.end(),
                          [](int x) { return x % 2 == 0; });
v.erase(it, v.end());

The two-step form is the conventional pattern. C++20 added std::erase_if as a single-call alternative:

std::erase_if(v, [](int x) { return x % 2 == 0; });

`emplace` for in-place construction

The emplace_back / emplace family forwards arguments to the element’s constructor without an intermediate temporary:

std::vector<std::pair<int, std::string>> v;
v.emplace_back(42, "hello");          // constructs the pair in place
                                       // (vs. v.push_back({42, "hello"}) which constructs a pair, then moves)

For move-only types and for types whose copy/move is non-trivial, emplace saves a temporary.

`try_emplace` and `insert_or_assign`

For std::map and std::unordered_map:

try_emplace(key, args...) — inserts only if the key is absent. Does not construct the value if the key is present.
insert_or_assign(key, value) — inserts or overwrites; returns whether the key was new.

The two replace the old m[key] = value idiom in cases where the difference matters.

The STL design

Sequence containers

std::array<T, N>

std::vector<T>

std::deque<T>

std::list<T> and std::forward_list<T>