Quant developer HFT course · Module 3: Containers and memory
Choosing a container by what it does in memory
The question
You need to keep the active orders for one instrument, look them up by id, and walk them in price order. Which containers would you use?
Start from the operations
Every container choice starts from the operations the hot path performs, how often each one happens, and how big the collection gets. For the active orders in the question:
- Look up an order by id: on every cancel, modify and fill.
- Walk orders in price order: on every match, or when building a market-data snapshot.
- Insert and remove: on every new order and every cancel.
- Size: hundreds to tens of thousands per instrument.
No single standard container does all three well, which is normal. Real designs combine a primary store with one or more indexes into it.
What each standard container is in memory
| Container | Layout | Good at | Costs |
|---|---|---|---|
std::vector | one contiguous array | scans, indexed access, push at the end | middle insert and erase shift elements; growth reallocates |
std::array | fixed array, no heap | known small sizes | fixed capacity |
std::deque | blocks plus a map of block pointers | push and pop at both ends without moving elements | indirection on every access |
std::list | separately allocated nodes, two links each | stable addresses, splicing | allocation per insert, pointer chasing |
std::map, std::set | red-black tree of nodes | ordered iteration, range queries | allocation per insert, a dependent load per level |
std::unordered_map | bucket array plus node chains | average O(1) lookup | allocation per insert, a chain walk per lookup, rehash spikes |
The rows that matter most for latency are the ones with "allocation per insert" and "pointer chasing" in them. They are not wrong, but they are the costs that the earlier lessons showed dominate a hot loop.
Flat alternatives
Most performance-sensitive code replaces the node-based containers with flat ones:
- A sorted vector in place of
std::mapfor small or rarely modified sets: binary search for lookup, contiguous iteration in order. C++23'sstd::flat_mappackages this. - An open-addressing hash map (Abseil
flat_hash_map,boost::unordered_flat_map, and many in-house tables) in place ofstd::unordered_map: keys and values in one array, no node allocation, a lookup that touches one or two cache lines. - An array indexed directly by key when keys are small dense integers, such as instrument ids mapped at start-up to
0..n-1, or price levels as offsets from a reference price.
Flat structures trade worse worst-case insertion for much better constant factors on the operations that dominate.
The answer, built up
For the order book in the question:
- Store the orders in a pool of fixed slots that never moves (Module 2, last lesson), so that everything else can refer to them by handle.
- Index by id with an open-addressing hash map from exchange order id to handle, reserved at start-up for the expected peak.
- Order by price with price levels in an array indexed by tick offset from a reference price, each level holding a FIFO of order handles in time priority. Prices near the touch are dense, so the array is mostly full where it matters; levels far away can fall back to a sorted structure.
Each piece uses flat memory, none allocates per order after start-up, and each operation is a small, predictable number of cache-line reads. Module 9 builds this book in detail.
How to say it
Name the operations, say which one dominates, choose the layout for that, and add an index for the rest. Mention the standard container you would start with if the sizes were small or the code were not on the hot path, and what you would measure before replacing it. An interviewer is more impressed by "std::map is fine here until profiling says otherwise" in the right place than by a custom structure everywhere.
Check yourself
Question 1 of 3
Which standard container gives O(log n) ordered lookup and stable element addresses?
A balanced tree gives logarithmic lookup and never moves its nodes. A sorted vector is also logarithmic and usually faster, but its elements move on insertion.
Question 2 of 3
Why do performance-sensitive codebases often replace std::unordered_map?
The standard's interface requirements push implementations towards separate chaining with nodes. Open-addressing tables keep entries in one array and avoid both the allocation and the pointer chase.
Question 3 of 3
Instrument ids from the exchange are arbitrary 32-bit numbers; there are 400 instruments. What is the fastest way to find the book for an instrument on every message?
A dense index makes the lookup an array access. The mapping from exchange id to index is built once, and can itself be a small hash table consulted per message, or avoided entirely if the feed carries a local index.
In the interview
Say your own answer out loud first, then open the one we would give.
How do you choose a container?
From the operations the hot path performs and how often: lookups, ordered walks, inserts and erases, and the expected size. Then by memory layout, because contiguous storage and no per-element allocation usually matter more than the Big-O difference between candidates. Often the answer is a primary store plus one or two indexes.
Why not just use std::map everywhere for ordered data?
It is correct and logarithmic, but each node is a separate allocation and each step down the tree is a dependent load. For small or read-mostly sets, a sorted vector or flat_map is usually faster; for price levels, an array indexed by tick offset is faster still.
What is a flat hash map?
An open-addressing table: keys and values stored directly in one array, with collisions resolved by probing nearby slots. Lookups touch one or two cache lines and inserts do not allocate nodes. The trade-off is that elements move on rehash, so pointers into it are not stable.