std::deque, std::list and iterator invalidation

std::deque and std::list are the two standard sequence containers that add and remove at the front as cheaply as at the back. A deque, short for double-ended queue, keeps its elements in fixed-size blocks, so push_front and push_back take constant time and you can still read any element by its position. A list links every element in a node of its own, so it can also insert or erase in the middle in constant time and move elements between lists without copying them. The price shows in ordinary work: walking a list was far slower than walking a vector in the previous lesson’s measurement, and when all the additions and removals happen at the end, a vector is the better choice.

What sets them apart most is iterator invalidation: which iterators, pointers and references stay usable after the container changes. A deque keeps references valid when it grows at either end but invalidates every iterator; a list keeps everything valid except what points to an erased element. This lesson shows both rules failing and holding, on two compilers, and ends with the rules for every container.

std::deque: fast at both ends

// Work at both ends of a std::deque: adding and removing at the front costs the same constant time as at the back,
// and elements can still be read by position.
#include <deque>
#include <print>

int main() {
    std::deque<int> d{30, 40};
    d.push_front(20);
    d.push_front(10);
    d.push_back(50);
    std::println("{}  front {}  back {}  d[2] = {}", d, d.front(), d.back(), d[2]);
    d.pop_front();
    d.pop_back();
    std::println("after pop_front and pop_back: {}", d);
    d.insert(d.begin() + 1, 25);  // the middle: the elements on the shorter side move
    std::println("after insert at position 1: {}, size {}", d, d.size());
}

from session import run

# deque_basics.cpp built and run with Apple clang and libc++, then with GCC 16 and libstdc++.
run("""
clang++ -std=c++23 -Wall -Wextra deque_basics.cpp -o deque_basics
./deque_basics
g++-16 -std=c++23 -Wall -Wextra deque_basics.cpp -o deque_basics-gcc
./deque_basics-gcc
""")

$ clang++ -std=c++23 -Wall -Wextra deque_basics.cpp -o deque_basics
$ ./deque_basics
[10, 20, 30, 40, 50]  front 10  back 50  d[2] = 30
after pop_front and pop_back: [20, 30, 40]
after insert at position 1: [20, 25, 30, 40], size 4
$ g++-16 -std=c++23 -Wall -Wextra deque_basics.cpp -o deque_basics-gcc
$ ./deque_basics-gcc
[10, 20, 30, 40, 50]  front 10  back 50  d[2] = 30
after pop_front and pop_back: [20, 30, 40]
after insert at position 1: [20, 25, 30, 40], size 4

The interface is a vector’s, plus push_front, emplace_front and pop_front. Underneath, a deque holds an index, an array of pointers to blocks of equal size, with spare slots at both ends of the index so that it can grow in either direction:

• push_back writes into the last block’s next spare slot, and when that block is full it allocates a new block and records it in the index. push_front does the same at the other end. Either way, each call constructs one element and takes constant time, as the standard requires.
• d[i] takes two steps: find the block in the index, then the slot in the block. That is still constant time, but a little slower than a vector’s single addition.
• Inserting in the middle moves the elements on whichever side of the position is shorter, so it costs time linear in that distance.
• A deque has no reserve and no capacity, because it never needs to move its elements to grow, and no data(), because its elements are not in one block.

Blocks have a cost of their own. The previous lesson measured blocks of 4,096 bytes in libc++ and 512 bytes in libstdc++ for int elements, and that matters for small deques:

// What a small deque costs: the bytes it requested, counted by an allocator that adds them up (the counting
// allocator of the previous lesson's memory.cpp), for an empty deque, a deque of one int and a deque of 1,000 ints.
#include <cstddef>
#include <cstdlib>
#include <deque>
#include <new>
#include <print>

inline std::size_t bytes = 0;  // bytes allocated and not yet freed

