1.4 Data Structures & Algorithms

You now know how memory works: bytes with numbered addresses, the stack and the heap, arrays laid out in a row, and why data sitting next to each other is fast to read (cache locality — the CPU pulls in a whole nearby chunk at once). This chapter is about data structures (ways to arrange data in memory) and algorithms (step-by-step methods that do work on that data). Picking the right pair is often the difference between a game that holds a steady 60 frames per second and one that stutters.

Every section here follows the same shape: a small piece of runnable code, the real output it prints, then a plain explanation. Type the examples in and run them. Watching the output is how this sticks.

1. Big-O: how work grows when the input grows

Big-O is a way to describe how the amount of work an algorithm does changes as the input gets bigger. It is not seconds and not a benchmark. It answers one question: if I give this code 10 times more data, does the work grow 10 times, 100 times, or barely at all?

Here are two functions that both look at a std::vector<int> (a resizable array). Notice how much work each one does.

#include <vector>
#include <iostream>

int first(const std::vector<int>& v) {   // O(1): one step
    return v[0];                          // jump straight to slot 0
}

int sumAll(const std::vector<int>& v) {  // O(n): one step per element
    int total = 0;
    for (int x : v) total += x;           // loop runs n times
    return total;
}

int main() {
    std::vector<int> v = {10, 20, 30, 40, 50};
    std::cout << first(v) << "\n";
    std::cout << sumAll(v) << "\n";
}

Output:

10
150

first does the same tiny amount of work whether the vector holds 5 items or 5 million. We call that O(1) — "constant time". sumAll touches every element once, so with n items it does about n steps. We call that O(n) — "linear time". Double the data, double the work.

The letter n means "the size of the input". The common growth rates you will meet, from fastest to slowest:

Read that last block again. At n = 1,000, an O(n^2) method does a million steps while an O(n) method does a thousand. That gap is why "which algorithm" matters far more than "which programming trick" once the data gets large.

An O(log n) ("log n") algorithm cuts the problem in half each step. Guessing a number between 1 and 1000 by always guessing the middle takes about 10 guesses, not 1000, because 2^10 = 1024. Halving is very powerful.

Big-O ignores constant factors — but you still feel them

Big-O throws away constant multipliers. Code that does 2*n steps and code that does 100*n steps are both O(n), because as n grows the shape is the same straight line. But on a real machine the second one is 50 times slower. Big-O tells you the shape of the growth; it does not tell you the speed. For picking between two structures that have the same Big-O, the constant factors — and cache behaviour, which we hit next — decide the winner.

2. Arrays vs linked lists: why the cache decides

A std::vector<int> stores its elements contiguously — one block of memory, values back to back. A std::list<int> (a doubly linked list) stores each element in its own little heap allocation called a node, and each node holds a pointer to the next and previous nodes. The nodes can sit anywhere in memory.

Here is the surprise. Walking every element of a vector and walking every element of a list are both O(n) — same Big-O. But the vector is usually several times faster. Why? Because of the memory chapter: when the CPU reads address 1000, it pulls in a whole cache line (a nearby chunk, typically 64 bytes) at once. That chunk already contains the next several vector elements, so they are "free" to read. With a list, each node lives at a random address, so nearly every step is a cache miss — the CPU stalls waiting for memory it did not already have.

#include <vector>
#include <list>
#include <numeric>   // std::accumulate
#include <iostream>

int main() {
    std::vector<int> vec(1000000, 1);   // a million 1s, contiguous
    std::list<int>   lst(1000000, 1);   // a million 1s, scattered nodes

    // Both sum the same way, both are O(n).
    long long a = std::accumulate(vec.begin(), vec.end(), 0LL);
    long long b = std::accumulate(lst.begin(), lst.end(), 0LL);

    std::cout << a << " " << b << "\n";
}

Output:

1000000 1000000

The numbers are identical, but if you time the two accumulate calls the vector version typically finishes several times faster on the same machine. Same algorithm, same Big-O, very different real speed — the layout in memory is the whole story.

3. The dynamic array: how std::vector grows

A vector can grow, but memory does not stretch — a heap block has a fixed size. So when a vector runs out of room, it does three things: allocate a bigger block, copy the old elements into it, and free the old block. The trick that keeps this cheap is geometric growth: it does not add one slot, it usually doubles the capacity. Let us build a tiny version to see it.

#include <iostream>

struct IntVec {
    int* data = nullptr;   // heap block holding the elements
    int  size = 0;         // how many slots are used
    int  cap  = 0;         // how many slots exist in total

    void push_back(int value) {
        if (size == cap) {                      // full? make room first
            int newCap = (cap == 0) ? 1 : cap * 2;   // DOUBLE the capacity
            int* bigger = new int[newCap];      // bigger block
            for (int i = 0; i < size; i++)
                bigger[i] = data[i];            // copy old elements over
            delete[] data;                      // free old block
            data = bigger;
            cap  = newCap;
            std::cout << "grew to cap " << cap << "\n";
        }
        data[size] = value;                     // now there is room
        size++;
    }
};

int main() {
    IntVec v;
    for (int i = 0; i < 5; i++) v.push_back(i * 10);
    for (int i = 0; i < v.size; i++) std::cout << v.data[i] << " ";
    std::cout << "\n";
    delete[] v.data;
}

Output:

grew to cap 1
grew to cap 2
grew to cap 4
grew to cap 8
0 10 20 30 40

