C++ STL Containers

  • Description: A note on the C++ STL containers, iteration patterns, and std::priority_queue with custom comparators
  • My Notion Note ID: K2A-B1-13
  • Created: 2018-04-11
  • Updated: 2026-02-28
  • License: Reuse is very welcome. Please credit Yu Zhang and link back to the original on yuzhang.io

Table of Contents

1. Container Overview

1.1 Sequence Containers

Sequence containers store elements in a linear order.

  1. std::vector<T> — Contiguous, dynamic array. Random access is O(1); back-insertion is amortized O(1).
  2. std::array<T, N> — Fixed-size array; size known at compile time.
  3. std::deque<T> — Double-ended queue with O(1) push/pop at both ends; not contiguous in memory.
  4. std::list<T> — Doubly linked list; O(1) insertion/removal anywhere given an iterator.
  5. std::forward_list<T> — Singly linked list; lower memory overhead than list.
#include <vector>
#include <array>
#include <deque>
#include <list>

// std::vector — the default choice for a dynamic array
std::vector<int> v = {1, 2, 3};
v.push_back(4);                  // {1, 2, 3, 4}
v[0] = 10;                       // random access
v.pop_back();                    // remove last
std::cout << v.size();           // 3

std::vector<int> v2(5, 0);       // five zeros
std::vector<int> v3(v.begin(), v.end());  // copy from another range

// std::array — size is part of the type
std::array<int, 3> a = {1, 2, 3};
a[0] = 10;
std::cout << a.size();           // 3 (known at compile time)

// std::deque — fast push/pop at both ends
std::deque<int> dq = {2, 3};
dq.push_front(1);                // {1, 2, 3}
dq.push_back(4);                 // {1, 2, 3, 4}
dq.pop_front();                  // {2, 3, 4}

// std::list — fast insertion anywhere given an iterator
std::list<int> l = {1, 2, 4};
auto it = std::next(l.begin(), 2);   // iterator to '4'
l.insert(it, 3);                     // {1, 2, 3, 4} — O(1)
l.remove(2);                         // {1, 3, 4}

When to pick which:

  1. Default to std::vector — cache-friendly, fastest for most workloads.
  2. Use std::array when the size is known at compile time and stack allocation is preferred.
  3. Use std::deque only when you need O(1) push/pop at both ends.
  4. Use std::list only when you have stable iterators across insertions or splice large sections cheaply.
  5. std::forward_list is rarely worth it — only for memory-tight scenarios.

1.2 Associative Containers

Associative containers index elements by key.

  1. Ordered (red-black tree, O(log n)): std::set, std::multiset, std::map, std::multimap. Iterates in sorted key order; supports range queries via lower_bound / upper_bound.
  2. Unordered (hash table, O(1) average): std::unordered_set, std::unordered_multiset, std::unordered_map, std::unordered_multimap. No iteration order guarantees.
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>

// std::map — ordered key→value
std::map<std::string, int> ages = {
    {"Alice", 30},
    {"Bob",   25},
};
ages["Carol"] = 28;                       // insert via subscript
ages.insert({"Dave", 40});                // explicit insert
ages.at("Alice") = 31;                    // throws if missing

if (auto it = ages.find("Bob"); it != ages.end()) {
    std::cout << it->second;              // 25
}

// std::unordered_map — same API, hash-based, faster average lookup
std::unordered_map<std::string, int> scores = {{"Alice", 100}};
scores["Bob"] = 95;
if (scores.contains("Alice")) {           // C++20
    // ...
}

// std::set — unique sorted keys
std::set<int> primes = {2, 3, 5, 7};
primes.insert(11);
primes.erase(3);
auto lo = primes.lower_bound(5);          // iterator to 5

// std::unordered_set — unique unsorted keys, O(1) lookup
std::unordered_set<std::string> seen = {"alpha", "beta"};
seen.insert("gamma");
if (seen.count("alpha")) { /* ... */ }

Important gotchas:

  1. map::operator[] inserts a default-constructed value if the key is missing — never use it for read-only lookups. Prefer at(), find(), or contains() (C++20).
  2. unordered_map requires a hash function for custom keys — specialize std::hash<Key> or pass a hasher as a template argument.
  3. Iterating std::map is in sorted key order; iterating std::unordered_map is in implementation-defined order.

1.3 Container Adaptors

