map and set (ordered)

Why this matters

A hash table answers "is this key here?" very quickly, but it cannot answer "what is the first time after 9:30?" or "how many prices fall between 100 and 200?". Those questions depend on order, and a hash table has none. C++ gives you two containers that keep their keys sorted: map for keys with values, and set for keys alone. They are slower per operation than the hash versions, but they answer the order questions directly. Interviewers ask about these questions often, so this lesson covers them in depth.

The idea: keys that stay sorted

A map<K, V> keeps its pairs sorted by key. A set<T> keeps its values sorted. Every time you insert, the container finds the right place for the new key, so the order is always correct. When you loop over the container, you see the keys from smallest to largest, no matter what order you inserted them in.

Think of a printed dictionary. You can look up a word quickly by flipping to its first letter, and you can also read the next word alphabetically without any search. The sorted container gives you both abilities. A hash table is closer to a filing box where each card is placed by a code. You can find a card fast, but the box has no sense of which card comes next.

Inside, a sorted container is a balanced binary search tree. Each node holds one key. Keys smaller than a node sit in its left subtree, and keys larger sit in its right subtree. "Balanced" means the tree never grows lopsided, so its height stays close to log n. The standard library does not specify the tree type, but the common implementations use a red-black tree, which is a balanced tree with a color stored in each node. You will see the picture in the tree section below.

Because the height is about log n, each insert, find and erase walks down one path of about log n nodes. For a million keys, log n is about 20. That is why these operations are called O(log n). The growth is slow, but it is not constant.

Your first map

Start with the basic behaviour. The next program inserts three names into a map in the order pear, apple, mango. It then prints the keys. The keys come out in alphabetical order, even though they went in a different order. It also prints the first and last keys, looks up a value with at, and catches the error for a missing key.

The output is:

apple=5
mango=1
pear=3
first: apple
last: pear
1
kiwi missing

The loop prints the pairs in sorted order. The expression score.begin() gives an iterator to the smallest key, and score.rbegin() gives a reverse iterator to the largest key. A reverse iterator walks the container backwards, so rbegin() starts at the end. Both return iterators, and ->first reads the key from the pair they point at.

The call score.at("mango") returns the stored value, and it throws std::out_of_range if the key is missing. Unlike the bracket operator, at never inserts. The try block catches the exception, so the program prints a message and keeps going. If you did not catch it, the program would stop, as you saw in lesson 2.

Notice the order of the three inserts. The map does not care. The position of each key is decided by comparing it with the keys already present. You can insert in any order and read in sorted order.

What sorted means in C++

A sorted container needs a rule for comparing two keys. By default it uses the < operator. For int and string, that gives numeric and alphabetical order. For string, the comparison is character by character, so "apple" comes before "mango" because a comes before m. Uppercase letters have smaller codes than lowercase letters, so "Zebra" comes before "apple". Keep that in mind when you sort names from users.

A comparison rule is called a comparator. The default comparator is less<K>, which means "smaller first". You can change it, and the section on custom orders below shows how. The comparator has one job: decide which of two keys comes first. Two keys are equal when neither comes before the other. A set keeps only one of two equal keys, and that rule is the reason set drops duplicates.

Looking at the tree

The next picture shows what the container looks like inside. It holds the five values 10, 20, 30, 40 and 50. The root is 30. The left subtree holds 10 and 20, and the right subtree holds 40 and 50. Every value in the left subtree is smaller than 30, and every value in the right subtree is larger. That property holds at every node, not just the root.

A balanced binary search tree holding 10, 20, 30, 40 and 50, with 30 at the root

Look at the walk order. If you visit the left subtree, then the node, then the right subtree, you print the values in sorted order: 10, 20, 30, 40, 50. This visit order is called an in-order traversal. A set does this walk every time you loop over it, which is why the loop gives sorted output.

Step through the traversal above. Watch how the walk goes down to the leftmost node first, prints it, and then moves up and to the right. The same order is what the loop over a set produces.

The tree also explains the cost. To find 40, the search starts at the root, 30. Since 40 is larger, it goes right to 40 and stops. That is two comparisons. In a tree of a million nodes, the search would take about 20 comparisons. Each comparison halves the remaining range in a balanced tree, so the depth is about log n.