Trace it: capacity goes 0 -> 1 -> 2 -> 4 -> 8. Five push_back calls, but only four re-grows, and after reaching capacity 8 the next few pushes are free. Most pushes just write one slot and bump size. Only occasionally does one push trigger a copy. When you average the cost over many pushes, each one is cheap — we call that amortized O(1) ("amortized" = spread out over many operations). If the vector grew by just +1 each time instead of doubling, every push would copy everything, and n pushes would cost O(n^2) total. Doubling is what makes it fast.

reserve(): skip the re-grows when you know the count

If you already know roughly how many items you will add, tell the vector up front with reserve. It allocates once, so no copies happen during the loop.

#include <vector>

int main() {
    std::vector<int> v;
    v.reserve(1000);                 // one allocation, capacity now 1000
    for (int i = 0; i < 1000; i++)
        v.push_back(i);              // zero re-grows, zero copies
}

4. Hash maps: find things by key in O(1) on average

A hash map (C++ calls it std::unordered_map) stores key -> value pairs and lets you look up a value by its key almost instantly. Inside, it keeps an array of buckets (slots). To store a key it runs a hash function — a function that turns the key into a big number — then takes that number modulo the bucket count to pick a bucket index.

Two different keys can land in the same bucket — that is a collision. The map handles it by keeping a small chain in that bucket and checking the actual keys. As long as collisions are rare, a lookup is: hash the key, jump to one bucket, check one or two entries. That is why lookup, insert, and erase are O(1) on average.

Collisions stay rare only if the buckets are not too crowded. The load factor is number of items / number of buckets. When it grows past a limit (around 1.0 for unordered_map), the map rehashes: it allocates more buckets and re-places everything. Same idea as the vector growing — occasional cost, cheap on average.

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

int main() {
    std::unordered_map<std::string, int> score;  // key: name, value: points
    score["alice"] = 10;
    score["bob"]   = 7;
    score["alice"] += 5;             // look up "alice", add 5 -> now 15

    std::cout << "alice: " << score["alice"] << "\n";
    std::cout << "has carol? " << score.count("carol") << "\n";  // 0 = not present

    for (const auto& [name, pts] : score)      // structured binding (C++17)
        std::cout << name << " = " << pts << "\n";
}

Output (the loop order is not guaranteed — a hash map has no order):

alice: 15
has carol? 0
bob = 7
alice = 15

5. Stacks and queues

These two are simple but show up everywhere. Both are usually built on top of a vector or deque; the point is the order things come out.

• A stack is LIFO — last in, first out. Like a stack of plates: you take the top one. Push adds to the top, pop removes from the top.
• A queue is FIFO — first in, first out. Like a line at a shop: first to arrive is first served. Push adds to the back, pop removes from the front.

#include <stack>
#include <queue>
#include <iostream>

int main() {
    std::stack<int> s;
    s.push(1); s.push(2); s.push(3);
    std::cout << "stack pops: ";
    while (!s.empty()) { std::cout << s.top() << " "; s.pop(); }
    std::cout << "\n";

    std::queue<int> q;
    q.push(1); q.push(2); q.push(3);
    std::cout << "queue pops: ";
    while (!q.empty()) { std::cout << q.front() << " "; q.pop(); }
    std::cout << "\n";
}

Output:

stack pops: 3 2 1
queue pops: 1 2 3

Where they show up in games: a stack models "undo", a menu back-history, or the call stack that runs your recursive functions. A queue models jobs waiting to be processed in order, network messages, or — importantly — the frontier of a breadth-first search, which is next.

6. Trees and binary heaps (the priority queue A* needs)

A tree is data arranged in a parent/child hierarchy: one root at the top, each node with some children, no cycles. Your scene graph (a character has a torso, the torso has arms, arms have hands) is a tree. A file system is a tree.

A binary heap is a special tree, stored compactly inside an array, whose one rule is: every parent is smaller than (or equal to) its children. That means the smallest value is always at the top (a min-heap). You cannot ask a heap for "the 3rd item", but you can always grab the minimum instantly, and inserting or removing the minimum is O(log n) because the item only has to bubble up or down the height of the tree, which is about log n levels.

A structure that always hands you the smallest (or largest) item is called a priority queue. In C++ that is std::priority_queue. This is the exact tool A* pathfinding uses to always expand the most promising tile next, so it is worth knowing now.

#include <queue>
#include <vector>
#include <iostream>

int main() {
    // A MIN-heap: std::greater makes the smallest value come out first.
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    pq.push(50); pq.push(10); pq.push(30); pq.push(20);

    while (!pq.empty()) {
        std::cout << pq.top() << " ";   // always the current smallest
        pq.pop();
    }
    std::cout << "\n";
}

Output:

10 20 30 50

We pushed them in a jumbled order but they came out sorted smallest-first, one pop at a time. By default (without std::greater) std::priority_queue is a max-heap and hands you the largest first.

7. Graphs and BFS: shortest number of steps

A graph is nodes (also called vertices) connected by edges. A road map, a social network, and a game level's walkable tiles are all graphs. The common way to store one is an adjacency list: for each node, a list of the nodes it connects to.

Breadth-first search (BFS) answers "what is the fewest number of steps from A to B?" in a graph where every edge counts as one step (an unweighted graph). It works like ripples spreading on water: visit everything 1 step away, then everything 2 steps away, and so on. Because it expands in rings, the first time BFS reaches a node it has reached it by the shortest path. The tool that keeps that ring order is a queue from section 5.

Here is BFS on a tile grid — the classic game case. # is a wall, . is walkable, S is start, G is goal.

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

