STL Container Choice
Module 2 taught how to write C++ that does not crash. Module 3 is about the next decision you make on every hot path, namely which container holds your data. You are keeping the live orders for AAPL. An incoming cancel names an order by its id, and you must find that order fast. Separately, you want to walk the orders from best price down to publish a quote. Finding by id wants one container; walking in price order wants another. No single container is best at both jobs.
Most engineers pick a container by its Big-O. That is the least useful axis. Every mature container gives you the headline complexity you expect: a hash map finds by key in average constant time, a tree finds in logarithmic time, a vector indexes in constant time. The differences that decide latency live underneath the Big-O, in how the container lays out memory and which operations move that memory around.
Three questions pick the container
The first question is the access pattern: how do you reach an element? If you reach it by position (the third one, the tenth one), you want random access by index, which std::vector and std::deque give in constant time. If you reach it by a key (the order with id == 90871), you want a map. If you always walk every element start to finish, any container can do it, but a contiguous one walks far faster, for reasons Module 1 made concrete. If you need to walk in sorted order, only an ordered container keeps that order for free.
The second question is the mutation pattern: where do you insert and erase, and must existing handles survive it? Appending at the end is cheap for a vector and a deque. Inserting in the middle is cheap only for a node-based container like std::list, where splicing a node touches two pointers and moves nothing. And as Module 2 showed, some mutations invalidate handles: a vector that grows relocates its whole buffer, so every pointer and index-free iterator into it goes stale. If you hold handles across mutations, stability is a hard requirement, not a nice-to-have.
The third question is memory behavior, and it is the one interviewers actually probe. A std::vector stores its elements in one contiguous block, so iterating it streams through cache lines and the CPU, seeing the steady forward march, fetches the next ones before you ask for them. A node-based container (std::list, std::map, std::set) allocates each element separately, so the nodes scatter across the heap and every step is a fresh pointer chase. A std::deque sits in between: it stores elements in fixed-size chunks, contiguous within a chunk and scattered between chunks. Same elements, very different cost to walk.
Container choice is an access-and-memory question, not a Big-O question.
Default to vector, then earn the exception
Because contiguous memory is the cheapest to walk and the simplest to reason about, the working default in latency-sensitive C++ is std::vector. You reach for something else only when one of the three questions forces it: you need keyed lookup (a map), you need stable handles across middle inserts (a list), you need cheap growth at both ends (a deque), or you need elements kept in sorted order (an ordered map or set). Each of those is a reason to pay for scattered memory. Absent a reason, the contiguous default wins.
Surprisingly often the fastest "map" is still a vector. If the keys are dense small integers, an array indexed by the key beats a hash map: no hashing, no buckets, no nodes, just data[key]. If the set is small and built once then searched many times, a sorted vector plus binary search beats a tree, because the binary search streams through contiguous memory while the tree chases pointers. The container that wins is the one whose memory layout matches how you touch it.
// Two jobs over the same AAPL orders, two containers.
// Job 1: find an order by id on every cancel. Keyed lookup -> hash map.
std::unordered_map<std::uint64_t, Order> by_id;
Order& o = by_id.at(cancel.order_id); // average O(1), scattered nodes
// Job 2: walk orders best-price first to publish a quote. Sorted -> ordered map.
std::map<std::int64_t, Order, std::greater<>> by_price;
for (auto& [price, order] : by_price) { /* ... */ } // sorted walk, pointer chase per node
// Job 3: append every print to a log and scan it. Sequential -> vector.
std::vector<Trade> tape;
tape.push_back(t); // contiguous, cache-friendly scan
The rest of this module opens up each of these containers and shows what is really inside. The next article goes inside std::vector's growth, the one after that inside std::unordered_map's buckets, then the node-based and segmented containers, then the memory resources that change where any of them allocate, the small-buffer trick that lets some of them avoid the heap entirely, and finally the templates that make all of them generic without a single virtual call.
"Which container would you use here, and why?" is one of the most common openers in a quant C++ interview, and the answer they want is this access-and-memory reasoning, not a recital of Big-O. The cppreference containers library lists every option and its complexity guarantees if you want the full menu.
Checkpoint
You hold 64 instrument records, built once at startup, and you look one up by a small integer instrument id millions of times in the hot path. Which container is the best default, and why?
In interviews
- "How do you choose an STL container?" → "By access pattern, mutation pattern, and memory behavior, not by Big-O. Most containers hit the headline complexity; the real difference is layout and which operations move memory."
- "What's your default container, and when do you move off it?" → "
std::vector. I move off it only when something forces me: keyed lookup, stable handles across middle inserts, growth at both ends, or sorted iteration." - "When is the fastest map not a map?" → "When keys are dense small integers, an array indexed by the key wins. When the set is small and search-heavy, a sorted vector with binary search beats a tree, because it stays contiguous."
Next we go inside the default itself: how std::vector grows, why the growth moves your objects, and what reserve really buys.