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

  • Linear-order containers.
  1. std::vector<T> — contiguous, dynamic array. Random access O(1); back-insert amortized O(1).
  2. std::array<T, N> — fixed-size; size known at compile time.
  3. std::deque<T> — double-ended queue; O(1) push/pop both ends; not contiguous.
  4. std::list<T> — doubly linked list; O(1) insert/remove anywhere given iterator.
  5. std::forward_list<T> — singly linked; lower memory 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 vector — cache-friendly, fastest for most workloads.
  2. array — size known at compile time, stack allocation preferred.
  3. deque — need O(1) push/pop at both ends.
  4. list — stable iterators across inserts, or cheap splice of large sections.
  5. forward_list — rarely worth it; only for memory-tight scenarios.

1.2 Associative Containers

  • Indexed by key.
  1. Ordered (red-black tree, O(log n)): set, multiset, map, multimap. Sorted-key iteration; range queries via lower_bound / upper_bound.
  2. Unordered (hash table, O(1) avg): unordered_set, unordered_multiset, unordered_map, 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 default-constructed value if key missing — never for read-only lookups. Prefer at(), find(), contains() (C++20).
  2. unordered_map requires hash for custom keys — specialize std::hash<Key> or pass hasher as template arg.
  3. map iterates sorted-key; unordered_map iterates in impl-defined order.

1.3 Container Adaptors

  • Wrap underlying container, expose restricted interface.
  1. std::stack<T> — LIFO; default std::deque<T> underneath.
  2. std::queue<T> — FIFO; default std::deque<T> underneath.
  3. std::priority_queue<T> — heap; default 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: adaptors don't expose iterators. To iterate, use underlying container directly (std::deque<int> instead of std::queue<int>).

2. Iterating Over Containers

  • Most STL ops return iterators / iterator pairs, but day-to-day code rarely needs them directly.
  • Modern C++ → range-based loops + structured bindings.

2.1 Range-Based for (Most Common)

  • Default in C++11+. Works on anything with begin()/end() (STL containers, raw arrays, 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 reference type with intent:

  1. for (T x : v) — copy. Only for cheap-to-copy types (int, char).
  2. for (const T& x : v) — read-only, no copy. Default read access.
  3. for (T& x : v) — mutable ref. Default write access.
  4. for (auto&& x : v) — universal ref; works with proxies (vector<bool>, C++20 views).

2.2 Iterator-Based for

  • For when you need the iterator itself — erase, advancing by >1, computing 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 list/map, erase only invalidates erased iterator — same defensive it = container.erase(it) pattern works everywhere.

2.3 Index-Based for (Random-Access Only)

  • Works on vector, deque, array, raw arrays — anything with operator[].
  • Use when index itself matters (printing positions, parallel iteration over same-length vectors).
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";
}
  • Map iteration with key + value → prefer structured bindings (next section).

2.4 Structured Bindings (C++17)

  • For iterating maps or ranges of pair/tuple — 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

  • Function-style alternative for applying a callable to each element. Less common than range-for, but 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

  • Heap-based container adaptor. Template:
template <
    class T,
    class Container = std::vector<T>,
    class Compare   = std::less<typename Container::value_type>
> class priority_queue;
  • top() returns element where Compare(top, other) is false for every other — i.e., "largest" under chosen comparator (ties allowed).

3.1 Default Behavior: Max-Heap

  • Default std::less<T> → max-heap (largest 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

  • Pass std::greater<T> as comparator. Must also specify underlying container (comparator is 3rd template param).
#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

  • Either provide operator< (default std::less works), or pass custom comparator (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

  • Comparator for priority_queue, set, map, sort must implement strict weak ordering:
    • cmp(a, b) returns true when a strictly precedes b; false otherwise (incl. a == b).
  • For priority_queue — inversion: cmp(a, b) true → a has lower priority than b; b popped first.

4.1 Function Object (Functor)

  • Most flexible — can hold state; type known at compile time → compiler inlines 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

  • Concise but requires both type (decltype) + lambda object — each lambda has 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);
  • C++20+: stateless lambdas are default-constructible, so ctor arg can be omitted:
std::priority_queue<Task, std::vector<Task>, decltype(cmp)> tasks;  // C++20

4.3 Free Function or Function Pointer

  • Works, but pass pointer at construction + use decltype(&fn) (or typedef) as 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

  • Correct comparator must satisfy:
  1. Irreflexivity — cmp(a, a) is false.
  2. Asymmetry — cmp(a, b) true → cmp(b, a) false.
  3. Transitivity — cmp(a, b) + cmp(b, c) → cmp(a, c).
  • Violations → UB in sort, set, priority_queue. Common bug: <= instead of < (breaks irreflexivity).

5. Other Container Tips

  1. vector::reserve(n) — reserves capacity without changing size; avoids repeated reallocations when final size is known.
  2. emplace_back(args...) — constructs in place, avoids copy/move. Prefer over push_back for complex types.
  3. map::operator[] — inserts default-constructed value if missing. Use at(key) (throws) or find(key) for read-only.
  4. unordered_map — requires hash for custom keys; specialize std::hash<Key> or pass hasher template arg.
  5. Iterator invalidation differs per container — vector invalidates all on realloc; list/map/set only invalidate iterators to erased elements.