All tutorials Mighty Professional
Build a Game Engine · Foundations

C++ Containers

An engine walks the same containers thousands of times a frame, and how long that takes often depends more on where the elements sit in memory than on the algorithm: on a desktop x86 core, reading from the L1 cache costs about 4 cycles and a trip to main memory around 250. This page shows what each standard container an engine uses looks like in memory (std::array, std::vector, std::deque, std::list, std::map, std::unordered_map, the adaptors and the views), which of your pointers into it survive which changes, and which one to pick for a given system. Live benchmarks race them in your browser.

Time~65 min LevelMid C++ engineer PrereqsYou've written a for loop over a vector. You've heard of big-O. The memory-model tutorial is useful if you want to know why unordered_map can't be lock-free. HardwareSome idea that DRAM is slower than cache
◂ Build a Game Engine Phase 0 · Foundations Next · Hash Tables ▸
What you'll be able to do by the end

01Why a container choice is a performance decision

A particle system keeps its live particles in a std::list, because removing a dead particle from a list is O(1). The profiler says the update loop spends most of its time waiting for memory rather than doing math. Switch to a std::vector, remove dead particles by swapping each with the last one, and the same O(n) loop can run many times faster. The difference is where the elements live.

Big O describes how a data structure's cost grows, not how fast it is. Keeping a linked list sorted and keeping a vector sorted are both O(n) per insert (find the position, then link or shift), and when a memory access cost about as much as an instruction, as it did through the mid-1980s, the two ran at comparable speed. On a modern CPU the vector wins by a margin so wide it stops being an algorithm question and becomes a memory-layout question. Bjarne Stroustrup made this point with a benchmark in his Going Native 2012 keynote[1], and "default to vector" is now the standard advice[16][17]. For sequence containers, the layout in memory is most of the performance story; complexity, reference stability and lookup pattern decide the rest.

The reason is the cache. The CPU doesn't fetch single bytes from memory: it fetches whole 64-byte blocks called cache lines, and keeps recently used ones close by. A vector's elements sit side by side, so one fetched line brings in the next 16 ints for free. A list's nodes sit wherever the allocator put them, so the next node is usually on some other line, and reaching it costs a cache miss: a wait while the line comes from slower memory.

Worked example

The widget below starts with 256 ints. At 4 bytes each that's 1,024 bytes, which is 16 cache lines.

Vector: the sweep enters a new line once every 16 elements, so 16 misses.

List, nodes in shuffled order: each step has only a 15-in-255 chance of landing on the same line as the previous node, so about 1 + 255 × 240/255 ≈ 241 misses, roughly 15 times as many.

The left column reads N integers from a contiguous block (a std::vector<int>). The right column reads N integers from nodes scattered across the heap (a std::list<int>). Both read the same N values, and both traversals are O(n). The difference is the order in which memory gets touched: the vector sweeps through cache lines in order, while the list jumps between unrelated lines and pays a miss on most accesses:

Live · Cache-line walker · vector vs list
vector misses
···
list misses
···
ratio
···
Each cell is one int in memory. Press RUN and watch the vector's head sweep the cells in order while the list's head jumps around; switch to both to see them side by side, and drag the element count to change N. The counters give the misses for each and their ratio: at the default 256, 16 for the vector against roughly 240 for the list. A 64-byte cache line holds 16 ints. The vector's sweep touches a new line once per 16 elements; the list visits the same cells in shuffled order, the way nodes from a general-purpose allocator scatter, so almost every step lands on a new line. A "miss" here is any step onto a different line from the previous one, which models a list too large to stay cached (a list this small would sit in L1 after one pass). The ratio climbs toward 16× as N grows. Real list<int> nodes are 24 bytes rather than 4, and the prefetcher can't help the list, so measured gaps are wider.

Four questions that predict a container's behavior

Every container on this page answers four questions, and you can mostly predict its performance from the answers:

02A short history of getting containers right

You don't need the history to pick a container, but it explains two things you'll run into in engine code: why std::unordered_map is slower than the hash tables outside the standard, and why so many studios ship their own container libraries. The pattern repeats: library authors ship a layout that's faster on real hardware, and the standard adopts it years later. By C++26 the standard has caught up for sorted lookup (flat_map) and for object pools with stable pointers (hive). The hash table is the conspicuous gap: std::unordered_map is still bound by its C++11 interface, while the open-addressing tables outside std report 2-3× better performance[9].

Timeline: from the STL to std::hive
1979
Alex Stepanov starts the generic-programming project. At GE Research, Stepanov and Dave Musser begin working on algorithms written against abstract requirements rather than specific data structures. The C++ Standard Template Library, written with Meng Lee at HP Labs in 1993-1994, is the eventual product[2][34]. Its central decision, that algorithms and containers are independent and meet only through iterators, grows out of this work.
1994
STL accepted into the draft ISO C++ standard. The container set that C++98 ships: vector, deque, list, set, map, multiset, multimap, plus the stack, queue, and priority_queue adaptors. The standard never names a data structure for the associative containers, but logarithmic complexity plus iterator-stable insert and erase narrows the practical choice to a balanced binary search tree[3]. Every shipping implementation (libstdc++, libc++, MSVC) uses a red-black tree[24].
2000
Sorted vectors as associative containers. Matt Austern's C++ Report column "Why You Shouldn't Use set (and What You Should Use Instead)" argues for a sorted vector with binary search; Andrei Alexandrescu's Loki library packages the idea as AssocVector, and Boost later ships it as flat_map (in Boost.Interprocess, then Boost.Container). Lookup is the same O(log n) as the tree, but the elements live contiguously. Insertion in the middle becomes O(n), a price most lookup-heavy code is happy to pay[4].
2007
Paul Pedriana's EASTL paper (N2271).[5] A WG21 paper describing Electronic Arts' in-house STL replacement and the places the standard library hurts game code: the allocator interface, debug-build cost, alignment, intrusive containers, fixed-storage containers. Parts of that wish list later reach the standard by other routes: runtime-selectable allocators (std::pmr, C++17), flat_map (C++23), and the fixed-capacity inplace_vector (C++26).
2011
C++11 ships std::array, std::forward_list, and the unordered containers.[6] A fixed-size sequence with no heap allocation, a singly-linked list, and hash tables with average-constant lookup. The interface of the unordered containers (a public bucket API, pointer stability, a user-set load factor) effectively requires closed addressing, where each bucket holds a linked list of the entries that hashed to it[7], and that constraint is what the "faster than unordered_map" libraries escape.
2012
Stroustrup, "Going Native" keynote.[1] The widely cited vector-vs-list benchmark: insert random integers into a sorted sequence, then remove them from random positions. The vector wins decisively even though both do O(n) work per operation; Stroustrup's follow-up write-up credits memory use and cache effects and deliberately avoids quoting absolute numbers. The keynote popularizes "default to vector" as a rule.
2012
Facebook open-sources Folly, including fbvector.[8] A reimplementation of std::vector with a 1.5× growth factor in the middle of its size range (so a later reallocation can reuse freed memory), sizing tuned for the jemalloc allocator's size classes, and memcpy relocation for types that can be moved bitwise.
2017
Matt Kulukundis, "Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step."[9] The CppCon talk that introduces SwissTable: an open-addressing table with a 1-byte control byte per slot holding 7 bits of the hash, scanned 16 at a time with one SIMD instruction. Google reported 2-3× better performance than std::unordered_map with significant memory savings. Open-sourced in Abseil in 2018[10].
2019
Facebook open-sources F14.[11] Chunks of 14 slots filtered with one SIMD compare, a design in the same family as SwissTable, with three storage variants (Value, Node, Vector) tuned for different key/value sizes. F14FastMap picks between the Value and Vector layouts at compile time based on entry size; code that needs pointer stability uses F14NodeMap.
2022
std::flat_map and std::flat_set adopted for C++23. The sorted-vector design, two decades after Austern's column, becomes standard. flat_map and flat_multimap arrive through P0429[30]; flat_set and flat_multiset arrive separately through P1222[31]. Lookup-heavy ordered associative containers no longer need a third-party dependency.
2025
std::hive adopted for C++26.[12] Matt Bentley's plf::colony, a formalization of the bucket-array object pool common in game engines, becomes the standard's stable-reference container. Erase leaves a gap that iteration skips and a later insert reuses; insert and erase leave pointers to every other element valid.

