set, map and unordered_map

Why this matters

Many questions in programming come down to lookup. Has this name been seen before? How many times does each word appear? Which two numbers add up to the target? Which account belongs to this user id? If you answer each lookup by scanning a list, the work grows with the square of the input size, and a program that handles a thousand items may take a million steps. A set or a map answers the same question in a small, almost constant number of steps, so a program that handles a million items still finishes quickly.

This lesson covers four containers. set keeps unique values in sorted order. map keeps unique keys in sorted order, each with a value attached. unordered_set and unordered_map do the same jobs without keeping any order, but they are usually faster. You will learn what each one costs, how to read and write keys, and which one a problem calls for.

Start with a guest list and a phone book

A set is a guest list at a party. Each name can appear only once. If someone writes a name a second time, the list does not change. And if you ask the list the names in order, you get them alphabetically, because the list is kept sorted.

A map is a phone book. You look up a name, which is the key, and you get a number, which is the value. Each name appears once. The book is kept in alphabetical order by name, so reading the whole book gives you the names in order. A map is a set where every item has a value attached to its key.

A hash map is a coat check. When you hand over your coat, you get a ticket with a number. The number tells the staff which hook to look at, so they do not search the whole room. In a computer, a hash function turns a key into a number that picks a slot. Finding a key means computing its hash and looking in that slot. The "unordered" versions in C++ use hashing, and that is why they have no natural order. The coats are on hooks by number, not by owner name.

These three pictures explain almost every difference between the containers in this lesson:

• Sorted containers (set, map) keep items in order, so they can answer questions like "the smallest", "the largest" and "the first value at least 50". They find a key in O(log n) steps by halving the search.
• Hashed containers (unordered_set, unordered_map) find a key in O(1) steps on average, but they keep no order at all.
• Keys must suit the container. Sorted containers need a way to compare keys with <. Hashed containers need a way to turn keys into numbers.

set: unique values in order

A set stores each value at most once, in sorted order. Its main operations are:

• insert(x) adds x. If x is already there, nothing changes. It costs O(log n).
• count(x) returns 0 or 1, because a set holds each value once. It costs O(log n).
• find(x) returns an iterator to x, or s.end() if x is missing. It costs O(log n).
• erase(x) removes x, if present. It costs O(log n).
• *s.begin() is the smallest value and *s.rbegin() is the largest. Both cost O(1).
• lower_bound(x) returns an iterator to the first value that is not less than x. It costs O(log n).

The usual implementation is a balanced binary search tree, which keeps the tree even so that every search takes about log n steps. You do not need the details to use a set. What matters is that the set stays sorted, which is why it can answer "smallest" and "first at least" questions that an unordered set cannot.

Sets are also the simplest way to remove duplicates, because insertion ignores repeats. A program that wants the distinct values of a list can insert every value into a set and then read the set in order. That is one line of work per value, so the whole job costs O(n log n).

Worked example 1: a set in action

This program inserts values into a set, shows that duplicates vanish, and then uses the sorted order to read the smallest and largest values.

The output is:

size 4
1 3 4 5 
has 3? 1
has 9? 0
smallest 1 largest 5
first >= 2 is 4

The list starts with the values 5, 1, 3, 3 and 1. Each of 3 and 1 appears twice in that list, but the set keeps one copy of each. Insertion of 4 gives four values: 1, 3, 4 and 5. The loop prints them in sorted order even though 5 went in first. The count of 3 is 1, which is also the set's way of answering "is it here?" in one call.

The find call returns an iterator. The program compares that iterator with s.end() to check whether 9 is there. That is the correct test. Writing if (s.find(9)) would be a mistake, as the common mistakes section shows.

After erase(3), the smallest value is 1 and the largest is 5. Finally lower_bound(2) returns the first value that is not less than 2, which is 4, because 2 is not in the set. The answer tells you where 2 would sit if you inserted it. That is the question a sorted container answers well and a hash set cannot answer at all.

