C++ Containers

01Why a container choice is a performance decision

Big-O describes how a data structure scales, 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 widget below makes that visible. 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 cache miss on most accesses:

The framing for the rest of the tutorial

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

• Where do the elements live? One contiguous block (vector, array), several contiguous blocks (deque, hive), or one independent heap allocation per element (list, map, unordered_map, the node-based containers)?
• How are they ordered? Insertion order (vector, deque, list), sorted by key (map, set), or hashed (unordered_map, unordered_set)?
• Which operations does the container want to be fast? Random index, find-by-key, push at the back, push anywhere, ordered iteration.
• Which references survive which mutations? A pointer into a vector can become invalid on the next push_back; a pointer into a list survives every mutation that doesn't touch that specific node. Engine code that holds long-lived handles depends on knowing this exactly. The rules for when this happens are called iterator invalidation (§7).

02A short history of getting containers right

The C++ standard library's container set didn't arrive fully formed in 1998. Its later additions are mostly answers to "this is faster on real hardware" arguments, made first by library authors and adopted by the committee years later. The modern set makes more sense with that history in view:

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. By C++26 the standard has closed the sorted-associative and bucket-array gaps (flat_map, hive). The hash table is the conspicuous remainder: std::unordered_map is still bound by its C++11 interface, while the open-addressing tables outside std report 2-3× better performance^[9]. The original containers are still the right default for most code. The rest of this tutorial 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

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 for memory:

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.

This is the central fact behind every container choice in the rest of the tutorial. 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.)

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

The smallest, simplest container. A thin wrapper around a C-style array, sized at compile time, no heap allocation, all 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.

// 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];.

05std::vector: the workhorse

The default. 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.

The four guarantees that matter

• Constant-time random access. v[i] is one pointer add, one load.
• Amortized constant-time push_back. When there's capacity, push_back is one construction plus one increment. When capacity runs out, the vector grows by a constant factor (2× or 1.5×, depending on the library) and reallocates. The amortized cost is O(1) regardless^[19].
• Linear-time insert/erase in the middle. Every element after the insertion point has to be shifted by one slot. For trivially copyable elements the library typically does this with one memmove, which runs at close to memory bandwidth; other types are moved one element at a time.
• Contiguous storage, guaranteed. &v[0], v.data(), and v.begin() all point at the same single block. You can pass v.data() to OpenGL, to memcpy, to ::write(). std::vector<bool> is the famous exception (see §20).

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

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):

For N a power of two, starting from capacity 1. Geometric growth turns N pushes into about 2N total work, which is O(N) and gives O(1) amortized per push. The word amortized matters: any individual push that triggers a reallocation is O(size), not O(1). Code that needs a hard real-time bound on a single push has to call reserve() first.

Why 1.5× sometimes beats 2×

Set the growth factor to r and call the initial capacity 1. After k growths the live block holds r^k units, and the blocks freed so far sum to 1 + r + r² + … + r^k−1 = (r^k − 1) / (r − 1). The next growth needs r^k+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 r^k+1 ≤ (r^k − 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, so the allocator can hand the previously freed addresses back (at 1.5×, after four reallocations); 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:

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

Every container has a set of "things that, if you do them, will invalidate some references into the container." 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:

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.

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.

08std::deque: chunked, two-ended

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]:

• libstdc++: 512-byte chunks. For deque<int>, 128 elements per chunk; for elements of 512 bytes or more, one element per chunk.
• libc++: 4096-byte chunks when the element is smaller than 256 bytes; a fixed 16 elements per chunk above that.
• MSVC: 16-byte chunks, so the element count shrinks with element size: 16 elements for 1-byte elements, 8 for 2-byte, 4 for 4-byte (so deque<int> has chunks of 4), 2 for 8-byte, and one element per chunk for anything larger than 8 bytes. That last regime has the poor cache behavior: a deque of any reasonably sized struct on MSVC is about one heap allocation per element. The chunk size is part of MSVC's ABI, so it can only change at an ABI break.

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.

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:

• Single-threaded work queues where new work goes on one end and gets processed from the other (a shared queue across threads needs a lock or a concurrent design).
• Event histories where new events go on the back and stale ones get popped off the front.
• The default backing store of std::queue and std::stack. queue<T> is just queue<T, deque<T>>.

09std::list and std::forward_list

A doubly-linked list. Each element lives in its own heap allocation, plus two pointers (prev and next). 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:

• Per-node allocation. Each push_back on a list<int> calls the allocator. A 2×-growth vector calls it about log2(N) times.
• Per-node memory overhead. On libstdc++ x86-64, a list<int> node struct is 24 bytes (8-byte prev, 8-byte next, 4-byte int, 4 bytes of padding). glibc's malloc serves a 24-byte request from a 32-byte chunk (the extra 8 bytes are its size header), so each 4-byte int costs 32 bytes of heap: 8× the payload, before any fragmentation.
• No random access. l[i] doesn't compile; you walk from begin().

The next section measures the gap directly.

10List vs vector, measured

Stroustrup's Going Native 2012 benchmark^[1]: 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.

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 L3 show the order-of-magnitude gap:

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

std::map<K, V> is a sorted, balanced binary search tree from keys to values. 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.

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

A hash table. Average-constant-time lookup, insert, and erase; worst-case linear when many keys collide. 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.

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. Hash flooding 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

Most high-performance hash tables outside the standard library use open addressing: no separate buckets, every entry stored inline in one flat array, and collisions resolved by probing other slots. 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 SIMD tricks. 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:

• The table is one flat array of {key, value} slots plus a parallel array of 1-byte control bytes, one per slot. The control bytes are stored together, separate from the slots, so 16 of them can be loaded at once.
• The hash is split in two: H1 picks the starting position, and H2, 7 bits, goes in the slot's control byte for fast filtering^[26]. Seven bits leaves the eighth for tagging the special states (empty, deleted, sentinel), and one byte per slot means 16 control bytes fill one 128-bit SSE register.
• On x86 with SSE2, lookup loads 16 consecutive control bytes (a group) into one register and runs one _mm_cmpeq_epi8 against the H2 being searched for; _mm_movemask_epi8 turns the result into a 16-bit mask of candidate positions^[9]. Abseil uses 8-wide groups elsewhere: 64-bit NEON operations on little-endian AArch64, and plain 64-bit integer bit tricks as the portable fallback.
• Each candidate gets a full key comparison. If none matches and the group has an empty slot, the key is absent; otherwise the probe moves to the next group. Most lookups read one group of control bytes and one slot.

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:

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

Three thin wrappers, each constraining an underlying container to a specific access pattern:

• std::stack<T>. LIFO. Defaults to std::deque<T> underneath, but any container with back(), push_back(), and pop_back() works. Pass std::vector<T> as the second template argument and you get a vector-backed stack with no deque overhead.
• std::queue<T>. FIFO. Defaults to std::deque<T> underneath. A vector won't work (it has no pop_front, so queue::pop won't compile); a std::list works but is slower than the deque default.
• std::priority_queue<T>. The largest element (by the comparator, std::less by default) is always on top. Defaults to a std::vector<T> arranged as a binary heap by the standard heap algorithms^[27].

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; pop takes the root, moves the last element to the root, and sifts down.

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:

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)});
}

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

Two additions, std::string_view (C++17) and std::span (C++20), that 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].

• std::span<T> (C++20). A view of a contiguous range of T. Construct it from a std::vector<T>, a std::array<T, N>, a C array, anything contiguous. The function on the other side gets a uniform interface to all of them.
• std::string_view (C++17). The same idea, specialized for character ranges. Has the methods that make string handling pleasant (find, substr, starts_with, ends_with) without owning the bytes.

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:

// 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

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

The standard's container set is the default, not the ceiling. A short tour of the non-std containers most game engines pick up:

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].

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

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]:

• Memory budget. Each subsystem gets a fixed pool. The renderer's containers allocate out of the renderer's pool; the AI's out of the AI's. Out-of-memory is a budget violation that's tractable to debug, not a process-wide crash.
• Frame allocators. A linear arena that resets at the start of each frame. Allocating from it is a pointer bump plus an alignment round-up; freeing is a no-op until the frame ends. Per-frame container allocations cost almost nothing once containers draw from it.
• Alignment. SSE/AVX/NEON vector types want 16- or 32-byte alignment. malloc guarantees 16 bytes on 64-bit glibc, Windows, and macOS (8 bytes on 32-bit Windows), which is not enough for a 32-byte-aligned AVX type like __m256. Since C++17, std::allocator routes over-aligned element types through aligned operator new, so std::vector<__m256> is safe on a conforming toolchain. Engine allocators that forward to plain malloc, and any codebase still on C++14, have to supply the over-alignment themselves before putting __m256 or any alignas(32) struct in a container.

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.

