Choosing the right container

Why this matters

Two programs that solve the same problem can differ by a factor of a thousand in speed, and the only difference may be the container. A search through a vector for each query can take minutes, while the same search through a set takes milliseconds. Interviewers watch for this choice closely. Often the "optimised" answer is not a clever trick. It is simply a better container, chosen because it makes the expensive operation cheap.

This lesson pulls the earlier four lessons into one decision method. You will learn to ask the right questions about a problem, to read the cost of each container from the table, and to justify your choice in one sentence. You will also see three designs that combine containers: a counting leaderboard, a fixed-size window with a deque, and an LRU cache that uses a list and a hash map together.

Ask three questions, then a fourth

Before you pick a container, ask these questions about the problem.

1. What will the program do most often: look things up by value or key, add and remove at the ends, or walk through the items in order?
2. Does the output need to be sorted, or does it need the smallest or largest item at any moment?
3. Can the same value appear twice, and does it matter?
4. How large is the input, and how many operations will run? A container that is slow only on rare operations is fine. One that is slow on the common operation is not.

The fourth question is the one beginners skip. An operation that costs O(n) is harmless when it runs ten times on ten items. It is a disaster when it runs a million times on a million items. Multiply the cost of each operation by the number of times it runs, and compare the totals.

Write your answers as a short sentence before you write any code. For example, "I need fast membership tests and no order, so an unordered set" is a good design note. It is also what a good interview answer sounds like.

The cost table

The table gathers the costs for all the containers you have met in this module. The first column is the lookup by value, which means finding an item by its content. The second and third columns show the cost of adding and removing items.

Read the table row by row for the containers you are comparing. The cell for "lookup by value" matters most in membership questions. The cell for "add" matters most when the program builds a large collection. Notice that the unordered rows are O(1) "on average", and the honest worst case is O(n). The sorted rows are O(log n) in every case.

Decision guide

The table below turns the questions into a choice. Find the row that matches your main operation, and check the reason in the last column.

A quick way to decide is to find the operation that runs the most times. If it is a lookup by key with no order needed, use a hash container. If it is a lookup with order or range questions, use a sorted container. If it is an add or remove at a known end, use a deque, stack or queue. Only then consider a vector, which is the default for everything else.

Worked example 1: a leaderboard of word counts

Here is a common task. Read a list of words, count how often each appears, then print the words from the most common to the least common, with ties in alphabetical order.

Counting is a lookup-and-update job, and order is needed only at the end. So the natural plan is an unordered_map for the counts, then a vector of the results, which is sorted once. The sort costs O(k log k) for k distinct words, which is small when k is much smaller than the number of words. The map gives O(1) updates, so counting costs O(n) for n words.

Type this into the Input box:

tea cup tea pot cup tea jar

The output is:

tea 3
cup 2
jar 1
pot 1

Trace the decisions. The words are counted in the hash map, one update per word. The map's order is arbitrary, so the program copies its entries into a vector and sorts that. The comparator puts the bigger count first, and for a tie it puts the alphabetically smaller word first. That gives jar before pot, both with count 1.

A learner might reach for a map here, which would give alphabetical order for free. That choice works, but it costs O(log k) per update instead of O(1), and the final order would still be by word, not by count. The counts need a sort either way. The choice of an unordered map for counting and a vector for ranking is the cheaper plan, and the reason is that the hot operation is the update.

Step through the animation to see the counts land in their buckets. The map does not care about the order of the words, and that is exactly what makes it fast.

Worked example 2: an LRU cache

A cache is a small store that keeps recently used results so that they can be reused quickly. An LRU cache keeps at most a fixed number of items. When it is full and a new item arrives, it throws out the least recently used item, which is the one nobody has touched for the longest time. Both a lookup and an update must be fast, and the design needs two containers that work together.

The design is as follows:

• A hash map from each key to a position in the usage list. This gives O(1) lookup of a key.
• A doubly linked list of the stored items, ordered from most recently used at the front to least recently used at the back. A list can move any item to the front in O(1) when you hold its position, and it can remove the back item in O(1).

