Lesson 07 · 18 min
unordered_map & unordered_set
Hashing in C++ — the weapon behind Two Sum, duplicates, and anagrams.
Hash tables in C++
unordered_map
unordered_map<int,int> mp;
mp[x] = i; // insert / assign
if (mp.count(need)) { ... } // exists?
int idx = mp[need]; // read (careful: [] inserts 0 if missing)Trap: mp[key] creates the key with default value if absent. Prefer .count / .find before read when existence matters.
unordered_set
unordered_set<int> st;
st.insert(x);
if (st.count(x)) { /* seen */ }Two Sum pattern
For each nums[i], look for target - nums[i] in the map before inserting nums[i].
Complexity
Average O(1) lookup. Worst case degraded (rare). For interviews, say "average O(1) with hash map".
Rules to remember
- Use .count/.find when you must not insert accidentally.
- map is ordered (tree) O(log n); unordered_map is hash average O(1).
- Hash map trades space for time — say that in interviews.
- Store value→index for Two Sum style problems.
Check yourself
1. Danger of reading mp[key] when key may be missing?