Look things up by key, not by position. The ordered tree vs the hashed table — how each works, the operator[] trap, and which to default to.
When you need to look something up by key (not by index), use an associative container. std::unordered_map hashes keys for O(1) average lookup; std::map keeps keys sorted in a balanced tree for O(log n). Default to unordered_map unless you need order.
A vector is great when you know where something is (its index). But "give me the score for player "Ada"" has no index — searching a vector for it is O(n). Maps turn that into a fast, direct lookup keyed on the value you actually have.
#include <unordered_map> #include <string> std::unordered_map<std::string, int> score; // key: name, value: points score["Ada"] = 42; // insert score["Grace"] = 37; score["Ada"] += 5; // update → 47 std::cout << score["Ada"]; // 47, found in ~O(1)
-std=c++17+).map<K,V> stores entries as std::pair<const K, V> — the key is const because changing it would break the structure.std::map<std::string, int> m; m["a"] = 1; // insert or assign m.insert({"b", 2}); // insert (does nothing if "b" exists) m.at("a"); // 1 — throws std::out_of_range if absent // existence check (DON'T use [] for this — see §03) if (m.contains("a")) { } // C++20 if (m.find("a") != m.end()) { } // pre-C++20, works everywhere m.count("a"); // 0 or 1 (keys are unique) m.erase("a"); // remove by key m.size(); // number of entries // iterate — structured bindings (C++17) unpack each pair for (const auto& [key, value] : m) std::cout << key << " = " << value << "\n"; // for std::map this prints in sorted key order: a, b, ...
auto [key, value] : m destructures each pair into named variables — far cleaner than it->first / it->second. (Lesson 11 covers pair/tuple.)
find returns an iteratorfind(k) gives an iterator to the entry, or end() if absent. Deref it to get the pair: it->second is the value.
Inserting an existing key is a no-op (the value isn't replaced by insert). Want duplicates? That's multimap (§05).
Source: cppreference — std::map · std::unordered_map.
operator[] trapThis is the #1 map surprise: m[key] inserts a default-constructed value if the key is missing — it never "just fails." So using it to check for a key silently grows your map.
std::map<std::string, int> m; if (m["missing"] == 0) { } // ✗ just INSERTED {"missing", 0}! m.size() is now 1 if (m.contains("missing")) { } // ✓ checks without inserting (C++20) if (m.find("missing") != m.end()) { } // ✓ same, any standard
[] facts
(1) operator[] doesn't exist on a const map (it might insert), so use at() or find() there. (2) The auto-insert behavior is actually handy for counting: ++count[word] works because a missing word starts at 0.// word frequency in one line, thanks to []'s auto-insert: std::unordered_map<std::string, int> freq; for (const auto& w : words) ++freq[w]; // missing → 0, then ++
Source: cppreference — map::operator[] inserts if the key does not exist.
Both map keys to values; they differ in how they store entries — and that drives everything.
std::map | std::unordered_map | |
|---|---|---|
| Structure | balanced binary search tree | hash table (buckets) |
| Lookup / insert / erase | O(log n) | O(1) average, O(n) worst |
| Iteration order | sorted by key | unspecified / "random" |
| Key requirement | ordered (<) | hashable (std::hash) + == |
| Reach for it when… | you need sorted order or range queries | you just need fast lookup (the common case) |
unordered_map is faster. Choose map when you need keys in sorted order, or to iterate a range of keys. Built-in types and std::string are hashable out of the box.Every map/set comes in four flavors built from two axes — ordered vs hashed, and unique vs duplicate keys:
| Unique keys | Duplicate keys allowed | |
|---|---|---|
| Ordered | map, set | multimap, multiset |
| Hashed | unordered_map, unordered_set | unordered_multimap, unordered_multiset |
A set is just a map with keys and no values — "is this in my collection?" Lesson 5 covers sets and pulls all of this into a single container-selection guide. multimap lets one key map to many values (e.g. tags → posts).
Source: cppreference — associative & unordered associative containers.
if (m["key"] == 0) as an existence check?std::map but not std::unordered_map?map vs unordered_map — the core trade?map = balanced tree, keys sorted, O(log n). unordered_map = hash table, no order, O(1) average. Default to unordered unless you need order.m[key] do when key is absent?[] to test existence — use contains/find.unordered_map<string,int> f; for (auto& w : words) ++f[w]; — [] default-inserts 0 for a new word, then increments.for (const auto& [k, v] : m). Each entry is a pair<const K, V>.multimap?map but without the unique-key constraint.Try: "how do I make my own struct usable as an unordered_map key?" (hint: provide std::hash + ==), or "show me grouping items with multimap".