Nearest-value questions: lower_bound and upper_bound

Many real questions ask for the nearest value rather than an exact match. Examples include the first bus after 9:30, the first sale price at least 100, or the last checkpoint before a deadline. The methods lower_bound and upper_bound answer these directly, in O(log n) time.

The method lower_bound(x) returns an iterator to the first element that is not less than x. In other words, it points at the first element equal to x, or, if there is no equal element, at the first element larger than x. If every element is smaller than x, it returns end().

The method upper_bound(x) returns an iterator to the first element that is strictly greater than x. If an element equal to x exists, upper_bound points past it.

The picture below shows the same five values from before. The lower bound for 25 is the value 30, because 30 is the first value not less than 25. The upper bound for 30 is the value 40, because 40 is the first value strictly greater than 30.

A row of sorted values with lower_bound of 25 pointing at 30 and upper_bound of 30 pointing at 40

Now the program. It reads a list of bus departure times in minutes after midnight, then reads queries. For each query time, it prints the first departure at or after the query, which is lower_bound. It also prints the last departure before the query, which is one step back from lower_bound.

Type this into the Input box:

5
540 600 720 780 900
4
545 780 1000 100

The output is:

545: next 600, previous 540
780: next 780, previous 720
1000: next NONE, previous 900
100: next 540, previous NONE

Trace the first query, 545. The lower bound is the first time not less than 545, which is 600. So the next bus is at 600. The bus before that is one step back from the iterator, which is 540. The second query, 780, has an exact match. The lower bound is 780 itself, because 780 is not less than 780. The previous bus is 720.

The query 1000 is past the last bus. The lower bound returns end(), so the program prints NONE for the next bus. The predecessor is 900, the last bus of the day. The query 100 is before the first bus. The lower bound is 540, and there is no earlier bus, so the predecessor check hits begin() and prints NONE.

Two details in that program matter for correctness. First, the program checks end() before it dereferences the iterator with *it. Dereferencing end() is undefined behaviour, and it often prints garbage or crashes. Second, the program checks begin() before it steps back with prev(it). Stepping back from the first element goes outside the container, which is also undefined behaviour.

The function prev is declared in <iterator>. The program gets it through the other headers it includes, so add #include <iterator> in your own code. The function returns an iterator one step before the one you pass in. The call prev(it) does not change it. That is why the program can print a value from the earlier position without losing its place.

The table below shows the same four queries again, with each step written out. Use it as a model when you trace your own code.

The query 1000 is the case that needs care. The iterator is end(), so the program must not read it. The step back from end() is the last element, which is a valid position. The check for end() comes before the read, and the check for begin() comes before the step back. Both checks appear in the program.

A checklist for nearest-value queries

Interview problems that ask for the nearest value follow one checklist. Ask each question before you write the loop.

• Do I want the first value at or above x? Use lower_bound.
• Do I want the first value strictly above x? Use upper_bound.
• Do I want the last value below x? Use lower_bound, then step back, and check begin() first.
• Do I want the last value at or below x? Use upper_bound, then step back, and check begin() first.
• What if no value qualifies? Return a sentinel or a flag, and never dereference end().

The checklist covers both boundary cases. Most wrong answers come from forgetting end() or begin().

Counting values in a range with multiset

A set drops duplicates, which is wrong when you want to count repeated values. A multiset keeps every copy and still sorts them. It has the same operations as a set, and lower_bound and upper_bound work the same way.

To count the values between lo and hi, inclusive, use two bounds. The first position is lower_bound(lo). The end position is upper_bound(hi), which is just past the last value equal to hi. The number of values between the two iterators is the count. The function distance from <iterator> returns that number by stepping from the first iterator to the second, one value at a time. It costs O(k) for k values in the range. So a range count costs O(log n + k) with this method. A standard multiset cannot count a range faster than that, so use this method when k is small or when you can accept the cost.

The next program reads a list of values with duplicates. It then answers queries of the form lo hi and prints how many values lie in that range.

Type this into the Input box:

6
5 3 5 8 5 10
3
3 5
6 9
11 20

