unordered_map and unordered_set

Why this matters

Most real C++ programs do not build their own hash table. They use the one in the standard library: unordered_map for keys with values, and unordered_set for keys alone. The containers are fast and easy to call, and that ease hides several traps. A lookup that accidentally inserts a key, a loop that deletes the wrong element, and a struct that cannot be a key all produce bugs that look fine at first glance. This lesson shows the containers in use, and it shows each trap with the output you will see when you fall into it.

The previous lesson explained the machinery: a hash function, buckets, collisions and rehashing. Here you use that machinery through its public interface. Keep the bucket picture in mind, because it explains why some operations are fast and why some results come out in an order that looks random.

The two containers

An unordered_map<K, V> stores pairs. Each unique key of type K maps to one value of type V. Think of a phone book. You look up a name and get a number. A name appears once, so asking for the same name again gives the same number, and writing a new number for a name replaces the old one.

An unordered_set<T> stores only values, with no pairs. Each value appears at most once. Think of a guest list at the door. A name is on the list or it is not. Adding the same name twice does not put two copies on the list.

To use them, include the headers <unordered_map> and <unordered_set>. Include <string> too when your keys are strings, because the examples here use string keys. Writing #include <string> yourself is a good habit, even though some headers pull it in indirectly.

#include <string>
#include <unordered_map>
#include <unordered_set>

Both containers live in the std namespace. The examples use using namespace std; to keep the code short. In a large project many teams write std:: in front of names instead, so you see it in code you read at work.

A phone book that reads commands

The first runnable program turns the phone book idea into a small command loop. Each line in the Input box starts with one of three words. add saves a name and number. find looks up a name. remove deletes a name. At the end the program prints how many entries are left.

Type this into the Input box, one command per line:

add asha 555-0101
add ravi 555-0199
find asha
find zed
add asha 555-0142
remove ravi
remove ravi
find ravi

The output is:

saved asha
saved ravi
asha: 555-0101
zed not found
saved asha
removed ravi
no such name ravi
ravi not found
entries: 1

Walk through it command by command. The first two lines add two entries, so the book now has two names. The find asha line looks up asha and prints her number. The find zed line fails, so the program prints zed not found. Then add asha 555-0142 runs. The key asha already exists, so book[name] = number replaces the old number. The map still holds one entry for asha, and the size does not grow. The program prints saved asha because the command is treated the same way whether the name is new or not.

The line remove ravi deletes the entry and returns 1, which is the number of entries erased. The second remove ravi finds nothing and returns 0, so the program prints no such name ravi. The last find ravi gets the same answer. At the end one entry is left, asha.

Three operations appear in this program. Each one has a different cost and a different side effect. The next sections explain each.

Looking up with find

The method find searches for a key and returns an iterator. An iterator is an object that points at an element in the container, a bit like a bookmark. If the key is present, the iterator points at the pair holding the key and its value. If the key is absent, the iterator equals book.end(). The method end() returns a position just past the last element, and it is the signal for "not found".

In the program, it->second reads the value. The arrow operator reaches into the pair, and second is the value half of the pair. The first half is first, the key. So it->first would be the name and it->second the number.

The rule for find is simple. It searches, and it never changes the container. That makes find the right tool when you want to test membership or read a value and you do not want a side effect.

Using brackets with operator[]

The square-bracket operator is the most convenient syntax, and it is also the most dangerous. For a map, book[name] reads or writes the value for name. When you write book[name] = number, the operator stores the value, and that is the behaviour you want in add.

When you only read with brackets, something surprising happens. If the key is missing, the operator inserts it with a default value and returns that value. For int the default is 0, and for string it is an empty string. The container grows, and nothing warns you. The next program shows the effect step by step.

The output is:

size after assignment: 1
pears = 0, size now 2
has kiwi? no
size after count: 2
has pears? 1

Read the output carefully. After the assignment there is one key. The line int a = stock["pears"]; only reads, but the size becomes 2 and the program reports pears = 0. The bracket operator created the key pears with the value 0. The next check, count("kiwi"), does not insert anything, so the size stays at 2. The final check finds pears, which is now a real entry.

The rule for beginners is short. Use brackets to write a value. Use find or count to test for a key. If you use brackets in a condition such as if (stock[name] > 0), you will add the missing names to the container without meaning to. Bugs of this kind show up later as a map that is larger than expected, or as keys that should not be there.

