map, set and unordered_map

Finding a product's price by name in a vector means comparing the name with every element in turn. For a million products, that is a million comparisons.

Think of a phone book. Its names are in alphabetical order, so you find a person's number quickly: you open the book near the right letter instead of reading it from the first line. The name here is the key, and the number is the value.

std::map works the same way: it stores key-value pairs in key order and finds a value by its key without a scan:

#include <iostream>
#include <map>
#include <string>

int main() {
    std::map<std::string, int> stock;
    stock["pear"] = 4;
    stock["apple"] = 7;
    stock["pear"] = 2;
    std::cout << stock.size() << ' ' << stock["pear"] << '\n';  // 2 2
    for (const auto& item : stock) {
        std::cout << item.first << '=' << item.second << ' ';  // apple=7 pear=2
    }
}

In std::map<std::string, int>, the first type is the type of the key, and the second is the type of the value. The line stock["pear"] = 4 puts a pair with the key "pear" into the container. Keys do not repeat: the second assignment to the key "pear" replaced the value, so there are still two elements.

The elements of a std::map are ordered by key, so apple is printed before pear, even though it was added later. Each element is a pair: item.first holds the key, and item.second holds the value. The variable item is declared as const auto&: the elements are not copied, and the compiler deduces the type.

This is where the phone book and std::map part ways. A book may list two people with the same name, but in a std::map each key occurs only once.

Lookup without inserting

The [] operator returns the value for a key, and if the key is missing, it adds the key first. The new value is initialized like int x{}: 0 for an int, an empty string for a std::string. So even reading a missing key increases the size. To check for a key without adding anything, use the contains (C++20) and count functions:

std::map<std::string, int> stock{{"apple", 7}};
std::cout << stock.contains("kiwi") << ' ' << stock.count("apple") << '\n';  // 0 1
std::cout << stock["kiwi"] << '\n';  // 0
std::cout << stock.size() << '\n';  // 2

Initial pairs are written in curly braces: {{"apple", 7}}. The count function returns how many elements in the container have the given key. For a std::map, that is 0 or 1.

set and unordered_map

std::set from the <set> header stores only keys, with no values. Its keys are unique and ordered, and inserting the same key again with insert changes nothing:

std::set<int> seen;
seen.insert(3);
seen.insert(1);
seen.insert(3);
std::cout << seen.size() << ' ' << seen.contains(1) << '\n';  // 2 1

std::unordered_map from the <unordered_map> header is built as a hash table: from a key, it computes where the element lies. On average, lookup in it is faster than in a std::map, and the functions are the same: [], contains, count. But its keys are not ordered, and the standard does not define the order of traversal.

Common mistake

A function takes a std::map by const reference and reads a value with []:

#include <map>
#include <string>

int price(const std::map<std::string, int>& stock) {
    return stock["apple"];  // ✗
}

error: no viable overloaded operator[] for type 'const std::map<std::string, int>' (aka 'const map<basic_string<char>, int>')

The [] operator may add a key, which changes the container, so a const std::map does not have it. Inside such a function, check the key with contains and read the value with at: stock.at("apple") adds nothing. For a missing key, at stops the program with an error, so the check comes first.

Key points

• std::map stores key-value pairs ordered by key, and each key occurs in it once.
• [] adds a missing key, while contains and count check for a key without adding anything.
• std::set stores only unique keys, in order.
• std::unordered_map is faster at lookup on average, but the order of its keys is not defined.