Choosing a Container

Part I · Module 19 · Chapter 19.7 · Choosing a Container

1. The Decision Path

The questions below are in a deliberate order. Each one eliminates candidates, and the earlier ones eliminate more, which is why asking them out of order produces worse answers.

Step 3 is the one that does the most work, and it is phrased as a presumption on purpose. The default is contiguous storage, and steps 4 through 6 exist to let you leave it — each for a reason you can name in a review. "I used a std::list because insertion is O(1)" is not one of those reasons, as Chapter 19.4 §6 measured; "I used a std::list because I hold pointers to elements and insert in the middle" is.

Step 7 is not a formality. §3 and §4 are what it looks like when you do it.

2. The Questions in Words

Keyed or positional? Does the code ask "the element with this key" or "the element at this position"? If a key, you are in the associative half of the library and vector is out unless §5's sorted-vector pattern applies. If a position, you are in the sequence half.

Does anything depend on order? This is the question that decides between the tree and the hash, and Chapter 19.5 §7 and Chapter 19.6 §6 measured both sides of it. Ordered iteration, range queries, nearest-key lookup, minimum or maximum: if any of those, std::map or std::set. If none, the unordered versions, which are several times faster at the lookup that remains.

Will a contiguous sequence do? Chapter 19.2 argued that the answer is almost always yes, and Chapter 19.8 §1 measures why it matters. Treat this as the default and require a reason to leave it.

Is the size a small compile-time constant? Then std::array: zero allocations, measured, and the length enforced by the type system.

Cheap insertion at both ends? Then std::deque, which is the only standard container offering it — four allocations for a thousand front insertions, against std::vector's O(n) per call.

Must references survive insertion? For a sequence, std::list. For keyed data, std::map, which gives iterator stability as well. This is a correctness requirement rather than a performance one, which is why it outranks everything below it.

Then measure. By this point there are rarely more than two candidates, and the difference between them is not usually predictable from the guarantees.

3. Validating the Path: Build Once, Query Many

Here is the first of three access patterns over identical data — 200,000 random integers, 200,000 random lookups. Three strategies: a std::set, a std::unordered_set, and a std::vector that is sorted once and then searched with std::binary_search.

Every figure is a median of nine timed repetitions after two warm-ups, with the full range reported. That is not ceremony: a single best-of-three was not reproducible between runs of the same binary, with one container's figure moving by nearly a factor of three, so a single number would have been an artefact rather than a measurement.

PATTERN 1: build once, then query many (200000 items, 200000 queries)
     set                        median   85.87 ms   range  73.67 - 103.62
     sort+unique+binary_search  median   19.36 ms   range  18.48 -  25.28
     unordered_set              median   18.40 ms   range  16.58 -  20.49

Two findings, and the second is the more useful one.

The tree loses badly — 4.7× the hash's median. std::set and the sorted std::vector both perform O(log n) comparisons per query, and the vector is more than four times faster. Chapter 19.8 §6 explains the mechanism; here it is enough to note that the complexity table ranked these two as equal and the measurement did not.

The vector and the hash are not separable. The vector's range is 18.48–25.28 ms and the hash's is 16.58–20.49 ms. Those overlap substantially. The medians differ by 5%, which is well inside the run-to-run variation of either. The honest conclusion is that this measurement does not distinguish them, and anyone reporting "the hash is 5% faster" from this data would be reporting noise.

That matters for the decision path, because it means at step 7 the tie-break has to come from somewhere else — and here it comes from memory. Chapter 19.8 §7 measures the same 100,000 entries at 4,000,000 bytes in a tree and 800,000 in a sorted vector, one allocation against 100,000. When the speed is indistinguishable, a fifth of the memory and one allocation is the deciding argument.

4. The Same Data, a Different Access Pattern

Now interleave the insertions with the queries — forty rounds, each adding a twentieth of the data and then running a twentieth of the queries. Nothing about the data changed; only when the queries happen.

PATTERN 2: queries INTERLEAVED with insertions
     set                        median   83.60 ms   range  73.03 - 136.51
     vector + re-sort/round     median  107.13 ms   range 104.90 - 116.86   <-- now it LOSES
     unordered_set              median   21.68 ms   range  19.51 -  27.09   <-- the HASH wins

The sorted vector has gone from indistinguishable-from-best to worst, and it is now slower than the tree it beat by 4.4× a moment ago. The reason is structural: std::binary_search requires sorted input, so every round that adds elements must re-sort before it can query, and the sort cost is paid forty times instead of once. The strategy that won Pattern 1 depended entirely on the sort being amortised over many queries, and Pattern 2 removes that.

Meanwhile the hash is essentially unaffected — 18.40 ms to 21.68 ms — because inserting into a hash table does not disturb any invariant that queries depend on. Its ranges in the two patterns overlap.

This is the result that justifies the decision path's shape. The containers did not change and the data did not change; the access pattern changed, and the ranking inverted. Choosing by complexity table cannot predict this, because the complexities are identical across the two patterns. Choosing by familiarity cannot predict it either. Only asking how the data is actually reached gets it right, which is why that is step 1 rather than step 7.