The underlying algorithms mostly date from the 1950s to the 1970s; the cache-friendly layouts are from the 2000s and 2010s; standardization trails whatever the large shops have already shipped by several years.

The original containers are still the right default for most code. The rest of this page walks them in order: array, vector, deque, list, map, unordered_map, the adaptors, the views, and the alternatives outside std at the end.

03The memory hierarchy the container sits on

Sum a million ints stored in a vector and the loop finishes in well under a millisecond. Sum the same million ints stored in a list whose nodes are scattered across the heap and it can take tens of milliseconds. The adds are identical. What differs is where each int has to come from, and every container is ultimately a way of arranging bytes for this memory hierarchy. On data that doesn't fit in cache, a CPU can spend most of its time waiting:

TierTypical latency (cycles)CapacityRelative cost of a miss
Register~016-32 general-purpose × 8 B per core
L1 data cache~432-48 KB per core
L2 cache~12256 KB-1 MB per core
L3 cache (shared)~404-64 MB per socket
DRAM~2508-128 GB

Cycle counts are Skylake-class x86 rule-of-thumb numbers, drawn from Hennessy and Patterson[13] and Intel's optimization manual[14]; AMD Zen, Apple M-series, and ARM Neoverse have their own profiles, and server parts with mesh interconnects push L3 and remote-socket DRAM substantially higher. The exact numbers vary by part; the ratio is what matters here. A miss to DRAM costs roughly 60 times an L1 hit on a desktop core.

The unit the cache moves around is a cache line: 64 bytes on x86-64 and most ARM, 128 bytes on Apple M-series. A line holds 16 ints, or 8 doubles, or 8 64-bit pointers. When the CPU touches a byte that isn't in cache, the hardware pulls the entire line that contains it, and pays the DRAM latency once. Every other byte on that line then costs only an L1 hit.

Worked example

Walk 1,000,000 ints, with a DRAM miss at about 250 cycles on a 4 GHz core.

List, if every hop misses all the way to DRAM (likely once the nodes are scattered across more memory than the L3 cache holds): 1,000,000 × 250 = 250 million cycles, about 62 ms. That's almost four 60 fps frames.

Vector: the 4 MB of ints is 62,500 cache lines. Even if every line missed, that's 62,500 × 250 = 15.6 million cycles, about 4 ms, and in practice the hardware prefetcher (below) hides most of those misses.

This is the central fact behind every container choice in the rest of the page. A contiguous container amortizes the cost of one DRAM fetch across 16 elements. A node-based container with a general-purpose allocator usually pays that fetch once per element, because consecutive nodes rarely share a cache line. (Intrusive containers and pool allocators can close some of the gap; see §16 and §17.)

What about the hardware prefetcher?

x86 (and most ARM) CPUs have a stream prefetcher that watches recent cache misses and, if they form a regular linear pattern, fetches ahead so the next miss is already on its way. A sequential vector scan triggers it: the prefetcher correctly predicts that the next line is wanted and brings it in before the CPU asks. A list traversal does not trigger it: the next node's address is in the current node's next pointer, and a stream prefetcher can't follow that indirection[14].

So the gap between vector and list grows with the working-set size. Below ~32 KB everything fits in L1 and the difference is small. Above L3 the vector streams at DRAM bandwidth (on the order of 10-40 GB/s for one core) while the list is bound by miss latency, roughly 250 cycles per node on a Skylake-class core, because each load has to finish before the next address is known. Stroustrup's keynote demo[1] is the usual reference, and his follow-up write-up deliberately reports the principles rather than absolute times. The exact factor depends on element size, allocator behavior, and the working-set range; expect the list to lose by one to two orders of magnitude once the working set outgrows L3.

With that established, the containers come in three structural families. The rest of the sections are organized by family:

  1. Contiguous sequence: array, vector. One block, indexable, cache-loving.
  2. Chunked or node-based sequence: deque (chunked), list and forward_list (one node per element).
  3. Associative: map/set (sorted, node-based, tree); unordered_map/unordered_set (hashed).

Plus the adaptors that wrap one of those (stack, queue, priority_queue) and the non-owning views (span, string_view) that point into someone else's storage.

04std::array: fixed size, on the stack

A vertex position is always three floats and a color is always four. Storing them in a std::vector would cost a heap allocation per value for a size that never changes. std::array is the container for that case: a thin wrapper around a C-style array, sized at compile time, with no heap allocation, because all the elements live in the object itself[6]. std::array<float, 3> is exactly three floats in twelve bytes, nothing more. It exists for two reasons: it gives a C array a real STL interface (.begin(), .size(), .data(), etc.), and it makes the size part of the type so the compiler can check it.

Worked example

std::array<float, 3>: 12 bytes, stored wherever the array object is, and no allocation.

std::vector<float> holding the same 3 floats, on 64-bit libstdc++ or libc++: a 24-byte object (three pointers) plus a separate 12-byte heap block, which glibc's malloc serves from a 32-byte chunk. That's 56 bytes and an allocator call to hold 12 bytes of data.

array_basics.cpp · what's actually in memory
// Three floats, allocated wherever the std::array object lives.
// If 'positions' is a local, it's on the stack; if it's a member of a class
// allocated on the heap, it lives in that class's heap block. No
// separate allocation either way.
std::array<float, 3> positions = {0.0f, 1.0f, 2.0f};

// sizeof(positions) is exactly 12. There's no length field; the size is
// encoded in the type so the compiler always knows it.
static_assert(sizeof(positions) == 3 * sizeof(float));

// The interface is std-container-shaped: iterate, index, ask the size.
for (float& element : positions) element *= 2.0f;

// data() returns a pointer to the first element, the same way a C array decays.
// Useful when calling C APIs (OpenGL, Vulkan, sockets) that want a raw pointer.
glBufferData(GL_ARRAY_BUFFER, sizeof(positions), positions.data(), GL_STATIC_DRAW);

Use it whenever the size is a compile-time constant and the container is small enough that copying it by value is cheap. Vertex positions, RGBA colors, 4×4 matrix rows, hash digests, fixed-channel audio mixes, lookup tables of known size. Anywhere a C programmer would have written float v[3];.

When std::array is the wrong answer

The size is part of the type. std::array<int, 3> and std::array<int, 4> are different types and you can't assign one to the other. If the size of the data is "small but not fixed" (usually up to 16 entries, occasionally more), reach for a vector with a small-buffer optimization, such as LLVM's SmallVector[15] or EASTL's fixed_vector, rather than std::array with the maximum size and a hand-maintained length counter. If the cap is hard, C++26's std::inplace_vector is the standard version of that array-plus-count.

05std::vector: the workhorse

The list of visible entities this frame, the triangles in a mesh, the bullets in flight: most engine collections are a run of same-typed elements you add to and loop over, and std::vector is the default container for them. Stroustrup's advice in The C++ Programming Language, fourth edition, is "use vector as your default container"[16] and the C++ Core Guidelines repeat it[17]. The reasoning is exactly the cache argument from §1: a contiguous block of memory is the friendliest layout for the CPU, and most workloads don't need more than that.

A std::vector is three pointers (or equivalents) in the object itself: begin, end, and end-of-storage[18]. The actual elements live in a single contiguous heap block. size() is end - begin; capacity() is end_of_storage - begin. Indexing is one pointer arithmetic plus one load. Iteration is a pointer walk that the hardware prefetcher loves.

Worked example

A vector<int> whose block starts at address 0x1000 holds 6 ints and has room for 10, as in the diagram below.

begin = 0x1000, end = 0x1000 + 6 × 4 = 0x1018, end_of_storage = 0x1000 + 10 × 4 = 0x1028.

size() = (0x1018 − 0x1000) / 4 = 24 / 4 = 6. capacity() = 40 / 4 = 10. v[3] is the int at 0x1000 + 3 × 4 = 0x100C.

Diagram · vector in memory
The three pointers on the left point into one heap block; drag the size and capacity sliders to move end and end_of_storage. size() is the number of constructed elements; capacity() is how much storage is reserved before the next reallocation. The gap between them is "free room"; push_back uses it without allocating.

The four guarantees that matter

