Map

A map is a set of keys where each key carries a value with it, such as a number and how many times it occurred. The keys are kept sorted and found in O(\log n), exactly as in a set; the set page shows how.

In C++

A map<K, V>, in the header <map>, has keys of type K and values of type V. m[key] gives the value of a key. If the key is missing, m[key] first adds it with the value 0 (or an empty string). So cnt[x]++ counts: the first time a number comes, it appears with 0 and becomes 1.

This program reads n, then n numbers, and prints each number with its count:

6
5 2 8 5 2 5

#include <iostream>
#include <map>
using namespace std;

int main() {
    int n;
    cin >> n;
    map<int, int> cnt;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;                               // a new number starts at 0
    }
    for (auto& [x, c] : cnt)                    // keys in increasing order
        cout << x << ' ' << c << '\n';
}

Each key and its value form a pair: .first is the key and .second the value, and auto& [x, c] names the two. count, find, erase and lower_bound work on the keys, as in a set.

The map cnt is empty.

cnt[5] adds the new key 5 with 0, in its sorted place, and ++ makes it 1.

cnt[2] adds the new key 2 with 0, in its sorted place, and ++ makes it 1.

cnt[8] adds the new key 8 with 0, in its sorted place, and ++ makes it 1.

5 is already a key, so cnt[5]++ raises its count to 2.

2 is already a key, so cnt[2]++ raises its count to 2.

5 is already a key, so cnt[5]++ raises its count to 3.

cnt[7] > 0 only reads, but 7 is missing, so cnt[7] adds it with 0.

1/8

Fig. 1. The keys sit in a binary search tree, as in a set, and each key carries its count beside it. cnt[key] adds a missing key with 0, even when the code only reads it.

unordered_map

unordered_map has the same calls except lower_bound and upper_bound, and keeps no order. It is a hash table: each call takes $O(1)$ on average, but tests can be built so that many keys land in the same bucket, and then every call takes $O(n)$. Use map by default.

Examples of use

Counting how many times each value occurs: cnt[x]++ for every value, then one loop over the map reads the counts in key order.

Giving numbers to names: when the vertices of a graph come as names, id[name] gives each new name the next free number, and the rest of the program works with numbers.

Similar structures

• A set keeps the keys alone, with no value.

• An array indexed by the key does the same in $O(1)$ when the keys are non-negative integers up to about 10^6.

Practice