The idea
A map stores key → value pairs. map keeps keys sorted with O(log n) operations; unordered_map hashes them for O(1) on average.
Typical uses: counting occurrences, remembering where a value was last seen, and turning large or non-numeric keys (strings, pairs, whole vectors) into something you can index.
Many “find a pair” problems become one pass: for each item, compute what its partner must be and look that up among the items already seen.
Sample problem
1. Two Sum ↗ Easy
Given an array and a target, return the indices of the two numbers that add up to the target.
nums = [8,2,11,5,4], target = 9 output = [3,4] (5 + 4)
Why the solution works
Trying every pair is O(n²). But for a number x the partner is not a search: it must be exactly target − x.
So the only question is “has that value appeared before, and where?”. A hash map from value to index answers it in O(1), turning the double loop into a single pass.
Looking the partner up before storing the current number guarantees the two indices are different.
Complexity: O(n) time on average, O(n) memory.
Watch out
m[key]creates the key if it is missing. Usem.count(key)orm.find(key)to test.unordered_maphas no default hash for pairs or vectors and can be slow on adversarial input;mapis the safe choice.- Iterating a
mapvisits keys in sorted order; anunordered_maphas no meaningful order.