3 The Standard Template Library

In Gorgo Starting C++ you learned std::vector and std::array — the two workhorses of sequential storage. But not every problem is a list. Sometimes you need to look up a value by key, enforce uniqueness, or process items in priority order. The Standard Template Library (STL) provides a rich set of containers, each optimized for different access patterns. In Chapter 2 you learned that these containers are class templates — they work with any type. In this chapter you will learn the associative containers, unordered containers, and container adaptors, and how to choose the right one for the job.

3.1 More Sequence Containers

std::vector and std::array from Gorgo Starting C++ are sequence containers — elements stored in order, accessed by position. The library provides three more sequence containers for cases where vector does not fit the access pattern.

3.1.1 `std::deque`

std::deque<T> is a double-ended queue: O(1) push_back and push_front, indexed access, but the elements are not stored in one contiguous block — they live in fixed-size chunks chained together.

#include <deque>
#include <iostream>

int main() {
    std::deque<int> d = {2, 3, 4};
    d.push_front(1);            // {1, 2, 3, 4}  --- vector cannot do this in O(1)
    d.push_back(5);             // {1, 2, 3, 4, 5}

    std::cout << d.front() << " " << d[2] << " " << d.back() << "\n";
    return 0;
}

Reach for deque when you need fast insertion at both ends and you do not need the strict cache-friendly contiguity of vector. A real example: a sliding-window buffer that drops the oldest element each tick and appends a new one.

Wut: A deque looks contiguous from the outside (d[i] is O(1)) but is not contiguous in memory. You cannot pass &d[0] to a C API that expects a single flat array — use vector for that.

3.1.2 `std::list` and `std::forward_list`

std::list<T> is a doubly linked list, and std::forward_list<T> is a singly linked list. Both give you O(1) insertion and deletion anywhere in the sequence (provided you already have an iterator to the spot), at the cost of poor cache locality and no random access:

#include <iostream>
#include <iterator>
#include <list>

int main() {
    std::list<int> nums = {1, 2, 4, 5};
    auto it = std::next(nums.begin(), 2);   // points at 4
    nums.insert(it, 3);                     // O(1): {1, 2, 3, 4, 5}
    nums.remove(2);                         // O(n): scan for value 2

    for (int n : nums) std::cout << n << " ";
    std::cout << "\n";
    return 0;
}

In modern C++, you reach for list rarely. The cache penalty of chasing pointers usually loses to vector even when you are inserting in the middle, because copying a few thousand ints is faster than the cumulative cache misses of walking a linked list. The legitimate uses are when you need to splice (move a sub-range from one list to another in O(1)), or when you need iterator stability across insertions.

forward_list halves the per-node memory overhead by dropping the back-pointer, at the cost of not being able to walk backward. Use it only when memory is genuinely tight; otherwise list (or, far more often, vector) is the right tool.

Tip: “I am inserting in the middle a lot, so I should use a list” is a common but usually wrong instinct. Measure first. For typical sizes (a few thousand elements or fewer), vector plus std::rotate or std::erase_if will outperform list because of cache locality.

3.2 Associative Containers

Associative containers store elements in sorted order and provide efficient lookup, insertion, and deletion — typically O(log n). They are implemented as balanced binary search trees (usually red-black trees).

3.2.1 `std::map`

std::map<Key, Value> stores key-value pairs sorted by key. Each key is unique:

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> album_years;
    album_years["Elephant"] = 2003;
    album_years["Hot Fuss"] = 2004;
    album_years["Funeral"] = 2004;

    for (const auto& [album, year] : album_years) {
        std::cout << album << ": " << year << "\n";
    }

    return 0;
}

Elephant: 2003
Funeral: 2004
Hot Fuss: 2004

The output is sorted alphabetically by key. The const auto& [album, year] syntax is a structured binding that unpacks each std::pair<const std::string, int> in the map.

Key operations:

// Insert or update
album_years["X&Y"] = 2005;
album_years.insert({"Absolution", 2003});

// Lookup
if (album_years.count("Funeral") > 0) {
    std::cout << "Found\n";
}

