What a dictionary is
A dictionary stores key-value pairs. You look up a value by its key, the way you look up a phone number by a name, instead of by a numeric position as in a vector. Each key appears at most once and maps to exactly one value.
C++ calls its everyday dictionary std::unordered_map. It is a hash map: the keys are run through a hash function, which lets the map find a key in constant time on average, however many entries it holds. The price is that the entries have no useful order. If you loop over the map, the order you get is unspecified and can differ between implementations. Use std::map when you need keys in sorted order, at the cost of slower lookups.
Declaring one
Include the header and name the key type and value type in angle brackets:
#include <unordered_map>
#include <string>
unordered_map<string, int> scores;
Here the keys are string values and the values are int values. A map declared like this starts empty. The two types do not have to differ: unordered_map<string, string> and unordered_map<int, double> are both fine. Most built-in types and string work as keys out of the box.
Adding entries
The square-bracket operator takes the key. Assigning to it creates the entry when the key is new:
scores["Alice"] = 95;
scores["Bob"] = 87;
scores["Charlie"] = 72;
After these three lines the map holds three pairs. Assigning to a key that already exists replaces its value, so a key never appears twice.
Starting with values
If you already know the contents, an initializer list builds the map in one statement. Each pair of braces is one key and its value:
unordered_map<string, int> ages = {
{"Alice", 25},
{"Bob", 30}
};
cout << ages["Alice"]; // 25
cout << ages.size(); // 2
The call ages.size() reports how many pairs the map holds.
One thing to watch: [] creates missing keys
Reading scores["Zed"] when "Zed" is not in the map does not fail. The bracket operator inserts a new entry with a default value, 0 for an int, and returns it. A lookup that was meant only to read has quietly grown the map. The next lessons cover safe ways to look up values, but keep this in mind now: brackets are for both reading and writing.
The exercise, step by step
The task is to build a map named scores with three students.
- Declare the map. Write the type
unordered_map<string, int>, then the namescores. With no initializer, it starts empty. - Add the three entries with the bracket operator, each on its own line: "Alice" gets 95, "Bob" gets 87 and "Charlie" gets 72. Because none of these keys exists yet, each assignment inserts a new pair.
unordered_map<string, int> scores;
scores["Alice"] = 95;
scores["Bob"] = 87;
scores["Charlie"] = 72;
The map now has three entries, and scores.size() is 3. The same map could be built with an initializer list, as in the earlier example. The bracket form is what you will use when entries arrive one at a time, for example while reading input.
Common mistakes
- Forgetting the template arguments.
unordered_map scores;does not compile, because the map needs both a key type and a value type. - Using the wrong key type. A map declared with
stringkeys cannot be indexed with a number. - Expecting insertion order. Do not rely on the order of iteration. If the order matters, sort the keys or use
map. - Using a missing key without noticing. The default value is inserted and returned, which hides typos in key names.
- Missing the include. The code needs
<unordered_map>.
Key takeaways
unordered_map<K, V>maps unique keys of typeKto values of typeVwith fast average-time lookup.m[key] = valueadds or replaces an entry, and an initializer list builds a map in one step.- Iteration order is unspecified.