map: keys with values

A map stores key-value pairs. Each key appears at most once and the keys are kept in sorted order. The most common way to use one is through square brackets:

map<string, int> m;
m["b"] = 2;
m["a"] = 1;
m["c"] += 5;     // creates "c" with 0, then adds 5

Writing m[key] does two things. It returns the value for that key, and if the key is missing, it creates the key with a default value. For an int, the default is 0. This makes counting easy: m[word]++ adds one to the count of a word, whether or not the word was there before. It is also the source of a common bug. Reading m["z"] in a condition quietly adds z to the map. If you only want to check for a key, use count or find.

Looping over a map gives you pairs, where kv.first is the key and kv.second is the value. The loop visits keys in sorted order. A map costs O(log n) for each lookup, insert and erase.

The next example builds a small map from words and then checks for keys in two ways.

map<string, int> m;
m["b"] = 2;
m["a"] = 1;
m["c"] += 5;
for (auto& kv : m) cout << kv.first << "=" << kv.second << " ";
// a=1 b=2 c=5

The map prints in key order, a, b, c, even though b went in first. That is the sorted rule at work.

unordered_map and unordered_set: the hashed versions

The unordered containers store their items in a hash table. A hash table is an array of slots, called buckets. The hash function turns a key into a bucket number. To insert, compute the bucket and place the item there. To look up, compute the bucket and check the few items in it. When the table gets too full, it grows and moves the items into a bigger array. That move is expensive, but it happens rarely.

The drawing below shows the idea. Each key goes to a bucket chosen by its hash, and a lookup only checks that bucket.

The costs are O(1) on average for insert, lookup and erase. "On average" is the honest word. If many keys land in the same bucket, a lookup has to check them one by one. A good hash function spreads the keys evenly, so this is rare in practice. In the worst case, every key lands in one bucket, and the costs grow to O(n). Interviewers sometimes ask about this, and you should mention it.

Hashed containers keep no order. Looping over an unordered_map gives the items in whatever order the buckets happen to hold them, and that order can change when the table grows. If you need the output sorted, sort it yourself, as the next section shows.

The standard hash function works on the built-in types, on string, and on some other types. It does not work on pair, so unordered_map<pair<int, int>, int> does not compile without an extra hash function. You will meet that error in the common mistakes section.

Worked example 2: word counts from input

This program reads any number of words from the input, counts each one, and prints the counts in alphabetical order. Because the program uses a map, the sorted order comes for free. Type this into the Input box:

the cat and the hat
The cat

The output is:

The 1
and 1
cat 2
hat 1
the 2
distinct 5

The loop while (cin >> word) reads one word at a time until the input ends. Each word goes into the map with freq[word]++. The first time a word appears, the map creates it with 0 and then adds 1. Later occurrences just add 1.

Look at the order carefully. The comes first, not the. That is because the program compares strings letter by letter using their character codes, and an uppercase T has a smaller code than a lowercase t. The word The and the word the are different keys, so the program counts them separately. Lowercasing the words before counting is the usual fix when the case should not matter, and you will see it again in the practice questions.

The count of distinct words is 5, because the and The are two keys. The total number of words is 7, and that is the sum of the counts: 1 + 1 + 2 + 1 + 2 = 7.

Worked example 3: two sum with a hash map

A classic interview question asks for two numbers in a list that add up to a target. A slow solution checks every pair, which costs O(n squared). The fast solution walks the list once and, for each number, asks whether its partner, which is the target minus the number, was seen before. A hash map of seen values answers that question in O(1) on average.

The program reads the size and target on the first line, then the numbers. It prints the indexes of the first pair it finds, or none if no pair exists. Type this into the Input box:

6 9
2 7 11 15 4 5

The output is:

0 1