5. The Third Pattern: a Query Only One Container Can Answer

PATTERN 3: the query needs ORDER (a range)
     set: keys in [500000,500100] = 16, found by two O(log n) walks
     unordered_set: same answer = 16, but only by scanning all 181424 elements

Both found the same sixteen keys, so this is not a correctness difference. The tree located the range with two logarithmic descents and then walked sixteen elements. The hash table had no way to locate anything, so it examined every one of its 181,424 elements and tested each against the bounds.

There is no tuning that fixes this and no hash function that helps, because spreading keys uniformly is exactly what destroys the adjacency the query needs. This is the one place in the module where a container is not merely slower but unable, and it is why "does anything depend on order?" is step 2 and not a refinement at the end.

The sorted std::vector can answer it too, with std::lower_bound, which is the pattern §6 is about.

6. The Sorted Vector Is a Container Choice

It does not appear in §1's diagram because it is not a container type, but "a std::vector kept sorted" is one of the most useful shapes in the library and it deserves naming.

std::vector<std::pair<Key, Value>> table;
// build phase
for (auto&& row : source) table.emplace_back(row.key, row.value);
std::sort(table.begin(), table.end());
table.erase(std::unique(table.begin(), table.end()), table.end());

// query phase
auto it = std::lower_bound(table.begin(), table.end(), k,
            [](const auto& a, const Key& b){ return a.first < b; });
bool found = it != table.end() && it->first == k;

What it gives you: O(log n) lookup, ordered iteration, range queries via lower_bound/upper_bound, one allocation, and contiguous memory. That is std::map's entire feature set except iterator stability, for a fifth of the memory and measurably faster lookups.

What it costs: insertion after the build phase is O(n), so this works only when the data has a build phase and a query phase that do not interleave — exactly the condition Pattern 1 satisfied and Pattern 2 destroyed.

So the rule for reaching for it is precise: the data is built, then sorted once, then only queried. Configuration loaded at startup, a lookup table computed once, a static set of identifiers, a sorted index over data that does not change. When insertions continue throughout, use the real associative container.

7. The Selection Table

Read down the left column to find your requirement; the right column is the container, with the chapter that measured it.

8. Anti-Patterns

These are the choices this module measured as wrong, with the figure.

std::list because insertion is O(1). Measured about 4.4× slower than vector on find-then-insert, because the search dominates — Chapter 19.4 §6.

std::map for pure lookup. Measured 4.7× the hash in §3 and about 47× in Chapter 19.8 §6, with five times the memory.

std::unordered_map with a hand-rolled hash that was never checked. Measured up to 6,180× slower — Chapter 19.6 §4.

std::deque for many small containers. 4,104 bytes each — Chapter 19.4 §4.

std::vector with no reserve when the count is known. 15 allocations and 3.3× the bytes — Chapter 19.3 §4.

A sorted std::vector with continuing insertions. Measured 5.5× worse than itself in Pattern 2.

std::unordered_map when the code iterates to produce stable output. The order is arbitrary and changes on rehash — Chapter 19.6 §5.

std::map<K, V> reached with operator[] to ask questions. Measured inserting — Chapter 19.5 §3.

9. What the Path Does Not Decide

Three things fall outside it and are worth naming so they are not forced into it.

The element type. A std::vector<std::unique_ptr<T>> and a std::vector<T> have very different performance for the same container choice, because the first one is a vector of pointers to separately-allocated objects and traverses like Chapter 19.8 §4's scattered list. Chapter 14.7 §4's guidance on when the indirection is necessary applies before this chapter's path runs.

Whether a container is the right structure at all. Sometimes the answer is two parallel std::vectors, or a std::vector with an index built over it, or a bitset, or no container — a running total rather than a list of values to sum later.

Concurrency. None of the standard containers is thread-safe for mutation, and the choice of container does not change that. Concurrent read-only access is fine for all of them.

10. What to Actually Do

• Ask the questions in §1's order. Earlier questions eliminate more.
• Treat std::vector as the default and require a nameable reason to leave it.
• Let correctness requirements outrank performance ones. Reference stability is a yes-or-no fact; speed is a measurement.
• Use §5's test for the hash: can it answer a range query? If the code needs one, the hash is out absolutely.
• Use the sorted-vector pattern only when the build and query phases do not interleave.
• Measure the last two candidates on real data, with medians and ranges rather than one sample.
• When the ranges overlap, say so and break the tie on memory or allocation count.
• Re-run the decision when the access pattern changes. Pattern 2 was Pattern 1 with the queries moved.
• Write the reason down next to the declaration. A container choice with a named requirement survives review; one chosen by habit does not.

11. Mistakes Worth Making Once

Choosing from the complexity table. Two measurements in this module invert it.

Reporting a single timing run. One container's figure moved by nearly 3× between runs of the same binary; the median-of-nine with ranges is the minimum honest instrument.

Reporting a 5% difference as a result. §3's vector and hash differ by 5% with ranges that overlap across most of their width. That is noise with a decimal point on it.

Optimising the container before measuring the access pattern. Pattern 2 shows the pattern is the dominant variable.