int main() {
    std::vector<std::string> grid = {
        "S....",
        ".###.",
        ".#G#.",
        ".#.#.",
        "....."
    };
    int rows = grid.size();
    int cols = grid[0].size();

    int sr = 0, sc = 0, gr = 0, gc = 0;      // find S and G
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == 'S') { sr = r; sc = c; }
            if (grid[r][c] == 'G') { gr = r; gc = c; }
        }

    // dist = steps from S; -1 means "not visited yet"
    std::vector<std::vector<int>> dist(rows, std::vector<int>(cols, -1));
    std::queue<std::pair<int,int>> q;
    dist[sr][sc] = 0;
    q.push({sr, sc});

    int dr[4] = {-1, 1, 0, 0};   // up, down, left, right
    int dc[4] = { 0, 0,-1, 1};

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i], nc = c + dc[i];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue; // off grid
            if (grid[nr][nc] == '#') continue;                          // wall
            if (dist[nr][nc] != -1)  continue;                          // seen
            dist[nr][nc] = dist[r][c] + 1;   // one more step than here
            q.push({nr, nc});
        }
    }

    std::cout << "shortest steps to goal: " << dist[gr][gc] << "\n";
}

Output:

shortest steps to goal: 8

Watch it spread. Each cell below shows how many steps BFS needed to first reach it. The numbers grow outward from S like ripples, and the goal ends up 8 steps away because the walls force a long path around the ring:

BFS is O(V + E) — it looks at every node (V) and every edge (E) at most once. On a grid that is roughly "the number of tiles". It is the right tool whenever every move costs the same. When moves cost different amounts (mud is slower than road), you need the next section.

8. Shortest paths with weights: Dijkstra, and a peek at A*

Now give each edge a weight (a cost). BFS no longer works, because the path with the fewest edges may not be the cheapest. Dijkstra's algorithm fixes this. It is BFS with a priority queue instead of a plain queue: instead of always expanding the nearest-in-steps node, it always expands the node with the smallest total cost so far. That is exactly what the min-heap from section 6 gives us.

#include <iostream>
#include <vector>
#include <queue>

int main() {
    int n = 5;
    // adjacency list: graph[u] = list of (neighbor, weight)
    std::vector<std::vector<std::pair<int,int>>> graph(n);
    auto addEdge = [&](int u, int v, int w) {
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});     // undirected: goes both ways
    };
    addEdge(0, 1, 4);
    addEdge(0, 2, 1);
    addEdge(2, 1, 2);
    addEdge(1, 3, 1);
    addEdge(2, 3, 5);
    addEdge(3, 4, 3);

    std::vector<int> dist(n, 1000000000);   // "infinity" = not reached yet
    dist[0] = 0;

    using P = std::pair<int,int>;           // (cost so far, node)
    std::priority_queue<P, std::vector<P>, std::greater<P>> pq;   // min-heap
    pq.push({0, 0});

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;          // an old, worse entry -> skip
        for (auto [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {     // found a cheaper way to v
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }

    for (int i = 0; i < n; i++)
        std::cout << "dist to " << i << " = " << dist[i] << "\n";
}

Output:

dist to 0 = 0
dist to 1 = 3
dist to 2 = 1
dist to 3 = 4
dist to 4 = 7

Notice node 1: the direct edge 0-1 costs 4, but going 0 -> 2 -> 1 costs 1 + 2 = 3, which is cheaper, so Dijkstra reports 3. It always settles on the cheapest total.

A* is Dijkstra with a hint

Dijkstra spreads out evenly in all directions until it happens to reach the goal — it does not know which way the goal is. A* (say "A-star") is the same loop, but it steers toward the goal using a heuristic (a cheap guess of the remaining distance to the goal, for example the straight-line or grid distance). The priority queue is ordered by:

As long as the heuristic never overestimates the remaining cost, A* still finds the true shortest path — it just examines far fewer nodes because it stops wandering away from the goal. This is why nearly every game uses A* for pathfinding. A full A* implementation is a later chapter; for now the important idea is that it is BFS/Dijkstra plus a priority queue plus a good guess.

9. Sorting: use std::sort, and know why it is O(n log n)

Sorting shows up constantly: draw order, leaderboards, sorting by distance so you can process the nearest things first. A naive sort that repeatedly scans for the next smallest is O(n^2) — a thousand items is a million comparisons. Good sorts are O(n log n) because they use the halving trick: split the data, sort the halves, merge. The log n is the number of times you can halve; the n is the work at each level.

You do not write the sort yourself. std::sort is a heavily optimized O(n log n) routine. Use it.

#include <algorithm>
#include <vector>
#include <iostream>

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

    std::sort(v.begin(), v.end());               // ascending, O(n log n)
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";

    // custom order: pass a comparator (returns true if a should come first)
    std::sort(v.begin(), v.end(), [](int a, int b){ return a > b; });
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";
}

Output:

1 2 5 5 6 9
9 6 5 5 2 1

The comparator (the little [](int a, int b){ ... } function, called a lambda) lets you sort by anything: enemies by health, items by price, sprites by their y coordinate. Return true when a should appear before b.

10. Dynamic programming: solve each subproblem once, remember it

Dynamic programming (DP) sounds fancy but the core idea is small: if your problem breaks into smaller subproblems and the same subproblems come up again and again (overlapping subproblems), then compute each one once and store the answer so you never redo it. Storing computed answers is called memoization ("memo" as in a note to yourself).

The classic example is the Fibonacci sequence (fib(n) = fib(n-1) + fib(n-2)). Here is the naive recursion:

long long fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);   // recomputes the same values endlessly
}