The price of the contiguous block is invalidation: every reallocation invalidates every pointer, reference, and iterator into the vector, and inserts that don't grow the vector still invalidate everything from the insertion point to the end. The next two sections take each in turn.

06Growth, amortization, and the cost of push_back

A culling loop calls push_back once per visible entity. Almost every call is cheap, but now and then one call copies the whole list. If that list is a few hundred thousand entries long, the one expensive call can show up as a spike in the frame time. Knowing how a vector grows tells you how often that happens and how to stop it.

When a vector's size() reaches its capacity(), the next push_back has to allocate a bigger block, move every existing element into it, and free the old one. That's a linear-time operation, and growing by a fixed amount each time would make every push linear on average. The standard library avoids this by growing the block by a constant factor (typically 2× or 1.5×), so the cost of all the reallocations across N pushes is O(N) total and the cost per push averages out to O(1)[19].

The widget below records the cost of each push, counting one unit per element written or moved. Reallocations appear as tall red bars; the running average per push settles at a small constant even though the pushes that reallocate cost O(size):

Live · push_back amortization
total work
···
reallocations
···
avg per push
···
Each bar is one push_back, its height the work it did; the green line is the running average. Press PUSH, then switch the growth factor and push again. At the default target of 64, 2× growth reads 127 total, 7 reallocations and 1.98 per push; 1.5× reads 243, 11 and 3.80. With a 2× growth factor (libstdc++ and libc++ default for push_back) the reallocation copies form the series 1 + 2 + 4 + ... + N/2, about N total; add the N element writes and total work is about 2N, so the average cost per push converges toward 2. The 1.5× factor (MSVC, and Folly's fbvector in its middle size range) reallocates more often: the copies sum to about 2N, so the average settles near 3 and swings higher when N lands just after a reallocation. What 1.5× buys is that, after a few growths, the blocks freed earlier add up to enough room for the next allocation, which 2× growth never allows[8].

The equation below adds up all the work for N pushes with 2× growth, for N a power of two and starting from capacity 1: one write per push, plus every element copied at every reallocation. It's the reason push_back is called "amortized O(1)".

Worked example

Push 8 elements with 2× growth. The capacity goes 1 → 2 → 4 → 8, and each step copies the elements already there: 1, then 2, then 4.

Copies: 1 + 2 + 4 = 7. Writes: 8. Total: 15, which is 2 × 8 − 1, or just under 2 units of work per push.

eq. 1 · amortized push_back cost cost(N pushes) = N writes + (1 + 2 + 4 + … + N/2) copies = 2N − 1

In words: N pushes cost N writes plus the copies at each doubling, and the copies add up to less than N, so the total is about 2N. Spread over N pushes, that's a constant amount of work each, which is what amortized O(1) means. Any single push that triggers a reallocation still costs O(size), so code that needs a hard bound on one push has to call reserve() first.

Why 1.5× sometimes beats 2×

A long-lived vector that keeps growing leaves a trail of freed blocks behind it. With a smaller growth factor, those freed blocks eventually add up to enough room for the next, bigger block, so the allocator can hand the same memory back instead of finding fresh address space. With 2× growth that never happens.

Worked example

1.5× growth from a block of 1: the blocks are 1, 1.5, 2.25, 3.375, 5.06. While the live block is 5.06, the four freed ones add up to 1 + 1.5 + 2.25 + 3.375 = 8.125, and the next block needs 5.06 × 1.5 = 7.59. It fits, after four reallocations.

2× growth: the blocks are 1, 2, 4, 8, 16. While the live block is 16, the freed ones add up to 1 + 2 + 4 + 8 = 15, and the next block needs 32. It never fits, because the freed total is always one less than the live block.

Why the cutoff is the golden ratio

Set the growth factor to r and call the initial capacity 1. After k growths the live block holds rk units, and the blocks freed so far sum to 1 + r + r² + … + rk−1 = (rk − 1) / (r − 1). The next growth needs rk+1 units, and it can't reuse the live block, because the elements are still being copied out of it. So the question is when rk+1 ≤ (rk − 1) / (r − 1). For large k the −1 stops mattering and the condition becomes r(r − 1) ≤ 1, that is r² ≤ r + 1. The largest r satisfying that is the golden ratio, φ ≈ 1.618. Any factor below φ eventually fits; r = 2 sits permanently above φ and never can.

That's the case for picking a factor below 2. The case against is that smaller factors mean more reallocations, so the average per-push cost rises. The shipping picks split the difference: MSVC uses 1.5×, Folly's fbvector uses 1.5× in the middle of its size range and 2× at the small and very large ends[8], and libstdc++ and libc++ stay at 2×. Whether the reuse actually happens depends on the allocator: the freed blocks have to be adjacent and coalesced, and nothing else can have claimed them in the meantime.

In practice, if you know how big the vector will get, the cure for all of this is one line:

reserve.cpp · the one line that fixes most push_back perf
std::vector<EntityId> visibleEntities;

// We know roughly how many entities will be visible this frame.
// One allocation up front beats log2(N) reallocations during the loop.
visibleEntities.reserve(estimatedVisibleCount);

for (const Entity& entity : worldEntities) {
  if (frustum.contains(entity.bounds))
    visibleEntities.push_back(entity.id);    // no reallocation until we exceed the reservation
}

07Iterator invalidation: the rule you can't forget

An AI system saves a pointer to the player's entry in a std::vector of targets. Next frame an enemy spawns, push_back reallocates the vector, and the saved pointer now points into freed memory. Nothing crashes yet: the old bytes are still there, so the AI keeps reading a stale copy of the player until something else reuses that memory.

Every container has a set of operations that invalidate some of the iterators, pointers and references you've saved into it, meaning they no longer point at a live element. Get it wrong and you have a dangling pointer that the compiler can't catch. The rules are precise and worth memorizing for the containers you use most:

ContainerWhat invalidates iteratorsWhat invalidates pointers/references
vector Anything that triggers a reallocation invalidates all iterators. Insert or erase invalidates iterators from the change point to end(). Same as iterators. References are pointers in disguise here.
deque Any insert invalidates all iterators, including push_front and push_back. Erase at the front or back invalidates only the erased iterators (plus the past-the-end iterator when erasing the back); erase in the middle invalidates all. Insert at front or back leaves all pointers/references valid; insert or erase in the middle invalidates everything. Erase at the front or back invalidates only the erased element’s references.
list, forward_list Only the iterators to erased elements are invalidated. Only the pointers to erased elements. Everything else survives.
map, set, multi* Same as list: only the erased ones. Same as list: only the erased ones.
unordered_map, unordered_set Insert may trigger a rehash, which invalidates all iterators. Erase invalidates only the erased iterator. Insert with no rehash leaves pointers/references valid; rehash leaves pointers/references valid (only iterators are invalidated). Erase invalidates only the erased element's references.

Adapted from the cppreference invalidation tables[19][20] and the formal ISO wording[3]. The unordered_map rule is the easy one to get wrong: a rehash invalidates iterators but not pointers or references, because the nodes stay where they are and only the bucket links change. That has held since C++11. The table leaves out shrink_to_fit, which may reallocate vector and deque storage and so can invalidate everything.

Worked example

The widget below starts with a vector of a, b, c, capacity 4, and two saved iterators: it₁ at index 0 and it₂ at index 2.

push_back(d): size 4, capacity 4, no reallocation. Both iterators are still valid (only end() moved).

push_back(e): size would be 5 but capacity is 4, so the vector moves to a new block of 8. Both iterators are now dangling.

From the start instead, insert in the middle at index 2: no reallocation, but everything from index 2 shifts right. it₂ is dangling; it₁, before the insertion point, stays valid.

Each button on the widget below performs one operation on a small vector. Two saved iterators point at fixed positions and turn red as soon as an operation invalidates them. A reallocation (including reserve past the current capacity) invalidates both; an insert or erase in the middle invalidates everything from that position onward.

Live · iterator invalidation
size
3
capacity
4
it₁ status
valid
it₂ status
valid
The cells are the vector's slots (filled and spare), and the two arrows are saved iterators; the readouts give size, capacity and each iterator's status. Press push_back twice from the start: the second push reallocates and both arrows go red. Reset, then try insert middle and erase middle. A reallocation moves the entire block, so every iterator into the old block becomes a pointer into freed memory. Even an insert that doesn't reallocate (capacity sufficient) shifts every element after the insertion point, so iterators that pointed there now refer to a different element. Using an invalidated iterator is undefined behavior, and tests often miss it because freed memory still holds the old values until something reuses it.

08std::deque: chunked, two-ended

A replay buffer appends each new event at the back and drops the oldest from the front. With a vector, dropping from the front shifts every remaining element. std::deque ("double-ended queue") gives you push_front and pop_front at O(1), which vector doesn't. It does this by storing elements in a sequence of fixed-size chunks, with a top-level index ("map") of pointers to those chunks[21]. When the front chunk is full, push_front allocates a new chunk and adds it to the map; the existing chunks don't move. Indexing is two loads (chunk pointer, then element) instead of one.

Implementations pick a chunk size, and the picks differ wildly[22]:

Worked example

A deque<double> holding 10,000 doubles (8 bytes each).

libstdc++: 512 / 8 = 64 doubles per chunk, so 10,000 / 64 = 156.25, rounded up to 157 chunks. Iterating crosses a chunk boundary 156 times in 10,000 steps.

MSVC: 16 / 8 = 2 doubles per chunk, so 5,000 chunks: 5,000 separate allocations, and a jump to a new address every second element.

Pictured below: a generic layout with 8-element chunks (libstdc++ with 64-byte elements). Push at either end and a new chunk is allocated when the current end chunk fills; existing chunks never move.

Diagram · deque chunk map
elements
···
chunks
···
chunk size
8 elems
The top row is the map of chunk pointers and each box below is one 8-element chunk. The deque starts empty in the middle of one chunk: press push_back five times and the fifth push allocates a second chunk (the readout goes to 5 elements, 2 chunks), then push and pop at both ends. Two-level structure: a map of pointers, each pointing to a fixed-size chunk. Iteration walks within a chunk (cache-friendly), then jumps to the next chunk at an unrelated address. push_front never moves existing elements; when the front chunk is full it allocates a new one. The widget frees a chunk once popping empties it, as libstdc++ does. O(1) work at both ends with no element moves is why std::deque is the default backing store for std::queue.

Use it when you need O(1) push and pop at both ends, when reference stability after front/back insertion matters, or when you want to grow without periodic 2× reallocations. Common production uses:

deque is not always cache-friendly

Within a chunk, iteration behaves like a vector: a 512-byte libstdc++ chunk of 8-byte doubles is 8 cache lines swept in order. Each jump to the next chunk lands at an unrelated address, costs an extra load through the map, and can break the prefetcher's stream, so a deque pays an extra penalty once per 64 doubles. That is far better than a list's miss per element and within a small constant of a vector. On MSVC, with one element per chunk for anything larger than 8 bytes, every element is a jump, and the deque behaves more like a list than a vector. For pure-iteration workloads on libstdc++ or libc++, std::vector typically wins by a small constant; for two-ended access, deque wins among the standard containers because the alternative is a vector with O(n) insert(begin()).

09std::list and std::forward_list

A job scheduler moves jobs between a ready queue and a waiting queue, and other systems hold pointers to those jobs the whole time. Moving a job must not copy it, and it must not invalidate anyone's pointer. That is the job std::list is built for. It's a doubly-linked list: each element lives in its own heap allocation, with two pointers (prev and next) to its neighbors. std::forward_list drops the prev pointer to halve the per-node overhead, at the cost of being singly-linked[23].

list has two real selling points in modern C++:

  1. Reference stability under all mutations. A pointer into a node survives every insert and every erase that doesn't touch that specific node. That matters in code that keeps long-lived handles to objects in containers.
  2. O(1) splice. list1.splice(pos, list2, it) moves a node from list2 into list1 by relinking pointers, with no copies and no allocations[23]. Apart from forward_list::splice_after, no other standard container moves an element between containers in O(1); C++17's extract/insert moves map and set nodes without copying, but the insert still pays for the lookup. LRU-eviction caches and ready-queue schedulers both lean on this.

Outside of those two use cases, it is almost always the wrong choice. The cache-miss penalty from §1 is the headline; smaller costs add up too:

Worked example

100,000 ints on 64-bit libstdc++ with glibc's malloc.

vector<int>: 100,000 × 4 = 400 KB in one block, one allocation if you reserve first.

list<int>: 100,000 nodes, each a 32-byte heap chunk, so 3.2 MB and 100,000 allocator calls. Eight times the memory, spread over eight times as many cache lines.

The next section measures the gap directly.

10List vs vector, measured

The claim that a vector beats a list even where the list "should" win deserves a measurement. Stroustrup's Going Native 2012 benchmark[1] is the standard one: generate N random integers; for each one, find its sorted position (linear scan from begin()) and insert it there. (The original then removes the elements again from random positions.) Run it on both a vector and a list. Both do the same comparisons and the same number of insertions; only the constant factor differs.

Worked example

N = 2,000 (the widget's default). When the sequence holds i elements, a random new value lands in the middle on average, so the search scans about i/2 elements and the vector shifts about i/2 more.

Summed over all 2,000 inserts: 2,000 × 1,999 / 4 ≈ 1,000,000 comparisons for both containers, plus about a million element moves for the vector. Same work on paper. The vector's comparisons read consecutive memory and its moves happen in bulk; the list's comparisons are a million loads that each wait for the one before.

Press RACE to run the insert half in JavaScript. The vector is an Int32Array shifted with copyWithin; the list is a pair of typed arrays (value, next) whose nodes sit at shuffled positions, so following next jumps around memory the way heap nodes do. Absolute times won't match native C++. At these sizes the whole list fits in L1 or L2, so each hop is a cache hit rather than a DRAM miss, and the list's handicap is mostly that every load has to wait for the previous one. Expect a gap of a few times here, widening with N; native runs whose lists outgrow the L3 cache show the order-of-magnitude gap:

Live · sorted-insert race
vector ms
···
list ms
···
ratio
···
The two bars are the measured times for the same N sorted inserts, scaled so the slower one fills the track. Press RACE, then raise N and race again: the ratio grows with N. At the smallest sizes both runs can finish faster than the browser's timer can measure, so the readouts there are noise. The vector wins because its sorted-position search sweeps contiguous memory, while the list's search is a chain of dependent loads to scattered nodes (a cache miss per node once the list outgrows the cache). The insert phase costs the vector a memmove of cache-resident bytes and the list a pointer relink. The list does less structural work per insert and still loses, because the search dominates. Both are O(n) per insert; the layout sets the constant[1].
When list actually wins

Two cases survive the cache argument. (a) Splice-heavy workloads where you move elements between containers without iteration: an LRU cache that touches one element per request, then moves that node to the front, is a textbook fit. (b) Code that holds long-lived pointers into the container across many mutations: a list<Job> where job dependency edges store raw Job*. Before C++26, the contiguous alternative in both cases needs a separate indirection table to provide the reference stability that list gets for free; whether that's a better deal depends on the specifics. C++26's std::hive (§16) covers case (b) with a cache-friendlier layout when element order doesn't matter, which leaves the splice-heavy case (a) and order-sensitive versions of (b) as the natural homes for list.

11std::map and std::set: ordered associative

A replay system stores events keyed by timestamp and needs to play them back in time order, or jump to "everything from 12.5 s onward". That needs a container that keeps its keys sorted as you insert. std::map<K, V> is a sorted, balanced binary search tree from keys to values: each node holds one key, smaller keys go in its left subtree and larger ones in its right. The standard requires logarithmic-time lookup, insert, and erase, and ordered iteration[3]. The standard never names a specific data structure, but every shipping implementation (libstdc++, libc++, MSVC) uses a red-black tree[24]. AVL trees meet the same logarithmic bounds with a shorter tree, but an AVL erase can rotate at every level on the way back up. A red-black insert needs at most two rotations and an erase at most three, with recoloring that is amortized O(1), which fits the standard's requirement that erase(iterator) run in amortized constant time.

Each element is its own heap-allocated node containing the key/value pair, a parent pointer, two child pointers, and a color field. In libstdc++ on x86-64 that header is 32 bytes per node (three pointers plus the color enum padded to pointer alignment), before the payload; the general-purpose allocator adds its own per-allocation header and rounding on top (8 bytes of header on glibc). Lookup is a logarithmic walk from the root, branching by key comparison at each node.

Worked example

A map<int, float> with 1,000 entries on 64-bit libstdc++ and glibc.

Each node is the 32-byte header plus the 8-byte key/value pair, 40 bytes, which glibc serves from a 48-byte chunk: 48 KB for 8 KB of data.

A perfectly balanced tree of 1,000 nodes is 10 levels deep (210 = 1,024). A red-black tree is allowed to be up to 2 × log2(1,001) ≈ 19.9 levels deep. So a lookup visits somewhere between 10 and 19 nodes, each one a separate allocation that may not be in cache.

Live · red-black tree
size
···
height
···
last op
···
The tree starts with 15 keys, perfectly balanced at height 4; the readouts give its size, its height and the last operation. Pick a key with the slider and press insert to watch it drop into place and the tree rotate and recolor, or find to highlight the search path. Red-black invariants: every node is red or black; the root is black; the empty (null) leaves count as black; a red node has black children; every root-to-leaf path has the same number of black nodes. These constraints bound the height at 2·log2(n + 1), which keeps lookup logarithmic. Insert and erase recolor and rotate to restore the invariants in O(log n) time[24]. The height stat counts the nodes on the longest root-to-leaf path.

When to use map, and when not

Use std::map when you need ordered iteration (lowest key first, highest key last) or when you need to find ranges by key (lower_bound, upper_bound, equal_range). For example: per-frame replay events keyed by timestamp, where you stream events in time order; or an interval tree by start coordinate.

Don't use std::map as a default associative container. For unordered "find by key" lookups, std::unordered_map is usually faster (constant vs logarithmic on average), and a flat sorted vector (std::flat_map in C++23, or boost::container::flat_map before that) often beats both for read-heavy workloads on small to medium key sets, because the contiguous layout fits the cache[4].

12std::unordered_map and the bucket interface

An asset manager looks up loaded textures by name hundreds of times a frame and never needs them in order. That's a job for a hash table: turn the key into a number with a hash function, use the number to pick a bucket, and look only in that bucket. std::unordered_map is the standard one. It gives average constant-time lookup, insert and erase, and worst-case linear time when many keys collide in one bucket. C++11 standardized it with an implementation strategy baked into the interface: closed addressing (each bucket holds a linked list of entries that hashed to it), exposed through the public bucket_count(), bucket_size(), and local_iterator APIs[20]. Together with the pointer-stability guarantee, that interface locks every shipping std::unordered_map into separate chaining[7], which is a large part of why open-addressing tables outside the standard beat it, by 2-3× in Google's measurements[9].

The widget shows the closed-addressing layout. Each bucket points to a linked list of {hash, key, value} nodes. Lookup hashes the key, picks the bucket, then walks the bucket's list comparing keys. The load factor (size() / bucket_count()) controls how long the bucket chains get; the default max_load_factor is 1.0, so the average chain holds at most one element.

Live · unordered_map (separate chaining)
size
···
buckets
···
load factor
···
max chain
···
Each numbered slot is a bucket, with its chain of nodes hanging below it; the readouts give size, bucket count, load factor and the longest chain. The table starts with about 20 random keys. Pick a key and press insert or find to highlight its bucket and node, or lower the load-factor target and seed more keys to watch it rehash into twice as many buckets. Separate chaining: each bucket is the head of a linked list. A lookup can miss the cache once reading the bucket and again for each chain node it visits. The interface of std::unordered_map bakes this in: the bucket API with its local_iterator, node-based pointer stability, and user-controlled load factor are requirements an open-addressing table can't meet[7]. The widget doubles the bucket count on rehash; libstdc++ and libc++ move to a prime near double.

Hash quality matters more than you think

The hash function decides whether the table runs at O(1) or degenerates to O(n). std::hash<int> on libstdc++ and libc++ is the identity function: hash(42) == 42. That works because both libraries use prime bucket counts and take hash % bucket_count, which mixes every bit of the key into the bucket index. The same identity hash fails badly in a table with a power-of-two bucket count, which keeps only the low bits: keys that share their low bits (16-byte-aligned pointers, IDs that are multiples of 256) all land in the same few buckets. That's why power-of-two tables scramble the hash first.

Worked example

Entity IDs 256, 512, 768 and 1,024, with the identity hash.

8 buckets (a power of two): 256 % 8, 512 % 8, 768 % 8 and 1,024 % 8 are all 0. Every key lands in bucket 0, and lookups walk one long chain.

13 buckets (a prime): the remainders are 9, 5, 1 and 10. Four different buckets.

Hash flooding, where an attacker picks keys that all collide, is a real attack, and the standard library does not defend against it: its hashes are unseeded. Code that hashes untrusted input (network packets, user-supplied strings) should use a keyed hash such as SipHash with a per-process random key[25].

For game code, where the inputs are usually engine-controlled, the default is usually fine. The bigger issue is the table's layout.

13Open addressing and SwissTable

Suppose the texture lookup from §12 shows up in a profile. Most of its cost is the chain of pointer hops: bucket array, then node, then maybe another node. Most high-performance hash tables outside the standard library avoid those hops with open addressing: no separate buckets, every entry stored inline in one flat array, and collisions resolved by probing other slots, checking the next slots until the key or an empty slot turns up. The flat layout is the cache argument from §1 applied to hash tables: one DRAM fetch covers several adjacent probe positions. The probing schemes predate the newer tricks that use SIMD instructions, which work on a whole register of values at once. Robin Hood hashing, which cuts probe-length variance by letting keys that have probed farther take slots from keys sitting close to their home slot, dates to the mid-1980s and underpinned several fast open-addressing tables before the SwissTable generation[33].

The most influential modern design is Google's SwissTable[9], open-sourced in Abseil in 2018[10]. Rust's standard HashMap (via the hashbrown crate) and Go's map since version 1.24 use SwissTable designs, and Folly's F14[11] is a close relative. The group size differs: SwissTable scans 16 control bytes at a time, one 128-bit SIMD register, and grows when a large table passes a load factor of 7/8 = 87.5%. F14 packs 14 one-byte tags into a 16-byte chunk header and spends one of the two spare bytes on an overflow count: the number of keys that wanted this chunk but had to be stored further along. Insert increments it and erase decrements it, so an unsuccessful lookup can stop at the first chunk whose count is zero instead of treating deleted slots as tombstones that force it to keep probing[35]. F14's max load factor is 12/14 ≈ 85.7%.

The design has four moving parts:

Worked example

A SwissTable with 1,024 slots holds up to 7/8 × 1,024 = 896 entries before it grows, and its control bytes take 1,024 bytes, about 1 byte per slot.

How often does the 7-bit filter let a wrong key through? A full slot holding some other key matches the searched H2 by chance with probability 1/128. A group of 16 has at most 15 other keys, so a lookup expects at most 15/128 ≈ 0.12 wasted full-key comparisons per group.

Press "find" on the widget below with a key. H1 picks a group, one compare against the key's 7-bit H2 produces the match mask over its 16 control bytes, and each match gets a full key comparison. A full group with no match sends the probe on to the next group:

Live · SwissTable lookup
size
···
groups
···
last probe
···
overhead
1 B / slot
Each row is one 16-slot group, with every slot's control byte (its 7-bit H2, in hex) above its key; the table starts with about 20 random keys in two groups. Pick a key and press find: the probed group is outlined, control bytes that match the key's H2 light up, and the slot whose key matches turns green. Seed more keys to fill groups and force multi-group probes. The core idea: keep 7 bits of each key's hash in a byte array beside the slots, so one SIMD compare filters 16 slots at once. The same control bytes mark empty and deleted slots, so a similar compare finds where an insert can go. The metadata costs 1 byte per slot, plus the empty slots the 7/8 load factor leaves. A node-based unordered_map instead pays a next pointer per node (often a cached hash too), a bucket array, and an allocator header for every node[7]. For readability the widget uses aligned groups and moves to the next group linearly; Abseil starts a group at any control byte and steps between groups with a triangular (quadratic) sequence.

Where the time goes

On a table that doesn't fit in cache, a closed-addressing std::unordered_map lookup typically pays a miss for the bucket entry, another for the first chain node, and one more for each further node it walks. A SwissTable lookup typically pays one miss for the group's control bytes and one for the matching slot; the SIMD compare itself is a couple of instructions. Google reported 2-3× better performance than std::unordered_map with significant memory savings[9].

No open-addressing hash table has been standardized as of C++26. The practical answer for new engine code is a third-party table: absl::flat_hash_map, boost::unordered_flat_map, or folly::F14FastMap. std::unordered_map stays useful where code relies on its pointer stability or its bucket interface.

14The adaptors: stack, queue, priority_queue

A sound system keeps a list of voices that want to play and, when it runs out of hardware channels, always drops the least important one. That access pattern, "give me the top item", doesn't need a general container: it needs a narrow one that does that job well. The standard library has three such adaptors, thin wrappers that restrict an underlying container to one access pattern:

The binary-heap layout is worth knowing because priority queues are hot in game code: A* pathfinding, sound voice priority, timed-event scheduling, most "do the most important thing next" systems. The heap is a vector where, for the element at index i, its children are at 2i+1 and 2i+2, and the parent is at (i-1)/2. push appends and sifts up (swaps the new element with its parent while it's bigger); pop takes the root, moves the last element to the root, and sifts down (swaps it with its bigger child while that child is bigger).

Worked example

The element at index 3 has children at 2 × 3 + 1 = 7 and 2 × 3 + 2 = 8, and its parent at (3 − 1) / 2 = 1 (integer division).

A heap of 1,000 elements is 10 levels deep, 9 steps from root to bottom (29 = 512 ≤ 1,000 < 1,024). A push compares at most once per level it climbs: 9 comparisons at most. A pop compares with up to two children per level on the way down: 18 at most.

Live · binary heap
size
···
top
···
last op compares
···
The tree and the flat array below it are the same heap; the readouts give its size, its top and the comparisons the last operation needed. Push a value with the slider, or seed 10 random ones, then pop and watch the last element sift down from the root. A binary max-heap stored in a vector. Push and pop are O(log n) (one sift-up or sift-down through the tree). Building a heap from a vector with std::make_heap is O(n), not O(n log n): it sifts down from the bottom up, and most nodes sit near the bottom where a sift-down is short[27]. "Last op compares" counts element comparisons in the most recent push or pop.

The standard library's priority queue is a max-heap by default. For Dijkstra and A*, where you want the smallest distance first, pass std::greater<T> as the comparator:

astar.cpp · min-heap for shortest-path search
struct PathNode {
  NodeId nodeId;
  float  estimatedTotalCost;        // f = g + h: A* total estimate through this node
};
struct SmallerFirst {
  bool operator()(const PathNode& lhs, const PathNode& rhs) const {
    // priority_queue puts the "largest" element on top; comparing with >
    // makes the smallest cost the largest, so it ends up on top.
    return lhs.estimatedTotalCost > rhs.estimatedTotalCost;
  }
};

std::priority_queue<PathNode, std::vector<PathNode>, SmallerFirst> openSet;

// Sketch of the queue's role only: the closed set, the g-cost table and
// its updates, and skipping stale entries are left out.
openSet.push({startNodeId, heuristic(startNodeId, goal)});
while (!openSet.empty()) {
  PathNode currentNode = openSet.top();   // O(1): best frontier node
  openSet.pop();                            // O(log n): sift the last element down
  if (currentNode.nodeId == goal) break;
  for (NodeId neighbor : neighborsOf(currentNode.nodeId))
    openSet.push({neighbor, gCostSoFar(neighbor) + heuristic(neighbor, goal)});
}
priority_queue's missing API

std::priority_queue does not let you change the priority of an element in place; it has no "decrease-key" operation[27]. A Dijkstra or A* implementation pushes a fresh entry with the lower cost and skips stale entries when they reach the top. That lazy approach is usually fast enough in practice. When stale entries bloat the heap (dense graphs where nodes improve many times), an indexed binary heap that tracks each node's position supports decrease-key directly.

15std::span and std::string_view: non-owning views

A draw function takes the vertices to draw. If it takes a std::vector<Vertex> by value, every call copies the mesh; if it takes a const std::vector<Vertex>&, a caller holding a std::array or a raw buffer has to copy into a vector first. Two additions, std::string_view (C++17) and std::span (C++20), fix that. They aren't really containers, but they're how you pass containers around without copying. They are both views: a pointer plus a size, owning nothing, valid only as long as the underlying storage outlives them[28].

Worked example

A mesh of 10,000 vertices at 32 bytes each is 320 KB.

Pass it as a std::vector<Vertex> by value: a 320 KB allocation and copy on every call.

Pass it as a std::span<const Vertex>: a pointer and a count, typically 16 bytes on a 64-bit platform, small enough to travel in two registers.

Use them as parameter types whenever a function takes a contiguous range and doesn't need to extend its lifetime. The function gets to work with any contiguous source without overloading on the container type, and the caller doesn't pay for a copy:

span_param.cpp · the right shape for read-only sequence parameters
// Old way: one overload per container type, each with a copy if you
// took the parameter by value, or coupling to a specific container if
// you took it by reference. Both unsatisfying.
void drawTriangles(const std::vector<Vertex>& vertices);
void drawTriangles(const std::array<Vertex, 64>& vertices);
void drawTriangles(const Vertex* vertices, size_t count);

// Modern way: one function, takes a view, the caller passes whatever
// they have. No copies, no overload set, no error-prone count parameter.
void drawTriangles(std::span<const Vertex> vertices);

// Call sites work uniformly:
drawTriangles(meshVertexVector);             // vector → span
drawTriangles(framePushArray);               // std::array → span
drawTriangles({rawPtr, count});              // raw pointer + count → span
Views don't own anything

A view is a pointer plus a length. The underlying storage has to outlive the view, or the pointer dangles. A classic std::string_view bug is constructing it from a temporary std::string and keeping the view past the end of the statement that created the temporary. Clang's -Wdangling warnings (on by default, driven by [[clang::lifetimebound]] annotations and built-in knowledge of view types) and MSVC's code-analysis warnings C26815 and C26816 catch many of these at compile time; turn them on.

16Beyond std: flat_map, hive, intrusive lists, ring buffers

Sooner or later an engine hits a case the standard containers handle badly: a table of settings looked up every frame but never changed, an entity pool where objects die constantly while other systems hold pointers to them, a bounded audio queue that must never allocate. The standard's container set is the default, not the ceiling. Here's a short tour of the non-std containers most game engines pick up for those cases:

flat_map and flat_set (C++23 / Boost.Container)

Sorted {key, value} storage wrapped in an associative interface. (boost::container::flat_map is one vector of pairs; std::flat_map keeps keys and values in two separate sorted vectors, so a lookup's binary search touches only keys.) Lookup is O(log n) binary search on contiguous memory; insertion and middle-erase are both O(n) because everything after the change point shifts. Insertion and erase are slower than the tree's O(log n); lookup and iteration are faster; memory overhead is lower. Lookup-heavy, small-to-medium key sets are the sweet spot. C++23 standardized it as std::flat_map and std::flat_set; Boost's version dates to 2004[4].

Worked example

1,000 int → float entries.

std::flat_map: a 4,000-byte vector of keys and a 4,000-byte vector of values, about 8 KB plus any spare capacity, and a lookup's binary search reads only the keys.

std::map on libstdc++ and glibc: 1,000 nodes in 48-byte chunks, 48 KB, as worked out in §11.

std::hive / plf::colony (C++26)

A bucket array with stable references on insert and erase. Elements live in a chain of blocks (each block's capacity is fixed when it's allocated; later blocks are usually larger), and each block has a skipfield recording which slots are erased. Iteration uses the skipfield to jump over runs of erased slots in constant time. Insert reuses an erased slot if one exists, else appends. Erase marks the slot in the skipfield, leaving every pointer to other elements valid. Element order is not preserved: an insert can land anywhere a gap exists[12].

Matt Bentley built it for game-engine object pools, where entities are created and destroyed constantly while other systems hold pointers to live ones[32]. It was adopted as std::hive for C++26.

Intrusive containers (Boost.Intrusive, EASTL)

A list or tree where each element carries the link pointers, and the container only holds the head (and usually the tail and a count); the user manages the storage. Two payoffs: no per-node heap allocation (the link state lives inside the element you already own), and an element can be in several intrusive containers at once, one set of links per container. EASTL's intrusive_list and Boost.Intrusive's list are the best-known implementations[5]. Engine schedulers (wait lists of suspended jobs) and allocator free lists commonly use this pattern.

Ring buffers (custom, no std equivalent)

A fixed-capacity contiguous array with two indices (head and tail) that wrap around. Push and pop are both O(1) with no allocation; the capacity is a hard cap. Used wherever a bounded queue makes sense: audio sample buffers, replay event buffers, bounded lock-free job queues. The standard has no ring buffer, partly because the variants don't reduce to one shape: bounded vs growing, single-producer vs multi-producer, overwrite-when-full vs block-when-full. The concurrent-queue proposal P0260 has been revised about twenty times since 2016 and is not in C++26.

SmallVector / fixed_vector (LLVM, EASTL)

A vector with an inline buffer of N elements; falls back to heap allocation when N is exceeded. The first N pushes touch no heap at all, which matches the workload pattern for "build a small list inside a function and discard it" code. LLVM's llvm::SmallVector<T, N> is the most widely cited implementation[15], and EASTL ships fixed_vector<T, N> in the same shape.

17Allocators and why games override them

A console title has a fixed memory budget per subsystem, and a profile shows thousands of small malloc calls per frame from temporary containers that are all thrown away at the end of the frame. Both problems come down to where containers get their memory. Every standard container except std::array takes an allocator template parameter (the adaptors pass it through to the container they wrap). The default is std::allocator<T>, which forwards to ::operator new and ::operator delete. Those usually sit on the platform's thread-safe general-purpose malloc (glibc's malloc, the Windows CRT heap, or a replacement such as jemalloc or tcmalloc), and that's the right answer for most code.

Game engines commonly override it for three reasons[5]:

Worked example

A bump arena that rounds every allocation up to 16 bytes, starting at offset 0. Allocate 100 bytes: it gets offset 0, and the next free offset is 100, rounded up to 112. Allocate 24: offset 112, next free 136, rounded to 144. Allocate 64: offset 144, next free 208.

Three allocations, three additions and roundings, no locks and no free lists. Resetting the frame sets the offset back to 0.

C++17 added std::pmr (polymorphic memory resources), which lets you pick an allocator at runtime instead of at type-instantiation time. std::pmr::vector<int> is a vector of int that takes its memory resource as a constructor argument. That lets engine pools plug in without making every container a different type, at the cost of a virtual call per allocation. The standard ships std::pmr::monotonic_buffer_resource (a linear arena) and std::pmr::unsynchronized_pool_resource (size-class pools with no locking, for use from one thread) out of the box.

pmr_frame.cpp · per-frame linear arena, no malloc on the hot path
// One frame's worth of scratch storage. Reused every frame.
// (Past the 4 MB, the arena falls back to its upstream resource, the heap.)
static std::array<std::byte, 4 * 1024 * 1024> frameArenaStorage;
std::pmr::monotonic_buffer_resource frameArena(
    frameArenaStorage.data(), frameArenaStorage.size());

void simulateFrame() {
  frameArena.release();    // "free everything from last frame": rewinds to the start of the buffer

  // The vector allocates from the arena: reserve() is one pointer bump, and
  // any growth past 1024 is another bump (the old block is simply abandoned).
  std::pmr::vector<VisibleEntity> visibleEntities(&frameArena);
  visibleEntities.reserve(1024);

  for (const Entity& entity : worldEntities)
    if (mainCameraFrustum.contains(entity.bounds))
      visibleEntities.push_back({entity.id, entity.transform});

  submitDraws(visibleEntities);
  // visibleEntities goes out of scope here. For trivially destructible
  // element types, no destructors run; the buffer's deallocate() on a
  // monotonic arena is a no-op, so the whole teardown is free until
  // frameArena.release() reclaims the arena at the top of next frame.
}

18The container race

Every section so far has argued from layout. This widget measures it. It times three workloads (push N elements, iterate them, look up random ones) across five containers. Each container is modeled in JavaScript with typed arrays laid out the way the C++ container lays out memory: the vector is one growing block, the deque is 128-element chunks (libstdc++'s 512 bytes of int), and the list, map and unordered_map are nodes placed at shuffled positions in a pool, the way heap allocations scatter. Every number is a real measurement in your browser, with no calibration factors. Absolute times aren't native C++ times: JavaScript adds bounds checks, and the pool allocation charges nothing for malloc, which understates push costs for the node-based containers. Pick a workload and a size:

Live · five-container race
vector ms
···
deque ms
···
list ms
···
map ms
···
unordered ms
···
Each bar is one container's measured time for the chosen workload, on a log scale, and each readout also shows the multiple of the vector's time. Pick a workload, set N and press RACE. Iteration shows the layout effect most cleanly: vector and deque stream through contiguous memory, while list, map and unordered_map chase pointers to shuffled nodes. How far apart the bars land depends heavily on your CPU's cache sizes. On a desktop CPU, expect the node-based containers to iterate roughly 10-40× slower than the vector at N = 100,000, where their pools still fit in L2 or L3, and roughly 80-200× slower at 1,000,000, once they spill to DRAM. Random access widens the spread: vector and deque index directly, unordered_map hashes to one bucket (tens of times the vector), map walks O(log n) scattered nodes (hundreds of times), and list has to walk from begin() for every query; ≈ marks a list time extrapolated from a subset of the queries. Push N is the one workload where the list keeps pace with the vector, because this model's pool hands out nodes for free; a real std::list pays a malloc per node. Large N takes a second or two to run.

19The decision cheat sheet

When you're about to declare a container, the useful question is "what do I need it to do?" This table is organized that way: find the need in the left column.

If you need…Reach forWhy
A sequence of T, default case std::vector<T> Contiguous, cache-friendly, O(1) push_back amortized, the right answer for the bulk of sequence workloads[16].
A fixed-size sequence, no heap allocation std::array<T, N> Size is part of the type. Lives inline in its owner.
A small bounded sequence, usually fits in N, sometimes overflows llvm::SmallVector<T, N> or eastl::fixed_vector Inline buffer for N, heap fallback past N. Zero allocations on the common path.
O(1) push and pop at both ends std::deque<T> Chunked storage means front pushes don't shift everything.
O(1) splice between containers, or stable pointers across all mutations std::list<T> or std::hive<T> (C++26) A pointer to element X survives any operation that doesn't erase X. list is node-based and keeps order; hive keeps pointers stable in contiguous blocks, iterates faster, but doesn't keep order or splice single elements.
Lookup by key, frequent inserts and erases, doesn't fit in a flat_map absl::flat_hash_map<K, V> or folly::F14FastMap<K, V> Open addressing with SIMD-filtered probing; Google reported 2-3× better performance than std::unordered_map[9]. Rehash moves elements, so pointers into it don't survive growth.
Lookup by key, small to medium static-ish key set, read-heavy std::flat_map<K, V> (C++23) or boost::container::flat_map Sorted vector. Binary search on contiguous memory is competitive with hashing at small N, and iteration is in key order[4].
Ordered iteration, range queries by key std::map<K, V> Red-black tree, sorted iteration is automatic, lower_bound/upper_bound work.
LIFO behavior, want to expose only push/pop/top std::stack<T, std::vector<T>> Vector-backed stack. The deque default works, but a vector keeps the stack in one contiguous block.
FIFO behavior std::queue<T> The deque default is a good fit. For a bounded queue, especially a lock-free one, use a ring buffer.
"Do the highest-priority job next" std::priority_queue<T> Vector + binary heap. O(log n) push and pop, O(1) top.
A read-only view of a contiguous range std::span<const T> / std::string_view Pointer + size. No copy, no allocation, no template-on-container.

20The container pitfalls list

Use this as a review checklist. Each item is a mistake that compiles cleanly and passes most tests, organized by the container that produces it:

vector pitfalls

deque pitfalls

list pitfalls

map pitfalls

unordered_map pitfalls

21What's next

The decision comes down to layout (one block, chunked, node-based, hashed) and access pattern; the container follows from those two. The cheat sheet in §19 is the lookup table, and the earlier sections are the reasoning behind each row.

Next in the series, Hash Tables builds a hash table from scratch: hash functions, chaining versus open addressing, load factors and probing, the ideas §12 and §13 used here. Further on:

22Sources & further reading

Numbered citations refer to the superscripts above: standards, papers, library documentation and source, conference talks, and implementers' write-ups.

A note on originality

The prose, code samples, CSS, and interactive demos on this page are original. The vector-vs-list framing follows Stroustrup's Going Native 2012 keynote [1]. The SwissTable description follows Matt Kulukundis's CppCon 2017 talk [9] and the Abseil design notes [26]. The growth-factor argument in §6 starts from Folly's documentation [8]; the golden-ratio derivation (r² ≤ r + 1) is worked through here. The F14 description follows Facebook's design doc and announcement [11][35]. The game-engine allocator concerns in §17 follow Paul Pedriana's N2271 paper [5]. Deque chunk sizes come from Raymond Chen's comparison of the three implementations [22]; complexity guarantees and invalidation rules follow the C++ standard [3] and cppreference.

  1. Stroustrup, B. (2012). C++11 Style. Going Native 2012 keynote. YouTube. Includes the vector-vs-list sorted-insertion benchmark and the "cache effects dominate" argument; follow-up at isocpp.org/blog/2014/06/stroustrup-lists.
  2. Stevens, A. (1995). Alexander Stepanov and STL Interview. Dr. Dobb's Journal. archived copy (stlport.org). Stepanov on his years at GE Research, the work with Dave Musser, and writing the STL with Meng Lee.
  3. ISO/IEC 14882:2020 (and subsequent revisions). Programming languages — C++. Standard reference for container complexity guarantees, sequence/associative requirements, and iterator invalidation. Open draft mirrored at eel.is/c++draft.
  4. Boost. Boost.Container Non-Standard Containers: flat_(multi)map / flat_(multi)set. boost.org. Boost's sorted-vector associative containers (available since 2004), with their history: Matt Austern's 2000 C++ Report column and Loki's AssocVector.
  5. Pedriana, P. (2007). EASTL: Electronic Arts Standard Template Library. WG21 paper N2271. open-std.org. The committee-facing case for the allocator model, intrusive containers, and fixed-storage containers that game code needs.
  6. cppreference. std::array. en.cppreference.com/w/cpp/container/array. Fixed-size sequence, no heap allocation, inline storage.
  7. López Muñoz, J. M. (2022). Advancing the State of the Art for std::unordered_map Implementations. Overload 170, ACCU. accu.org. Why the standard interface (bucket API, pointer stability, user-set load factor) locks std::unordered_map into closed addressing, the node layouts and memory overhead of the major implementations, and what can still be optimized within that constraint.
  8. Facebook / Meta. FBVector — Folly C++ Library. github.com/facebook/folly. The 1.5× growth-factor argument (reuse after four reallocations), jemalloc cooperation, and relocation optimization. The actual push_back policy, 2× below jemalloc's in-place-expandable size and above 128 KB and 1.5× between, is in FBVector.h.
  9. Kulukundis, M. (2017). Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step. CppCon 2017. YouTube. The original public description of SwissTable: H1/H2 split, 16-wide SIMD groups, 1-byte control bytes. The talk abstract reports "2-3x better performance with significant memory reductions (compared to unordered_map)".
  10. Google. Abseil Swiss Tables and absl::Hash. abseil.io/blog/20180927-swisstables. Open-sourcing announcement and integration with Abseil's hash framework.
  11. Facebook / Meta. F14 Hash Table. github.com/facebook/folly. 14-key chunks, three storage variants (Value/Node/Vector), engineering announcement at engineering.fb.com.
  12. Bentley, M. Introduction of std::hive to the standard library. WG21 paper P0447R28 (2024). open-std.org/p0447r28; tracker at cplusplus/papers#328. The standardized bucket-array container, evolved from plf::colony; reference implementation at github.com/mattreecebentley/plf_hive. Adopted for C++26 at the February 2025 Hagenberg meeting.
  13. Hennessy, J. L., & Patterson, D. A. Computer Architecture: A Quantitative Approach, 6th ed. Morgan Kaufmann (2017). Background for the cache-hierarchy latency ratios in §3.
  14. Intel. Intel® 64 and IA-32 Architectures Optimization Reference Manual. intel.com. Chapter on memory hierarchy and the hardware prefetcher's pattern requirements.
  15. LLVM. llvm::SmallVector documentation. llvm.org. The best-known inline-buffer-with-heap-fallback vector.
  16. Stroustrup, B. (2013). The C++ Programming Language, 4th ed. Addison-Wesley. §31.6 (Advice), item 2: "Use vector as your default container."
  17. C++ Core Guidelines Working Group. SL.con.2: Prefer using STL vector by default unless you have a reason to use a different container. isocpp.github.io.
  18. GCC libstdc++. stl_vector.h source. github.com/gcc-mirror/gcc. Three-pointer layout (begin / end / end-of-storage); _M_check_len doubles the size on growth.
  19. cppreference. std::vector. en.cppreference.com/w/cpp/container/vector. Complexity table, iterator-invalidation rules, vector<bool> note.
  20. cppreference. std::unordered_map. en.cppreference.com/w/cpp/container/unordered_map. Bucket API, complexity, rehash and invalidation rules.
  21. cppreference. std::deque. en.cppreference.com/w/cpp/container/deque. Chunked-array implementation note, indexing complexity.
  22. Chen, R. (2023). Inside STL: The deque, implementation. The Old New Thing, Microsoft DevBlogs. devblogs.microsoft.com. Side-by-side description of the libstdc++, libc++, and MSVC deque layouts and chunk sizes.
  23. cppreference. std::list. en.cppreference.com/w/cpp/container/list. Doubly-linked layout, O(1) splice, reference-stability guarantee.
  24. Chen, R. (2023). Inside STL: The map, set, multimap, and multiset. The Old New Thing, Microsoft DevBlogs. devblogs.microsoft.com. "In practice, everybody seems to choose a red-black tree": the node layouts of the libstdc++, libc++, and MSVC associative containers.
  25. Aumasson, J.-P., & Bernstein, D. J. (2012). SipHash: a fast short-input PRF. aumasson.jp/siphash/siphash.pdf. The keyed hash that Rust, Python (3.4 and later) and Ruby adopted for their hash tables to resist hash flooding.
  26. Google. Swiss Tables Design Notes. abseil.io/about/design/swisstables. H1/H2 hash split, control-byte layout, SIMD match details.
  27. cppreference. std::priority_queue. en.cppreference.com/w/cpp/container/priority_queue. Binary-heap backing, O(log n) push/pop, no decrease-key.
  28. cppreference. std::span. en.cppreference.com/w/cpp/container/span. C++20 non-owning view, lifetime requirements.
  29. cppreference. std::map. en.cppreference.com/w/cpp/container/map. std::less<> transparent comparator details under C++14.
  30. Laine, Z. A Standard flat_map. WG21 paper P0429R9 (2022). open-std.org/p0429r9. The paper that brought std::flat_map and std::flat_multimap into C++23.
  31. Laine, Z. A Standard flat_set. WG21 paper P1222R4 (2022). wg21.link/p1222r4. The companion paper for std::flat_set and std::flat_multiset in C++23.
  32. Bentley, M. (2016). Colonies, performance and why you should care. CppCon 2016. YouTube. The first conference talk on plf::colony, the game-engine object-pool container that became std::hive.
  33. Celis, P. (1986). Robin Hood Hashing. University of Waterloo, tech report CS-86-14. cs.uwaterloo.ca. The open-addressing insertion rule that cuts probe-length variance; the conference version (with Larson and Munro) appeared at FOCS 1985.
  34. Stepanov, A., & Lee, M. (1995). The Standard Template Library. HP Labs Technical Report HPL-95-11. stepanovpapers.com. The original STL design document.
  35. Bronson, N., & Shi, X. (2019). Open-sourcing F14 for faster, more memory-efficient hash tables. Facebook Engineering. engineering.fb.com. Source for the 14-slot chunk ("filters 14 slots at once"), the 12/14 max load factor, and the 1-byte per-chunk overflow count that replaces tombstones. The F14 design markdown in the Folly repository (F14.md) gives the chunk-layout details (14 tag bytes + 2 metadata bytes = one 16-byte aligned block).

See also