STL Container Performance

std::vector, std::map, and std::unordered_map all let you store a collection of things and get them back later, and it's tempting to treat them as interchangeable. They are not. Each one is built on a completely different underlying structure — a contiguous array, a balanced tree, a hash table — and that structural choice determines what's fast, what's slow, and how the data sits in memory relative to the CPU cache. In a low-latency system, picking std::map where std::vector would do is a routine way to leave an order of magnitude of speed on the table.

The core trade-offs

Container	Layout	Lookup	Insert (middle)	Cache friendliness
std::vector	Contiguous array	O(n) linear scan (O(1) by index)	O(n), shifts elements	Excellent — sequential memory
std::deque	Chunked array-of-arrays	O(1) by index	O(n) middle, O(1) ends	Good, but chunk boundaries hurt
std::map	Red-black tree	O(log n)	O(log n)	Poor — nodes scattered on heap
std::unordered_map	Hash table + buckets	O(1) average	O(1) average	Poor — buckets scattered on heap
std::list	Doubly linked list	O(n)	O(1) with an iterator	Very poor — every node a separate allocation

Worked example: why "faster" std::map can lose to std::vector

Suppose an order book needs to look up a price level among roughly 50 active levels, thousands of times per second. std::map gives $O(\log n)$ lookup — for 50 elements, about 6 comparisons. std::vector, scanned linearly, gives $O(n)$ — up to 50 comparisons in the worst case. On paper, std::map looks like the clear winner.

In practice, benchmark the two on real hardware and std::vector is often faster anyway, sometimes by 2-3x. The reason is memory layout: std::map's 50 nodes are scattered across the heap, so each of those 6 comparisons is likely a separate cache miss — a 100+ cycle wait for main memory. std::vector's 50 elements sit in one contiguous block; the CPU prefetcher pulls the whole block into cache in a handful of memory accesses, and the "worst case" 50 comparisons run almost entirely out of L1 cache at roughly one cycle each. Fewer, more expensive steps loses to more, cheaper steps.

What this means in practice

The rule of thumb in performance-sensitive C++ is: default to std::vector, and only reach for std::map or std::unordered_map when the collection is large enough (typically many thousands of elements) that the asymptotic gap actually overcomes the cache-miss penalty, or when you genuinely need ordered iteration or true O(1) hashed lookup at scale. std::list is rarely the right answer in latency-sensitive code at all — its per-node allocation and pointer-chasing access pattern is close to worst-case for a modern CPU's cache and prefetcher.