Look at what fib(5) actually does. fib(3) is computed twice, fib(2) three times, and it gets far worse as n grows:

The naive tree roughly doubles in size for every +1 to n — that is exponential, close to O(2^n). Computing fib(45) this way makes about 3.7 billion calls and takes seconds. Now cache each answer the first time we find it:

#include <iostream>
#include <vector>

long long fibMemo(int n, std::vector<long long>& cache) {
    if (n < 2) return n;
    if (cache[n] != -1) return cache[n];      // already solved? reuse it
    cache[n] = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
    return cache[n];
}

int main() {
    std::vector<long long> cache(50, -1);      // -1 means "not computed yet"
    std::cout << fibMemo(45, cache) << "\n";
}

Output:

1134903170

The memoized version computes each fib(k) exactly once, so fib(45) does about 46 real computations instead of 3.7 billion. Same answer, but now it is O(n) and finishes instantly. That is the whole trick of DP: spot the repeated work, store it, look it up next time. It powers text diff tools, inventory/crafting cost problems, and many puzzle-game solvers.

11. The engine twist: measure, do not assume

Here is the lesson that separates textbook knowledge from shipping games. Big-O tells you how something scales, but the CPU also cares deeply about how the data sits in memory (section 2). In practice, a structure with a "worse" Big-O but a contiguous, cache-friendly layout often beats a "better" Big-O structure that chases pointers all over the heap.

A concrete example: to remove items from a collection you loop every frame, a linked list gives O(1) removal, while removing from a vector is O(n) (it shifts elements). Big-O says list wins. But in reality the vector usually wins overall, because iterating the vector every frame is many times faster (no cache misses), and that iteration dominates the total cost. This mindset — arrange data in flat arrays and stream through it — is called data-oriented design, and it is how high-performance engines lay out entities, particles, and physics bodies.

12. Putting a clock on Big-O: measured timings

Section 1 counted steps on paper. Now let us count milliseconds on a real machine, so the growth curves stop being abstract. <chrono> is the standard stopwatch: read the clock before the work, read it after, subtract. We run the same job at ever-larger n and print how long each took.

#include <chrono>
#include <cstdio>
#include <vector>

using Clock = std::chrono::steady_clock;
static double ms(Clock::time_point a, Clock::time_point b){
    return std::chrono::duration<double,std::milli>(b-a).count();
}

int main(){
    printf("O(n) linear scan (sum every element once):\n");
    for(long long N : {1000LL,10000LL,100000LL,1000000LL,10000000LL}){
        std::vector<int> v(N,1);
        auto t0=Clock::now();
        long long s=0;
        for(long long i=0;i<N;i++) s+=v[i];
        auto t1=Clock::now();
        printf("  N=%9lld  time=%9.3f ms\n", N, ms(t0,t1));
    }
    printf("\nO(n^2) nested loop (touch every pair):\n");
    for(int N : {2000,4000,8000,16000}){
        auto t0=Clock::now();
        long long c=0;
        for(int i=0;i<N;i++) for(int j=i+1;j<N;j++) c++;
        auto t1=Clock::now();
        printf("  N=%6d  pairs=%12lld  time=%9.3f ms\n", N, c, ms(t0,t1));
    }
}

Output (your exact numbers will differ by machine and run — watch the ratios, not the absolute times):

O(n) linear scan (sum every element once):
  N=     1000  time=    0.001 ms
  N=    10000  time=    0.011 ms
  N=   100000  time=    0.105 ms
  N=  1000000  time=    1.021 ms
  N= 10000000  time=   13.590 ms

O(n^2) nested loop (touch every pair):
  N=  2000  pairs=     1999000  time=    1.018 ms
  N=  4000  pairs=     7998000  time=    4.055 ms
  N=  8000  pairs=    31996000  time=   16.175 ms
  N= 16000  pairs=   127992000  time=   64.552 ms

Read the O(n) block: each time n grows 10x, the time grows about 10x too (0.001 → 0.011 → 0.105 → 1.02 → 13.6 ms). A straight line — that is what "linear" feels like on a clock.

Now the O(n^2) block, where n only doubles each row: the time roughly quadruples (1.0 → 4.1 → 16.2 → 64.6 ms). Doubling the input quadrupled the work, because 2 squared is 4. That is the fingerprint of quadratic growth, and it is why an O(n^2) loop that feels instant at 2,000 items takes 60x longer at 16,000 — and would take hours at 10 million.

13. Arrays vs linked lists, actually on the clock

Section 2 claimed a std::vector beats a std::list at the same O(n) work because of the cache. Let us stop claiming and measure. Same ten million integers, same "add them all up" loop, two memory layouts.

#include <vector>
#include <list>
#include <chrono>
#include <cstdio>
using Clock=std::chrono::steady_clock;
static double ms(Clock::time_point a,Clock::time_point b){
    return std::chrono::duration<double,std::milli>(b-a).count();
}
int main(){
    const int N=10000000;
    std::vector<int> v(N,1);
    std::list<int>   l(N,1);

    long long s=0;
    auto t0=Clock::now();
    for(int x: v) s+=x;                // straight sweep through one block
    auto t1=Clock::now();

    long long s2=0;
    for(int x: l) s2+=x;               // hop pointer-to-pointer across the heap
    auto t2=Clock::now();

    printf("vector sum=%lld  time=%8.3f ms\n", s,  ms(t0,t1));
    printf("list   sum=%lld  time=%8.3f ms\n", s2, ms(t1,t2));
    printf("list is %.1fx slower for the SAME O(n) work\n", ms(t1,t2)/ms(t0,t1));
}