The walk goes like this. The target is 9. At index 0 the value is 2, and its partner is 7. The map is empty, so 7 is not found. The program stores seen[2] = 0. At index 1 the value is 7, and its partner is 2. The map has 2 at index 0, so the lookup succeeds. The program prints the stored index, 0, followed by the current index, 1.

Notice the order of two steps. The program looks for the partner first, then stores the current value. If it stored first, a value could pair with itself, for example 4 and 4 when the target is 8. Looking first avoids that. The map stores each index, not just a yes or no, so the answer can report where the partner sits.

The map also needs no sorting. That is the point. The input is in any order, and the answer comes out in one pass.

Step through the animation again and follow the lookup for 7. Notice that the program never looks at the whole map. It only checks the bucket that the partner's hash points to.

Worked example 4: grouping anagrams

Two words are anagrams when they use the same letters with the same counts, as eat and tea do. A common interview task groups a list of words so that each group holds anagrams of each other. The trick is to give every word a shared key. Sorting the letters of a word gives the same key for all of its anagrams. The program puts each word into a map under its sorted key, and the map's sorted order also orders the groups.

Type this into the Input box:

6
eat tea tan ate nat bat

The output is:

abt: bat
aet: eat tea ate
ant: tan nat
groups 3

Trace one word. The input tea has the sorted key aet. The map has no aet yet, so groups[key] creates an empty vector and push_back adds tea. Later, eat also has the key aet, so it joins the same vector. The vector keeps the words in the order they arrived, which is why eat comes before tea and ate in the output.

The keys come out in sorted order. abt is smaller than aet because b is smaller than e, and aet is smaller than ant because e is smaller than n. The map gives this order for free, which a hash map would not.

The structured binding auto& [key, words] unpacks each map entry into two names. It is the same tool you met in lesson one, now used on map entries. Each entry is a pair of key and value, so the binding works.

Sorting each word costs O(k log k) for words of length k, so the whole job is O(n k log k) with a map. A hash map gives the same answer and avoids the ordering cost of the groups, but since the final output must be in order, the map is a good fit here.

Worked example 5: the longest run of consecutive values

The last example uses a hash set for a question that asks about neighbours. Given a list of numbers, find the longest run of consecutive whole numbers that all appear in the list. For instance, the values 1, 2, 3 and 4 form a run of length 4 when all four are present, even if they were listed in any order.

The clever part is to start a count only at the first number of each run. A number is a run start when its predecessor, one less, is not in the set. From a start, count upward while the next number is present. Each number belongs to at most one run, and the count from a start visits only numbers in that run. So each number is visited a constant number of times, and the whole job costs O(n) on average.

Type this into the Input box:

9
100 4 200 1 3 2 4 101 102

The output is:

4

The set holds 100, 4, 200, 1, 3, 2, 101 and 102. The duplicate 4 is stored once. The loop checks each value as a possible start. The value 4 has 3 in the set, so it is skipped. The value 1 has no 0, so it is a start. Counting up from 1 finds 2, 3 and 4, and then 5 is missing, so the run has length 4. The value 100 is a start because 99 is missing, and its run is 100, 101, 102, length 3. The value 200 is alone, length 1. The best is 4.

The count calls on an unordered set are O(1) on average, which keeps the whole loop linear in practice. In C++20 you can write contains instead of count, but this program targets C++17, so it uses count.

Keys with a custom order

A set or a map decides its order with a comparator, which is a rule that answers whether one key comes before another. By default the comparator is less, which uses <. You can change it by passing a second template argument. For a set of numbers that should run from largest to smallest, write set<int, greater<int>>. Iteration then starts at the largest value, so *s.begin() is the largest, and every other operation works as before.

Strings are a common case where the default order is not what you want. The default compares character codes, so the capital Z comes before the lowercase a. If you want words in a dictionary order that ignores case, write the comparator as a small struct. The struct needs an operator() that takes two keys and returns true when the first comes before the second. The program below lowers each word before it compares them, and it needs <cctype> for tolower.

