Container Adaptors

Overview

The C++ standard library ships three classic container adaptors: std::stack, std::queue, and std::priority_queue. All three live conceptually on top of an underlying container whose type is a template parameter with a sensible default. C++23 adds a second generation of flat adaptors — std::flat_map, std::flat_multimap, std::flat_set, and std::flat_multiset — which wrap sorted contiguous storage to deliver better cache behaviour than their tree-based counterparts.

The adaptor pattern matters because it enforces a discipline on access: you cannot accidentally index into a stack or call front() on a priority queue. The underlying container is an implementation detail the adaptor hides completely; swapping it changes performance characteristics without touching any call sites.

Underlying container requirements

std::stack and std::queue require back(), push_back(), and pop_back(). std::queue additionally needs front() and pop_front(). std::priority_queue requires random-access iterators and the full push_back / pop_back protocol, which is why std::list is excluded.

Syntax

#include <stack>
#include <queue>

// Stack — LIFO
template<typename T, typename Container = std::deque<T>>
class stack;

// Queue — FIFO
template<typename T, typename Container = std::deque<T>>
class queue;

// Priority queue — heap-ordered
template<
    typename T,
    typename Container = std::vector<T>,
    typename Compare   = std::less<typename Container::value_type>
>
class priority_queue;

Since C++17, all three support class template argument deduction (CTAD), so you can write std::stack s{1, 2, 3} when constructing from an iterator range — though the range constructor was only standardised in C++23.

Examples

std::stack — expression evaluator

std::stack backed by std::vector avoids the segment-per-block overhead of std::deque when you know the maximum depth up front.

#include <stack>
#include <stdexcept>
#include <string_view>

double eval_rpn(std::string_view expr) {
    std::stack<double, std::vector<double>> stk;  // vector backing; C++98 syntax

    for (char c : expr) {
        if (c == ' ') continue;
        if (c >= '0' && c <= '9') {
            stk.push(c - '0');
        } else {
            if (stk.size() < 2) throw std::runtime_error{"malformed RPN"};
            double b = stk.top(); stk.pop();
            double a = stk.top(); stk.pop();
            switch (c) {
                case '+': stk.push(a + b); break;
                case '-': stk.push(a - b); break;
                case '*': stk.push(a * b); break;
                case '/': stk.push(a / b); break;
                default:  throw std::runtime_error{"unknown operator"};
            }
        }
    }
    if (stk.size() != 1) throw std::runtime_error{"malformed RPN"};
    return stk.top();
}

// eval_rpn("3 4 + 2 *") == 14.0

std::queue — breadth-first search

#include <queue>
#include <unordered_map>
#include <vector>
#include <optional>

using Graph = std::unordered_map<int, std::vector<int>>;

std::optional<int> bfs_distance(const Graph& g, int src, int dst) {
    std::queue<std::pair<int,int>> q;          // {node, distance}
    std::unordered_map<int,bool>   visited;

    q.emplace(src, 0);                         // emplace; C++11
    visited[src] = true;

    while (!q.empty()) {
        auto [node, dist] = q.front();         // structured bindings; C++17
        q.pop();
        if (node == dst) return dist;
        for (int nb : g.at(node)) {
            if (!visited[nb]) {
                visited[nb] = true;
                q.emplace(nb, dist + 1);
            }
        }
    }
    return std::nullopt;                       // C++17
}

std::priority_queue — Dijkstra's shortest path

std::priority_queue is a max-heap by default. For shortest-path algorithms you want a min-heap; pass std::greater<> as the comparator (the heterogeneous void specialisation requires C++14).

#include <queue>
#include <vector>
#include <limits>

using Dist = long long;
constexpr Dist INF = std::numeric_limits<Dist>::max();

std::vector<Dist> dijkstra(int n,
                            const std::vector<std::vector<std::pair<int,Dist>>>& adj,
                            int src)
{
    // min-heap: pair<distance, node>; C++14 for std::greater<>
    using Entry = std::pair<Dist, int>;
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> pq;

    std::vector<Dist> dist(n, INF);
    dist[src] = 0;
    pq.emplace(0, src);

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();      // C++17 structured bindings
        if (d > dist[u]) continue;             // stale entry
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);
            }
        }
    }
    return dist;
}

C++23 flat container adaptors

std::flat_map and std::flat_set (headers <flat_map> and <flat_set>) use a sorted array of keys (and a separate array of values for maps) instead of a red-black tree. Lookup is O(log n) binary search over a contiguous range, which is cache-friendly for read-heavy workloads with moderate N. Insertions and erasures are O(n) due to shifting.

#include <flat_map>    // C++23
#include <flat_set>    // C++23
#include <print>       // C++23

void demo_flat() {
    std::flat_map<std::string, int> scores;    // C++23
    scores["alice"] = 42;
    scores["bob"]   = 99;
    scores.emplace("carol", 77);

    // Underlying keys and values are separate contiguous sequences
    for (const auto& [name, score] : scores) {
        std::println("{}: {}", name, score);   // C++23
    }

    std::flat_set<int> primes{2, 3, 5, 7, 11};  // C++23
    std::println("contains 7: {}", primes.contains(7));  // contains(); C++20 on flat_set C++23
}

You can also construct a std::flat_map from pre-sorted key and value containers to avoid the O(n log n) sort on construction — pass std::sorted_unique as the first argument.

Best Practices

Prefer std::vector as the stack backing when the maximum depth is bounded. std::deque allocates in fixed-size chunks; for small stacks that fit in a few cache lines, a std::vector-backed std::stack avoids extra pointer indirection.

Never call top() or front() without checking empty() first. These functions have undefined behaviour on empty adaptors — no exception is thrown. Consider wrapping in a helper that throws on precondition violation in debug builds.

Use emplace over push for non-trivial element types. Since C++11, all three adaptors expose emplace() which constructs in-place, forwarding arguments directly to the element constructor.

For std::priority_queue, store pairs {priority, payload} rather than writing a custom comparator on a struct. The pair's default operator< compares lexicographically, making the priority the first member the most natural choice. Use std::greater<> (C++14) for min-heap semantics.

Reach for C++23 std::flat_map / std::flat_set when your map is populated once and read many times. The sorted-vector representation is 2–3× faster for iteration and binary search over small-to-medium maps due to cache locality, but not suitable for maps that see frequent insertions interleaved with lookups.

Common Pitfalls

pop() returns void. All three adaptors follow the two-operation idiom: inspect with top() / front() / back(), then discard with pop(). Expecting a value from pop() is a compilation error, but the intent is a design decision from C++98 that predates move semantics — a throwing copy in a single combined operation would leave the container in a broken state.

std::priority_queue does not support iteration or arbitrary removal. You cannot remove an element from the middle. If you need a decrease-key operation (common in graph algorithms), you must either use a sentinel-invalidation trick (push a duplicate and skip stale entries, as shown in the Dijkstra example above), or use a mutable heap from Boost.

std::flat_map invalidates all iterators on insert or erase, unlike std::map. Code that holds iterators across mutation will silently access freed memory.

Comparing adaptors directly is not always possible. std::stack and std::queue support == and <=> (C++20) only if the underlying container supports them. std::priority_queue provides no comparison operators at all.

See Also

• std::deque, std::list, std::queue — the sequence containers most often used as adaptor backing
• std::flat_set — C++23 sorted flat container adaptor detail
• std::array — fixed-size contiguous sequence; occasionally useful as a stack backing with a known-small capacity