Compiled the plain way (clang++ -std=c++17, no optimizer) the list comes out only about 1.6x slower here — an unoptimized build adds a fat, uniform cost to every line that hides the memory difference. But games ship with the optimizer on. Rebuild with -O2 (a release build) and the real gap appears:

vector sum=10000000  time=   2.959 ms
list   sum=10000000  time=  28.665 ms
list is 9.7x slower for the SAME O(n) work

Nearly ten times slower, and not one line of the algorithm changed — both are O(n), both add ten million ones. The optimizer turned the vector's sweep into a tight loop marching straight through one contiguous block, so the hardware prefetcher feeds it the next cache line before it is even asked. The list cannot be sped up that way: each node stores a pointer to the next, and the CPU cannot fetch node k+1 until it has read node k to learn its address. That forced serial pointer-chase, with a cache miss at nearly every hop, is the tax section 2 warned about — now you can see its size.

The real std::vector doubles too

Section 3 built a toy vector that doubled its capacity. The real std::vector does exactly the same, and you can print capacity() to watch it happen:

#include <vector>
#include <cstdio>
int main(){
    std::vector<int> v;
    size_t last=(size_t)-1;
    for(int i=0;i<17;i++){
        v.push_back(i);
        if(v.capacity()!=last){
            printf("size=%2zu  capacity=%2zu\n", v.size(), v.capacity());
            last=v.capacity();
        }
    }
}

Output:

size= 1  capacity= 1
size= 2  capacity= 2
size= 3  capacity= 4
size= 5  capacity= 8
size= 9  capacity=16
size=17  capacity=32

Capacity climbs 1, 2, 4, 8, 16, 32 — doubling, exactly as predicted. Seventeen pushes allocated only six blocks total (the first, then five doublings); every other push just wrote into space the vector already owned. The growth factor is not fixed by the standard — some libraries use 1.5x instead of 2x — but it is always geometric, and that is what keeps push_back amortized O(1). If you know you will add about 5,000 items, one v.reserve(5000) skips all six of those reallocations.

14. Choosing a container: a decision table

The standard library hands you a shelf of containers. Picking the right one comes down to two questions: how do I add and remove items, and how do I find them again. Here are the five you will reach for most, and the one-line reason each exists.

Two of these are new here. A std::deque ("deck", a double-ended queue) is like a vector that can also push and pop cheaply at the front — it is what std::queue from section 5 uses underneath. A std::map keeps its keys in sorted order using a balanced binary search tree (a red-black tree), so iterating it always comes out in order and you can ask range questions like "the smallest key not less than K" — things a hash map simply cannot do. The price is O(log n) instead of O(1), and pointer-chasing nodes just like a list.

#include <map>
#include <unordered_map>
#include <deque>
#include <string>
#include <cstdio>
int main(){
    std::map<std::string,int>           ord;   // red-black tree, sorted
    std::unordered_map<std::string,int> hsh;    // hash table, no order
    const char* keys[]={"delta","alpha","charlie","bravo"};
    for(auto k:keys){ ord[k]=1; hsh[k]=1; }

    printf("insertion order:          delta alpha charlie bravo\n");
    printf("std::map order:           ");
    for(auto&kv:ord) printf("%s ", kv.first.c_str());
    printf("\nstd::unordered_map order: ");
    for(auto&kv:hsh) printf("%s ", kv.first.c_str());

    std::deque<int> d;
    d.push_back(2); d.push_back(3);
    d.push_front(1); d.push_front(0);           // O(1) at BOTH ends
    printf("\n\nstd::deque after push_front 0,1 / push_back 2,3: ");
    for(int x:d) printf("%d ", x);
    printf("\n");
}

