map: Each Key Holds a Value, and the Keys Stay Sorted

Kenji's café gives a loyalty stamp for every visit. At each visit, the counter asks how many stamps this customer has now. At closing time, Kenji wants every customer and their stamps, in alphabetical order. A vector of (name, stamps) pairs answers each question with a scan of the whole list, Module 2's find. This lesson gives Kenji a container that does both jobs while the customers walk in.

A key and its value

A map is a container of pairs, like Module 1's pair. The first part of each pair is its key, what you look things up by: here, a customer's name. The second part is its value, what the key holds: here, a number of stamps. A map holds each key at most once, and it keeps its pairs sorted by key.

An array can answer "how many stamps?" too, but only by a number: stamps[3], never stamps["maria"]. A map's key can be a name, a word or any type that < can compare. Here are Kenji's stamps after seven visits, drawn twice.

Both pictures hold the same six pairs. The table is what a walk through the map gives back. The tree is how the map stores them, and the next section opens it. So stamps["bob"] names Bob's value, 2, and Bob's pair sits between Amara's and David's in key order.

Inside: Module 8's tree, with a pair in every node

Module 8 kept a set in a balanced binary search tree, where a search walks down one level at a time. A map is that same tree. The only change is what a node holds: a key and its value together, as one pair. The tree is ordered by the key alone, and the value rides along.

The C++ standard names no tree. It promises only O(log n) steps to find, add or erase a key, where n is the number of keys. GCC's library, libstdc++, keeps a red-black tree, as it does for a set. The pictures in this module leave the colours out. So the names stay sorted because the tree keeps them sorted, not because anything sorts them at the end.

Watch the stamps arrive

Here is Kenji's first morning, one call per visit: maria, bob, zara, kenji, bob again, amara and david. Then the counter looks up zara and carol with find, and finally reads carol with []. Every picture is the real shape GCC 12's library built, printed from a run on Compiler Explorer. The values are in the notes and in the table under the widget.

Bob's second visit walked down to his node and only raised his count. find("carol") fell off the tree below david and changed nothing. The last step is this lesson's trap: a read with [] added carol with 0 stamps, and the tree turned to make room. So a map grows only when a new key is stored, and [] stores one even when you only meant to read.

The syntax you need on day one

#include <map>

map<K, V> m;                      an empty map from K keys to V values
map<K, V> m{{k1, v1}, {k2, v2}};  a map made from a list of pairs
m[k] = v;                         store v under k, or overwrite k's value
m[k]++;                           add 1 to k's value; a missing k starts at 0
m.count(k)                        1 if k is there, 0 if not; adds nothing
m.find(k)                         an iterator to k's pair, or m.end()
it->first   it->second            the key and the value of that pair
m.erase(k);                       remove k and its value, if k is there
m.size()                          how many keys
for (const auto& [k, v] : m)      every pair, in key order

multimap<K, V> mm;                the same, but a key may repeat; no []

So everyday map code names a key every time, and the map decides where its pair lives.

m[k] stores a value, and a missing key starts at zero

m[k] = v stores v under k. When k is new, the map first adds it with the value type's zero, written V() in C++. That zero is 0 for an int and an empty string for a string. Then the = writes over the zero. m[k]++ and m[k] += 2 work the same way, so counting needs no setup.

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

int main() {
    map<string, int> stamps;
    stamps["maria"] = 3;
    stamps["bob"]++;
    stamps["bob"]++;
    stamps["maria"] += 2;
    cout << "maria " << stamps["maria"] << ", bob " << stamps["bob"] << '\n';

    map<string, string> note;
    note["kenji"] += "tea";
    note["kenji"] += ", no sugar";
    cout << "kenji: " << note["kenji"] << '\n';
    cout << stamps.size() << " customers, " << note.size() << " note\n";
    return 0;
}

maria 5, bob 2
kenji: tea, no sugar
2 customers, 1 note

Bob's first ++ found no bob, so the map added him at 0 and raised him to 1. Kenji's note started as an empty string, and += added the words to it. Two customers and one note: every key was added once, however often it was touched. So m[k]++ is a whole counting program, with no check and no starting value.

count and find: look without adding

m.count(k) says how many pairs have the key k, which on a map is 1 or 0. m.find(k) returns an iterator to k's pair, or m.end() when k is missing. Through that iterator, it->first is the key and it->second the value. Neither call ever adds a key.

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

int main() {
    map<string, int> stamps{{"bob", 2}, {"maria", 5}, {"zara", 1}};
    cout << stamps.count("zara") << ' ' << stamps.count("kenji") << '\n';

    auto it = stamps.find("maria");
    if (it != stamps.end()) {
        cout << it->first << " has " << it->second << " stamps\n";
    }
    if (stamps.find("kenji") == stamps.end()) {
        cout << "kenji is not a customer yet\n";
    }
    cout << "still " << stamps.size() << " customers\n";
    return 0;
}