struct CaseInsensitive {
    bool operator()(const string& a, const string& b) const {
        return lowered(a) < lowered(b);
    }
    static string lowered(string s) {
        for (char& c : s) c = tolower(static_cast<unsigned char>(c));
        return s;
    }
};
 
set<string, CaseInsensitive> names = {"apple", "Zebra", "mango", "Apple"};

Iterating over names gives apple mango Zebra. The second Apple is dropped, because the comparator says it equals apple. Two keys that the comparator calls equal count as one key, even when their spelling differs. That is a surprise for beginners, and it is the right behaviour for a set of words that should ignore case.

The comparator has the same rule as a sort comparator, from lesson four. It must be a strict weak ordering, so it must never call an item before itself, and it must be consistent. A comparator that changes its answer between calls breaks the tree, and the container can then give wrong answers without any error message. Keep the comparator a pure function of its two arguments.

A comparator does not change the cost. A greater set is as fast as a less set, because both are balanced trees with the same height. The comparator only decides the direction. Use it when the natural order of your output is different from the default, and avoid sorting a copy afterwards, which would cost extra time and space.

Learning whether an insert added something

The insert function of a set returns a pair. Its first part is an iterator to the value, and its second part is a bool. The bool is true only when the value was new. That makes insert a duplicate check in one call, which is the same job the lesson five duplicate program did with an explicit count.

set<int> seen;
for (int x : {4, 9, 4}) {
    auto result = seen.insert(x);
    cout << x << (result.second ? " new" : " repeat") << endl;
}

The output is:

4 new
9 new
4 repeat

The first 4 is new and goes into the set. The 9 is new as well. The second 4 is already present, so insert leaves the set unchanged and returns second as false. A single call replaces a count followed by an insert, which saves a second search through the tree.

The same return value works for map::insert, and it is the reason the map's insert does not overwrite an old value. If you want the new value to win, use the square bracket form m[key] = value, which overwrites, or check the bool first and then assign.

Erasing while you walk a map

Removing items while you loop over a map follows the same rule as removing from a vector, from lesson one. The erase function returns an iterator to the next item, so the loop must take that value. Since C++11, the same is true for set and map. The loop below removes every entry whose count is below 2.

for (auto it = freq.begin(); it != freq.end();) {
    if (it->second < 2) it = freq.erase(it);
    else ++it;
}

The loop advances only when it keeps the entry. If you wrote ++it after every erase, you would skip the entry that moved into the erased spot, and you could move past end(). The loop has no ++it in its header, because the update happens in exactly one of the two branches.

A trap sits next to this rule. The overload erase(key) takes a key, not an iterator, and it returns the count removed, which is 0 or 1. Calling it inside a loop that walks the map does not return an iterator, so the loop would not know where to go next. Use the iterator form whenever you are looping and erasing at the same time.

Ordered or hashed?

The table compares the four containers. Read the last row before you choose.

Interviewers often ask which one you would choose. A good answer names the question the problem asks. If the problem asks for the first value at least some number, or the values in order, pick the sorted container. If it asks only whether a value is present or what it maps to, pick the hashed container. If you are not sure, the sorted container is safer, because its cost never degrades.

The containers multiset and multimap allow a key to appear more than once. They keep the same sorted order and the same costs, and they are the right tool when duplicates must be kept.

What happens inside: the cost of a set lookup

A sorted set is a tree. Each node holds one value, and the left child holds smaller values while the right child holds larger ones. To find a value, start at the root and compare. If the value is smaller, go left. If larger, go right. Each comparison throws away about half of the remaining tree, so the search takes about log n steps. A set of a million values needs about 20 comparisons. The tree is kept balanced, so no branch grows too long.