When you use a key, you find it in the map, move its node to the front of the list, and return the value. When you store a new key while the cache is full, you remove the back node and erase its key from the map. The map finds the item quickly, and the list keeps the order cheaply. Neither container alone can do both jobs in O(1). A vector would make the move O(n), and a map alone cannot tell which key is oldest.

The diagram below is the same idea as a picture. The list holds the order, and the map is a shortcut into the list.

The program below reads a capacity, a number of operations, and then the operations. A P key value line stores a value. A G key line prints the value, or -1 when the key is missing. Type this into the Input box:

2
8
P 1 10
P 2 20
G 1
P 3 30
G 2
P 4 40
G 1
G 3

The output is:

10
-1
-1
30

Trace the first four operations. P 1 10 stores key 1 at the front, so the list reads 1. P 2 20 puts key 2 at the front, so the list reads 2 1. G 1 finds key 1 through the map and moves it to the front, so the list reads 1 2 and the answer is 10. P 3 30 finds that the cache is full, so it removes the back item, key 2, and puts key 3 at the front: 3 1. G 2 finds nothing, because key 2 was evicted, and prints -1. P 4 40 evicts the back item, key 1, so the list is 4 3. G 1 prints -1, because key 1 is gone. The last G 3 finds key 3 and prints 30.

The splice call is the key trick. splice moves a node from one place in a list to another without copying the value and without shifting other nodes. The map keeps an iterator to each node, so the program can reach the node in O(1). Without the iterator stored in the map, finding the node would mean walking the list, which costs O(n).

Worked example 3: the largest value in each window

A sliding window is a block of k consecutive values that moves one step at a time along a sequence. A common question asks for the largest value in each window. The naive method scans each window in full, which costs O(n times k). The better method uses a deque that holds indexes of values in decreasing order. The front of the deque is always the index of the largest value in the current window.

The rule is simple. When a new value arrives, remove from the back every index whose value is smaller than or equal to the new value, because the new value is larger and will stay in the window longer. Then add the new index at the back. Before reading the front, remove any index that has slipped out of the window from the front. Each index enters and leaves the deque at most once, so the whole job costs O(n).

Type this into the Input box. The first line holds n and k, and the second line holds the numbers.

8 3
1 3 -1 -3 5 3 6 7

The output is:

3 3 5 5 6 7

Trace the first window, 1 3 -1. The index 0 goes in. The value 3 arrives at index 1, and the back holds index 0 with value 1, which is smaller, so it leaves. The deque holds index 1. The value -1 at index 2 joins at the back, so the deque is indexes 1 and 2. The front is index 1, with value 3, which is the answer for the first window.

Now the window moves on. At index 4, the value is 5. The front, index 1, has fallen out of the window of size 3, because the window now covers indexes 2, 3 and 4. So the first pop removes it. The back values, -3 and -1, are smaller than 5, so they leave too. The deque holds only index 4, and the answer is 5.

The deque never holds more than k indexes, and its values decrease from front to back. That is why the front is always the maximum. The choice of a deque is the point: the removal at the front and the removal at the back are both O(1), while a vector would need O(k) work to remove the front.

Worked example 4: a duplicate within distance k

A different question asks whether any value appears twice within k positions of itself. The clean solution keeps a set of the last k values. Before inserting the new value, check whether the set already holds it. If it does, a duplicate exists within the distance. When the set grows past k values, remove the value that just left the window.

The set is the right tool because the question is membership, and it has no order to keep. An unordered set would also work, with O(1) average cost. This program uses a set, which keeps the cost at O(log k) per step and never degrades on unlucky inputs. Both choices are defensible, and an interviewer will accept either if you explain why.

Type this into the Input box:

7 3
1 2 3 1 5 2 6

The output is:

YES at index 3

Trace the first four values. The set takes 1, 2 and 3. At index 3 the value is 1 again, and the set still holds it, so the program reports a duplicate at index 3. The distance between the two 1s is 3, which is equal to k, so the rule "within k positions" is satisfied.

The erase line keeps the set small. When the set has more than k values, the value at index i - k has left the window, so the program removes it. That only works because the program stops at the first duplicate: while it runs, every value in the set is different from the others, so removing a[i - k] never removes a copy that is still needed.