// C++20: contains()
//   bool contains(const Key& key) const;
if (album_years.contains("Funeral")) {
    std::cout << "Found\n";
}

// Safe access with find()
//   iterator find(const Key& key);
auto it = album_years.find("Elephant");
if (it != album_years.end()) {
    std::cout << it->second << "\n";  // 2003
}

Trap: Using operator[] on a key that does not exist will insert a default-constructed value. If you just want to check whether a key exists, use find() or contains() instead.

3.2.2 `std::set`

std::set<T> stores unique values in sorted order. It is like a map with only keys:

#include <iostream>
#include <set>
#include <string>

int main() {
    std::set<std::string> genres;
    genres.insert("Rock");
    genres.insert("Pop");
    genres.insert("Rock");  // duplicate --- ignored
    genres.insert("Indie");

    for (const auto& g : genres) {
        std::cout << g << "\n";
    }

    std::cout << "Size: " << genres.size() << "\n";

    return 0;
}

Indie
Pop
Rock
Size: 3

insert() returns a std::pair<iterator, bool> — the bool tells you whether the insertion actually happened:

auto [it, inserted] = genres.insert("Pop");
if (!inserted) {
    std::cout << "Pop was already in the set\n";
}

3.2.3 `std::multimap` and `std::multiset`

std::multimap and std::multiset are like map and set but allow duplicate keys:

#include <iostream>
#include <map>
#include <string>

int main() {
    std::multimap<std::string, std::string> songs_by_genre;
    songs_by_genre.insert({"Rock", "Seven Nation Army"});
    songs_by_genre.insert({"Rock", "Mr. Brightside"});
    songs_by_genre.insert({"Pop", "Crazy in Love"});
    songs_by_genre.insert({"Pop", "Toxic"});

    // equal_range returns a pair of iterators: [first match, past last match)
    //   pair<iterator, iterator> equal_range(const Key& key);
    auto [begin, end] = songs_by_genre.equal_range("Rock");
    std::cout << "Rock songs:\n";
    for (auto it = begin; it != end; ++it) {
        std::cout << "  " << it->second << "\n";
    }

    return 0;
}

Rock songs:
  Seven Nation Army
  Mr. Brightside

Tip: multimap does not have operator[] because a key can map to multiple values. Use find(), equal_range(), or a range-based loop to access elements.

3.3 Unordered Containers

Unordered containers use hash tables instead of trees. They provide O(1) average-case lookup, insertion, and deletion — faster than the O(log n) of ordered containers. The trade-off is that elements are not stored in any particular order.

3.3.1 `std::unordered_map`

std::unordered_map<Key, Value> is the hash-table equivalent of std::map:

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> play_counts;
    play_counts["Rehab"] = 42;
    play_counts["Poker Face"] = 87;
    play_counts["Use Somebody"] = 55;

    play_counts["Rehab"] += 1;

    for (const auto& [song, count] : play_counts) {
        std::cout << song << ": " << count << " plays\n";
    }

    return 0;
}

The output order is not alphabetical — it depends on the hash function and internal bucket layout.

The API is nearly identical to std::map: operator[], find(), contains(), insert(), erase() all work the same way.

3.3.2 `std::unordered_set`

std::unordered_set<T> is the hash-table equivalent of std::set:

#include <iostream>
#include <string>
#include <unordered_set>

int main() {
    std::unordered_set<std::string> tags = {"chill", "summer", "dance", "chill"};

    std::cout << "Tags (" << tags.size() << "):\n";
    for (const auto& t : tags) {
        std::cout << "  " << t << "\n";
    }

    return 0;
}

Duplicates are ignored, just like std::set, but the elements are not sorted.

Wut: To use a custom type as a key in an unordered container, you must provide a hash function and an equality operator. Standard types like std::string, int, and double already have hash functions.

3.3.3 Ordered vs. Unordered

Feature	`map`/`set`	`unordered_map`/`unordered_set`
Order	Sorted by key	No guaranteed order
Lookup	O(log n)	O(1) average, O(n) worst
Insertion	O(log n)	O(1) average, O(n) worst
Requires	`operator<` or comparator	Hash function + `operator==`
Memory	Tree nodes (pointer overhead)	Hash buckets (may waste space)