A hash table works differently. The hash function computes a bucket number in one step. The bucket is an array slot, so jumping to it takes one step. The bucket holds a short list of items with the same bucket number, and the lookup checks that list. If the table is sized well, the list is very short, and the lookup takes about one comparison. The cost of growing the table is spread across all the inserts, so the average stays O(1).

Both designs answer the same question, but the sorted design also remembers order, while the hashed design remembers only membership. That trade-off is the reason for the table above.

Common mistakes and the messages you will see

Mistake 1: reading a map with brackets to check for a key. A learner writes if (m["z"] == 0) to check whether z is present. The read creates z with the value 0. The map has grown by one entry, and the check did not answer the question. Use m.count("z") or m.find("z") != m.end() instead.

Mistake 2: testing a find result as a boolean. A learner writes if (s.find(9)). The compiler stops with:

error: could not convert 's.std::set<int>::find(2)' from 'std::set<int>::iterator' to 'bool'

The message says find returns an iterator, and an iterator cannot be used as a yes or no value. The fix is to compare with the end: if (s.find(9) != s.end()).

Mistake 3: using a pair as an unordered key. A learner declares unordered_map<pair<int, int>, int> grid; and writes grid[{1, 2}] = 5;. The compiler reports:

error: static assertion failed: hash function must be copy constructible

followed by long messages about a deleted default constructor. The root cause is the missing hash for pair. The fix is to write a small struct with a hash function, or to encode the pair as one number, such as r * 1000 + c, when the values are small. A map with pair keys works without any extra code, because pair has a < comparison.

Mistake 4: expecting unordered output to be sorted. A learner loops over an unordered_map and expects alphabetical output. The order is whatever the buckets hold, and it can change between runs or machines. Copy the entries into a vector, sort it, and then print.

Mistake 5: changing a key. Keys in a set or map cannot be changed in place, because the container depends on them for its order or buckets. To change a key, erase the old entry and insert the new one.

Mistake 6: dereferencing end. A learner writes *s.find(9) without checking. When the value is missing, find returns end(), and reading it is undefined behaviour. Check the iterator first.

Debugging walkthrough: a count that is too small

A learner counts how often each word appears in the input the cat The the. They expect the to appear three times, but the program prints the 2 and The 1.

Work through the code.

1. The loop reads each word with cin >> word, so every word is read exactly as it was typed, capital letters included.
2. The count increments with freq[word]++. That adds one to the key with that exact spelling.
3. Print the map and look at its keys. The lowercase the has 2 and the capital The has 1. Those are two different keys, so the program is doing what it was written to do.
4. The learner's expectation was wrong, because the code compares spellings. Nothing in the program crashes or loses a word, and the three words are all counted.

The point of the walkthrough is to print the keys. Printing the map shows exactly which key holds which count, and a difference like this one is visible at once. If case should not matter, lower-case each word before counting. In C++ you can call tolower on each character of the word, or use transform with tolower from <cctype>.

Variations and edge cases

A few details change the answer in ways that surprise beginners.

• An empty set or map has size 0, and begin() equals end(). Taking *s.begin() on an empty set is undefined behaviour, so check empty() first.
• set and map treat keys as equal when neither is less than the other. Two strings differing only in case are different keys, because < compares the character codes.
• unordered_set holds one copy of each value, just like set. multiset and multimap allow duplicates.
• lower_bound on a set returns the first value that is not less than the key. upper_bound returns the first value greater than the key. Together they give a range.
• Inserting an item that already exists in a map does not replace the value. insert leaves the old value in place, while m[key] = value overwrites it.

Interview-style practice in plain words

Three problems appear in many interviews. First, find whether a list has any duplicate. A set answers this in O(n) on average, by stopping at the first value it has already seen. Second, find the most common element. Count with a hash map, then scan the map for the largest count, breaking ties in a fixed way. Third, find the first unique character in a string. Count each character in a map, then scan the string in order and return the first character whose count is 1. The string scan keeps the original order, which the map does not.