Worked example 5: values in both lists

The last example asks which values appear in both of two lists, with each value printed once in sorted order. The natural solution builds a set from the first list, then checks each value of the second list against it, collecting the matches into a second set. The second set removes repeats and sorts the output for free.

Type this into the Input box. The first list has five values, the second list has four.

5
4 9 5 9 1
4
9 4 9 8

The output is:

4 9 
common count 2

The first set holds 1, 4, 5 and 9. The values of the second list are checked one at a time. The 9 is in the first set, so it joins common. The 4 is too. The second 9 is found again, but common keeps one copy. The 8 is not in the first set, so it is skipped. The final set is 4 and 9, which prints in sorted order.

An alternative sorts both lists and walks them together with two pointers, as lesson four showed. That costs O(n log n + m log m), which is slower than the set version for most inputs, but it needs no extra memory beyond the sorted copies. Both are good answers. Name the trade-off when you give one.

Trade-offs to remember

A cost table tells you the big picture, but a few practical effects change the real speed.

• A vector often beats a list even for insertions in the middle. Items in a vector sit side by side, so the processor reads them quickly. Items in a list are scattered, and each step may miss the cache. Use the list only when splicing or holding many iterators is the main job.
• Hashed containers are fast on average. Their worst case is O(n) when many keys collide, and that can happen with a poor hash function or with adversarial input. Sorted containers give a steady O(log n), which is why some designs choose them for safety.
• Hashed containers need extra memory for their buckets, and they grow in large steps. A set or map uses memory for each node. A vector uses the least memory per item, because it stores values in one block.
• A sorted container can answer questions that a hashed one cannot, such as "the first value at least x" or "all values between a and b". If the problem asks for such a question, the hashed container is not an option, however fast it is.

When two choices look equally good on paper, measure. Write both versions, run them on a large input that looks like the real one, and time them with the chrono library. Do not measure a tiny input. The costs only show themselves when n is big enough.

What happens inside: the two halves of an LRU cache

The LRU cache relies on a fact about iterators that you met in lesson one. A list iterator stays valid when other nodes change, unless its own node is erased. That is why the map can store a list iterator for each key, and why the list can move nodes around without invalidating the map's entries. The map's stored iterator is the bridge between the two halves. When a node moves to the front, the iterator still points at the same node, so the map does not change.

When the cache evicts, the order matters. The program first erases the key from the map, while the back node is still valid, because it reads items.back().first to know which key to remove. Then it removes the node from the list. Swapping those two steps would read a removed node, which is undefined behaviour.

Designing with a scenario

Here is a realistic design question. A chat application shows a list of online users. Users join and leave all the time. The app checks whether one particular user is online many times per second, to decide whether to show a green dot. The sidebar lists the online names in alphabetical order, but the sidebar is redrawn only a few times per minute. Which containers should the app use?

Start with the questions from the top of this lesson. The most common operation is the membership check, which runs many times per second. Joins and leaves are also frequent, but each is a single change. Order matters only for the sidebar, and the sidebar is rare. That tells you where the cost sits.

The plan that fits is an unordered_set of online names. Membership checks and joins and leaves are all O(1) on average, so the frequent work is cheap. When the sidebar must be drawn, copy the names into a vector and sort them. That costs O(u log u) for u online users, which is paid only a few times per minute. The sorted copy is not kept, so no order has to be maintained on every change.

A plausible wrong plan is a single set for everything. It gives sorted order for free, and it is correct. But each membership check and each join costs O(log u) instead of O(1), and the frequent work is now slower. The set is a good choice when the sidebar is redrawn on every change, because then the sorting cost is paid anyway. Here it is not.

Write the decision down in one sentence, as the module asks: "Membership is the hot path and the sidebar is rare, so I use an unordered set and sort a copy when drawing." That sentence names the operation, the container, the cost and the reason. It also says why the other plan was rejected, which is the part interviewers listen for most.

When a hash table is risky

The average O(1) cost of a hash table depends on the keys spreading out over the buckets. If many keys share a bucket, a lookup must check them one by one, and the cost slides towards O(n). A hash function that is predictable can be targeted on purpose, with input chosen so that every key lands in the same bucket. Competitive programmers meet this when a problem setter writes tests against a known hash, and servers that accept keys from strangers have to think about it too.

