std::map and std::unordered_map

A vector finds things by position; a map finds things by a key you choose, such as a name or a letter. By the end of this lesson you can build a map, count with it, look up keys without changing the map, and print every entry in sorted order.

Keys and values

A map stores entries: each entry pairs a key with a value, and each key appears at most once. The two type arguments in the angle brackets are the key type and the value type.

#include <map>

std::map<std::string, double> price;
price["tea"] = 2.5;          // insert a new entry
price["cake"] = 4.0;
price["tea"] = 3.0;          // same key: overwrite, still one entry

std::cout << price["tea"] << "\n";    // 3
std::cout << price.size() << "\n";    // 2  (keys, not assignments)
price.erase("cake");                  // size is now 1

C++ ships two maps with the same operations. std::map (header <map>) keeps its keys sorted; lookup costs O(log n). std::unordered_map (header <unordered_map>) is a hash table: O(1) on average, but its keys come out in no particular order.

operator[] inserts missing keys

Reading m[key] for a key that is not there does not fail. It inserts the key with a default value (0 for numbers, "" for strings) and hands that value back. That makes counting a one-liner:

std::map<char, int> freq;
std::string letters = "banana";
for (char ch : letters) {
    freq[ch]++;          // first 'n': inserted as 0, then 1
}
// freq now holds a -> 3, b -> 1, n -> 2

The same behaviour is a trap when you only want to ask a question. if (price["milk"] > 0) creates a milk entry while checking for it, and price.size() grows by one. For a read-only check use count (returns 0 or 1) or find:

if (price.count("milk") == 0) {
    std::cout << "no milk\n";
}
auto it = price.find("tea");          // an iterator to the entry, or price.end()
if (it != price.end()) {
    std::cout << it->first << " costs " << it->second << "\n";   // tea costs 3
}

Every entry is a std::pair: .first is the key, .second is the value. Through an iterator you write ->first and ->second.

Iterating: sorted for free

A range-for over a map visits each entry as a pair. With std::map the order is sorted by key, guaranteed:

for (const auto& entry : freq) {
    std::cout << entry.first << "=" << entry.second << "\n";
}

Output:

a=3
b=1
n=2

Change the declaration to std::unordered_map<char, int> and the same loop may print n=2 first. When the output must be in order, choose std::map.

Sorted means the order of < on the key type. For std::string that compares character codes one position at a time, so every uppercase letter sorts before every lowercase one, and digits compare as characters, not numbers:

Common mistakes

• Using std::unordered_map. The counts are right but the lines come out in hash order, so input zebra yak xray may not start with xray.
• Reading one line with std::getline. Words on the second and later lines are never counted; read with >> in a loop until input ends.
• Printing how many words were read instead of how many keys exist. a a a has one distinct word, not three.
• Changing the words. Lowercasing merges Apple and apple, which must stay separate keys with their own counts.

Your exercise

Count how often each word occurs, then report how many distinct words there are and each word's count in sorted order. The starter reads nothing yet and declares an empty map for you; you write the reading loop, the counting, and the printing. The most likely slip is reaching for unordered_map and getting the right counts in the wrong order.