Library

since C++98

Basic

Container Adaptors

Wrapper classes that restrict and redefine the interface of sequence containers to model stacks, queues, and priority queues.

Container Adaptorssince C++98

Container adaptors are class templates that wrap an existing sequence container and expose only the interface appropriate for a specific abstract data structure — stack, queue, or priority queue.

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

Adaptor	Default container	Accepted alternatives
`std::stack`	`std::deque<T>`	`std::vector<T>`, `std::list<T>`
`std::queue`	`std::deque<T>`	`std::list<T>`
`std::priority_queue`	`std::vector<T>`	`std::deque<T>`

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

cpp

#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.

cpp

#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

cpp

#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).

cpp

#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.

cpp

#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.

`std::priority_queue` Deep Dive

The heap invariant

std::priority_queue maintains a max-heap by default: the element at top() is always the greatest according to Compare. Internally it stores elements in the underlying Container (default std::vector<T>) and calls std::push_heap / std::pop_heap / std::make_heap on that container at each mutating operation. The invariant guarantees:

top() — O(1), reads c.front()
push() / emplace() — O(log n), appends then calls push_heap
pop() — O(log n), calls pop_heap then pop_back

The comparison predicate Compare defaults to std::less<T>, meaning the largest element wins. To flip to a min-heap, supply std::greater<T>:

cpp

#include <queue>
#include <functional>  // std::greater

// Max-heap (default) — largest element at top
std::priority_queue<int> max_pq;
max_pq.push(3); max_pq.push(1); max_pq.push(4);
// max_pq.top() == 4

// Min-heap — smallest element at top
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(3); min_pq.push(1); min_pq.push(4);
// min_pq.top() == 1

// Min-heap with C++14 transparent comparator (avoids template arg)
std::priority_queue<int, std::vector<int>, std::greater<>> min_pq2;

Custom comparators

Any callable that satisfies strict weak ordering works as Compare. Lambdas require the comparator to be passed to the constructor (the type cannot be deduced from a bare lambda without CTAD), while function objects and structs work directly as template arguments.

cpp

#include <queue>
#include <string>

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

// Struct comparator — lower numeric priority value = more urgent
struct ByPriority {
    bool operator()(const Task& a, const Task& b) const {
        return a.priority > b.priority;  // inverted: smallest number wins
    }
};

std::priority_queue<Task, std::vector<Task>, ByPriority> task_queue;
task_queue.push({1, "critical"});
task_queue.push({3, "low"});
task_queue.push({2, "medium"});
// task_queue.top().name == "critical"

// Lambda comparator — must name the type via decltype
auto cmp = [](const Task& a, const Task& b) {
    return a.priority > b.priority;
};
std::priority_queue<Task, std::vector<Task>, decltype(cmp)> lambda_pq(cmp);
// C++20: can capture lambda type without passing instance in some contexts

`std::make_heap` / `std::push_heap` / `std::pop_heap` — when to use them directly

priority_queue intentionally hides its underlying container. If you need to inspect all elements (e.g., serialize the queue, remove an arbitrary element, or sort the remaining entries), use the raw heap algorithms on a plain std::vector instead:

cpp

#include <algorithm>
#include <vector>

std::vector<int> v{5, 1, 8, 3, 9, 2};

// Turn v into a max-heap in O(n)
std::make_heap(v.begin(), v.end());
// v[0] is now the largest element (9)

// Push a new element
v.push_back(7);
std::push_heap(v.begin(), v.end());   // restores heap invariant in O(log n)

// Pop the top (moves it to v.back(), does NOT erase)
std::pop_heap(v.begin(), v.end());    // O(log n)
int top = v.back();
v.pop_back();                         // now erase it

// Sort in-place (ascending) — destroys the heap
std::sort_heap(v.begin(), v.end());   // O(n log n)

The trade-off is discipline: using a raw vector lets you iterate, index, and remove arbitrary elements at the cost of having to manage the heap invariant manually. priority_queue buys you the invariant as an iron guarantee.

