Maps and sets

Introduction

Searching a vector for a value means looking at each element. When you need to find things by name or check whether you have seen something, maps and sets do the job far faster, and the code says what it means.

How it works

map<K, V> stores pairs, sorted by key:

A trap. Just reading m[k] adds the key if it was not there, with a default value. Use count or find to check for a key without adding it.

Looping gives each entry as a pair, with .first as the key and .second as the value, and the keys come out sorted.

set<T> stores values once each, sorted:

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

int main() {
    set<int> seen = {5, 1, 5, 3};
    seen.insert(2);
    cout << seen.size() << " " << seen.count(5) << endl;
    for (int x : seen) {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

Unordered versions. unordered_map and unordered_set use a hash table. They are usually faster, but their order is unpredictable. Use the ordered versions when you need sorted output, and the unordered ones when you only need speed.

Syntax

map<string, int> ages;
ages["Mitu"] = 21;
if (ages.count("Rafi")) { ... }
for (const auto& item : ages) {
    cout << item.first << item.second;
}

Example

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

int main() {
    map<string, int> counts;
    counts["pen"] = 2;
    counts["book"]++;
    counts["pen"]++;
    cout << counts.size() << " " << counts.count("bag") << endl;
    for (const auto& item : counts) {
        cout << item.first << " " << item.second << endl;
    }
    return 0;
}

Line by line

1. counts maps text to whole numbers.
2. counts["pen"] = 2 adds a pair.
3. counts["book"]++ creates book with 0, and then adds 1.
4. count("bag") is 0, and it does not add the key.
5. The loop prints the pairs in key order, so book comes before pen.

Expected result

2 0
book 1
pen 3

In the real world

Maps count words, cache results and hold settings. Sets remove duplicates and track what has already been visited. Competitive programmers and software engineers use these two containers constantly.

Common mistakes

• Reading m[k] to test for a key, which adds it.
• Expecting a set to keep insertion order. It is sorted.
• Assuming an order from unordered_map.
• Changing a map's key through an iterator. Keys cannot be changed.

Best practices

• Use count or find to test whether a key exists.
• Use map when you need sorted output.
• Loop with const auto& to avoid copying each pair.

Summary

map stores sorted pairs, and set stores unique sorted values. m[k] creates missing keys, so use count to check. The unordered versions are faster, but have no order.

Mark lesson complete