Standard Template Library (STL)
Unordered Containers
Hash-based unordered_set and unordered_map with O(1) average operations
Interview: Most-used containers in interview solutions — O(1) lookup for frequency counting, deduplication, and caching
Unordered Containers
std::unordered_set and std::unordered_map use a hash table internally. They provide O(1) average time for insert, erase, and find. Worst case is O(n) when all keys hash to the same bucket, but this is rare with good hash functions. No order is preserved — iteration order is implementation-defined.
How Hash Tables Work
The key is hashed to a bucket index. The element is stored in that bucket's linked list (or open-addressing slot). On lookup, the key is hashed again to find the bucket, then the chain is searched for an exact match. Load factor (elements / buckets) controls performance — rehashing doubles the bucket count when it exceeds the max load factor (default 1.0).
Custom Types as Keys
To use a custom type as a key, provide a hash function and equality operator. Either specialize std::hash<T> or pass a custom hasher as a template parameter. Combine hash values using XOR with shifts or boost::hash_combine pattern.
Reserve and Max Load Factor
Call reserve(n) before inserting n elements to prevent rehashing. max_load_factor(0.5) reduces collision probability at the cost of memory. For performance-critical code, pre-sizing the hash table eliminates costly rehash operations.
Interview Corner
Q: What is the worst-case complexity of unordered_map operations and when does it occur?
A: O(n) worst case when all n keys hash to the same bucket — linear scan of the bucket chain. This can be triggered adversarially with crafted inputs in competitive programming. The fix: use a randomized hash (seed with current time), or use std::map for guaranteed O(log n). In interviews, state the average O(1) but mention the worst case.
Q: How do you implement an O(1) frequency counter?
A: Use unordered_map<T, int> freq; for (auto& x : arr) freq[x]++;. Each increment is O(1) average. To find most frequent: iterate the map in O(n). This is the foundation of many interview solutions — two-sum, anagram detection, character frequency analysis.
Common Pitfalls
- No order guarantee: Iterating an unordered_map doesn't yield keys in any predictable order. Don't depend on insertion order or sorted order.
- Using floating point as key: Float/double keys are legal but problematic — tiny rounding differences create different hash values. Use integers or fixed-precision representations as keys.
- Rehashing invalidates iterators: After insert triggers rehashing, all iterators are invalidated. Don't store iterators across insertions.
Best Practices
- Call
reserve(expectedSize)when inserting a known number of elements — prevents rehashing overhead. - Default to unordered_map/set for O(1) performance; switch to map/set when sorted order or range queries are needed.