Accessing the Underlying Container

All three adaptors store their underlying container in a protected member named c with type Container. This is part of the standard (N4988 §[container.adaptors.general]) and is explicitly accessible to derived classes.

The inheritance trick

The cleanest way to expose c in production code is to subclass the adaptor:

cpp

#include <queue>
#include <vector>

// Exposes the protected container member of priority_queue
template<typename T,
         typename Container = std::vector<T>,
         typename Compare   = std::less<T>>
class inspectable_pq : public std::priority_queue<T, Container, Compare> {
public:
    using base = std::priority_queue<T, Container, Compare>;
    using base::base;   // inherit constructors; C++11

    // Read-only view over all elements (heap order, not sorted)
    const Container& elements() const { return this->c; }

    // Drain to a sorted vector — empties the queue
    std::vector<T> drain_sorted() {
        std::vector<T> out;
        out.reserve(this->size());
        while (!this->empty()) {
            out.push_back(this->top());
            this->pop();
        }
        return out;
    }
};

// Usage
inspectable_pq<int> pq;
pq.push(5); pq.push(2); pq.push(8);
for (int x : pq.elements()) { /* iterate in heap (not sorted) order */ }
auto sorted = pq.drain_sorted();   // {8, 5, 2}

The same pattern works for std::stack and std::queue — their protected member is also c. The reinterpret_cast technique that appears in some Stack Overflow answers is undefined behaviour and must be avoided.

Choosing the Underlying Container

`std::stack` with non-default containers

The default std::deque backing allocates in fixed-size memory blocks. For stacks where the maximum depth is known or bounded, std::vector<T> is almost always faster:

cpp

#include <stack>
#include <vector>
#include <list>

// Deque-backed (default) — good general choice; no realloc penalty
std::stack<int> s_deque;

// Vector-backed — better cache locality; single contiguous allocation
// Prefer when max depth is bounded or reserve() can be called on c
std::stack<int, std::vector<int>> s_vec;

// List-backed — stable iterators into the stack (rarely needed)
// Each element is a separate heap allocation: high per-element cost
std::stack<int, std::list<int>> s_list;

Benchmark guidance: for stacks that stay below ~1 000 elements and are push/pop heavy, std::vector backing typically wins by 20–40 % on modern hardware because elements live in a single contiguous block and the compiler can auto-vectorise load/store sequences.

`std::queue` with non-default containers

std::vector cannot back a std::queue because vector has no pop_front(). The two viable options are:

cpp

#include <queue>
#include <list>
#include <deque>

// Deque-backed (default) — O(1) push_back + pop_front; chunked allocation
std::queue<int> q_deque;

// List-backed — every node is an individual heap allocation
// Use when you need pointer/iterator stability into queue elements
// or when your element type is so large that copying on deque-reblock is costly
std::queue<int, std::list<int>> q_list;

For high-throughput producer-consumer pipelines, neither std::queue specialisation approaches lock-free ring buffers. Reach for boost::lockfree::queue or a hand-rolled power-of-two ring buffer when throughput matters more than simplicity.

`std::priority_queue` with `std::deque`

Substituting std::deque for the default std::vector backing is rare but legal:

cpp

#include <queue>
#include <deque>
#include <functional>

// Deque-backed min-heap
std::priority_queue<int, std::deque<int>, std::greater<int>> pq_deque;

The performance story is generally worse than std::vector: heap algorithms require random-access iterators and perform many index calculations; deque's chunked layout adds a layer of indirection on every access. Prefer std::vector unless iterator stability or push-front is genuinely required (it is not for a heap).

`emplace` vs `push`

All three adaptors expose emplace() since C++11. For non-trivial element types, emplace constructs the object in-place inside the container, avoiding a copy or move that push would require:

cpp

#include <queue>
#include <string>
#include <utility>   // std::pair