1 0
maria has 5 stamps
kenji is not a customer yet
still 3 customers

The map still holds 3 customers after asking about kenji twice. Compare find's answer with end() before you read it->second; lesson 02 shows what reading end() printed in one run. So use count for a plain yes or no, and find when you also want the value.

The trap: reading m[k] adds k

m[k] cannot tell a read from a write. When k is missing, it adds k with a zero value first, even inside a cout. So a map you only read can still grow.

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

int main() {
    map<string, int> stamps{{"bob", 2}, {"maria", 5}};
    cout << "size before: " << stamps.size() << '\n';
    cout << "carol has " << stamps["carol"] << " stamps\n";
    cout << "size after:  " << stamps.size() << '\n';
    cout << "count(\"carol\") is now " << stamps.count("carol") << '\n';
    return 0;
}

size before: 2
carol has 0 stamps
size after:  3
count("carol") is now 1

One read printed a believable 0 and added carol for good. The size went from 2 to 3, and count now finds her. Kenji's closing list would show a customer who never came. So when you only want to ask, ask with count or find.

The walk in key order

A range-for walks a map from the smallest key to the largest, one pair at a time. Each pair has two parts: p.first, the key, and p.second, the value. Module 1's structured binding names both parts at once, so [name, count] reads better than .first and .second.

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

int main() {
    map<string, int> stamps;
    stamps["zara"] = 1;
    stamps["amara"] = 4;
    stamps["kenji"] = 2;

    for (const auto& p : stamps) {
        cout << p.first << ": " << p.second << '\n';
    }

    cout << "again:";
    for (const auto& [name, count] : stamps) {
        cout << ' ' << name << '=' << count;
    }
    cout << '\n';
    return 0;
}

amara: 4
kenji: 2
zara: 1
again: amara=4 kenji=2 zara=1

The keys went in as zara, amara and kenji and came out in alphabetical order, in both loops. const auto& reads each pair where it is, without a copy. So every walk of a map is a walk in key order.

erase by key

m.erase(k) removes k together with its value, and returns how many pairs it removed. On a map that is 1 or 0. Erasing a key that is not there does nothing, with no error.

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

int main() {
    map<string, int> stamps{{"bob", 2}, {"maria", 5}, {"zara", 1}};
    cout << "erase(\"bob\") removed " << stamps.erase("bob") << '\n';
    cout << "erase(\"carol\") removed " << stamps.erase("carol") << '\n';
    for (const auto& [name, count] : stamps) {
        cout << name << ' ' << count << '\n';
    }
    return 0;
}

erase("bob") removed 1
erase("carol") removed 0
maria 5
zara 1

Bob's pair is gone, and the walk no longer meets him. The 0 for carol says she was never there. So erasing a missing key is safe, and its answer tells you whether anything went.

Each key once

A map never holds two pairs with the same key. A second m[k] = v finds the first pair and overwrites its value. So the newest write wins.

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

int main() {
    map<string, string> phone;
    phone["maria"] = "555-0101";
    phone["bob"] = "555-0102";
    phone["maria"] = "555-0188";
    cout << phone.size() << " names\n";
    for (const auto& [name, number] : phone) {
        cout << name << ": " << number << '\n';
    }
    return 0;
}

2 names
bob: 555-0102
maria: 555-0188

Maria's old number is gone, and the map still holds two names. So a map suits any job where each key has one current value, like a phone number that changed.

multimap: the cousin that keeps repeated keys

Sometimes one key needs several values: Bob has a home number and a work number. A multimap keeps every pair, repeated keys included, still sorted by key. It lives in the same header and has the same insert, count, find and erase. Its count(k) says how many pairs have the key k.

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

int main() {
    multimap<string, string> phones;
    phones.insert({"bob", "555-0102"});
    phones.insert({"maria", "555-0101"});
    phones.insert({"bob", "555-0177"});
    for (const auto& [name, number] : phones) {
        cout << name << ": " << number << '\n';
    }
    cout << "bob has " << phones.count("bob") << " numbers, " << phones.size() << " in all\n";
    return 0;
}

bob: 555-0102
bob: 555-0177
maria: 555-0101
bob has 2 numbers, 3 in all

Both of Bob's numbers stayed, side by side, in the order they arrived. A multimap has no [], because phones["bob"] could not know which of Bob's numbers you mean.

multimap<string, string> phones;
phones["bob"] = "555-0102";

GCC 12 stops at the runner's flags with error: no match for 'operator[]' (operand types are 'std::multimap<std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> >' and 'const char [4]'). Lesson 02 shows equal_range, which hands you every value of one key. So reach for a multimap when a key needs several values, and for a map when one is enough.

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

int main() {
    map<string, int> price;
    price["mango"] = 120;
    price["banana"] = 60;
    price["apple"] = 180;
    price["guava"] = 80;

    cout << price.size() << " fruits on the board:\n";
    for (const auto& [fruit, taka] : price) {
        cout << fruit << ' ' << taka << '\n';
    }
    return 0;
}