What should you do? For learning and for most internal programs, the standard hash is fine, and you should use the hashed container. For an input that an outsider controls, a sorted container removes the risk, because its cost is O(log n) on every input. A set or a map guarantees that, whatever the keys are. If you must use a hash table with untrusted keys, pick a hash function that is seeded at random when the program starts, so an attacker cannot predict the buckets.

This risk is one more reason to name the worst case when you justify a choice. "O(1) on average" is true and useful. But an answer that ends at the average, with no mention of when the average fails, is only half an answer.

Interview view: how to justify a container

A good answer has three parts. Name the main operation. Name the container. Give the cost and the reason. For example:

"The main operation is checking whether a value has been seen, and order does not matter. So I use an unordered_set. Each check is O(1) on average, so the whole scan is O(n). The worst case is O(n squared) if every value collides, which is rare with the standard hash, and a set would give O(n log n) with no such risk."

That answer names the operation, names the choice, gives the average and worst cases, and states the alternative. Interviewers value the last part most, because it shows you chose on purpose.

Common mistakes and the messages you will see

Mistake 1: indexing a list. A learner writes l[2] on a list, and the compiler stops with:

error: no match for 'operator[]' (operand types are 'std::__cxx11::list<int>' and 'int')

The fix is to pick a vector, or to step with an iterator. Choosing the right container removes the need for the index in the first place.

Mistake 2: a hash key with no hash. A learner uses a pair as the key of an unordered_map. The compiler reports a static assertion about the hash function, followed by errors about a deleted default constructor. The message is long, but the cause is the missing hash for pair. Either write a small hash struct, or choose a map, which compares pairs with < and needs no hash.

Mistake 3: iterating a queue as if it were a container of values. A learner writes for (int x : q) on a queue, and gets a message about begin not being found. Queues and stacks hide their items on purpose. Pop them in a loop instead.

Mistake 4: picking a list for speed. A learner says "inserting in the middle is O(1), so a list is faster". The insert is O(1) only after the position is known, and finding the position costs O(n). The whole job is still O(n), and the list is often slower than a vector in practice, because of scattered memory.

Mistake 5: a map for a membership check in a loop. A learner keeps a vector and calls find for each value in a loop. The total cost is O(n squared). The fix is a set or an unordered set, which turns each check into O(log n) or O(1) on average.

Mistake 6: reading an empty container. Calling front() on an empty deque, or top() on an empty stack, is undefined behaviour. The program may print garbage or crash later. Check empty() first.

Debugging walkthrough: an LRU that forgets to refresh on get

A learner writes an LRU cache, but the get function does not move the node to the front. The test below uses a capacity of 2. The learner expects G 1 to print 10 after the key 1 was read recently.

Work through the trace.

1. P 1 10 puts key 1 in the list: 1.
2. P 2 20 puts key 2 at the front: 2 1.
3. G 1 finds key 1 and returns 10, but the buggy get does not move it. The list is still 2 1.
4. P 3 30 finds the cache full. It evicts the back node, which is key 1, because nothing moved it. The list is 3 2.
5. G 1 now finds nothing and prints -1. The correct answer is 10 in a real LRU, because key 1 was used most recently at step 3, so key 2 should have been evicted instead.

The fix is one line: after a successful get, call items.splice(items.begin(), items, it->second), exactly as the working version does. The lesson is that a cache has two rules, and the second one, refreshing on read, is the one that is easiest to forget. Trace a small case by hand, writing the list after every operation, and the missing refresh shows itself at once.

Variations and edge cases

A few details change the answer for beginners.

• An LRU with capacity 0 must store nothing. The code above assumes capacity of at least 1, and a learner should check the constraints before writing the eviction branch.
• A put on an existing key updates the value and refreshes its place, but it does not change the size, so it should not evict anything. The working code returns early for that case.
• A get on a key that was evicted returns -1, and it does not restore the key. Eviction is final.
• In the sliding window, a window size larger than the input has no complete windows, so the program prints nothing. Check whether the problem wants an empty line in that case.
• In the duplicate check, a value that repeats exactly k positions apart counts as within distance k. A value that repeats k plus one positions apart does not.

