Maps: Looking Things Up by Name

Finding a contact by name in chapter 14 meant looping over the whole book and comparing every name. It worked, and it’s what a vector is for: things in order, looked at one at a time.

But that isn’t how you think about a phone book. You don’t scan it. You look up a name and get a number.

A map

#include <map>

std::map<std::string, int> ages;

ages["Ada"] = 36;
ages["Alan"] = 41;
ages["Grace"] = 29;

std::cout << "Ada is " << ages["Ada"] << '\n';

Ada is 36

std::map<std::string, int> holds pairs: a std::string key and an int value. Two types in the angle brackets this time, and the same slot-filling idea as vector<int>: key type first, value type second.

The square brackets look like a vector’s and behave completely differently. A vector’s index is a position, must be a number, and must already exist. A map’s key is a name, can be nearly any type, and doesn’t have to exist yet, since writing to a key that isn’t there creates it.

No push_back. Assigning to a key is how things get in.

Reading it back out

for (const auto& [name, age] : ages) {
    std::cout << "  " << name << " -> " << age << '\n';
}

  Ada -> 36
  Alan -> 41
  Grace -> 29

That [name, age] is a structured binding, and it is one of C++17’s nicest additions. Each element of a map is a key-value pair, and the brackets unpack it into two named variables in one go. Without it you’d be writing .first and .second and remembering which was which.

const auto& is chapter 12’s rule plus chapter 3’s auto: don’t copy, don’t modify, and don’t make me write out the type. This exact line, for (const auto& [k, v] : some_map), is worth memorising as a shape.

They came out sorted by name, and they will every time. A std::map keeps its keys in order, which is free if you want it and a small cost if you don’t. There is another container, std::unordered_map, that skips the sorting and is faster for large collections; it works the same way and you can look it up when you need it.

Asking without adding

count tells you how many entries have that key, which for a map is 0 or 1:

if (ages.count("Ada") == 1) {
    std::cout << "Ada is " << ages["Ada"] << '\n';
}

count Ada:    1
count Nobody: 0

Reading count never changes the map. Use it whenever you’re not certain the key exists, and treat [] as a thing you do to keys you know about or intend to create.

There’s also find, which behaves like chapter 13’s, returning a marker you compare against end(). count is easier and enough here.

The trap, used on purpose

The auto-creating [] is exactly what you want for counting:

std::map<std::string, int> counts;

counts["the"]++;
counts["the"]++;
counts["fox"]++;

the=2 fox=1

The first counts["the"]++ finds no such key, creates it with 0, and adds one. Every later one just adds one. No “have I seen this word before” check, no special case for the first time. Three characters do the whole job.

Counting things is most of what maps get used for, and this line is why.

Removing, and holding more than a number

erase takes a key and removes that entry:

ages.erase("Alan");

Erasing a key that isn’t there is not an error. It removes nothing and carries on, which is usually what you want.

The value type can be anything, including a container:

std::map<std::string, std::vector<std::string>> groups;

groups["mathematicians"].push_back("Ada");
groups["mathematicians"].push_back("Alan");
groups["sailors"].push_back("Grace");

mathematicians: 2
sailors: 1

Read that first push_back slowly, because a lot happens in one line. groups["mathematicians"] finds no such key, creates one with an empty vector as its value, and hands that vector back, and then push_back puts "Ada" in it. The same auto-creation as before, doing more work.

A map of vectors is how you group things: one key, many values under it. It looks alarming written out and it is the natural shape for “all the people in each department”, or “all the words starting with each letter”.

Vector or map?

Both hold a collection. The question is how you get things out again.

The tell is the question you keep asking. “What’s the third item” is a vector. “What’s Ada’s number” is a map. This chapter’s project needs both, one after the other, because the questions change halfway through.

One more difference worth knowing: a map has no duplicate keys. Assign to the same key twice and the second wins, silently. If your counting program is losing entries, that’s usually why.

11 different words
  the: 4
  dog: 2
  fox: 2
  and: 1
  barks: 1

std::map<std::string, int> counts;
std::string word;
while (in >> word) {
    counts[word]++;
}

struct Entry {
    std::string word;
    int count;
};

bool by_count(const Entry& a, const Entry& b) {
    return a.count > b.count;
}