The output is:

4
1
0

The first query asks for values from 3 to 5. The input holds 5, 3, 5, 8, 5, 10, so the sorted multiset is 3, 5, 5, 5, 8, 10. The first position is at 3, and the upper bound for 5 is just past the last 5, which is at 8. Four values sit between them: 3, 5, 5, 5. The second query asks for 6 to 9, which holds only 8. The third query asks for 11 to 20, and nothing in the list is that large, so both bounds are end() and the distance is 0.

This pattern is common enough to memorise. Two bound calls and a distance give a range count in O(log n) plus the distance cost. For a set the same idea works, but the count is at most 1 for each value, so the answer is 0 or 1.

Notice what multiset does with duplicates. A set would have kept one 5 and given a count of 2 for the first query. Use a multiset when every copy must count, and a set when only the distinct values matter.

Equal values and bounds

Repeated values make lower_bound and upper_bound behave in a way that surprises people. Suppose a multiset holds three 5s and you call lower_bound(5). The answer points at the first 5, because that is the first value not less than 5. The call upper_bound(5) points past the last 5. The range between them holds exactly the 5s, and its length is 3.

If you need the last copy of a value, the answer is one step back from upper_bound. If you need the first copy, use lower_bound directly. Both steps need the begin() check, because stepping back from the first position is not allowed. A set has at most one copy of each value, so the two bounds differ only by one position there, and the same check is needed.

The standard library also offers equal_range(x), which returns both bounds in one call as a pair. It is convenient when you want the range of equal values in a single expression. For a multiset with three 5s, equal_range(5) returns the first 5 and the position past the last 5. Its result is the same as calling the two bounds separately.

Erasing and custom orders

Two more features complete the toolkit: deleting while you loop, and changing the sort order. Both come up in interview problems.

Erasing from a sorted container during a loop uses the same iterator pattern as in lesson 2. The erase function returns the iterator to the next element, so you should assign it back to the loop variable. The next program removes the even numbers from a set. It also shows a set with a custom order and a set built with a lambda comparator.

The output is:

1 3 5 7 
pear mango apple 
fig kiwi 
size: 2

The first part removes the evens. Each erase returns the iterator to the next element, so the loop visits every remaining value exactly once. The second part uses greater<string> as the comparator. That makes the set sorted from largest to smallest, so the names come out in reverse alphabetical order.

The third part is the one that surprises people. The comparator compares only lengths. kiwi and plum both have four letters, so the comparator says neither comes first. The set treats them as equal and keeps only the first one inserted. That is why plum is missing from the output and the size is 2. A comparator that says two different keys are equal makes the container merge them. This is a deep point, and interviewers like to test it. If you want to keep both words, you need a tie-breaker, such as comparing the words alphabetically when the lengths match.

Notice also that the lambda must be passed to the constructor, because a lambda's type is unique and the set needs its value. The code set<string, decltype(byLength)> shortFirst(byLength); does that.

Top k with reverse iteration

A sorted container also answers "largest k" questions. Walk from the end with rbegin() and stop after k items. The next program reads names and scores into a set of pairs. A pair compares its first element, the score, and then its second element, the name, when the scores are equal. The program prints the top three.

Type this into the Input box:

6
asha 70
ravi 92
meera 85
zoya 92
kiran 60
tara 88

The output is:

zoya 92
ravi 92
tara 88

The sorted set holds the pairs in this order: (60, kiran), (70, asha), (85, meera), (88, tara), (92, ravi), (92, zoya). The reverse walk starts at the largest pair, which is (92, zoya). Next comes (92, ravi), because the scores tie and "ravi" comes before "zoya" alphabetically. Then comes (88, tara). The loop stops after three pairs, so the lower scores are never visited.

The tie-break is the detail to explain in an interview. The pairs are ordered by score, then by name. If you wanted the earlier name to win a tie in the printed list, you would need a comparator that reverses the name order. Store the name first and the score second if the name should be the main key.

The loop checks shown < 3 before it reads the next pair. A set with fewer than three entries stops the loop at rend(), so a short set prints fewer lines and does not crash. Building the set costs O(n log n). The walk costs O(k), where k is the number of lines printed, so the walk does not depend on the size of the set.