Container adaptors wrap an underlying container and expose a restricted interface.

  1. std::stack<T> — LIFO; defaults to std::deque<T> underneath.
  2. std::queue<T> — FIFO; defaults to std::deque<T> underneath.
  3. std::priority_queue<T> — Heap-based priority queue; defaults to std::vector<T> underneath.
#include <stack>
#include <queue>

// std::stack — LIFO
std::stack<int> s;
s.push(1);
s.push(2);
s.push(3);
std::cout << s.top();           // 3
s.pop();                        // pop returns void; read top() first
std::cout << s.size();          // 2

// std::queue — FIFO
std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);
std::cout << q.front();         // 1 (oldest)
std::cout << q.back();          // 3 (newest)
q.pop();                        // also returns void

// std::priority_queue — see section 3 for full coverage
std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
std::cout << pq.top();          // 4 (max-heap by default)
pq.pop();

Note: Container adaptors do not expose iterators. If you need to iterate, use the underlying container directly (e.g., std::deque<int> instead of std::queue<int>).

2. Iterating Over Containers

Most STL operations return iterators or iterator pairs, but day-to-day code rarely needs to handle them directly. Modern C++ favors range-based loops and structured bindings for readability.

2.1 Range-Based for (Most Common)

The default choice in C++11 and later. Works on any type with begin() and end() (all STL containers, raw arrays, std::initializer_list).

std::vector<int> v = {1, 2, 3, 4, 5};

// Read-only: const reference avoids copies
for (const int& x : v) {
    std::cout << x << " ";
}

// Modify in place: non-const reference
for (int& x : v) {
    x *= 2;
}

// auto&& — universal reference; works with both lvalue ranges and proxy iterators
for (auto&& x : v) {
    // x binds to whatever the iterator yields
}

Pick the reference type with intent:

  1. for (T x : v) — copy each element. Use only for cheap-to-copy types (int, char).
  2. for (const T& x : v) — read-only, no copy. Default for read access.
  3. for (T& x : v) — mutable reference. Default for write access.
  4. for (auto&& x : v) — universal reference; lets the loop work uniformly with proxy types like std::vector<bool> or C++20 ranges views.

2.2 Iterator-Based for

Useful when you need the iterator itself — for example, to pass to erase, to advance by more than one, or to compute distances.

std::vector<int> v = {1, 2, 3, 4, 5};

for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << " ";
}

// Erase even numbers in place. erase invalidates 'it', so use the returned iterator:
for (auto it = v.begin(); it != v.end(); ) {
    if (*it % 2 == 0) {
        it = v.erase(it);   // returns iterator to next element
    } else {
        ++it;
    }
}

For containers like std::list and std::map, erase only invalidates the erased iterator — but the same defensive pattern (it = container.erase(it)) works everywhere.

2.3 Index-Based for (Random-Access Only)

Works on vector, deque, array, and raw arrays — anything supporting operator[]. Useful when the index itself matters (printing positions, parallel iteration over two same-length vectors, etc.).

std::vector<std::string> names = {"Alice", "Bob", "Carol"};

for (size_t i = 0; i < names.size(); ++i) {
    std::cout << i << ": " << names[i] << "\n";
}

// Parallel iteration over two same-length vectors
std::vector<int> ages = {30, 25, 28};
for (size_t i = 0; i < names.size(); ++i) {
    std::cout << names[i] << " is " << ages[i] << "\n";
}

For map iteration with both key and value, prefer structured bindings (next section) over pair::first / pair::second.

2.4 Structured Bindings (C++17)

When iterating maps or any range of std::pair / std::tuple, structured bindings give named locals.

std::map<std::string, int> ages = {{"Alice", 30}, {"Bob", 25}};

// C++17 and later — clean and readable
for (const auto& [name, age] : ages) {
    std::cout << name << " is " << age << "\n";
}

// Pre-C++17 equivalent
for (const auto& kv : ages) {
    std::cout << kv.first << " is " << kv.second << "\n";
}

2.5 std::for_each

A function-style alternative for applying a callable to each element. Less common in modern C++ — range-for is shorter — but still useful with parallel execution policies.

#include <algorithm>
#include <execution>
#include <vector>

std::vector<int> v = {1, 2, 3, 4, 5};

std::for_each(v.begin(), v.end(), [](int x) {
    std::cout << x << " ";
});

// Parallel execution (C++17): the runtime picks how to schedule the work
std::for_each(std::execution::par, v.begin(), v.end(), [](int& x) {
    x = expensiveCompute(x);
});