Use ordered containers when you need sorted iteration or range queries. Use unordered containers when you only need fast lookup by key.

3.4 Container Adaptors

Container adaptors wrap an underlying container and restrict its interface to provide a specific behavior. They are not full containers — you cannot iterate through them.

3.4.1 `std::stack`

std::stack<T> provides LIFO (last in, first out) access:

#include <iostream>
#include <stack>
#include <string>

int main() {
    std::stack<std::string> history;
    history.push("Chasing Cars");
    history.push("How to Save a Life");
    history.push("Fix You");

    while (!history.empty()) {
        std::cout << history.top() << "\n";
        history.pop();
    }

    return 0;
}

Fix You
How to Save a Life
Chasing Cars

Key methods:

void push(const T& value);    // add to top
void pop();                   // remove from top (does not return it)
T& top();                     // access top element
bool empty() const;
size_t size() const;

Trap: pop() does not return the removed element. You must call top() first to get the value, then pop() to remove it.

push() is also overloaded for rvalues: void push(T&& value);.

3.4.2 `std::queue`

std::queue<T> provides FIFO (first in, first out) access:

#include <iostream>
#include <queue>
#include <string>

int main() {
    std::queue<std::string> playlist;
    playlist.push("Crazy");
    playlist.push("Gold Digger");
    playlist.push("Single Ladies");

    while (!playlist.empty()) {
        std::cout << "Now playing: " << playlist.front() << "\n";
        playlist.pop();
    }

    return 0;
}

Now playing: Crazy
Now playing: Gold Digger
Now playing: Single Ladies

Key methods:

void push(const T& value);    // add to back
void pop();                   // remove from front
T& front();                   // access front element
T& back();                    // access back element
bool empty() const;
size_t size() const;

As with std::stack, push() also has an rvalue overload: void push(T&& value);.

3.4.3 `std::priority_queue`

std::priority_queue<T> is a queue where the highest-priority element is always at the top. By default, it is a max-heap — the largest element has the highest priority:

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);

    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    std::cout << "\n";

    return 0;
}

50 30 20 10

To get a min-heap (smallest first), use std::greater<T> (from <functional>) as the comparator:

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

3.5 Iterators in Depth

Every container you have seen so far hands out iterators through begin() and end(). Gorgo Starting C++ used iterators as “pointers into a container.” That intuition is mostly right, but iterators come in different categories, and a few iterator behaviors — invalidation, constness, reverse traversal — routinely trip up readers of other people’s code.

3.5.1 Iterator Categories

Not all iterators support the same operations. The standard organizes them into a hierarchy:

Category	Can do	Examples
Input	`*it`, `++it`, single pass forward	reading from `std::cin`
Output	`*it = x`, `++it`, single pass forward	`std::back_inserter`
Forward	input/output + multi-pass	`std::forward_list::iterator`
Bidirectional	forward + `--it`	`std::list`, `std::map`, `std::set`
Random access	bidirectional + `it + n`, `it - it2`, `it[n]`	`std::vector`, `std::deque`, raw arrays
Contiguous (C++20)	random access + memory is contiguous	`std::vector`, `std::array`, raw arrays

Algorithms list the category they require. std::sort needs random-access iterators, so std::sort(list.begin(), list.end()) is a compile error — a list only gives you bidirectional iterators. std::list provides its own list.sort() member function that knows how to sort linked lists.

Tip: When an algorithm refuses to compile with a particular container’s iterator, the error is almost always “wrong iterator category.” Check the algorithm’s docs for the minimum category it requires.

3.5.2 `cbegin` / `cend` and Reverse Iterators

Every container provides begin() and end(), plus four variants:

cbegin() / cend() — iterators that are guaranteed const, so *it = x will not compile. Useful when you want a read-only view even from a non-const container.
rbegin() / rend() — reverse iterators, walking from the last element back to the first.
crbegin() / crend() — both: const reverse.

#include <iostream>
#include <vector>

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

    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        std::cout << *it << " ";        // 5 4 3 2 1
    }
    std::cout << "\n";

    for (auto it = v.cbegin(); it != v.cend(); ++it) {
        // *it = 0;                     // ERROR: const iterator
        std::cout << *it << " ";
    }
    std::cout << "\n";
    return 0;
}