Floor and ceiling names

Interview questions often use two names for the nearest-value queries. The ceiling of x is the smallest value at least x. The floor of x is the largest value at most x. C++ has no function named either of those, but the idea maps onto lower_bound and upper_bound, as the table shows.

For the set {10, 20, 30, 40, 50}, the floor of 35 is 30, and the ceiling of 35 is 40. The lower of 30 is 20, and the higher of 30 is 40. The two pairs of names differ only when the query equals a stored value. A floor of 30 is 30 itself, while a lower of 30 is 20. Read the question carefully to see whether it says "at most" or "strictly less".

Iterators across inserts and erases

The tree in a set or map is made of nodes, and an iterator points at one node. An insert changes the links between nodes, but it does not move the node you are holding. So an iterator you saved before an insert still points at the right element afterwards. An erase invalidates only the iterator to the erased node.

This differs from the hash containers in lesson 2, where a rehash can invalidate every iterator. Keep that difference in mind when your code holds an iterator across a change. The following fragment shows the safe case for a set.

set<int> s = {10, 20, 30, 40};
auto it = s.lower_bound(25);
s.insert(27);
cout << *it;

The fragment prints 30. The node that holds 30 did not move when 27 was inserted, so the saved iterator still points at it. With an unordered_set, the same insert could rehash the table and make it invalid. The safe habit with hash containers is to look up the key again after any insert.

Cost of each operation

The table below compares the sorted containers with the hash containers from lesson 2.

The last row needs a comment. Both kinds of container store one node per element, so the memory costs are close. The tree nodes hold pointers to the left and right children and a color, which is a little more than the hash versions need. The difference is small compared with the cost of the operations you need.

Choosing a container

Use the question you need to answer to pick the container. The rule is short. If you only need membership or counts, use a hash container, because it is faster. If you need sorted output, the smallest or largest value, or a nearest-value query, use the sorted container.

If you are unsure, ask whether the question mentions "sorted", "smallest", "largest", "next", "previous", "closest", "range" or "between". Any of those words points at the ordered containers.

What happens inside: the tree and its rules

You do not need to implement a red-black tree for daily work, but it helps to know what the container does on each insert. The tree stays balanced by a few rules. Each node has a color, red or black. No red node has a red child. Every path from the root to a null link passes through the same number of black nodes. These rules together keep the longest path at most about twice the shortest path, so the depth stays near log n.

When an insert breaks the rules, the tree repairs itself with a small number of local changes. A rotation moves a node up one level and another node down, keeping the order intact. The repair takes a constant number of rotations and recolourings in the worst case. Each insert therefore costs O(log n) for the search, plus O(1) for the repair.

Iterators stay valid in a tree. An insert or erase does not move the nodes in memory. It changes the links between them. An iterator is a pointer to a node, so it still points at the same node after other inserts. That is the main reason to choose map or set when you keep iterators around while changing the container. Erasing invalidates only the iterator to the erased node.

Common mistakes and the messages they produce

Dereferencing end(). This is the most common bug with ordered containers. The code *s.lower_bound(99) on a set whose largest value is 50 reads from end(). The program does not print an error. It may print a wrong value, or crash, depending on the compiler and the data. Always compare with end() before you use the iterator.

Stepping back from begin(). The code prev(s.begin()) is undefined behaviour. Check it != s.begin() before you call prev, as the nearest-value program did.

Changing a value through an iterator. The values in a set are const, because changing a value could break the sorted order. The compiler reports this when you try:

error: assignment of read-only location

The fix is to erase the old value and insert the new one. The compiler message is short, and the word read-only is the clue.

Using the free function on a set. The call std::lower_bound(s.begin(), s.end(), x) works on a set, but it walks the iterators one step at a time, so it costs O(n). The member function s.lower_bound(x) costs O(log n). Use the member function on a set or a map.

Forgetting that set drops duplicates. A set keeps one copy of each equal key, so its size is smaller than the number of inserts when values repeat. If you need every copy, use a multiset.