struct Event {
    int time;
    std::string description;
    // No copy constructor — move-only for illustration
    Event(int t, std::string d) : time(t), description(std::move(d)) {}
};

std::priority_queue<Event, std::vector<Event>,
    decltype([](const Event& a, const Event& b) {
        return a.time > b.time;   // earlier time = higher priority
    })> event_queue(
        [](const Event& a, const Event& b) { return a.time > b.time; });

// push requires constructing a temporary first:
event_queue.push(Event{10, "deadline"});  // move-constructed into container

// emplace forwards arguments directly — zero temporaries:
event_queue.emplace(5, "startup");
event_queue.emplace(15, "cleanup");
// top().description == "startup"

The difference matters when element construction is expensive (e.g., strings with SSO, large structs) or when the element type is move-only. For trivially copyable types (int, float, plain structs), the compiler eliminates the difference entirely.

Updating Priority: the Decrease-Key Problem

std::priority_queue has no decrease_key or update operation. The heap invariant is maintained globally; patching one element's key in-place without reshuffling the entire structure is not possible through the public interface. Two standard workarounds exist.

Lazy deletion (sentinel invalidation)

Push a new entry with the updated priority and mark the old one as stale. On pop, skip stale entries. This is the technique used in the Dijkstra example in the Examples section:

cpp

#include <queue>
#include <vector>
#include <unordered_set>

// Generic lazy-deletion priority queue
// T must be hashable and provide a "key" for staleness tracking
template<typename Key, typename Priority>
class lazy_pq {
    using Entry = std::pair<Priority, Key>;
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> heap_;
    std::unordered_map<Key, Priority> best_;   // current best priority per key

public:
    void push_or_update(Key k, Priority p) {
        best_[k] = p;
        heap_.emplace(p, k);   // old entry becomes stale automatically
    }

    // Returns {priority, key} of the current best; skips stale entries
    std::optional<Entry> pop() {
        while (!heap_.empty()) {
            auto [p, k] = heap_.top();
            heap_.pop();
            auto it = best_.find(k);
            if (it != best_.end() && it->second == p) {
                best_.erase(it);
                return Entry{p, k};
            }
            // stale — keep draining
        }
        return std::nullopt;
    }

    bool empty() const { return best_.empty(); }
};

The heap can grow to O(E) entries (one per relaxation in a graph algorithm), but pop amortises the drain over all operations, keeping the overall complexity O(E log E).

Direct heap manipulation for decrease-key

When you need true O(log n) decrease-key, maintain your own std::vector and call the raw heap algorithms:

cpp

#include <algorithm>
#include <vector>

// Conceptual sketch — real Dijkstra with indexed decrease-key
// Requires an index map to find an element's position in the heap
struct Node { int dist; int id; };

std::vector<Node> heap;
// ... populate ...
std::make_heap(heap.begin(), heap.end(),
    [](const Node& a, const Node& b) { return a.dist > b.dist; });

// To decrease key of node at position pos:
//   heap[pos].dist = new_dist;
//   std::push_heap(heap.begin(), heap.begin() + pos + 1, cmp);
// This is O(log n) but requires knowing pos — maintained via an index array

For production graph algorithms requiring true decrease-key with O(log n) amortised complexity, the Boost.Heap library (boost::heap::fibonacci_heap) is the practical answer. The standard library deliberately omits indexed heaps to keep the interface simple.

C++23 Flat Adaptors: A Note on Naming

std::flat_map, std::flat_multimap, std::flat_set, and std::flat_multiset (C++23, headers <flat_map> and <flat_set>) are often called "container adaptors" in the standard, but they differ from the classic three in an important way: they wrap sorted contiguous storage and expose the full associative container interface including iterators, find(), lower_bound(), and count(). They are not access-restricting wrappers.

The naming reflects the implementation strategy (adapting a sorted vector into an associative interface) rather than an interface restriction. Prefer the dedicated pages for std::flat_set and std::flat_map for detailed coverage.

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