# Container adaptors and flat containers

> stack, queue and priority_queue restrict a real container to a narrow interface, and the C++23 flat_map and flat_set family turns sorted vectors into associative containers. Both trade a wide interface for a layout you can reason about, and both have sharp edges.

- **Source:** C++ Atlas (https://cppatlas.com/topics/container-adaptors-and-flat-containers)
- **Track:** Containers and strings
- **Estimated reading time:** 12 minutes
- **ISO C++ clauses:** [container.adaptors] (https://eel.is/c++draft/container.adaptors), [stack] (https://eel.is/c++draft/stack), [queue] (https://eel.is/c++draft/queue), [priority.queue] (https://eel.is/c++draft/priority.queue), [flat.map] (https://eel.is/c++draft/flat.map), [flat.set] (https://eel.is/c++draft/flat.set)
- **cppreference links:** [std::stack](https://en.cppreference.com/w/cpp/container/stack), [std::queue](https://en.cppreference.com/w/cpp/container/queue), [std::priority_queue](https://en.cppreference.com/w/cpp/container/priority_queue), [std::flat_map](https://en.cppreference.com/w/cpp/container/flat_map), [std::flat_set](https://en.cppreference.com/w/cpp/container/flat_set), [std::sorted_unique](https://en.cppreference.com/w/cpp/container/sorted_unique), [std::flat_map::extract](https://en.cppreference.com/w/cpp/container/flat_map/extract)
- **Prerequisites:** sequence-containers, associative-and-unordered-containers, iterator-invalidation

## The one idea

A container adaptor is not a container. It holds a real container, the **underlying container**, as a data member and exposes only a few operations on it. `stack` shows the back, `queue` shows both ends, and `priority_queue` keeps a heap inside a random access container and shows only the largest element. The restriction is the feature: it states what the program needs and prevents anything else.

The C++23 flat containers use the same trick in the other direction. `flat_map` and `flat_set` hold a sorted sequence container, or two for a map, and add associative operations on top. They are adaptors that give you the interface of `map` and `set` with the layout of a sorted `vector`.

> **Mental model.** An adaptor is a wrapper around a sequence container plus an invariant it maintains for you. A stack's invariant is "only the back is touched", a priority queue's is "the underlying range is a heap", and a flat map's is "keys are sorted and unique and values line up with them".

## `stack`, `queue` and `priority_queue`

The defaults are `deque` for `stack` and `queue`, and `vector` for `priority_queue`. You may substitute any container that supplies the operations the adaptor calls. A stack needs `back`, `push_back` and `pop_back`. A queue needs `front`, `back`, `push_back` and `pop_front`, so it works over `deque` and `list` but not `vector`. A priority queue needs random access iterators, plus `front`, `push_back` and `pop_back`.

The requirements are checked lazily. A `std::queue<int, std::vector<int>>` can be declared and pushed to, and fails to compile only when you call `pop()`, which needs `pop_front`.

```cpp
#include <list>
#include <queue>
#include <stack>
#include <vector>

std::stack<int, std::vector<int>> s;   // a vector-backed stack: common and fast
std::queue<int, std::list<int>> q;     // OK: list has pop_front
// std::queue<int, std::vector<int>> bad; bad.pop();   // ill-formed: no pop_front
```

The interface is deliberately small. There are no iterators, so you cannot walk a stack, a queue or a priority queue; popping is the only way to see an element other than the top. `pop()` returns `void`, and `top()` and `front()` return references. A `pop` that returned the element by value could lose it if the copy or move out of the container threw, so the standard splits reading from removing. Calling `top`, `front` or `pop` on an empty adaptor is undefined behavior.

## `priority_queue`: comparator direction and the const top

`priority_queue<T, Container, Compare>` keeps the elements of its container arranged as a heap using `push_heap` and `pop_heap`. `push` and `pop` are logarithmic, `top` is constant, and building from a range is linear.

The comparator is where people trip. `Compare(a, b)` returns true when `a` comes before `b` in a weak ordering, and the queue's top is the element that comes last. The default `std::less` therefore produces a max-heap, and `std::greater` a min-heap. The comparator expresses "is lower priority than", not "should be served first".

```cpp
#include <functional>
#include <queue>
#include <vector>

std::priority_queue<int> maxq;                                         // top is largest
std::priority_queue<int, std::vector<int>, std::greater<int>> minq;   // top is smallest
```

`top()` returns a `const` reference, because changing the top element in place would silently break the heap. That has a consequence for move-only or expensive elements: `std::move(pq.top())` is a `const T&&`, which binds to the copy constructor, so you copy and leave the original in the queue.

> **Pitfall.** `T x = std::move(pq.top()); pq.pop();` compiles and runs, but it copies every time. The compiler may warn about the redundant move, which is a hint that it does nothing.

There is no member that extracts an element, but the underlying container and comparator are `protected` members named `c` and `comp`, and the standard specifies that, so a derived class can pop the heap properly and move the element out.

```cpp
#include <algorithm>
#include <functional>
#include <queue>
#include <utility>
#include <vector>

template <class T, class C = std::vector<T>, class Cmp = std::less<T>>
struct MovablePQ : std::priority_queue<T, C, Cmp> {
  T pop_value() {
    std::pop_heap(this->c.begin(), this->c.end(), this->comp);  // top moves to the back
    T v = std::move(this->c.back());
    this->c.pop_back();
    return v;
  }
};
```

C++23 adds range constructors that take `std::from_range`, and `push_range` members, to all three adaptors.

## Flat containers: sorted vectors with a map interface

C++23 added `flat_map`, `flat_set`, `flat_multimap` and `flat_multiset`. A `flat_set<T>` is a sorted `vector<T>` with no duplicates. A `flat_map<K, V>` is two vectors: a sorted vector of keys, and a vector of values where position `i` belongs to key `i`. The container types are template parameters, so you may use `deque` or any other random access container instead of `vector`.

```text
flat_map<int,char>:   keys   [ 1   3   7   9 ]   sorted, unique
                      values [ a   b   c   d ]   same positions
```

The trade-offs follow from that layout. Lookup is a binary search over contiguous memory, so it is logarithmic and cache friendly. Iteration is a linear scan and is very fast. Insertion and erasure in the middle shift elements of both vectors, so they are linear in the size. That is the opposite of `std::map`, where every operation is logarithmic and every access chases a pointer. A flat container wins when it is built once and read often, when it is small, or when iteration dominates; it loses on large containers with frequent random insertion.

Because the storage is a plain sequence, there are no nodes. That has three consequences. There are no node handles and no `merge`. Insertion and erasure invalidate iterators, references and pointers the way `vector` does, so treat every modification as invalidating everything; `clear` certainly does. And the memory is reusable: you can take the underlying containers out and put them back.

```cpp
#include <flat_map>
#include <utility>
#include <vector>

void demo() {
  std::flat_map<int, char> m{{3, 'c'}, {1, 'a'}};
  auto c = std::move(m).extract();       // m is now empty; c.keys == {1, 3}
  c.values[0] = 'z';                     // plain vectors, edit freely
  m.replace(std::move(c.keys), std::move(c.values));  // keys must be sorted, unique
}
```

`extract()` is rvalue-qualified and moves out both containers as a struct with `keys` and `values` members, leaving the map empty. `replace(keys, values)` installs them again, and the sizes must match, the keys must be sorted by the comparator, and they must be unique, or the behavior is undefined. `keys()` and `values()` give const access to the vectors without extracting.

## Building: `sorted_unique` and the cost of trust

Constructing from a general range sorts and removes duplicates. If you already have sorted, unique data, the tag `std::sorted_unique` says so and skips that work. The constructor believes you: if the data is not sorted or has equivalent keys, the behavior is undefined.

```cpp
#include <flat_map>
#include <flat_set>
#include <vector>

void demo() {
  std::vector<int> keys{1, 2, 3}, vals{10, 20, 30};
  std::flat_map<int, int> a(std::sorted_unique, keys, vals);   // trusted: O(n)
  std::flat_set<int> b{3, 1, 2, 3};                            // sorted, deduplicated
  // std::flat_set<int> c(std::sorted_unique, {3, 1, 2});      // undefined behavior
  (void)a; (void)b;
}
```

For bulk loading prefer `insert(first, last)` or `insert_range`, which append and merge, over a loop of single insertions that each shift the tail. For multi variants the tag is `std::sorted_equivalent`, which allows equal keys but still requires sorted order.

## The proxy-like reference of `flat_map`

A `flat_map` has no `pair<K, V>` objects in memory, so dereferencing an iterator cannot return a reference to one. Its `reference` type is `pair<const K&, V&>`, built on the fly and returned by value, while `value_type` is `pair<K, V>`. That differs from `map`, whose value type is `pair<const K, V>`, and it changes code that works with `map`.

```cpp
#include <flat_map>

void demo() {
  std::flat_map<int, int> m{{1, 10}, {2, 20}};
  // for (auto& [k, v] : m) v += 1;   // ill-formed: cannot bind auto& to a prvalue
  for (auto&& [k, v] : m) v += 1;     // OK
  for (auto [k, v] : m) v += 1;       // also modifies m: auto copies the pair of references
}
```

The last loop is the one that bites. `auto` copies the pair, but the pair holds references, so the value is still modified in the map. Write `auto&&`, or `const auto&` for read-only loops.

The same applies to code that stores `*it` in a variable or passes it to an algorithm expecting `value_type&`. The key is never mutable: the first element of the pair is `const K&`.

## Exception safety and implementation status

Two containers must stay in step. A flat map update is a pair of operations on two vectors, so the failure modes are different from a node-based `map`, where an insertion is a single allocation and either happens or does not. The reference documents a no-effect guarantee for single-element `insert` and `emplace`, and documents nothing for the range operations, so do not assume strong exception safety for bulk updates. The underlying containers' `size` and `max_size` must not throw.

For implementation status, I compiled and ran a `flat_map` and `flat_set` program with GCC 16.2 (libstdc++) and with Homebrew LLVM 21.1.2 (libc++), both on arm64 macOS, using `-std=c++23`. Both provide `<flat_map>` and `<flat_set>`, with the multi variants. GCC reports `__cpp_lib_flat_map` and `__cpp_lib_flat_set` as 202511, libc++ as 202207. In `-std=c++20` mode GCC does not provide the types. I did not check other implementations.

> **Standardese.** The synopses in [stack], [queue] and [priority.queue] declare the underlying container `c`, and for `priority_queue` also the comparator `comp`, as protected members, which is what makes a derived class legal and portable. For `flat_map` and `flat_set`, [flat.map] and [flat.set] define the `sorted_unique` overloads and say the input must be sorted and unique with respect to the comparator, so a violation is a precondition failure and therefore undefined behavior.

## What to remember

- An adaptor wraps a container and exposes a narrow interface; the underlying container is a template parameter.
- `stack` needs a back; `queue` needs `pop_front`, so not `vector`; `priority_queue` needs random access.
- Adaptors have no iterators, `pop()` returns `void`, and `top`, `front` and `pop` on an empty adaptor are undefined behavior.
- `priority_queue` surfaces the element that is last under the comparator: `less` gives a max-heap, `greater` a min-heap.
- `top()` is const so you cannot break the heap, which means `std::move(pq.top())` copies; move out through a derived class or `pop_heap` yourself.
- `flat_map` and `flat_set` are sorted vectors: logarithmic lookup, linear insertion and erasure, fast iteration.
- No nodes means no stable references and no node handles; `extract()` and `replace()` move whole containers in and out.
- `sorted_unique` skips sorting and trusts you; wrong input is undefined behavior.
- `flat_map` dereferences to `pair<const K&, V&>`: write `auto&&`, not `auto&`, and know that `auto` still writes through.
- GCC 16.2 and libc++ 21.1 both ship the flat containers in C++23 mode.

## Concept Map Outline

- **Adaptors and flat containers:** Narrow interfaces over real containers, and sorted vectors with a map interface.
  - **What an adaptor is:** It wraps an underlying container as a member and exposes a restricted interface.
    - **Underlying container:** A template parameter: deque for stack and queue, vector for priority_queue.
    - **Required operations:** queue needs pop_front, so vector fails at pop(); priority_queue needs random access.
    - **No iteration:** There are no iterators; pop() returns void, and top, front, pop on empty are undefined.
  - **priority_queue:** A heap kept in a random access container with push_heap and pop_heap.
    - **Comparator direction:** The top is the element that comes last: less gives a max-heap, greater a min-heap.
    - **Const top:** top() is const to protect the heap, so std::move(top()) copies instead of moving.
    - **Moving out:** Derive and use protected c and comp with pop_heap, then move from back().
    - **Complexity:** push and pop are logarithmic, top is constant, building from a range is linear.
  - **Flat container layout:** C++23 flat_map and flat_set wrap sorted sequence containers.
    - **Two vectors:** A flat_map keeps sorted keys and a parallel vector of values; flat_set keeps one sorted vector.
    - **Trade-offs:** Lookup is a cache-friendly binary search; insert and erase are linear; iteration is fast.
    - **No nodes:** No node handles or merge; insert and erase invalidate iterators and references like vector.
  - **Construction and access:** Bulk operations that trust the caller.
    - **sorted_unique:** Skips sorting; input that is unsorted or has duplicates is undefined behavior.
    - **extract and replace:** extract() moves out the keys and values containers; replace() needs equal sizes and sorted unique keys.
    - **sorted_equivalent:** The tag for multi variants: sorted input, equal keys allowed.
  - **flat_map reference type:** Dereferencing yields a prvalue pair of references.
    - **Pair of references:** reference is pair<const K&, V&> returned by value; value_type is pair<K, V>.
    - **auto& fails:** for (auto& [k, v] : m) is ill-formed; use auto&&, and know that auto still writes through.
  - **Status and safety:** Caveats for real-world use.
    - **Exception safety:** Two containers must stay in step; the reference documents no-effect only for single-element insertion.
    - **Implementation status:** GCC 16.2 libstdc++ and libc++ 21.1 ship the flat containers in C++23 mode.

## Standardese Quiz Questions

### Question 1 [warmup] ([priority.queue])

What does this program print?

```cpp
#include <iostream>
#include <queue>

int main() {
  std::priority_queue<int> pq;
  for (int x : {3, 1, 4, 1, 5}) pq.push(x);
  while (!pq.empty()) {
    std::cout << pq.top() << ' ';
    pq.pop();
  }
  std::cout << '\n';
}
```

A. 5 4 3 1 1
B. 1 1 3 4 5
C. 3 1 4 1 5
D. 5 4 3 1

**Answer (A):** 5 4 3 1 1

**Why:** The default comparator is `std::less`, and `priority_queue` surfaces the element that is largest under the comparator, so the default is a max-heap and the pops come out in descending order. Duplicates are kept, so the second 1 is printed too. Getting ascending order needs `std::greater` as the comparator.

### Question 2 [warmup] ([stack])

Is this program well-formed?

```cpp
#include <stack>

int main() {
  std::stack<int> s;
  s.push(1);
  int x = s.pop();
  (void)x;
}
```

A. No: `pop` returns `void`
B. Yes; `x` is 1
C. Yes; the value of `x` is unspecified
D. Yes, but undefined behavior at run time

**Answer (A):** No: `pop` returns `void`

**Why:** `stack::pop` only removes the top element and returns `void`. Reading is done with `top()` and removing with `pop()`, so the program is rejected at compile time. The split is deliberate: a `pop` that returned the element by value could lose it if the copy or move out threw.

### Question 3 [warmup] ([queue], [container.adaptors])

Is this program well-formed?

```cpp
#include <queue>
#include <vector>

int main() {
  std::queue<int, std::vector<int>> q;
  q.push(1);
  q.pop();
}
```

A. Yes
B. No: `queue` requires a `list` as its underlying container
C. No: `pop()` needs `pop_front`, which `vector` lacks
D. Yes, but `pop()` is undefined behavior for a `vector`

**Answer (C):** No: `pop()` needs `pop_front`, which `vector` lacks

**Why:** `queue` is built on the underlying container's `front`, `back`, `push_back` and `pop_front`. The class template can be named with a `vector`, and `push` works because `vector` has `push_back`, but `pop()` is implemented with `pop_front`, which `vector` does not provide. The default is `deque`; `list` also works.

### Question 4 [tricky] ([priority.queue])

What does this program print?

```cpp
#include <iostream>
#include <queue>
#include <vector>

int main() {
  auto cmp = [](int a, int b) { return a % 10 > b % 10; };
  std::priority_queue<int, std::vector<int>, decltype(cmp)> pq(cmp);
  for (int x : {15, 21, 7, 32}) pq.push(x);
  while (!pq.empty()) {
    std::cout << pq.top() << ' ';
    pq.pop();
  }
  std::cout << '\n';
}
```

A. 7 15 32 21
B. 21 32 15 7
C. 7 32 21 15
D. 32 21 15 7

**Answer (B):** 21 32 15 7

**Why:** The comparator returns true when its first argument should come before the second in the weak ordering, and the queue's top is the element that comes last in that ordering. With `>` on the last digit, larger last digits come first and the smallest last digit ends up on top: 1 (21), 2 (32), 5 (15), 7 (7). That is why `std::greater` gives a min-heap, and the opposite of the intuition "top is whatever my predicate prefers".

### Question 5 [tricky] ([priority.queue], [dcl.init.general])

What does this program print?

```cpp
#include <iostream>
#include <queue>
#include <string>
#include <utility>

int main() {
  std::priority_queue<std::string> pq;
  pq.push(std::string(30, 'x'));
  std::string s = std::move(pq.top());
  std::cout << s.size() << ' ' << pq.top().size() << '\n';
}
```

A. 30 0
B. Ill-formed: you cannot move from a const reference
C. Undefined behavior: the move breaks the heap
D. 30 30

**Answer (D):** 30 30

**Why:** `top()` returns a `const` reference, so `std::move(pq.top())` is a `const std::string&&`. That cannot bind to the move constructor, which takes a non-const rvalue reference, so overload resolution selects the copy constructor. The program is well-formed, `s` is a copy, and the queue's element is untouched. To really move an element out you need access to the underlying container, for example via a derived class with a `protected` member `c`, or by choosing a different design.

### Question 6 [tricky] ([flat.map])

In C++23, with a library that provides `<flat_map>`, is this program well-formed?

```cpp
#include <flat_map>

int main() {
  std::flat_map<int, int> m{{1, 10}, {2, 20}};
  for (auto& [k, v] : m) v += 1;
}
```

A. Yes; each value increases by one
B. Yes, but it increments copies, so `m` is unchanged
C. No: dereferencing an iterator yields a prvalue that `auto&` cannot bind to
D. Undefined behavior: keys must not be bound by reference

**Answer (C):** No: dereferencing an iterator yields a prvalue that `auto&` cannot bind to

**Why:** The keys and values live in two separate vectors, so there is no `pair<K, V>` in memory to refer to. `flat_map`'s `reference` type is a `pair<const K&, V&>` built on the fly, and `*it` returns it by value. A prvalue cannot bind to a non-const lvalue reference. `for (auto&& [k, v] : m)` works and modifies the values through the reference inside the pair.

### Question 7 [standardese] ([flat.set])

What does the standard say about this program?

```cpp
#include <flat_set>

int main() {
  std::flat_set<int> s(std::sorted_unique, {3, 1, 2});
}
```

A. It compiles and the set holds 1, 2, 3, sorted by the constructor
B. It is ill-formed: the tag cannot be used with a braced list
C. It throws `std::invalid_argument`
D. Undefined behavior: the elements must already be sorted and unique

**Answer (D):** Undefined behavior: the elements must already be sorted and unique

**Why:** The `sorted_unique` tag is a promise from the caller that the input is already sorted by the comparator and free of equivalent elements; the constructor trusts it and skips the sort. {3, 1, 2} is not sorted, so a precondition is violated and the behavior is undefined. Without the tag the constructor sorts and removes duplicates itself.

### Question 8 [standardese] ([flat.map])

What does the standard guarantee this program prints?

```cpp
#include <flat_map>
#include <iostream>
#include <utility>

int main() {
  std::flat_map<int, char> m{{2, 'b'}, {1, 'a'}};
  auto c = std::move(m).extract();
  std::cout << m.size() << ' ' << c.keys.size() << ' ' << c.keys[0] << '\n';
}
```

A. 2 2 1
B. 0 2 a
C. Ill-formed: `extract` takes a key, not nothing
D. 0 2 1

**Answer (D):** 0 2 1

**Why:** `flat_map::extract()` is rvalue-qualified; it moves the two underlying containers out into a `containers` struct with members `keys` and `values`, and leaves the flat_map empty even if an exception is thrown. The keys are sorted, so `keys[0]` is the integer 1, which prints as `1`; the character 'a' would be in `values[0]`. This is different from `std::map::extract(key)`, which returns a node handle.