Accidental merging with a comparator. As the custom-order program showed, a comparator that treats different keys as equal makes the container drop keys. Make sure the comparator gives a strict order, with a tie-breaker when two different keys could compare as equal.

A debugging walkthrough

Suppose a function is meant to return the first bus at or after a time, and it returns the bus before it when the times match exactly. The symptom is an off-by-one error that appears only when the query equals a departure. Look at the bound you used. If you used upper_bound, the answer points past the matching time, which is the bus after the exact match. Switch to lower_bound, which points at the matching time itself.

Now suppose the function crashes when the query is later than every time. The usual cause is dereferencing end(). Add a check for end() before the dereference, and return a sentinel value such as -1 when the iterator is at the end.

Finally, suppose the answer is right for most queries but wrong for the first one. The cause is probably the predecessor step, because it calls prev on begin(). Check it != s.begin() before stepping back.

Each of these bugs has a visible symptom and a short fix. When you test, include the three edge cases: a query equal to a stored value, a query before the first value, and a query after the last value. Those three cases catch nearly every bound mistake.

Interview angle

A typical interview question is "given a set of times, find the first time after t". The answer is lower_bound with a check for end(). A follow-up asks for the time before t. The answer is the predecessor step with a check for begin(). Another common question is "count values in a range". The answer is two bounds and a distance.

Expect questions that compare map with unordered_map. The key points are that the sorted containers give O(log n) and an order, and that only the sorted containers support the nearest-value queries. A complete answer also mentions that the sorted containers never rehash, so their iterators stay valid across inserts.

Sliding-window problems can keep the values of the current window in a multiset. Then the smallest and largest values are one begin() call and one rbegin() call away, and each step of the window costs O(log n).

Real uses

Ordered containers appear wherever order carries meaning. A calendar application keeps appointments in a sorted set so it can show the next event. A leaderboard keeps scores in a sorted map so it can show the top players. An order book in a stock exchange keeps prices sorted, so it can match the best bid against the best offer. A time series store keeps timestamps sorted, so it can answer range queries over a time window. In each case the operations are nearest-value and range queries, which only the sorted containers support.

Practice

1. Insert the words delta, alpha and charlie into a set in that order, and print them. Predict the output first.

2. Given a set<int> of times, write a function that returns the first time at or after a query, or -1 if none exists. Test with the example from this lesson.

3. Write a program that reads numbers and prints the largest value strictly less than a query. Handle the case where no value qualifies.

4. Count how many values in a multiset equal exactly 7. Use equal_range or two bounds, and check that both methods agree.

5. Change the first map program so the keys are stored in descending order. Predict the output of the loop before running it.

6. Write a function that returns the smallest and largest values in a set in O(log n). What happens if the set is empty?

7. Show why std::lower_bound(s.begin(), s.end(), x) is slower on a set than s.lower_bound(x). Explain the difference in number of iterator steps.

8. Build a set<pair<int, string>> of scores and names, and print the top three scores. Decide which order you want for ties, and explain your choice.

9. Find the number of distinct values in a multiset in O(n). Then explain why set would give the answer directly with size().

10. Write a comparator for a set<string> that sorts words by their last letter, and breaks ties alphabetically. Test with cat, bat and dog.

11. A set of event times holds 10, 20, 30. A query asks for the last event strictly before 30. Give the answer, and write the code in two steps.

12. Explain in one paragraph why a map iterator stays valid after an insert but an unordered_map iterator might not.

What you now know

• A map and a set keep keys sorted, using a balanced binary search tree. Insert, find and erase cost O(log n).
• A loop over a sorted container visits keys in order, because an in-order walk of the tree is sorted.
• lower_bound(x) gives the first value not less than x. upper_bound(x) gives the first value strictly greater than x.
• To find the value before a position, step back with prev, and check begin() first.
• Always check end() before you dereference an iterator from lower_bound.
• A multiset keeps duplicates, and two bounds give a range count.
• A comparator defines the order, and one that treats different keys as equal makes the container merge them.
• Use the sorted containers for order questions, and the hash containers for plain membership and counts.

The next lesson uses these tools together on classic interview problems, and it shows the patterns that turn an O(n squared) search into a single pass.