Forgetting that the path has to be re-run. Code that gains an insertion in a loop may have invalidated its own container choice.

Treating "vector is the default" as "vector is always right." Steps 4 to 6 exist and each is measured.

12. Interview Relevance

The frozen curriculum marks this chapter Critical, and "how do you choose a container?" is one of the most common senior-level questions there is.

"How do you choose a container?" The answer that lands is a path, not a list of containers. Access pattern first, then order dependence, then the contiguity presumption, then the specific guarantees, then measure. Naming the order and saying why earlier questions matter more is the signal.

"map or unordered_map?" Does anything depend on order? If yes, map, and the discriminating detail is that a hash cannot answer a range query at all — measured as a 181,424-element scan. If no, unordered_map, several times faster.

"When is std::vector the wrong choice?" Cheap insertion at both ends, stable references under insertion, or a fixed small size where allocation is unwanted. Three nameable conditions.

"You need a lookup table built at startup and never modified. What do you use?" A sorted std::vector with std::lower_bound is the strong answer: map's feature set minus iterator stability, one allocation, a fifth of the memory, faster lookups. Quoting §3's measurement is better still.

"Two containers both look suitable. What now?" Measure both on representative data, medians with ranges. And the follow-up worth volunteering: if the ranges overlap, break the tie on memory or allocation count rather than inventing a winner.

"Have you ever chosen wrong?" The anti-patterns in §8 are all real and all measured. Having a specific one with a number attached is a far better answer than a generality.

13. What You Should Be Able to Say Now

• The seven questions in order, and why the order matters.
• That std::vector is the default and steps 4 to 6 are the named exits from it.
• That the same data and containers under three access patterns produced three different winners.
• That the sorted vector went from 19.36 ms to 107.13 ms purely because queries began interleaving with insertions.
• That in Pattern 1 the vector and hash were not separable, and what to break the tie on.
• That a hash cannot answer a range query at all — 181,424 elements scanned against two logarithmic descents.
• The condition for the sorted-vector pattern: a build phase and a query phase that do not interleave.
• That correctness requirements like reference stability outrank performance ones.

14. Exercises

Exercise 1 — run the path. For six designs from your own code, walk §1's path and record which step eliminated each candidate. Note any case where the path left more than two finalists.

Exercise 2 — reproduce Pattern 1. Build the three-way benchmark with medians and ranges. Report whether your vector and hash ranges overlap as ours did.

Exercise 3 — find the crossover. In Pattern 2, vary the number of rounds from 1 to 200 and find the round count at which the sorted vector stops beating and starts losing to the tree.

Exercise 4 — the honest report. Take two containers whose medians differ by under 10% and write the three-sentence conclusion you would put in a review. Then increase the data size until the difference exceeds the ranges, and write it again.

Exercise 5 — the sorted vector in full. Implement a SortedVectorMap with find, lower_bound, ordered iteration and a build() that sorts and uniques. Measure it against std::map on lookup, memory and allocation count.

Exercise 6 — the element type. Benchmark std::vector<Widget> against std::vector<std::unique_ptr<Widget>> on traversal for a 64-byte Widget. Relate the result to Chapter 19.8 §4.

Exercise 7 — the range query. Add a range query to Pattern 2's workload and re-run all three strategies. Show that it changes the winner again.

Exercise 8 — defend a choice. Write the one-sentence comment you would leave beside a std::list declaration that would survive review, and the one beside a std::deque.

15. Summary

• Choose from the access pattern, not from familiarity and not from the complexity table.
• The path is seven questions in order: keyed or positional; does order matter; will contiguous do; fixed small size; both ends; stable references; then measure.
• std::vector is the default and steps 4 to 6 are the named reasons to leave it.
• Measured, Pattern 1 (build once, query many): set 85.87 ms, sorted vector 19.36 ms, unordered_set 18.40 ms — the tree loses by 4.7×, and the vector and hash are not separable (ranges 18.48–25.28 against 16.58–20.49).
• Measured, Pattern 2 (interleaved): the sorted vector went to 107.13 ms — worst, and 5.5× its own Pattern 1 figure — because the sort no longer amortises. The hash barely moved.
• The ranking inverted with no change to the containers or the data, only to the access pattern.
• Measured, Pattern 3: a range query cost the hash a scan of all 181,424 elements against the tree's two logarithmic descents. This is an inability, not a slowdown.
• The sorted-vector pattern gives map's features minus iterator stability for one allocation — when build and query do not interleave.
• Report medians and ranges, and when ranges overlap, break the tie on memory rather than inventing a winner.

Every measurement in this chapter had the same shape: the container the complexity table preferred lost to one it ranked lower, or two containers with different complexities came out indistinguishable. That is not a coincidence and it is not a flaw in the notation — it is the notation working exactly as specified, on a model of cost that stopped matching hardware some decades ago. Chapter 19.8 is the explanation: what memory actually costs to touch, why a contiguous traversal is thirty times faster than a linked one on identical arithmetic, how much of that is the cache and how much is something else entirely, and the measurement that isolates the effect by comparing a container against itself.