std::map and std::unordered_map

Key → value lookup is the other half of programming (the first half being "a list of things"), and C++ ships two flavors with one API: std::map keeps keys sorted (a balanced tree underneath, O(log n)), std::unordered_map is a hash table (O(1) average, arbitrary order). Same operations; choosing between them is a one-question quiz: does output order matter?

The API

#include <map>

std::map<std::string, int> ages;
ages["alice"] = 30;              // insert or overwrite
ages["bob"] = 25;

ages["alice"]                    // 30
ages.count("carol")              // 0 or 1 — the existence test
ages.erase("bob");
ages.size();

The operator[] surprise — read this twice

m[key] on a missing key doesn't fail: it inserts the key with a default value (0 for ints, "" for strings) and returns it. Feature and footgun in one:

std::map<std::string, int> counts;
counts["apple"]++;               // absent → inserted as 0 → incremented to 1

That's the counting idiom — one line, no existence check, the same move as Rust's entry().or_insert(0) and Go's zero-value read. It powers your exercise.

The footgun: if (m["carol"] > 0) creates carol while asking about her — mutating the map during a read, growing it with ghost entries. Read-only checks use count or find:

if (ages.count("carol")) { … }               // exists?
auto it = ages.find("carol");                // find returns an iterator
if (it != ages.end()) {
    std::cout << it->second;                 // ->first = key, ->second = value
}

(That it->first/it->second pattern — map entries are std::pairs — reads oddly at first and then you see it everywhere forever.)

Iteration — and the ordering superpower

for (const auto& kv : counts) {
    std::cout << kv.first << ": " << kv.second << "\n";
}

Here the two flavors diverge: std::map iterates in sorted key order — guaranteed. Alphabetical word counts, leaderboards by ID, any "print grouped results in order" task: map does the sorting as a side effect of existing. unordered_map iterates in whatever order hashing produced (don't even expect it to be stable). Hence the working rule: output ordered → map; pure speed, order irrelevant → unordered_map. Graders print in order more often than not, which makes map the safer default here — a genuinely useful inversion of the "always hash" instinct other languages teach.

Your exercise: Distinct Words

Count the distinct words in the input. A map's key-set is a set, so:

std::map<std::string, int> seen;
std::string w;
while (std::cin >> w) {
    seen[w]++;                   // counting idiom; duplicates just re-count
}
std::cout << seen.size() << "\n";

size() counts keys — insert "apple" ten times, it's one key. (C++ also has literal std::set<std::string> — insert and size, no values — either is idiomatic here; the map version practices the counting idiom you'll need the day the exercise asks how many of each, which is this exercise's big sibling and interview-question form.)