Reverse iterators are real iterators with one quirk: rbegin() points at the last element (not one before it), and rend() points one before the first. Incrementing a reverse iterator moves it toward the front of the container.

3.5.3 Iterator Invalidation

The single most important iterator rule: an iterator stays valid only as long as the underlying container is not modified in a way that disturbs that element.

Each container has its own rules:

vector — push_back, insert, erase, and resize invalidate iterators (and pointers and references) at and after the modification point — and all of them if the operation triggers a reallocation, as reserve-with-growth always does. A capacity-preserving push_back invalidates only the past-the-end iterator.
deque — any insert or erase that is not at one of the ends invalidates all iterators. Insert at the ends invalidates all iterators but leaves references valid; erase at the ends invalidates only iterators and references to the erased elements.
list / forward_list — only iterators to the erased element become invalid; everything else keeps working.
map / set / unordered_map / unordered_set — erase invalidates only iterators to the erased element. For tree-based containers, insert never invalidates anything; for hash-based containers, insert may invalidate iterators when the hash table rehashes (but pointers and references survive).

A classic broken loop:

std::vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); ++it) {
    if (*it == 3) {
        v.erase(it);                  // invalidates `it`
        // ++it on next iteration is undefined behavior
    }
}

The fix is to use the iterator that erase returns:

for (auto it = v.begin(); it != v.end(); ) {
    if (*it == 3) {
        it = v.erase(it);             // erase returns the next valid iterator
    } else {
        ++it;
    }
}

Or, even better, use std::erase_if(v, [](int n) { return n == 3; }); (C++20, declared in each container’s own header — <vector> here) and let the library do it correctly.

Trap: Iterator invalidation is undefined behavior, not a runtime error. A program that ignores the invalidation rules may appear to work — right up until you change compilers, optimization level, or container size, at which point it silently corrupts memory.

3.5.4 Hashing Custom Types

The default std::unordered_map<Key, Value> uses std::hash<Key> and Key::operator== to bucket and compare keys. The standard library specializes std::hash for the built-in types and std::string, but for your own types you have to provide both.

#include <functional>
#include <string>
#include <unordered_set>

struct Track {
    std::string title;
    int         year;

    bool operator==(const Track& other) const = default;
};

template<>
struct std::hash<Track> {
    std::size_t operator()(const Track& t) const noexcept {
        std::size_t h1 = std::hash<std::string>{}(t.title);
        std::size_t h2 = std::hash<int>{}(t.year);
        return h1 ^ (h2 << 1);                  // simple combine
    }
};

int main() {
    std::unordered_set<Track> seen;
    seen.insert({"Hey Ya!", 2003});
    return 0;
}

The point is that opting into unordered_set<MyType> is a deliberate two-step act: define equality, then specialize std::hash.

Trap: Do not ship a plain h1 ^ h2 as your real hash combiner. XOR is commutative and self-inverse, so swapped pairs collapse against each other — 0xAAAA ^ 0x5555 and 0x5555 ^ 0xAAAA both combine to 0xFFFF, for example. The h1 ^ (h2 << 1) form above shifts one operand to break that symmetry, but it is still a weak mix. For production code, use a proven helper:

boost::hash_combine (<boost/container_hash/hash.hpp>) is the canonical reference.
std::format + std::hash<std::string> is a slow but trivially-correct fallback when you don’t have Boost.
Hand-rolled mixing along the lines of seed ^= h + 0x9e3779b9 + (seed << 6) + (seed >> 2); (the formula Boost used for many years) avoids the collapse but should be copied from a known-good source rather than reinvented.

The h1 ^ (h2 << 1) form above is fine for one-shot examples and tests, not for code that goes near a real workload.

Tip: If you skip the std::hash specialization, the compiler error is long and confusing — usually something about “no matching function for call to std::hash<...>.” The fix is always to provide the specialization (or pass a custom hash type as the third template argument).

3.6 Choosing the Right Container

Here is a quick decision guide:

Need	Container
Sequential access, dynamic size	`std::vector`
Fixed-size array	`std::array`
Fast `push_front` and `push_back`	`std::deque`
Stable iterators across mid-sequence inserts	`std::list`
Fast lookup by key (sorted)	`std::map`
Fast lookup by key (unsorted)	`std::unordered_map`
Unique values (sorted)	`std::set`
Unique values (unsorted)	`std::unordered_set`
Duplicate keys allowed (sorted)	`std::multimap` / `std::multiset`
LIFO (stack behavior)	`std::stack`
FIFO (queue behavior)	`std::queue`
Priority-based access	`std::priority_queue`

When in doubt, start with std::vector. It has the best cache performance and works well for most tasks. Switch to a different container only when you have a specific need that std::vector does not serve well.

Tip: std::vector is almost always faster than you expect. Even linear search through a small vector often beats hash table or tree lookup because of CPU cache effects. Profile before switching containers.

3.7 Try It: Container Sampler

Here is a program that exercises multiple container types. Type it in, compile with g++ -std=c++23, and experiment:

#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>

int main() {
    // map: album ratings
    std::map<std::string, double> ratings;
    ratings["Hot Fuss"] = 4.5;
    ratings["Elephant"] = 4.8;
    ratings["Funeral"] = 4.7;
    ratings["X&Y"] = 3.9;

    std::cout << "Albums (sorted):\n";
    for (const auto& [album, rating] : ratings) {
        std::cout << "  " << album << ": " << rating << "\n";
    }

    // set: unique genres
    std::set<std::string> genres = {"Rock", "Indie", "Pop", "Rock", "Indie"};
    std::cout << "\nGenres: ";
    for (const auto& g : genres) {
        std::cout << g << " ";
    }
    std::cout << "\n";

    // unordered_map: fast lookup
    std::unordered_map<std::string, int> track_num;
    track_num["Intro"] = 1;
    track_num["Verse"] = 2;
    track_num["Chorus"] = 3;

    if (track_num.contains("Chorus")) {
        std::cout << "\nChorus is track " << track_num["Chorus"] << "\n";
    }

    // stack: undo history
    std::stack<std::string> undo;
    undo.push("add track");
    undo.push("change volume");
    undo.push("delete track");

    std::cout << "\nUndo stack:\n";
    while (!undo.empty()) {
        std::cout << "  undo: " << undo.top() << "\n";
        undo.pop();
    }

    // priority_queue: highest rated first
    std::priority_queue<std::pair<double, std::string>> top_albums;
    for (const auto& [album, rating] : ratings) {
        top_albums.push({rating, album});
    }

    std::cout << "\nTop albums:\n";
    while (!top_albums.empty()) {
        auto [rating, album] = top_albums.top();
        std::cout << "  " << album << " (" << rating << ")\n";
        top_albums.pop();
    }

    return 0;
}

Try adding a std::multimap that maps genres to multiple songs. Experiment with std::unordered_set and see how the iteration order differs from std::set.

3.8 Key Points

Associative containers (std::map, std::set, std::multimap, std::multiset) store elements in sorted order using balanced trees, with O(log n) operations.
std::map stores unique key-value pairs; std::set stores unique values only.
std::multimap and std::multiset allow duplicate keys.
Unordered containers (std::unordered_map, std::unordered_set) use hash tables for O(1) average-case operations, but elements have no guaranteed order.
Use contains() (C++20) or find() to check for existence without inserting. operator[] on a map inserts a default value if the key is missing.
Container adaptors (std::stack, std::queue, std::priority_queue) wrap other containers to provide restricted interfaces.
stack is LIFO, queue is FIFO, priority_queue is a max-heap by default.
pop() on adaptors does not return the removed element — call top() or front() first.
When choosing a container, start with std::vector and switch only when you have a specific need.
Use structured bindings (auto [key, value]) to iterate over maps concisely.
std::deque gives you O(1) push at both ends; std::list and std::forward_list give you cheap mid-sequence insertion at the cost of cache locality.
Iterators come in categories (input, output, forward, bidirectional, random access, contiguous); algorithms list the minimum category they require.
cbegin/cend produce const iterators; rbegin/rend walk the container backward.
Iterator invalidation rules vary by container; modifying a container while iterating it is the most common source of memory-safety bugs in C++ collections code.
To use a custom type as a key in an unordered container, define both operator== and a std::hash specialization.