Testing membership with count

The method count returns 0 or 1 for these containers, because keys are unique. You can read it as a yes-or-no test. count(key) does not insert anything. It is safe to use inside an if.

Both count and find are read-only. Use find when you also need the value, because it returns an iterator to the pair. Use count when you only need to know whether the key is there. Many programmers use contains, a newer member function in C++20, but this module targets C++17, so count is the portable form.

Unique values with unordered_set

An unordered_set removes duplicates for you. Each insert either adds a new value or does nothing. The set's size after many inserts is the number of distinct values. That is the answer to the most common question in this area: how many different things did I see?

The next program reads a count, then that many numbers. It inserts the numbers into a set, which keeps only one copy of each. It prints the number of distinct values, and then the values in sorted order.

Type this into the Input box:

7
4 7 4 9 7 1 9

The output is:

distinct: 4
1 4 7 9

The set holds 4, 7, 9 and 1, and it discards the second 4, the second 7 and the second 9. Its size is 4. The second half of the program copies the set into a vector, sorts the vector, and prints it. That step exists because an unordered_set has no defined order. The values happen to come out in some order, but you cannot rely on it. If you need sorted output, sort a copy, as the program does.

Notice the constructor vector<int> values(seen.begin(), seen.end());. It takes two iterators, the first element and the one past the last, and copies every element between them. Almost every container in C++ accepts this pair-of-iterators form, and you will use it again in lesson 3.

The order you cannot rely on

The order of elements in an unordered_map or unordered_set depends on the hash function, the bucket count and the history of inserts. It can change after a rehash. Two programs compiled with different standard libraries can print the same keys in different orders. Even on one machine, the order can change when the table grows.

Because of this, a program that prints a hash container directly may look correct on your machine and fail a test on another. The rule is simple. If the output must be in a particular order, put the keys in a sorted container or sort them first. The sorting step in the previous program follows that rule.

Here is an example of the trap. Suppose you loop over a map and print each key, and the test expects alphabetical order. Your output might match by luck, and then fail when the test data changes. Always decide first whether order matters. If it does, do not use an unordered container to produce the output.

Looping over a container

You can loop over the pairs of an unordered_map with a range-based for loop. C++17 structured bindings let you unpack each pair into two names. The line for (const auto& [key, value] : book) is the most readable form. The const says the loop does not change the keys, and the & avoids copying each pair.

Use the loop to read the data, not to change the container. Changing the key of a pair is not allowed, because the key decides the bucket. The value can change through a non-const reference, but a loop that changes values and then searches the same map in the same loop is easy to get wrong. Keep each loop simple: read in one loop, write in another if you can.

The loop order is unspecified. The earlier warning applies. Sort first if the output matters.

Worked example: counting words

Counting is the most common job for an unordered_map. The next program reads any number of words from the Input box, counts each one, and prints the words that appear more than once, in alphabetical order. It also prints how many different words it saw.

Type this into the Input box:

the cat and the dog and the bird

The output is:

and 2
the 3
distinct words: 5

Trace the first few words by hand. The table shows the map after each word is read.

The ++ on a missing key works because the bracket operator creates the entry with value 0 first. That is the intended use of brackets in a counter. Nothing in this program reads a key it does not want to create.

The loop after the reading loop chooses the repeated words. It copies each word whose count is greater than one into a vector, and then it sorts the vector, because the map's own order is not defined. The print loop calls counts[w] only on words that are known to exist, so the bracket operator inserts nothing there. The last line prints counts.size(), which is the number of distinct words, 5 here.

The reading loop costs O(n) on average, where n is the number of words. Sorting the k repeated words costs O(k log k). The sort is the only step that depends on order. Without it, the output would follow the hash order, which can change when the table grows.

insert, emplace and try_emplace

The bracket operator is one of four ways to add a pair. Each one behaves a little differently, and interviewers sometimes ask which to use.

m[key] = value always stores the value. If the key was absent, it is created. If the key was present, its old value is replaced. Use it when the latest value should win, as in the phone book.

m.insert({key, value}) adds the pair only if the key is absent. If the key is present, nothing changes. It returns a pair: an iterator to the element, and a bool that says whether an insert happened. Use it when the first value should win.

m.emplace(key, value) does the same as insert, but it builds the pair in place rather than copying one in. For simple types the speed difference is small, and the return value is the same as insert's.

