8. Maps & Sets

What & why

A vector answers "what's at position 3?". A map answers "what's the value for key "Ada"?" — phone books, word counts, config settings, caches. A set answers "have I seen this before?" and keeps only unique values.

The standard library gives you two flavors of each:

Container	Ordered?	Lookup	Header
std::map<K, V>	yes, sorted by key	O(log n)	<map>
std::unordered_map<K, V>	no	O(1) average	<unordered_map>
std::set<T>	yes	O(log n)	<set>
std::unordered_set<T>	no	O(1) average	<unordered_set>

Default to unordered_map / unordered_set for speed; use map / set when you need sorted output or ordered range queries.

std::map basics

#include <map>
#include <string>

std::map<std::string, int> ages{
    {"Ada", 36},
    {"Alan", 41},
};

ages["Grace"] = 85;          // insert or overwrite
ages["Ada"] = 37;            // overwrite
std::cout << ages["Alan"];   // 41

ages.size();                 // 3
ages.erase("Alan");          // remove by key

The [] trap

operator[] inserts a default value if the key is missing:

std::cout << ages["Nobody"];   // prints 0 — and "Nobody" is now IN the map!

To look up without inserting:

if (ages.contains("Nobody")) { ... }            // C++20

auto it = ages.find("Ada");
if (it != ages.end()) {
    std::cout << it->first << " is " << it->second << '\n';
}

int a = ages.at("Ada");       // throws std::out_of_range if missing

[] also doesn't work on a const map. Use find or at.

Iterating with structured bindings

Each element is a std::pair<const Key, Value>:

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

A std::map iterates in sorted key order. An unordered_map iterates in no particular order.

Counting things

The classic word count:

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> counts;
    std::string word;
    while (std::cin >> word) {
        ++counts[word];          // [] default-inserts 0 — perfect here
    }
    for (const auto& [w, n] : counts) {
        std::cout << w << ": " << n << '\n';
    }
}

To print the most frequent words, copy into a vector and sort:

#include <algorithm>
#include <vector>

std::vector<std::pair<std::string, int>> sorted(counts.begin(), counts.end());
std::ranges::sort(sorted, [](const auto& a, const auto& b) {
    return a.second > b.second;          // descending by count
});

Grouping: a map of vectors

std::map<char, std::vector<std::string>> by_letter;
for (const std::string& name : {"Ada", "Alan", "Grace", "Guido"}) {
    by_letter[name[0]].push_back(name);
}
// 'A' → {"Ada", "Alan"}, 'G' → {"Grace", "Guido"}

Inserting without overwriting

auto [it, inserted] = ages.insert({"Ada", 99});
if (!inserted) {
    std::cout << "Ada already there with " << it->second << '\n';
}

ages.try_emplace("Linus", 54);    // inserts only if absent
ages.insert_or_assign("Ada", 38); // always sets

Sets

#include <set>
#include <unordered_set>

std::set<int> s{5, 1, 3, 3, 1};    // {1, 3, 5} — sorted, duplicates dropped
s.insert(4);
s.erase(1);
s.contains(3);                      // true (C++20)
s.size();                           // 3

std::unordered_set<std::string> seen;
for (const auto& w : words) {
    if (!seen.insert(w).second) {   // .second is false if it was already present
        std::cout << "duplicate: " << w << '\n';
    }
}

Set algebra

The <algorithm> set operations work on sorted ranges (e.g. std::set):

#include <algorithm>
#include <iterator>

std::set<int> a{1, 2, 3, 4};
std::set<int> b{3, 4, 5};
std::vector<int> out;

std::ranges::set_intersection(a, b, std::back_inserter(out));  // {3, 4}
out.clear();
std::ranges::set_union(a, b, std::back_inserter(out));         // {1, 2, 3, 4, 5}
out.clear();
std::ranges::set_difference(a, b, std::back_inserter(out));    // {1, 2}

Keys must be comparable or hashable

• std::map / std::set keys need <.
• std::unordered_map / std::unordered_set keys need a hash (std::hash<K>) and ==.

Built-in types and std::string work out of the box. For your own types you'll supply these (intermediate track).

Common mistakes

• Using [] to check for a key — it inserts. Use contains or find.
• Expecting unordered_map to be sorted — it isn't. Use std::map or sort afterwards.
• Modifying a key — keys are const. Erase and re-insert.
• Erasing inside a range-for — invalidates the iterator. Use std::erase_if(map, pred) (C++20) or it = m.erase(it).
• Forgetting const auto& in loops — copies every pair (including the string key).

Exercises

1. Word frequency: read text from standard input, count words case-insensitively (lowercase them), ignore punctuation, and print the top 10.
2. Phone book: a loop that accepts add NAME NUMBER, find NAME, remove NAME, list, and quit.
3. Given two vectors of strings, print the words that appear in both, and the words that appear in only one.
4. Group a list of words by their length into std::map<std::size_t, std::vector<std::string>> and print each group.
5. Anagram groups: key each word by its sorted letters ("listen" → "eilnst") and print groups with more than one word.
6. Check whether a string has all unique characters using an std::unordered_set<char>.

Recap

• std::map (sorted) and std::unordered_map (hashed, faster) store key → value.
• m[k] inserts if missing — great for counting, bad for checking. Use contains, find, at.
• for (const auto& [k, v] : m) iterates with structured bindings.
• std::set / std::unordered_set store unique values; insert(...).second tells you if it was new.
• std::ranges::set_union / set_intersection / set_difference for set algebra on sorted ranges.

Next: Functions →