3. std::priority_queue

std::priority_queue is a heap-based container adaptor. The full template signature is:

template <
    class T,
    class Container = std::vector<T>,
    class Compare   = std::less<typename Container::value_type>
> class priority_queue;

The element returned by top() is always one for which Compare(top, other) is false for every other element — that is, no element compares "greater" than top under the chosen comparator (the "largest" element, with ties allowed).

3.1 Default Behavior: Max-Heap

By default, priority_queue uses std::less<T>, which produces a max-heap (largest element on top).

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;  // max-heap
    for (int x : {3, 1, 4, 1, 5, 9, 2, 6}) {
        pq.push(x);
    }
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    std::cout << std::endl;
    // Output: 9 6 5 4 3 2 1 1
    return 0;
}

3.2 Building a Min-Heap

To get a min-heap (smallest element on top), pass std::greater<T> as the comparator. Note that you must also specify the underlying container type, since the comparator is the third template parameter.

#include <queue>
#include <vector>
#include <functional>

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

for (int x : {3, 1, 4, 1, 5, 9, 2, 6}) {
    min_pq.push(x);
}
// min_pq.top() == 1

3.3 Custom Element Types

For custom types, either provide an operator< (and rely on the default std::less), or pass a custom comparator (see the next section).

struct Task {
    int priority;
    std::string name;
};

// Option A: define operator< on the type itself
bool operator<(const Task& a, const Task& b) {
    return a.priority < b.priority;  // higher priority on top
}

std::priority_queue<Task> tasks;

4. Writing Custom Comparators

A comparator for std::priority_queue, std::set, std::map, and std::sort must implement a strict weak ordering: cmp(a, b) returns true when a strictly precedes b, and false otherwise (including when a == b).

For priority_queue, remember the inversion: returning true from cmp(a, b) means a has lower priority than b, i.e. b will be popped first.

4.1 Function Object (Functor)

A class with operator() is the most flexible form: it can hold state, and its type is known at compile time so the compiler can inline calls.

#include <queue>
#include <vector>
#include <string>

struct CompareTaskByPriority {
    bool operator()(const Task& a, const Task& b) const {
        // Min-heap by priority: smaller 'priority' value comes out first
        return a.priority > b.priority;
    }
};

std::priority_queue<Task, std::vector<Task>, CompareTaskByPriority> tasks;

4.2 Lambda

Lambdas are concise but require passing both the type (decltype) and the lambda object, because each lambda has a unique anonymous type.

#include <queue>
#include <vector>

auto cmp = [](const Task& a, const Task& b) {
    return a.priority > b.priority;  // min-heap by priority
};

std::priority_queue<Task, std::vector<Task>, decltype(cmp)> tasks(cmp);

In C++20 and later, stateless lambdas are default-constructible, so the constructor argument can be omitted:

std::priority_queue<Task, std::vector<Task>, decltype(cmp)> tasks;  // C++20

4.3 Free Function or Function Pointer

A free function works too, but you must pass its pointer at construction time and use decltype(&fn) (or a typedef) as the comparator type.

bool taskLess(const Task& a, const Task& b) {
    return a.priority > b.priority;
}

std::priority_queue<Task, std::vector<Task>, decltype(&taskLess)>
    tasks(taskLess);

4.4 Strict Weak Ordering

A correct comparator must satisfy three properties:

  1. Irreflexivity: cmp(a, a) is false.
  2. Asymmetry: if cmp(a, b) is true, then cmp(b, a) is false.
  3. Transitivity: if cmp(a, b) and cmp(b, c), then cmp(a, c).

Violating these causes undefined behavior in std::sort, std::set, and std::priority_queue. A common bug is using <= instead of < — that breaks irreflexivity.

5. Other Container Tips

  1. std::vector::reserve(n) reserves capacity without changing size; use it to avoid repeated reallocations when the final size is known up front.
  2. emplace_back(args...) constructs the element in place, avoiding a copy or move. Prefer it over push_back when constructing complex types.
  3. std::map::operator[] inserts a default-constructed value if the key is missing. Use at(key) (throws on miss) or find(key) for read-only lookup.
  4. std::unordered_map requires a hash function for custom keys; specialize std::hash<Key> or pass a hasher as a template argument.
  5. Iterator invalidation rules differ per container — vector invalidates all iterators on reallocation, list/map/set only invalidate iterators to erased elements.