3.9 Exercises

Think about it: Why does std::map::operator[] insert a default value when the key is missing, instead of throwing an exception? What would the implications be if it threw instead?

What does this print?

std::map<std::string, int> m;
m["b"] = 2;
m["a"] = 1;
m["c"] = 3;

for (const auto& [k, v] : m) {
    std::cout << k << v;
}
std::cout << "\n";

Where is the bug?

std::map<std::string, int> scores;
scores["Alice"] = 95;
scores["Bob"] = 87;

int charlie_score = scores["Charlie"];
std::cout << "Charlie: " << charlie_score << "\n";

What does this print?

std::set<int> s = {5, 3, 1, 4, 1, 5, 3};
std::cout << s.size() << "\n";

Calculation: A std::map<std::string, int> has 1,000,000 entries. Approximately how many comparisons does a lookup require? (Hint: O(log n) with base 2.)
Think about it: When would you choose std::map over std::unordered_map? Give two concrete scenarios.

What does this print?

std::stack<int> s;
s.push(10);
s.push(20);
s.push(30);
s.pop();
std::cout << s.top() << "\n";
s.pop();
std::cout << s.top() << "\n";

Where is the bug?

std::priority_queue<int> pq;
pq.push(5);
pq.push(15);
pq.push(10);

int smallest = pq.top();
std::cout << "Smallest: " << smallest << "\n";

What does this print?

std::multiset<int> ms = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
std::cout << ms.count(5) << "\n";

Write a program that reads words from the user (one per line, until they type “done”) and uses a std::map<std::string, int> to count how many times each word was entered. Print the word counts in alphabetical order.

What does this print?

#include <deque>
#include <iostream>

int main() {
    std::deque<int> d = {2, 3};
    d.push_front(1);
    d.push_back(4);
    for (auto it = d.crbegin(); it != d.crend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";
    return 0;
}

Where is the bug?

#include <vector>

int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    for (auto it = v.begin(); it != v.end(); ++it) {
        if (*it % 2 == 0) {
            v.erase(it);
        }
    }
    return 0;
}

What goes wrong on the first even element? Rewrite the loop two ways: once using the value erase returns, and once using a single call to a C++20 algorithm.

Think about it: Which iterator category does std::map<std::string, int>::iterator belong to? Why can you not call std::sort on a std::map’s iterators, and what is the alternative if you really want to “sort” a map?

Where is the bug?

#include <unordered_set>

struct Point { int x, y; };

int main() {
    std::unordered_set<Point> seen;
    seen.insert({1, 2});
    return 0;
}

What two things is the program missing? Add the smallest changes that make it compile and behave correctly.

3 The Standard Template Library

3.1 More Sequence Containers

3.1.1 std::deque

3.1.2 std::list and std::forward_list

3.2 Associative Containers

3.2.1 std::map

3.2.2 std::set

3.2.3 std::multimap and std::multiset

3.3 Unordered Containers

3.3.1 std::unordered_map

3.3.2 std::unordered_set

3.3.3 Ordered vs. Unordered

3.4 Container Adaptors

3.4.1 std::stack

3.4.2 std::queue

3.4.3 std::priority_queue

3.5 Iterators in Depth

3.5.1 Iterator Categories

3.5.2 cbegin / cend and Reverse Iterators

3.5.3 Iterator Invalidation

3.5.4 Hashing Custom Types

3.6 Choosing the Right Container

3.7 Try It: Container Sampler

3.8 Key Points

3.9 Exercises

3.1.1 `std::deque`

3.1.2 `std::list` and `std::forward_list`

3.2.1 `std::map`

3.2.2 `std::set`

3.2.3 `std::multimap` and `std::multiset`

3.3.1 `std::unordered_map`

3.3.2 `std::unordered_set`

3.4.1 `std::stack`

3.4.2 `std::queue`

3.4.3 `std::priority_queue`

3.5.2 `cbegin` / `cend` and Reverse Iterators