4 fruits on the board:
apple 180
banana 60
guava 80
mango 120

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

int main() {
    map<string, int> stamps;
    for (string name : {"maria", "bob", "zara", "kenji", "bob", "amara", "david"}) {
        stamps[name]++;
    }

    auto it = stamps.find("bob");
    if (it != stamps.end()) {
        cout << "bob has " << it->second << " stamps\n";
    }

    cout << "closing list:\n";
    for (const auto& [name, count] : stamps) {
        cout << "  " << name << ' ' << count << '\n';
    }
    return 0;
}

bob has 2 stamps
closing list:
  amara 1
  bob 2
  david 1
  kenji 1
  maria 1
  zara 1

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

int main() {
    map<string, int> calling_code{
        {"bangladesh", 880}, {"brazil", 55}, {"japan", 81},
        {"kenya", 254}, {"peru", 51}, {"spain", 34}};

    for (string country : {"japan", "chile", "kenya"}) {
        auto it = calling_code.find(country);
        if (it != calling_code.end()) {
            cout << country << ": +" << it->second << '\n';
        } else {
            cout << country << ": not found\n";
        }
    }
    cout << calling_code.size() << " countries in the book\n";
    return 0;
}

japan: +81
chile: not found
kenya: +254
6 countries in the book

#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>
using namespace std;

int main() {
    vector<pair<string, string>> cards{
        {"bob", "555-0102"}, {"zara", "555-0144"}, {"bob", "555-0177"}, {"amara", "555-0110"}};

    map<string, string> latest;
    multimap<string, string> every;
    for (const auto& [name, number] : cards) {
        latest[name] = number;
        every.insert({name, number});
    }

    cout << "map keeps " << latest.size() << ":\n";
    for (const auto& [name, number] : latest) {
        cout << "  " << name << ' ' << number << '\n';
    }
    cout << "multimap keeps " << every.size() << ":\n";
    for (const auto& [name, number] : every) {
        cout << "  " << name << ' ' << number << '\n';
    }
    return 0;
}

map keeps 3:
  amara 555-0110
  bob 555-0177
  zara 555-0144
multimap keeps 4:
  amara 555-0110
  bob 555-0102
  bob 555-0177
  zara 555-0144

map<string, int> stamps{{"bob", 2}, {"maria", 5}};
if (stamps["zara"] == 0) {
    cout << "zara has no stamps yet\n";
}
for (const auto& [name, count] : stamps) {
    cout << name << ' ' << count << '\n';
}

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

int main() {
    map<string, int> stamps;
    stamps["maria"]++;
    cout << stamps.size() << '\n';
    return 0;
}

map<int, int> guests{{12, 4}, {15, 2}};
auto it = guests.find(12);
it->first = 13;

map<string, int> course;
course["soup"] = 1;
course["rice"] = 2;
course["sweet"] = 3;
for (const auto& [dish, number] : course) {
    cout << dish << '\n';
}

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

int main() {
    map<char, int> letters;
    string word = "banana";
    for (char c : word) {
        letters[c]++;
    }
    for (const auto& [c, n] : letters) {
        cout << c << ' ' << n << '\n';
    }
    return 0;
}

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 0;
    cin >> n;
    map<string, int> price;   // item name -> its price in taka
    for (int i = 0; i < n; i++) {
        string item;
        int taka = 0;
        cin >> item >> taka;
        // Remember that item costs taka.
    }

    int m = 0;
    cin >> m;
    long long total = 0;   // the day's total can pass 2147483647
    for (int i = 0; i < m; i++) {
        string item;
        int qty = 0;
        cin >> item >> qty;
        // Print the cost of this order, and add it to total.
    }

    // Print the day's total.

    return 0;
}

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

int main() {
    int n;
    cin >> n;
    map<string, int> first;   // name -> score in the first round
    for (int i = 0; i < n; i++) {
        string name;
        int score;
        cin >> name >> score;
        first[name] = score;
    }
    int m;
    cin >> m;
    map<string, int> second;   // name -> score in the second round
    for (int i = 0; i < m; i++) {
        string name;
        int score;
        cin >> name >> score;
        second[name] = score;
    }

    // Walk first in key order. For every name that second also holds,
    // print the name and both scores. Print none if nobody sat both.

    return 0;
}

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

int main() {
    int n;
    cin >> n;
    map<string, int> stamps;
    for (int i = 0; i < n; i++) {
        string name;
        cin >> name;
        stamps[name]++;
    }

    // Walk stamps once. Keep the most stamps seen so far, and the names
    // that have that many. Then print the most stamps on one line, and
    // those names on the next, separated by single spaces.

    return 0;
}

Next, lesson 02 goes through every map and multimap operation, one by one, each with its cost.