// 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

The widget below 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:

19The decision cheat sheet

A one-page summary, organized by the question you're actually asking when you reach for a container:

20The container pitfalls list

Common mistakes, organized by the container that produces them:

vector pitfalls

• vector<bool> is not a container of bool. The standard permits a packed representation (one bit per element) and explicitly carves out the contiguous-storage and ordinary-reference guarantees so implementations can pack; every shipping implementation does. operator[] returns a proxy, &v[0] isn't a bool*, and the type doesn't satisfy the normal sequence-container requirements^[19]. Use std::vector<char> or std::vector<std::uint8_t> when you need real bools in contiguous memory, or std::bitset when the size is fixed.
• Iterators held across push_back can dangle. Any push that reallocates invalidates every iterator, pointer and reference, and every push invalidates end(). This is one of the most common invalidation bugs. Hold an index instead, or reserve() enough capacity up front.
• shrink_to_fit() is a non-binding request. It is allowed to do nothing (the major implementations do honor it). To force the issue, swap with a right-sized copy, std::vector<T>(v.begin(), v.end()).swap(v), or with an empty vector, std::vector<T>().swap(v), to release everything.

deque pitfalls

• MSVC's deque collapses to one element per chunk for any element larger than 8 bytes. A deque<MyStruct> on MSVC costs about one heap allocation per element, with the cache misses that implies. libstdc++ and libc++ size chunks in bytes (512 and 4096 respectively), so their chunks hold many elements until elements get large^[22].
• Iteration has a per-chunk cost. Each increment checks for the end of the current chunk; within a chunk the branch is predictable, but each chunk transition typically costs a branch mispredict plus a load through the map. For hot inner loops that run many times over the same data, a vector is faster.

list pitfalls

• It is rarely the right answer. Reach for it only when you have a real splice or reference-stability requirement. See §10.
• size() could be O(n) before C++11. C++03 only said it "should" be constant time, and libstdc++'s was linear so that splicing a range stayed O(1). C++11 requires O(1) size(), which makes range splice between two lists O(n) instead. libstdc++ built with its old ABI (_GLIBCXX_USE_CXX11_ABI=0) still has the linear size().

map pitfalls

• m[key] default-constructs the value if the key isn't present and writes the new entry. A "lookup" that mutates the map. Use find or contains (C++20) for "is it there?" checks.
• String-keyed lookups can build a temporary string. With the default comparator, m.find("foo") on a map<std::string, V> constructs a temporary std::string, which allocates when the key is longer than the string's inline (SSO) buffer. Since C++14, declaring the map with std::less<> makes the comparator transparent, and find compares against the const char* directly^[29].

unordered_map pitfalls

• The default integer hash is the identity on libstdc++ and libc++. Their prime bucket counts make that work, but code that reuses std::hash in its own power-of-two table (or moves to one) keeps only the low bits, so keys that share their low bits (aligned pointers, IDs in steps of 256) collide. Mix the hash first, or use a hasher that does. MSVC's std::hash for integers already mixes (FNV-1a over the bytes).
• Insertion may rehash, which invalidates all iterators (but not pointers/references). Code that inserts in a loop with iterators outstanding has to call reserve() first, just like vector^[20].
• It is usually the slowest hash table available. If a hash table shows up in your profile, swap in absl::flat_hash_map, boost::unordered_flat_map or folly::F14FastMap. The interface is source-compatible enough for most call sites, but the invalidation rules differ: flat storage means a rehash invalidates pointers and references too, not just iterators. Check your reference-holding code before swapping, or use a node-based variant such as absl::node_hash_map.

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.

Past this tutorial:

• The C++ memory model tutorial covers the atomics and orderings that concurrent containers depend on. Bounded lock-free queues are usually ring buffers built on those orderings.
• The job-systems tutorial uses work-stealing deques. They share std::deque's two-ended interface but are usually built on a circular array (the Chase-Lev design): the owning thread pushes and pops at one end while thieves take from the other, which keeps most operations free of contention.
• The Abseil hash containers (flat_hash_map, node_hash_map), boost::unordered_flat_map and Folly's F14 are widely used open-addressing implementations. The F14 design doc lays out the trade-offs between its storage variants^[11].
• For production game-engine practice, EASTL's source is worth reading: it reimplements the standard containers around a simpler allocator model and adds fixed-storage and intrusive variants^[5].

22Sources & further reading

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

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).