m.try_emplace(key, args...), added in C++17, is the one to know for expensive values. If the key is present, it builds nothing. If the key is absent, it builds the value from the arguments you pass. Use it when building the value is costly and many keys already exist.

Here is a fragment that uses the return value of insert on an unordered_set:

auto [it, added] = seen.insert(word);
if (added) cout << "first time: " << word << "\n";

The structured binding from earlier in this lesson unpacks the pair. The variable added is true only on the first insert of a word. This pattern is the basis of a deduplicator, which removes repeated items from a stream as they arrive.

Custom keys: when a struct is not enough

A hash container needs two things about its key type. It needs a way to hash the key, and it needs a way to test two keys for equality. For int and string, the standard library supplies both. For a pair or a custom struct, you must supply them yourself. Many beginners only discover this when they try to store grid cells or coordinates.

Here is what happens when you try to use a pair as a key with no hash supplied. The code is short, and the compile error is long.

#include <unordered_set>
#include <utility>
using namespace std;
 
int main() {
    unordered_set<pair<int, int>> visited;
    visited.insert({1, 2});
}

The compiler stops with an error. The first line of the message is long and includes this text:

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

The message does not say "you need a hash for pair". It says the hash function is not usable. The honest meaning is that the standard library has no default hash for pair, so the container cannot be built with the default. When you see a long error that mentions hash, the fix is almost always to supply a hash for your key type. The next section does that.

Some compilers print a different wording, and some print many lines of template names. Look for the word hash in the message and for the line number in your file. That line shows which container declaration caused the problem.

A custom key with its own hash

A common interview task is to track which grid cells a walker has visited. A cell is a point with an x and a y coordinate. To store points in an unordered_set, the point type needs two things. It needs an operator== that says when two points are equal, and it needs a hash object that turns a point into a number. The container calls the hash object, and it calls == to resolve collisions.

The program below moves a walker across a grid. Each letter moves it one step: R moves right, L moves left, U moves up and D moves down. The program counts the distinct cells visited, and it reports whether the walker ever returned to a cell it had seen before. It reads the moves from one line of input.

Type this into the Input box:

RRUULLDDRR

The output is:

distinct cells: 8
revisited: yes

The Point struct has two parts. The operator== member says two points are equal when both coordinates match. The PointHash struct is a function object: a type that you can call like a function. Its operator() takes a point and returns a size_t, which is the unsigned integer type the containers expect for hash values. The body mixes the coordinates into one number. Multiplying x by a large prime and adding y gives a different number for most pairs. The hash<long long> call uses the standard hash for that type. You pass the hash type as the second template argument, unordered_set<Point, PointHash>, so the container knows which hash to call.