Output (the unordered_map line's order is implementation-defined — yours may differ):

insertion order:          delta alpha charlie bravo
std::map order:           alpha bravo charlie delta
std::unordered_map order: charlie bravo alpha delta

std::deque after push_front 0,1 / push_back 2,3: 0 1 2 3 

std::map printed its keys alphabetically no matter what order they went in — the sorted tree at work. The hash map printed them in bucket order, which looks arbitrary and is never something you should rely on. And the deque grew from both ends, ending up 0 1 2 3 even though 0 and 1 were pushed to the front after 2 and 3 were pushed to the back.

15. Inside a hash map: functions, collisions, load factor

Section 4 said a hash map runs a hash function to pick a bucket. Let us actually look at what that function spits out, and at the machinery that keeps lookups O(1). std::hash is the standard hash object; you call it like a function.

#include <unordered_map>
#include <string>
#include <functional>
#include <cstdio>
int main(){
    std::hash<std::string> h;
    const char* names[]={"alice","bob","carol"};
    for(auto s:names){
        size_t hv=h(s);
        printf("hash(%-6s) = %20zu   %% 8 = %zu\n", s, hv, hv%8);
    }
    printf("\ngrowing an unordered_map<int,int> (watch buckets jump):\n");
    std::unordered_map<int,int> m;
    printf("  start           buckets=%2zu  load=%.2f  (max %.1f)\n",
        m.bucket_count(), m.load_factor(), m.max_load_factor());
    for(int i=1;i<=20;i++){
        size_t before=m.bucket_count();
        m[i]=i;
        const char* note = (m.bucket_count()!=before) ? "  <-- REHASH" : "";
        printf("  after insert %2d  buckets=%2zu  load=%.2f%s\n",
            i, m.bucket_count(), m.load_factor(), note);
    }
}

Output (the exact hash numbers depend on your compiler's library; the pattern is the point):

hash(alice ) = 12039928513911456776   % 8 = 0
hash(bob   ) = 13671481681542908696   % 8 = 0
hash(carol ) =  2926835018909119080   % 8 = 0

growing an unordered_map<int,int> (watch buckets jump):
  start           buckets= 0  load=0.00  (max 1.0)
  after insert  1  buckets= 2  load=0.50  <-- REHASH
  after insert  2  buckets= 2  load=1.00
  after insert  3  buckets= 5  load=0.60  <-- REHASH
  after insert  4  buckets= 5  load=0.80
  after insert  5  buckets= 5  load=1.00
  after insert  6  buckets=11  load=0.55  <-- REHASH
  after insert  7  buckets=11  load=0.64
  after insert  8  buckets=11  load=0.73
  after insert  9  buckets=11  load=0.82
  after insert 10  buckets=11  load=0.91
  after insert 11  buckets=11  load=1.00
  after insert 12  buckets=23  load=0.52  <-- REHASH
  after insert 13  buckets=23  load=0.57
  after insert 14  buckets=23  load=0.61
  after insert 15  buckets=23  load=0.65
  after insert 16  buckets=23  load=0.70
  after insert 17  buckets=23  load=0.74
  after insert 18  buckets=23  load=0.78
  after insert 19  buckets=23  load=0.83
  after insert 20  buckets=23  load=0.87

The hash values are enormous, near-random 64-bit numbers — that is the whole job of a hash function: scramble the key so different keys spread evenly. But now look at the % 8 column: all three names come out 0. Reducing a hash with % 8 keeps only the low 3 bits, and here those bits happen to be zero for every one of these keys — so all three would pile into bucket 0. A total collision, and lookups in that bucket degrade to an O(n) walk.

That is exactly why a real unordered_map does not reduce with a power of two like 8. Watch the bucket counts in the second block: 2, 5, 11, 23 — prime numbers. Taking the hash modulo a prime mixes in all the bits, not just the low few, so keys scatter even when the raw hash has regular patterns like these.

The second block also shows the load factor (items divided by buckets) doing its job. This map's max_load_factor is 1.0. The moment an insert pushes the load factor up to 1.0, the very next insert triggers a rehash: the table jumps to the next prime bucket count (2, then 5, then 11, then 23) and re-places every item. It is the same amortized bargain as the growing vector — most inserts are O(1), the occasional one pays to grow, and it averages out to O(1).

Chaining vs open addressing

When two keys really do land in the same bucket, the map needs a plan. The standard library uses separate chaining: each bucket is a tiny linked list of the entries that hashed there, and a lookup walks that short chain comparing keys. The alternative, used by most high-performance game hash maps (Google's dense_hash_map, robin_hood, EA's containers), is open addressing: on a collision, probe the next slot, then the next, until an empty one turns up — every entry lives in one flat array, which is far friendlier to the cache than chasing chain pointers. If you ever need a map faster than std::unordered_map, an open-addressed flat map is usually the answer, for the exact cache reasons you measured in section 13.

16. Sorting for real: std::sort is introsort, and stability

Section 9 said "use std::sort, it is O(n log n)." Two things are worth knowing about what it actually is.

First, std::sort is not one algorithm — it is introsort (introspective sort), a hybrid. It begins as quicksort, which is fast in practice and has excellent cache behaviour. Quicksort's weakness is that an unlucky run of bad pivots can drag it down to O(n^2); so introsort watches its own recursion depth, and if it dives too deep it switches to heapsort (guaranteed O(n log n), built on the heap from section 6) to escape the worst case. And for the small pieces at the bottom of the recursion — typically 16 elements or fewer — it drops to insertion sort, which has almost no overhead and flies through tiny, nearly-sorted runs. Quicksort for raw speed, heapsort as a safety net, insertion sort for the small stuff: that is why the library crushes a hand-written bubble sort, and why you should never ship your own.

Second, and this one bites people: std::sort is not stable. "Stable" means two items that compare equal keep their original relative order. std::sort makes no such promise; when you need it, use std::stable_sort. Here is the difference made visible — 25 events, each tagged with the order it arrived, sorted only by a priority of 0 or 1:

#include <algorithm>
#include <vector>
#include <cstdio>

struct Event { int priority; int arrived; };   // arrived = original order

int main(){
    std::vector<Event> base;
    for(int i=0;i<25;i++) base.push_back({ i%2, i });  // priorities 0,1,0,1,...

    auto cmp=[](const Event&a,const Event&b){ return a.priority<b.priority; };
    auto s1=base, s2=base;
    std::sort(       s1.begin(), s1.end(), cmp);
    std::stable_sort(s2.begin(), s2.end(), cmp);

    printf("arrival order of the priority-0 events:\n");
    printf("  std::sort   : ");
    for(auto&e:s1) if(e.priority==0) printf("%d ", e.arrived);
    printf("\n  stable_sort : ");
    for(auto&e:s2) if(e.priority==0) printf("%d ", e.arrived);
    printf("\n");
}

Output:

arrival order of the priority-0 events:
  std::sort   : 0 24 4 6 8 10 12 14 16 18 2 20 22
  stable_sort : 0 2 4 6 8 10 12 14 16 18 20 22 24 

All the priority-0 events are "equal" as far as the comparator cares, so both results are correctly sorted by priority. But look at their arrival numbers. stable_sort kept them in the order they arrived — 0 2 4 6 .... std::sort shuffled them — 24 and 2 jumped out of place — because it is free to reorder equal elements, and its quicksort partitioning did exactly that. (The precise scramble is implementation-specific; the only guarantee is that stable_sort preserves order and std::sort does not.)

17. Object pools: reuse instead of allocate

Asking the system for memory (new, or a container that has to grow) is not free — a single allocation can cost hundreds of nanoseconds, it can block on an internal lock, and over time it fragments the heap. A game that does new Bullet() every time the player fires and delete on every hit is doing thousands of allocations a second, right inside the frame loop, and that shows up as stutter. The fix is the object pool: allocate a fixed block of objects once, then hand them out and take them back without ever allocating again.

The pool keeps a free list — the indices of the slots not currently in use. spawn pops a free index and fills that slot; despawn pushes the index back. After construction, nothing is ever allocated.

#include <vector>
#include <cstdio>

struct Bullet { float x, y; bool active=false; };

struct BulletPool {
    std::vector<Bullet> slots;   // fixed block, allocated ONCE
    std::vector<int>    freeList;// indices currently free

    BulletPool(int n) : slots(n) {
        for(int i=n-1;i>=0;i--) freeList.push_back(i);
    }
    int spawn(float x,float y){
        if(freeList.empty()) return -1;         // pool exhausted
        int i=freeList.back(); freeList.pop_back();
        slots[i]={x,y,true};
        return i;
    }
    void despawn(int i){ slots[i].active=false; freeList.push_back(i); }
};

int main(){
    BulletPool pool(3);
    int a=pool.spawn(0,0);
    int b=pool.spawn(1,1);
    printf("spawn a -> slot %d\n", a);
    printf("spawn b -> slot %d\n", b);
    pool.despawn(a);                            // a dies, its slot goes free
    int c=pool.spawn(2,2);                       // no new allocation
    printf("despawn a, spawn c -> slot %d  (reused a's slot: %s)\n",
           c, c==a ? "yes" : "no");
    int d=pool.spawn(3,3);
    int e=pool.spawn(4,4);                        // nothing left
    printf("spawn d -> slot %d\n", d);
    printf("spawn e -> slot %d  (-1 means pool full)\n", e);
}

Output:

spawn a -> slot 0
spawn b -> slot 1
despawn a, spawn c -> slot 0  (reused a's slot: yes)
spawn d -> slot 2
spawn e -> slot -1  (-1 means pool full)

When a was despawned, slot 0 went back on the free list, so the very next spawn handed slot 0 straight to c — same memory, zero allocation. Once all three slots were in use, the pool returned -1 instead of growing. A fixed budget is usually what you want in a game: you would rather cap the number of bullets than let one busy frame allocate without limit.

Because the objects live in one contiguous std::vector, sweeping the live ones each frame is also cache-friendly — the pool buys you "no per-frame allocation" and "good memory layout" in a single move. This pattern is everywhere in games: bullets, particles, enemies, audio voices, network packets, floating damage numbers. Anything spawned and destroyed rapidly should almost always come from a pool.

18. Spatial partitioning: "which objects are near me?"

A question games ask every single frame: which objects are close to this one? Collision, explosion radius, "enemies that can see the player", picking up nearby loot. The naive answer is to test every object against every other object — that is the O(n^2) pair loop from section 1, and it collapses fast: 1,000 objects is half a million checks per frame; 10,000 objects is fifty million.

The fix is a spatial structure: chop the world into cells, drop each object into the cell it sits in, then only compare objects that share a cell (or touch a neighbouring one). Objects far apart never get compared at all. The simplest version is a uniform grid: fixed-size cells, stored as a hash map from cell coordinate to the list of objects in it.

Below we scatter 1,000 points and count the pairs within radius R, once the naive way and once with a grid, so you can see they find the same pairs with wildly different amounts of work.

#include <vector>
#include <unordered_map>
#include <cstdio>

struct V2 { float x, y; };

int main(){
    std::vector<V2> pts;
    for(int i=0;i<1000;i++)
        pts.push_back({ (float)((i*37)%100), (float)((i*53)%100) });

    const float R=5.0f;

    // --- naive: test every pair, O(n^2) ---
    long long naiveChecks=0, naivePairs=0;
    for(size_t i=0;i<pts.size();i++)
        for(size_t j=i+1;j<pts.size();j++){
            naiveChecks++;
            float dx=pts[i].x-pts[j].x, dy=pts[i].y-pts[j].y;
            if(dx*dx+dy*dy<=R*R) naivePairs++;
        }

    // --- uniform grid: bucket by cell of size R, only check the 3x3 block ---
    const int cell=(int)R;
    auto key=[&](int cx,int cy){ return (long long)cx*100000+cy; };
    std::unordered_map<long long,std::vector<int>> grid;
    for(int i=0;i<(int)pts.size();i++)
        grid[key((int)(pts[i].x/cell),(int)(pts[i].y/cell))].push_back(i);

    long long gridChecks=0, gridPairs=0;
    for(int i=0;i<(int)pts.size();i++){
        int cx=(int)(pts[i].x/cell), cy=(int)(pts[i].y/cell);
        for(int ox=-1;ox<=1;ox++) for(int oy=-1;oy<=1;oy++){
            auto it=grid.find(key(cx+ox,cy+oy));
            if(it==grid.end()) continue;
            for(int j:it->second){
                if(j<=i) continue;              // count each pair once
                gridChecks++;
                float dx=pts[i].x-pts[j].x, dy=pts[i].y-pts[j].y;
                if(dx*dx+dy*dy<=R*R) gridPairs++;
            }
        }
    }

    printf("naive: %8lld distance checks, found %lld pairs\n", naiveChecks, naivePairs);
    printf("grid : %8lld distance checks, found %lld pairs\n", gridChecks, gridPairs);
    printf("grid did %.1fx fewer checks for the same answer\n",
           (double)naiveChecks/gridChecks);
}

Output:

naive:   499500 distance checks, found 4500 pairs
grid :    10000 distance checks, found 4500 pairs
grid did 50.0x fewer checks for the same answer

Both found the same 4,500 pairs — the grid is not an approximation, it is exact. But the naive loop did 499,500 distance checks (every pair among 1,000 points) while the grid did only 10,000, because each point only ever looked at the handful of others sharing its 3x3 neighbourhood. That 50x gap widens as the world grows: the naive method stays O(n^2), while the grid is roughly O(n) when objects are spread out evenly.

When the grid is not enough: quadtrees

A uniform grid is perfect when objects are spread evenly and you can pick one good cell size. It struggles when objects clump — a thousand units packed in one town, empty wilderness everywhere else — because the crowded cells fill up (drifting back toward O(n^2) inside a single cell) while millions of empty cells waste memory. The fix is a structure that adapts to density: a quadtree.

The 3D cousins are the octree (splits a cube into 8) and the BVH (bounding-volume hierarchy), which is what ray tracers and physics engines use to answer "what could this ray, or this moving body, possibly hit?" without testing everything. You do not need to write one today. The idea to carry forward is the one this whole chapter keeps circling back to: never pay for O(n^2) work when a structure can throw away the comparisons that were never going to matter.

19. Glossary

• Big-O — how the work of an algorithm grows as the input size n grows; ignores constant factors.
• O(1) / O(log n) / O(n) / O(n log n) / O(n^2) — constant / logarithmic / linear / linearithmic / quadratic growth, fastest to slowest.
• Cache locality — data that sits close together in memory is fast to read because the CPU loads a whole cache line at once.
• Cache miss — the CPU needs memory it did not already load, so it stalls waiting for RAM.
• Contiguous — stored back-to-back in one block (a vector), versus scattered nodes (a list).
• Amortized O(1) — cheap on average across many operations, even if one operation occasionally costs more (vector push_back).
• Geometric growth — growing capacity by a multiple (doubling), which keeps push_back amortized O(1).
• Hash function — turns a key into a number used to pick a bucket.
• Collision — two keys landing in the same bucket.
• Load factor — items divided by buckets; too high triggers a rehash.
• Stack / queue — LIFO (last in first out) / FIFO (first in first out) ordering.
• Binary heap / priority queue — a tree in an array that hands you the smallest (or largest) item in O(log n).
• Graph, node, edge, adjacency list — data as connected points; the adjacency list stores each node's neighbours.
• BFS — breadth-first search; finds the fewest steps in an unweighted graph using a queue.
• Dijkstra / A* — shortest path with edge weights; A* is Dijkstra guided by a heuristic (a guess of remaining distance) via a priority queue.
• Heuristic — a cheap estimate; in A*, the guessed cost from a node to the goal.
• Memoization / dynamic programming — store answers to repeated subproblems so you compute each once.
• Data-oriented design — arranging data in flat, contiguous arrays for cache-friendly, high-speed processing.
• std::chrono — the standard timing library; read a clock before and after work to measure elapsed milliseconds.
• Debug vs release build — -O0 (no optimizer) vs -O2; only the optimized release build reflects real shipping speed, so profile that one.
• std::deque — double-ended queue; O(1) push/pop at both front and back; backs std::queue.
• std::map (ordered map) — a balanced binary search tree (red-black tree); keys stay sorted; O(log n) insert/find; supports range queries.
• std::unordered_map (hash map) — hash-table map; O(1) average insert/find; no order.
• Rehash — a hash map growing its bucket count (to the next prime) and re-placing every item when the load factor crosses its limit.
• Separate chaining / open addressing — two ways to handle collisions: a linked list per bucket (the standard library) vs probing the next free slot in one flat array (fast game maps).
• Introsort — what std::sort is: quicksort, falling back to heapsort at deep recursion and insertion sort on small pieces.
• Stable sort — a sort that keeps equal elements in their original relative order; std::stable_sort guarantees it, std::sort does not.
• Object pool / free list — a fixed block of objects allocated once and reused via a list of free indices, to avoid per-frame allocation.
• Uniform grid — a spatial structure that buckets objects into fixed-size cells so only nearby objects are compared; roughly O(n) for evenly spread objects.
• Quadtree / octree / BVH — spatial structures that adapt to density by subdividing crowded regions; used for collision, culling, and ray/hit queries.

20. Exercises

int a(const std::vector<int>& v) {
    return v.empty() ? 0 : v[v.size() - 1];   // (A)
}

int b(const std::vector<int>& v) {           // (B)
    int best = 0;
    for (int i = 0; i < (int)v.size(); i++)
        for (int j = i + 1; j < (int)v.size(); j++)
            if (v[i] + v[j] > best) best = v[i] + v[j];
    return best;
}

grew to cap 1
grew to cap 2
grew to cap 4
grew to cap 8
grew to cap 16

That is the toolbox. You now know how to reason about the cost of code (Big-O), how the common structures are laid out in memory and why the cache decides between same-Big-O choices, and the core algorithms — hashing, heaps, BFS, Dijkstra/A*, sorting, and DP — that games lean on every frame. The recurring theme, and the one worth carrying into every later chapter: pick a sane Big-O, keep your data contiguous, and measure before you trust any speed claim.