Practice

The solutions are hidden below each exercise. Try each one before you open it.

1. For each case, name the container: an undo history, a leaderboard sorted by score, a dictionary of word to meaning, a to-do list processed in order. Give one word for each: stack, priority_queue or map, unordered_map or map, and queue.

2. Find the first character that appears twice in a string, using the right container. Input abcbd prints b. Input abc prints none.

unordered_set<char> seen;
string s = "abcbd";
char found = 0;
for (char c : s) {
    if (seen.count(c)) { found = c; break; }
    seen.insert(c);
}
cout << (found ? string(1, found) : string("none")) << endl;

3. Merge two sorted vectors into a set to get their sorted union without duplicates. Input {1, 4, 6} and {2, 4, 9}. Expected output: 1 2 4 6 9.

vector<int> a = {1, 4, 6}, b = {2, 4, 9};
set<int> u(a.begin(), a.end());
u.insert(b.begin(), b.end());
for (int x : u) cout << x << " ";
cout << endl;

4. Count the number of values in an unsorted vector that are between 10 and 20, inclusive, for many queries. Explain in two sentences which container you would build first and why.

5. Two steps: a vector holds {7, 7, 3}. Build a set from it, then insert 3 and 9. Print the size. Expected output: 3.

vector<int> v = {7, 7, 3};
set<int> s(v.begin(), v.end());
s.insert(3);
s.insert(9);
cout << s.size() << endl;

6. Explain why an unordered_map is fine for counting word frequencies, but a map is the better choice when the output must list the words alphabetically and you want no extra sort. Give three or four sentences.

7. Debug this. A learner counts the number of distinct values in a vector with set<int> s; for (int x : v) s.insert(x); cout << s.size();, but expects the count to be 4 for {1, 2, 2, 3, 4, 4}. The output is 4, so the code is right. Explain what the learner might have got wrong, and show the correct count of duplicates instead, which is 2.

8. Find the longest run of consecutive values in {9, 1, 4, 7, 3, 8, 2}. Use a set and print the length. Expected output: 4, for the run 1, 2, 3, 4.

unordered_set<int> present = {9, 1, 4, 7, 3, 8, 2};
int best = 0;
for (int x : present) {
    if (present.count(x - 1)) continue;
    int len = 1;
    while (present.count(x + len)) len++;
    best = max(best, len);
}
cout << best << endl;

9. Given the LRU code from the worked example, trace P 1 1, P 2 2, G 1, P 3 3, G 2. Write down the printed values for the two G operations. Expected output: 1 then -1.

10. Explain in three or four sentences why the sliding-window deque keeps the indexes in decreasing order of value, and why the front is always the answer for the current window.

11. Two steps: a priority_queue holds 2, 8, 5. Pop one value, push 9, then print the top. Expected output: 9.

priority_queue<int> pq;
pq.push(2); pq.push(8); pq.push(5);
pq.pop();
pq.push(9);
cout << pq.top() << endl;

What you now know

• Ask what the program does most often, whether order or the extremes matter, whether duplicates matter, and how large the input is.
• Multiply each operation's cost by how often it runs. The hot operation decides the container.
• Use unordered_map or unordered_set for fast lookups without order, map or set when order or range questions matter, a deque for both ends, and a stack or queue for their jobs.
• Combine containers when one cannot do both jobs: an LRU cache uses a list for order and a hash map for lookup.
• Justify every choice in one sentence that names the operation, the container, the cost and the alternative.

What this module covered

• Sequence containers: vector (the default), deque (both ends), list (cheap splice), and pair for two values.
• Adaptors: stack (last in, first out), queue (first in, first out), priority_queue (largest first, a heap).
• set and map are sorted and O(log n); unordered_set and unordered_map are hashed and O(1) on average.
• Iterators mark positions, and ranges are [begin, end).
• Algorithms: sort, binary_search, lower_bound, upper_bound, next_permutation, unique and more.
• Pick the container from the operations you need most, and check the choice with the cost argument.