Trace the walk. The walker starts at (0, 0), and the start is inserted into the set. The moves R, R, U, U, L, L, D, D take it around a square, through (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2), (0, 1) and back to (0, 0). The eighth move lands on the start, which is already in the set, so count returns 1 and revisited becomes true. The last two moves go back to (1, 0) and (2, 0). The distinct cells are (0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (1, 2), (0, 2) and (0, 1), which is 8. The walk has 11 positions in total, counting the start, but only 8 are distinct.

Notice the design choice. The program checks count before insert. If it inserted first, every move would look like a revisit, because the new position would already be in the set. The order matters in exactly the same way as the Two Sum check in lesson 4.

Removing entries while you loop

Deleting from a container during a loop is a classic bug. The fix is a pattern you can memorise. Use an explicit iterator in the loop. When you erase, take the iterator that erase returns, because the old iterator is no longer safe to use. When you do not erase, advance the iterator yourself.

The next program reads a list of names and scores into an unordered_map. Then it removes every entry with a score below 10, using the erase pattern. The survivors are printed in sorted order, which is a good habit when the output is shown to a person.

Type this into the Input box:

5
alpha 12
beta 3
gamma 40
delta 7
epsilon 10

The output is:

alpha 12
epsilon 10
gamma 40
left: 3

The loop has no increment in its header. Each pass either erases and takes the new iterator, or moves forward with ++it. The erase call returns the iterator to the element after the one removed, so the loop does not skip anything. The names beta and delta have scores below 10, so they are removed. The score 10 is not below 10, so epsilon stays. The size drops from 5 to 3.

The map copy at the end uses the range constructor. It takes two iterators from the unordered_map and copies each pair into a sorted map. Now the output comes out alphabetical, and the program does not depend on the hash order.

Here is what goes wrong with the naive loop. Suppose you write for (auto it = scores.begin(); it != scores.end(); ++it) if (it->second < 10) scores.erase(it);. The erase invalidates it. The next ++it uses a dangling iterator, which is undefined behaviour. The program may crash, or it may appear to work and then fail on other data. The erase pattern avoids this.

Iterators and rehashing

A rehash can move every element into a new bucket array. When that happens, every iterator into the container can become invalid. References and pointers to an element stay valid. The standard guarantees this, because an element is not copied during a rehash. Only the iterators are affected.

The practical rule is short. Do not keep an iterator across an insert into an unordered container unless you are sure no rehash happens. If you need the element after an insert, store a key and look it up again, or store a pointer to the value. Erasing an element invalidates only iterators to that element, so the erase pattern above is safe.

This is one place where an unordered_map differs from a map. A map never rehashes, and its insert does not invalidate iterators. If your code keeps iterators around while adding keys, a map is the safer choice. Lesson 3 covers that container.

Cost of each operation

The table below gives the average and worst-case cost for the common operations. The average assumes a good hash. The worst case happens when every key lands in one bucket, which is rare in practice but important for an interview.

The row for m[key] is the same as insert, because a missing key is inserted. The row for size() is O(1), because the container tracks its own count. You can call size() in a loop condition without slowing the loop.

What happens inside: buckets and the bracket operator

An unordered_map is built from a bucket array, similar to the table in lesson 1. The bracket operator first looks for the key. If it finds it, the operator returns a reference to the stored value. If it does not, the operator creates a new pair with the key and a default-constructed value, inserts it, and returns a reference to the new value. A default-constructed int holds 0, and a default-constructed string is empty.

This explains the trap from earlier. The bracket operator always returns a reference, so it cannot say "not found". It must create the entry to give you something to return. A find call returns an iterator, which can equal end(), so it can say "not found" without creating anything.

The animation below shows how keys fill buckets as a table grows, which is the picture behind every insert in this section.

Inserting a pair with insert or emplace is an alternative to brackets. The insert function does nothing if the key exists, and it reports whether it inserted. The bracket operator overwrites the value. Choose the one whose effect you want. In add commands of the phone book, overwriting is right. In a "first occurrence wins" counter, insert is right.

Common mistakes and the messages they produce

These are the mistakes that most often end a lesson-level program early. Each one has a message that is easy to misread.

Forgetting the include. If the program uses unordered_map without #include <unordered_map>, the compiler stops early with messages like this:

error: 'unordered_map' was not declared in this scope

The fix is the include. The compiler points at the first use of the name, which is where your mistake shows.

Using a const map with brackets. Brackets can insert, so they cannot be used on a const map. The compiler reports:

error: passing 'const std::map<...>' as 'this' argument discards qualifiers

The message is long because of the template names. The words that matter are "discards qualifiers" and the name of the function being called. Use find on a const container, and at if you want an exception for a missing key.

Calling at with a missing key. The at function looks up a key and throws an exception if the key is missing. It does not insert. If the program does not catch the exception, the program stops and prints a message. Here is a complete program that triggers it.

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
 
int main() {
    unordered_map<string, int> m;
    m["a"] = 1;
    cout << m.at("zzz") << "\n";
}

Its runtime output on a Linux system with GCC is:

terminate called after throwing an instance of 'std::out_of_range'
  what():  unordered_map::at

The program exits with code 134. The first line names the exception type, and the second line says which function threw it. Read the second line to find the function, then check whether the key should have been there. If the key is optional, use find and check for end() before reading the value.

Using a custom struct without a hash. The compile error for a pair key appeared in the previous section. The same error happens for a struct key with no hash. The fix is the Point pattern: an operator== and a hash type.

Modifying the key. A pair's key is const inside the container, because changing it would move the element to a different bucket without rehashing. Assigning to a key fails to compile. The message for m.begin()->first = "b"; on a map of strings is this:

error: no match for 'operator=' (operand types are 'const std::__cxx11::basic_string<char>' and 'const char [2]')

The word const in the message is the clue. If you want to change a key, erase the old pair and insert a new one.

A debugging walkthrough

Suppose a program counts how often each word appears, and the counts are too high. Here is a method you can follow.

Start with a tiny input, such as the sentence the the. Predict the output by hand. The word the should have count 2. If the program says 3, the bug is in how the loop reads the words. Print each word as the loop reads it, and you will see the extra call.

Next, check for [] in a condition. A line like if (counts[w] == 0) ... inserts w even when it does not exist. The map then holds every word you asked about, and the count of distinct words is too large. Replace the test with count or find.

Last, check whether the output order matters. If you printed the counts directly from the container, and the test expects them sorted, the order is the problem, not the counts. Copy the pairs into a map or a vector and sort them before printing.

A simple habit prevents most of these bugs. Print size() before and after each stage of the program. A size that grows when it should not is the clearest sign of a bracket insert.

Interview angle

An interviewer may ask, "What is the difference between map and unordered_map?" A complete answer covers four points. The unordered_map uses a hash function and gives average O(1) operations. The map keeps keys sorted and gives O(log n) operations. Only the map can answer "smallest key greater than x" directly. Finally, the unordered_map needs a hash for the key type, and the map needs a comparison.

Another common question is about the bracket operator. Expect to be asked why m[key] in a condition is a bug. The answer is that it inserts a missing key, so the container grows and later code sees entries that were never added on purpose.

A related question is the stream deduplicator. An interviewer gives you a stream of user IDs and asks you to print each ID the first time it appears. Use an unordered_set and the bool from insert, as in the fragment above. The answer costs O(1) average per ID. The memory grows with the number of distinct IDs, and that is the point to raise next. If memory is limited, a bounded cache from lesson 5 forgets old IDs. That saves memory, but an ID that returns after it was forgotten would print again, so the design must say which behaviour is wanted.

Real uses

Hash containers appear almost everywhere in production code. A web server checks whether a request ID is already in a set, to reject duplicates. A word counter in a search engine maps each term to its frequency. A game stores objects by an ID in a map, so it can find an object in constant time. A compiler maps variable names to their types. In each of these, the code needs membership or lookup much more often than it needs order, which is why the hash containers are the default choice.

Practice

1. Write a program that reads a list of words and prints how many distinct words there are. Use an unordered_set. Test it with the cat and the dog, which should print 4.

2. Write a program that reads words and prints the number of times each word appears, sorted alphabetically. Use an unordered_map and copy the result into a map for printing.

3. Change the phone book so that find also prints how many times the name was added. Decide where that count lives, and explain your choice in a comment.

4. Write a function bool hasDuplicate(const vector<int>& a) that returns true if any value appears twice. Use count before insert.

5. Predict the output of this code before you run it: unordered_map<string, int> m; if (m["x"] == 0) cout << m.size();. Then run it and check.

6. Write a program that reads a list of numbers and prints the first number that appears twice. Print none if no number repeats. Use an unordered_set.

7. Rewrite the erase loop so it removes every key that starts with the letter a. Use the same iterator pattern.

8. Create a struct Pair with two int fields, supply operator== and a hash, and store five pairs in an unordered_set. Print the size after inserting one pair twice.

9. Explain why find returns an iterator but m[key] returns a reference to the value. Give one case where each is the right choice.

10. The walker program prints revisited: yes for RRUULLDDRR. Predict whether it prints yes for RRRR and explain why.

11. Write a program that reads a list of numbers and prints the distinct values in the order they first appear. Use an unordered_set to skip repeats, and a vector to keep the order.

12. Measure how often a loop calls size() in the erase example. Explain why the count does not change the complexity of the loop.

What you now know

• An unordered_map stores unique keys with values, and an unordered_set stores unique values, both with average O(1) operations.
• find and count only read. The bracket operator m[key] inserts a missing key with a default value.
• Use count for yes-or-no checks, and find when you also need the value.
• An unordered_set size gives the number of distinct values, and a copy into a vector followed by sort gives you ordered output.
• The order of elements in a hash container is not defined, and it can change after a rehash. Sort before you print.
• A custom key needs an operator== and a hash type. A missing hash shows up as a long error that mentions hash.
• To erase while looping, use the iterator returned by erase.
• Rehashing invalidates iterators, but not references to elements.

The next lesson covers map and set, the sorted versions of these containers. They trade a little speed for order, and that order unlocks questions a hash table cannot answer.