Maps & Sets (map, unordered_map, set)

Vectors are great for ordered lists, but real programs constantly need to answer "have I seen this before?" and "what value is stored under this key?". That's exactly what sets and maps are for. By the end of this lesson you'll store key/value data, count and deduplicate in a few lines, and know when to pick the sorted tree version over the faster hash version.

Learn Maps & Sets (map, unordered_map, set) in our free C++ course — a beginner-friendly interactive lesson with worked examples, a practice exercise and a…

Part of the free C++ course at LearnCodingFast — hands-on lessons with examples you run in your browser, plus practice exercises and a quick quiz.

A map is a dictionary: you look up a word (the key) to get its definition (the value). You don't scan every page — you jump straight to the entry. A set is a guest list at a door: each name appears once, and the bouncer only cares "is this name on the list?" — not how many times. A keeps its words alphabetized; a throws them in a giant hashed filing cabinet where you can still find any one instantly, but they're no longer in alphabetical order.

Rule of thumb: reach for unordered_map / unordered_set for speed; switch to map / set when you need sorted order or ordered range queries.

1. std::map — Key → Value

A stores pairs where each key is unique and maps to one value . You include the header, then read and write with map[key] . When you iterate, a map walks its keys in sorted order — handy when you want predictable output. Each element is a std::pair , so entry.first is the key and entry.second is the value.

2. Looking Up Keys Safely

There's a famous gotcha: map[key] on a key that doesn't exist inserts it with a default value (0 for numbers) and the map silently grows. To check whether a key exists without changing the map, use .count(key) , .contains(key) (C++20), or .find(key) . Use .at(key) when you want an exception if the key is missing.

The "insert on access" behaviour is actually a feature for counting. Fill in the blank to tally how often each word appears:

3. unordered_map — The Fast Default

std::unordered_map uses a hash table : it computes a hash of the key to jump straight to a bucket, giving average O(1) lookup and insertion. The trade-off is that iteration order is unspecified. For most "look up by key" work where you don't care about ordering, this is the container to reach for. The interface is almost identical to map .

These lines build a map of fruit prices, raise one price, and print the total — but they're scrambled. Put them in the correct order:

Open main (C), declare and initialize the map (D), bump the apple price (B), print the combined total — now 1.20 + 1.50 = $2.7 (A), then return 0; (E) and close the brace (F).

4. std::set — Unique Values

A std::set stores unique values in sorted order. Inserting a duplicate is simply ignored, which makes deduplication a one-liner. .insert() returns a pair whose .second tells you whether the value was actually new. As with maps, there's an unordered_set hash-based variant for speed.

5. Erasing Entries

Remove a single key with .erase(key) . Removing entries while iterating needs care: map::erase returns an iterator to the next element, so the safe pattern is to assign that result back rather than incrementing a now-invalid iterator. In C++20 you can use the free function std::erase_if for a one-liner.

Since C++17 you can unpack a key/value pair directly in the loop header with structured bindings : for (const auto& [key, value] : myMap) . It reads far better than entry.first / entry.second .

To add elements you can use .insert({' key, value '}) or .emplace(key, value) . emplace constructs the element in place and can avoid a temporary. Both refuse to overwrite an existing key — use operator[] or .insert_or_assign() (C++17) when you intend to replace.

Predict the output before revealing the answer.

2 — the first m["x"] creates the key at 0, then two ++ raise it to 2.

3 — duplicates are dropped, leaving the unique values 1, 2, 3.

3. What does this print, and what is the size of m afterward?

0 2 — reading m["b"] inserts "b" with value 0, so the map now holds two keys.

Combine everything: build a frequency map, iterate it, and find the maximum. The outline in the comments keeps you on track.

Practice quiz

In iteration order, how does std::map walk its keys?

  • In insertion order
  • In sorted key order
  • In random order
  • In reverse order

Answer: In sorted key order. std::map is a balanced tree, so iterating it walks the keys in sorted order (by < on the key by default).

What is the average lookup complexity of std::unordered_map?

  • O(n)
  • O(log n)
  • Average O(1)
  • O(n log n)

Answer: Average O(1). unordered_map is a hash table giving average O(1) lookup and insertion, but its iteration order is unspecified.

What happens with map[key] when key does not exist?

  • It throws an exception
  • It returns garbage
  • It inserts the key with a value-initialized value (0 for int) and returns a reference
  • It returns nullptr

Answer: It inserts the key with a value-initialized value (0 for int) and returns a reference. operator[] inserts a value-initialized entry for a missing key and silently grows the map. Use .find() or .at() to look without inserting.