template <class T>
struct Counting {
    using value_type = T;
    Counting() = default;
    template <class U>
    Counting(const Counting<U>&) noexcept {}
    T* allocate(std::size_t n) {
        bytes += n * sizeof(T);
        if (void* p = std::malloc(n * sizeof(T))) return static_cast<T*>(p);
        throw std::bad_alloc{};
    }
    void deallocate(T* p, std::size_t n) noexcept {
        bytes -= n * sizeof(T);
        std::free(p);
    }
    friend bool operator==(Counting, Counting) { return true; }
};

int main() {
    using Deque = std::deque<int, Counting<int>>;
    {
        Deque d;
        std::println("empty deque:  {:>5} bytes, plus the deque object itself, {} bytes", bytes, sizeof d);
    }
    {
        Deque d;
        d.push_back(1);
        std::println("one int:      {:>5} bytes", bytes);
    }
    {
        Deque d;
        for (int i = 0; i < 1000; ++i) d.push_back(i);
        std::println("1000 ints:    {:>5} bytes", bytes);
    }
}

from session import run

# deque_memory.cpp with libc++ (Apple clang) and with libstdc++ (GCC 16).
run("""
clang++ -std=c++23 -Wall -Wextra deque_memory.cpp -o deque_memory
./deque_memory
g++-16 -std=c++23 -Wall -Wextra deque_memory.cpp -o deque_memory-gcc
./deque_memory-gcc
""")

$ clang++ -std=c++23 -Wall -Wextra deque_memory.cpp -o deque_memory
$ ./deque_memory
empty deque:      0 bytes, plus the deque object itself, 48 bytes
one int:       4104 bytes
1000 ints:     4104 bytes
$ g++-16 -std=c++23 -Wall -Wextra deque_memory.cpp -o deque_memory-gcc
$ ./deque_memory-gcc
empty deque:    576 bytes, plus the deque object itself, 80 bytes
one int:        576 bytes
1000 ints:     4240 bytes

With libc++, a deque holding one int requested 4,104 bytes: a whole block and an index of one pointer. With libstdc++, even an empty deque requested 576 bytes, a block and an index of eight pointers, because its constructor allocates them before the first element arrives. A program that keeps thousands of short queues, such as one per open connection, pays this for every queue, while a std::vector that stays empty asks for nothing.

References survive, iterators do not

The standard’s rule for a deque is precise: an insertion at either end invalidates every iterator to the deque but does not affect the validity of references to its elements. This program takes a reference, a pointer and an iterator to the first element, adds 10,000 elements at the two ends, and then uses all three:

// push_back and push_front on a std::deque keep every reference and pointer to its elements valid, but they
// invalidate every iterator. This program checks the reference, then walks on with the old iterator, which is
// undefined behaviour: the sanitizer and the debug library in the session catch it.
#include <cstdio>
#include <deque>
#include <print>

