Welcome to Programming and Data Structures

You may have noticed that while looping through key-value pairs in our word count example, the order of the words printed was not the same as the order they were added. This is because the map container keeps its elements in sorted order based on the keys. (And, as with a set, this means that whatever type is used as the key must define the < operator for comparison.)

If we do not care about the order of elements and want potentially faster access times, we can use an unordered_map. An unordered_map is similar to a map but does not keep its elements in any particular order. Instead, it uses a structure called a hash table internally that provides for extremely fast access.

The syntax for using an unordered_map is the same as for a map. You declare it with the key and value types, and you use the same methods like .insert() and .at() to add and access elements.

If you loop through the elements of an unordered_map, the order in which you get the elements is not defined. The order they come out will not necessarily match the order they were added, nor will it be sorted. The ordering of all the elements may even change if you add or remove elements from the map!

Here is a modified version of the previous word count program that uses an unordered_map instead of a map. Notice that nothing but the container type (and include) has changed.

We can also make an unordered_set in the same way to store unique values without any particular order. The syntax and usage is the same as for a set, you just replace set with unordered_set.

Because unordered containers do not try to sort their contents, we do not need to provide a way to compare elements using the < operator. However, they do require a way to compute a hash for the key type. A hash function is a function that takes a value and produces a fixed-size number (the hash) that represents that value.

The standard types in C++ have built-in hash functions, so you can use them directly as keys in an unordered_map or elements in an unordered_set. But if you want to use a custom data type as a key or element, you will need to provide your own hash function. We will save that for when we learn about how hash tables work.