For each answer, state the cost and the reason. "O(n) time and O(n) space, because each value enters the set once" is a good answer for the duplicate problem.

Practice

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

1. Count the distinct numbers in the vector {4, 4, 9, 1, 9, 9} using a set. Expected output: 3.

vector<int> v = {4, 4, 9, 1, 9, 9};
set<int> distinct(v.begin(), v.end());
cout << distinct.size() << endl;

2. Print the most common word in a list of words, and on a tie print the word that comes first alphabetically. Input pear apple pear fig apple pear. Expected output: pear 3.

map<string, int> freq;
string w;
while (cin >> w) freq[w]++;
string best;
int bestCount = 0;
for (auto& kv : freq) {
    if (kv.second > bestCount) {
        best = kv.first;
        bestCount = kv.second;
    }
}
cout << best << " " << bestCount << endl;

3. Check whether two strings have the same letters with the same counts. Input listen and silent gives YES. Input abc and abd gives NO.

string a = "listen", b = "silent";
map<char, int> count;
for (char c : a) count[c]++;
for (char c : b) count[c]--;
bool same = true;
for (auto& kv : count) if (kv.second != 0) same = false;
cout << (same ? "YES" : "NO") << endl;

4. Check whether two strings have the same set of letters, ignoring counts. Input aab and ba gives YES. Input abc and abd gives NO.

set<char> x(a.begin(), a.end());
set<char> y(b.begin(), b.end());
cout << (x == y ? "YES" : "NO") << endl;

5. Find the first character that appears twice in a string, using an unordered set. Input abcbd gives 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);
}
if (found) cout << found << endl;
else cout << "none" << endl;

6. Given a sorted vector {1, 3, 3, 5, 8}, use a set to answer whether 4 is present and print the first value at least 4. Expected output: no on one line and 5 on the next.

set<int> s = {1, 3, 3, 5, 8};
cout << (s.count(4) ? "yes" : "no") << endl;
cout << *s.lower_bound(4) << endl;

7. Merge two sorted vectors {1, 4, 6} and {2, 4, 9} into a set to get their sorted union without duplicates. 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;

8. Build a phone book map from the input lines Asha 555-0101, Ravi 555-0199. Then look up Ravi and print the number, and look up Mei and print unknown without adding Mei to the book. Expected output: 555-0199 and then unknown.

map<string, string> book = {{"Asha", "555-0101"}, {"Ravi", "555-0199"}};
cout << book["Ravi"] << endl;
auto it = book.find("Mei");
cout << (it == book.end() ? "unknown" : it->second) << endl;

9. A learner counts the letters of the string aAa and expects the count for a to be 3, ignoring case. The program below prints 2. Explain why, then fix it so that it prints 3.

unordered_map<char, int> freq;
for (char c : string("aAa")) freq[c]++;
cout << freq['a'] << endl;

10. Explain in three or four sentences why map and unordered_map both answer "how many times does each word appear?" but only the map gives the answer in alphabetical order. Name the cost of each lookup.

11. Two steps: a map holds {"b": 2, "a": 1}. Insert "a" with the value 5 using insert, then insert "c" with 3. Print the value stored for "a". Expected output: 1.

map<string, int> m = {{"b", 2}, {"a", 1}};
m.insert({"a", 5});
m.insert({"c", 3});
cout << m["a"] << endl;

What you now know

• A set keeps unique values in sorted order, costs O(log n) per operation, and answers "smallest", "largest" and "first at least" questions.
• A map keeps unique keys in sorted order, each with a value. Reading m[key] creates a missing key, so check with count or find when you only want to test.
• unordered_set and unordered_map use hashing for O(1) average lookups but give no order, and their worst case is O(n).
• A two-sum search, an anagram grouping and a longest-run count each follow the same idea: store what you have seen, then ask the table a fast question.
• Use find and compare with end(), never convert an iterator to a bool, and provide a hash before you use a pair key in an unordered container.