int main() {
    std::deque<int> d{10, 20, 30};
    int& first = d.front();
    const int* where = &d.front();
    auto it = d.begin();                         // invalidated by the first push_back below

    for (int i = 0; i < 5'000; ++i) d.push_back(i);
    for (int i = 0; i < 5'000; ++i) d.push_front(-i);
    std::println("the reference still reads {}, at the same address: {}", first, &first == where);
    std::fflush(stdout);                         // print that line before any error report

    long long sum = 0;
    for (int k = 0; k < 3'000; ++k, ++it) sum += *it;  // walking with the invalidated iterator: undefined behaviour
    std::println("sum {}", sum);
}

from session import run

# deque_refs.cpp twice: with AddressSanitizer (Clang) and with libstdc++'s debug mode (GCC, -D_GLIBCXX_DEBUG). grep
# keeps the key lines of each report, and sed hides the addresses, which change on every run.
run("""
clang++ -std=c++23 -g -fsanitize=address deque_refs.cpp -o deque_refs
ASAN_OPTIONS=symbolize=0 ./deque_refs 2>&1 | grep -E "reference still|ERROR|of size" | sed -E 's/==[0-9]+==//; s/0x[0-9a-f]+/0x…/g'
g++-16 -std=c++23 -g -D_GLIBCXX_DEBUG deque_refs.cpp -o deque_refs-debug
./deque_refs-debug 2>&1 | grep -E "reference still|Error"
""")

$ clang++ -std=c++23 -g -fsanitize=address deque_refs.cpp -o deque_refs
$ ASAN_OPTIONS=symbolize=0 ./deque_refs 2>&1 | grep -E "reference still|ERROR|of size" | sed -E 's/==[0-9]+==//; s/0x[0-9a-f]+/0x…/g'
the reference still reads 10, at the same address: true
ERROR: AddressSanitizer: heap-use-after-free on address 0x… at pc 0x… bp 0x… sp 0x…
READ of size 8 at 0x… thread T0
$ g++-16 -std=c++23 -g -D_GLIBCXX_DEBUG deque_refs.cpp -o deque_refs-debug
$ ./deque_refs-debug 2>&1 | grep -E "reference still|Error"
the reference still reads 10, at the same address: true
Error: attempt to dereference a singular iterator.

The reference still read 10, at the same address, with both libraries: elements in a deque never move. The iterator is another matter. A deque iterator remembers where its block is listed in the index, and adding blocks at the ends eventually fills the index, so the deque allocates a bigger one and frees the old one. Walking on with the old iterator then reads a block pointer from freed memory: AddressSanitizer stopped the program with a heap-use-after-free, a read of 8 bytes, the size of one pointer. Without a checker, the same walk reads whatever the freed memory holds, so it may return a wrong sum or crash.

GCC’s library has a second checker, its debug mode, switched on with -D_GLIBCXX_DEBUG. Its iterators record which container they belong to and whether that container has invalidated them, so it stopped at the very first use of the old iterator with “attempt to dereference a singular iterator”. The mode changes the size and layout of the standard containers, so every file that passes containers to another must be compiled with it; it is for testing, like the sanitizers in the sanitizers lesson.

Erasing follows similar rules. pop_front and pop_back invalidate only iterators and references to the element they remove (and end() when the last element goes), while an insertion or erasure in the middle invalidates every iterator and every reference.

A sliding-window maximum with a deque

Work at both ends is not only for queues. A classic use is finding the largest of every k consecutive values in one pass, such as the worst air-quality reading in each three-hour window. Checking every window from scratch costs n × k steps. The deque below holds positions whose readings are in decreasing order: a new reading first removes smaller readings from the back, because they can never be a window’s maximum again, and the front is dropped once its position leaves the window:

// The highest of every k consecutive readings, in one pass with a std::deque of positions. The deque keeps the
// positions of readings that can still become a window's maximum, with their readings in decreasing order: the
// front is the current maximum, a new reading removes every smaller one from the back, and a position that has left
// the window is removed from the front. Each position enters and leaves the deque at most once, so the whole pass is
// O(n), while checking every window from scratch costs O(n * k).
#include <algorithm>
#include <cstddef>
#include <deque>
#include <print>
#include <random>
#include <vector>

std::vector<int> window_maxima(const std::vector<int>& readings, std::size_t k, long long& deque_steps) {
    std::vector<int> maxima;
    std::deque<std::size_t> candidates;  // positions, their readings in decreasing order
    for (std::size_t i = 0; i < readings.size(); ++i) {
        while (!candidates.empty() && readings[candidates.back()] <= readings[i]) {
            candidates.pop_back();       // a smaller reading can never be a maximum again
            ++deque_steps;
        }
        candidates.push_back(i);
        ++deque_steps;
        if (candidates.front() + k <= i) {
            candidates.pop_front();      // the maximum's position has left the window
            ++deque_steps;
        }
        if (i + 1 >= k) maxima.push_back(readings[candidates.front()]);
    }
    return maxima;
}

std::vector<int> window_maxima_slow(const std::vector<int>& readings, std::size_t k, long long& comparisons) {
    std::vector<int> maxima;
    for (std::size_t start = 0; start + k <= readings.size(); ++start) {
        int best = readings[start];
        for (std::size_t j = start + 1; j < start + k; ++j, ++comparisons) best = std::max(best, readings[j]);
        maxima.push_back(best);
    }
    return maxima;
}

int main() {
    std::vector<int> aqi{62, 75, 71, 58, 90, 84, 66, 70, 95, 61};
    long long steps = 0;
    std::println("readings     {}", aqi);
    std::println("max of 3     {}", window_maxima(aqi, 3, steps));

    std::mt19937 random(11);
    std::vector<int> many;
    for (int i = 0; i < 100'000; ++i) many.push_back(int(random() % 500));
    long long deque_steps = 0, comparisons = 0;
    auto fast = window_maxima(many, 1'000, deque_steps);
    auto slow = window_maxima_slow(many, 1'000, comparisons);
    std::println("100000 readings, windows of 1000: same maxima: {}", fast == slow);
    std::println("deque pushes and pops: {}, comparisons from scratch: {}", deque_steps, comparisons);
}

from session import run

# sliding_max.cpp built and run with both compilers and their standard libraries.
run("""
clang++ -std=c++23 -O2 -Wall -Wextra sliding_max.cpp -o sliding_max
./sliding_max
g++-16 -std=c++23 -O2 -Wall -Wextra sliding_max.cpp -o sliding_max-gcc
./sliding_max-gcc
""")

$ clang++ -std=c++23 -O2 -Wall -Wextra sliding_max.cpp -o sliding_max
$ ./sliding_max
readings     [62, 75, 71, 58, 90, 84, 66, 70, 95, 61]
max of 3     [75, 75, 90, 90, 90, 84, 95, 95]
100000 readings, windows of 1000: same maxima: true
deque pushes and pops: 199992, comparisons from scratch: 98901999
$ g++-16 -std=c++23 -O2 -Wall -Wextra sliding_max.cpp -o sliding_max-gcc
$ ./sliding_max-gcc
readings     [62, 75, 71, 58, 90, 84, 66, 70, 95, 61]
max of 3     [75, 75, 90, 90, 90, 84, 95, 95]
100000 readings, windows of 1000: same maxima: true
deque pushes and pops: 199992, comparisons from scratch: 98901999

Both versions found the same 99,001 maxima for 100,000 readings and windows of 1,000. The deque version made 199,992 pushes and pops, at most two per position, while the version that checks every window made 98,901,999 comparisons, nearly 500 times as much work. The deque is the right container here because the algorithm removes from both ends; with a vector, every removal from the front would move all the remaining positions.

std::list: nodes that never move

A std::list stores each element in its own node, linked to the previous and the next. Inserting or erasing at a known position relinks two or three pointers, and no other element is touched, so iterators, pointers and references stay valid until their own element is erased. The same idea gives a list its most useful operation, splice, which moves nodes from one position or one list to another:

// std::list moves nodes instead of elements: splice relinks nodes between positions or between lists, and
// list::sort reorders the links. No element is copied or moved, so pointers, references and iterators to the
// elements stay valid throughout and keep following their element.
#include <iterator>
#include <list>
#include <print>
#include <string>

int main() {
    std::list<std::string> folders{"inbox", "drafts", "sent", "spam", "archive"};
    auto sent = std::next(folders.begin(), 2);
    const std::string* address = &*sent;

    folders.splice(folders.begin(), folders, sent);  // move "sent" to the front: one node relinked
    std::println("{}", folders);
    std::println("the iterator still points to {:?}, same object: {}", *sent, &*sent == address);

    std::list<std::string> hidden;
    auto from = std::next(folders.begin(), 3);       // "spam"
    hidden.splice(hidden.end(), folders, from, folders.end());  // a run of nodes into another list
    std::println("folders {} | hidden {}", folders, hidden);

    folders.sort();                                  // a merge sort that relinks nodes
    std::println("sorted {}, \"sent\" has not moved in memory: {}", folders, &*sent == address);
}

from session import run

# splice.cpp built and run with both compilers and their standard libraries.
run("""
clang++ -std=c++23 -Wall -Wextra splice.cpp -o splice
./splice
g++-16 -std=c++23 -Wall -Wextra splice.cpp -o splice-gcc
./splice-gcc
""")

$ clang++ -std=c++23 -Wall -Wextra splice.cpp -o splice
$ ./splice
["sent", "inbox", "drafts", "spam", "archive"]
the iterator still points to "sent", same object: true
folders ["sent", "inbox", "drafts"] | hidden ["spam", "archive"]
sorted ["drafts", "inbox", "sent"], "sent" has not moved in memory: true
$ g++-16 -std=c++23 -Wall -Wextra splice.cpp -o splice-gcc
$ ./splice-gcc
["sent", "inbox", "drafts", "spam", "archive"]
the iterator still points to "sent", same object: true
folders ["sent", "inbox", "drafts"] | hidden ["spam", "archive"]
sorted ["drafts", "inbox", "sent"], "sent" has not moved in memory: true

• splice(pos, other, it) moves one node and splice(pos, other) moves a whole list, both in constant time. Moving a range from another list takes time linear in the range, because the list counts the moved nodes to keep both sizes right; within one list it is constant.
• After every splice, the iterator sent and the pointer address still referred to the same "sent" object, which now belongs wherever its node was linked.
• std::ranges::sort needs random access iterators, which a list does not have, so the list brings its own sort(), which relinks the nodes instead of moving elements. Even sorting left "sent" at the same address. merge, remove_if, unique and reverse are list members for the same reason.
• std::forward_list links each node to the next one only: 16 bytes per int instead of 24 in the previous lesson’s measurement. It has insert_after and erase_after instead of insert and erase, and no size().

A list is the right tool when the program holds iterators into the middle of a sequence and inserts or erases there, when it moves runs of elements between sequences, or when its elements are large objects that must never move. For everything else, the previous lesson’s measurements apply: walking a list is several times slower than walking a vector.

emplace or insert?

Every container that can add an element has two kinds of function for it. push_back, push_front and insert take an element that already exists and copy or move it in. emplace_back, emplace_front and emplace take the arguments of a constructor and build the element in the container’s own memory. This type counts what happens:

// What each way of adding an element costs, counted by a type that reports its constructions, copies and moves.
#include <deque>
#include <list>
#include <print>
#include <string>
#include <utility>
#include <vector>

struct Ticket {
    static inline int built = 0, copied = 0, moved = 0;
    std::string route;
    int seat;
    Ticket(std::string r, int s) : route(std::move(r)), seat(s) { ++built; }
    Ticket(const Ticket& t) : route(t.route), seat(t.seat) { ++copied; }
    Ticket(Ticket&& t) noexcept : route(std::move(t.route)), seat(t.seat) { ++moved; }
    static void reset() { built = copied = moved = 0; }
    static void report(const char* what) {
        std::println("{:<38} built {}  copied {}  moved {}", what, built, copied, moved);
        reset();
    }
};

int main() {
    std::deque<Ticket> d;
    Ticket t("Pune-Goa", 12);
    Ticket::reset();

    d.push_back(t);                    Ticket::report("push_back(t)");
    d.push_back(std::move(t));         Ticket::report("push_back(std::move(t))");
    d.push_back(Ticket("Pune-Goa", 14)); Ticket::report("push_back(Ticket(\"Pune-Goa\", 14))");
    d.emplace_back("Pune-Goa", 15);    Ticket::report("emplace_back(\"Pune-Goa\", 15)");

    std::list<Ticket> l;
    l.emplace(l.end(), "Goa-Pune", 3); Ticket::report("list: emplace(end, \"Goa-Pune\", 3)");

    // Growing: a vector moves its elements to a bigger buffer, a deque and a list never move them.
    std::vector<Ticket> v;
    for (int i = 0; i < 1000; ++i) v.emplace_back("Delhi-Agra", i);
    Ticket::report("vector: 1000 emplace_back");
    std::deque<Ticket> d2;
    for (int i = 0; i < 1000; ++i) d2.emplace_back("Delhi-Agra", i);
    Ticket::report("deque: 1000 emplace_back");
    std::list<Ticket> l2;
    for (int i = 0; i < 1000; ++i) l2.emplace_back("Delhi-Agra", i);
    Ticket::report("list: 1000 emplace_back");
}

from session import run

# emplace.cpp built and run with both compilers and their standard libraries.
run("""
clang++ -std=c++23 -Wall -Wextra emplace.cpp -o emplace
./emplace
g++-16 -std=c++23 -Wall -Wextra emplace.cpp -o emplace-gcc
./emplace-gcc
""")

$ clang++ -std=c++23 -Wall -Wextra emplace.cpp -o emplace
$ ./emplace
push_back(t)                           built 0  copied 1  moved 0
push_back(std::move(t))                built 0  copied 0  moved 1
push_back(Ticket("Pune-Goa", 14))      built 1  copied 0  moved 1
emplace_back("Pune-Goa", 15)           built 1  copied 0  moved 0
list: emplace(end, "Goa-Pune", 3)      built 1  copied 0  moved 0
vector: 1000 emplace_back              built 1000  copied 0  moved 1023
deque: 1000 emplace_back               built 1000  copied 0  moved 0
list: 1000 emplace_back                built 1000  copied 0  moved 0
$ g++-16 -std=c++23 -Wall -Wextra emplace.cpp -o emplace-gcc
$ ./emplace-gcc
push_back(t)                           built 0  copied 1  moved 0
push_back(std::move(t))                built 0  copied 0  moved 1
push_back(Ticket("Pune-Goa", 14))      built 1  copied 0  moved 1
emplace_back("Pune-Goa", 15)           built 1  copied 0  moved 0
list: emplace(end, "Goa-Pune", 3)      built 1  copied 0  moved 0
vector: 1000 emplace_back              built 1000  copied 0  moved 1023
deque: 1000 emplace_back               built 1000  copied 0  moved 0
list: 1000 emplace_back                built 1000  copied 0  moved 0

• push_back(t) copied the ticket and push_back(std::move(t)) moved it: both start from an object you already have.
• push_back(Ticket("Pune-Goa", 14)) built a temporary, then moved it in: one construction and one move.
• emplace_back("Pune-Goa", 15) built the ticket once, where it lives. In a list, emplace builds the element inside its new node.
• While growing to 1,000 tickets, the vector moved its elements 1,023 times, every time its buffer was full. The deque and the list moved none: they never relocate an element. The vector could move rather than copy because Ticket’s move constructor is noexcept; a vector copies, instead of moving, elements whose move constructor might throw, whenever they can be copied.

Use emplace when you would otherwise build a temporary, and push_back when you already have the object: the two cost the same then, and push_back cannot call an explicit constructor by accident.

Invalidation rules for every container

These rules come from the C++ standard. An invalidated iterator, pointer or reference may still seem to work, as the deque example showed, but using it is undefined behaviour:

• vector: an insertion invalidates everything if it reallocates, and otherwise the iterators, pointers and references at or after the position, end() included. An erasure invalidates those at or after the erased element, end() included.
• deque: an insertion at either end invalidates every iterator but no reference or pointer; one in the middle invalidates everything. An erasure at either end invalidates only what referred to the erased elements, plus end() when the last element goes; one in the middle invalidates everything.
• list and forward_list: an insertion invalidates nothing. An erasure invalidates only what referred to the erased elements.
• map, set and their multi versions: the same as a list.
• unordered_map and unordered_set: an insertion invalidates no reference or pointer, but every iterator if it made the table rehash. An erasure invalidates only what referred to the erased elements.
• flat_map and flat_set: treat every insertion and every erasure as invalidating everything.

The flat containers keep their elements in vectors, and the standard gives them none of the guarantees of the other associative containers. The unordered containers’ rehashing rule has a lesson of its own later in this module.

Your turn: an LRU cache

A least-recently-used cache keeps the most recently used entries and, when it is full, evicts the one used longest ago. The standard library has no such container, but a list and a hash map make one with constant-time operations: the list keeps the entries from most to least recently used, and the map stores, for each key, an iterator to its node. This works only because list iterators stay valid while other nodes are spliced, inserted and erased.

Write get and put in lru.h:

1. get(key) returns the value, or std::nullopt for a missing key; a hit makes the entry the most recently used.
2. put(key, value) stores the value and makes the entry the most recently used. When the cache is full and the key is new, it first evicts the least recently used entry, from both the list and the map.

// Starter code for "Your turn": a least-recently-used (LRU) cache from int keys to int values. order_ keeps the
// entries from most to least recently used, and where_ finds an entry's node in order_ without walking the list.
#pragma once
#include <cstddef>
#include <list>
#include <optional>
#include <unordered_map>
#include <utility>
#include <vector>

class LruCache {
public:
    explicit LruCache(std::size_t capacity) : capacity_(capacity) {}

    // The value stored for key, or std::nullopt. A hit makes key the most recently used entry.
    std::optional<int> get(int key) {
        // TODO
        (void)key;
        return std::nullopt;
    }

    // Stores value for key and makes key the most recently used entry. When the cache is full and key is new,
    // evict the least recently used entry first. Capacity is at least 1.
    void put(int key, int value) {
        // TODO
        (void)key;
        (void)value;
    }

    std::size_t size() const { return order_.size(); }

    // The keys from most to least recently used, for the tests.
    std::vector<int> keys() const {
        std::vector<int> out;
        for (const auto& [key, value] : order_) out.push_back(key);
        return out;
    }

private:
    std::size_t capacity_;
    std::list<std::pair<int, int>> order_;                                     // (key, value), most recent first
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> where_;  // key -> its node in order_
};

// Sample tests for lru.h. Build: clang++ -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra lru_tests.cpp -o lru_tests
#include <algorithm>
#include <cstddef>
#include <optional>
#include <print>
#include <random>
#include <utility>
#include <vector>
#include "lru.h"

int checks = 0;
int failures = 0;

void check(bool ok, const char* what) {
    ++checks;
    if (!ok) {
        ++failures;
        std::println("FAIL {}", what);
    }
}

// A slow cache that is easy to get right: a vector of (key, value), most recently used first.
struct SlowCache {
    std::size_t capacity;
    std::vector<std::pair<int, int>> entries;
    std::optional<int> get(int key) {
        auto it = std::ranges::find(entries, key, &std::pair<int, int>::first);
        if (it == entries.end()) return std::nullopt;
        std::rotate(entries.begin(), it, it + 1);
        return entries.front().second;
    }
    void put(int key, int value) {
        auto it = std::ranges::find(entries, key, &std::pair<int, int>::first);
        if (it != entries.end()) entries.erase(it);
        else if (entries.size() == capacity) entries.pop_back();
        entries.insert(entries.begin(), {key, value});
    }
};

int main() {
    LruCache empty(2);
    check(!empty.get(1).has_value(), "a key that was never stored is a miss");

    LruCache c(2);
    c.put(1, 10);
    check(c.get(1) == 10, "get returns the value put stored");
    c.put(2, 20);
    (void)c.get(1);  // 1 is now the most recently used, so 2 is the least
    c.put(3, 30);
    check(!c.get(2).has_value(), "the least recently used key is evicted");
    check(c.keys() == std::vector<int>{3, 1}, "the order is 3, then 1, after the eviction");
    c.put(1, 11);
    check(c.get(1) == 11 && c.size() == 2, "put on an existing key replaces its value without evicting");
    (void)c.get(42);
    check(c.keys() == std::vector<int>{1, 3}, "a miss changes nothing");

    LruCache one(1);
    one.put(1, 10);
    one.put(2, 20);
    check(!one.get(1).has_value() && one.get(2) == 20, "a cache of one entry keeps the newest");

    // 20,000 random operations, compared with the slow cache.
    LruCache fast(100);
    SlowCache slow{100, {}};
    std::mt19937 random(5);
    bool same = true;
    for (int i = 0; i < 20'000 && same; ++i) {
        int key = int(random() % 300);
        if (random() % 2) {
            fast.put(key, i);
            slow.put(key, i);
        } else {
            same = fast.get(key) == slow.get(key);
        }
        same = same && fast.size() == slow.entries.size();
    }
    check(same, "20,000 random operations give the same results as a simple cache");

    std::println("{} of {} checks passed", checks - failures, checks);
    return failures == 0 ? 0 : 1;
}

from session import run

# The sample tests run against the starter code, before any TODO is done, with AddressSanitizer and
# UndefinedBehaviorSanitizer switched on, so that a solution which uses an invalidated iterator is caught.
run("""
clang++ -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra lru_tests.cpp -o lru_tests && ./lru_tests
g++-16 -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra lru_tests.cpp -o lru_tests-gcc && ./lru_tests-gcc
""")

$ clang++ -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra lru_tests.cpp -o lru_tests && ./lru_tests
In file included from lru_tests.cpp:9:
./lru.h:40:17: warning: private field 'capacity_' is not used [-Wunused-private-field]
   40 |     std::size_t capacity_;
      |                 ^
1 warning generated.
FAIL get returns the value put stored
FAIL the order is 3, then 1, after the eviction
FAIL put on an existing key replaces its value without evicting
FAIL a miss changes nothing
FAIL a cache of one entry keeps the newest
FAIL 20,000 random operations give the same results as a simple cache
2 of 8 checks passed
[exit status 1]
$ g++-16 -std=c++23 -g -fsanitize=address,undefined -Wall -Wextra lru_tests.cpp -o lru_tests-gcc && ./lru_tests-gcc
FAIL get returns the value put stored
FAIL the order is 3, then 1, after the eviction
FAIL put on an existing key replaces its value without evicting
FAIL a miss changes nothing
FAIL a cache of one entry keeps the newest
FAIL 20,000 random operations give the same results as a simple cache
2 of 8 checks passed
[exit status 1]

The tests compile with AddressSanitizer and UndefinedBehaviorSanitizer, so a solution that keeps an iterator to an erased node is stopped at the bad access. You are done when both compilers print 8 of 8 checks passed and the sanitizers report nothing; Clang’s warning that capacity_ is unused disappears once put uses it. Hints: order_.splice(order_.begin(), order_, it) moves an entry to the front in constant time without invalidating it; where_.find(key) gives you the node; and for an eviction, read the key from order_.back() before pop_back destroys it. The last check compares 20,000 random operations with a simple, slow cache built on a vector.

Interview questions

Fresher · Why does push_back on a std::deque invalidate its iterators but not references to its elements?

A deque keeps its elements in fixed-size blocks and finds them through an index, an array of pointers to the blocks. push_back either uses a spare slot in the last block or allocates a new block, so the elements already stored never move, and pointers and references to them stay valid. A new block needs a slot in the index, though, and when the index is full the deque allocates a bigger one and copies the block pointers into it. A deque iterator remembers its block’s place in the index, so after that it would point into freed memory. The standard therefore treats every insertion at either end as invalidating all iterators, end() included, even when the index did not move. Erasing at an end invalidates only what referred to the erased element.

Key takeaways

• A deque adds and removes at both ends in constant time and keeps O(1) indexing; it has no reserve, no data(), and its blocks make small deques expensive: 4,104 bytes for one int with libc++, 576 for an empty deque with libstdc++.
• Growing a deque at either end keeps references and pointers valid but invalidates every iterator; AddressSanitizer and libstdc++’s debug mode both caught a walk with a stale iterator.
• A list never moves its nodes: splice relinks them in constant time (a range from another list in linear time), and list::sort reorders them without moving an element.
• emplace builds an element in place from constructor arguments; push_back and insert copy or move an object that already exists.
• Learn the invalidation rules: vectors invalidate from the position onwards, deques everything at each insertion, lists and maps only what was erased, and flat containers everything.