Topic 65 of 83
Unordered Containers
Overview
Unordered containers are Hash Tables. They provide incredible O(1) average time complexity for insertions and lookups. Elements are NOT sorted.
Syntax
cpp
#include <unordered_set>
#include <unordered_map>
// Hash Set
std::unordered_set<int> uset;
uset.insert(10);
uset.insert(20);
// Hash Map
std::unordered_map<std::string, std::string> dns;
dns["google.com"] = "142.250.190.46";Common Pitfalls
- Hash Collisions can degrade performance to O(N) in the worst case, particularly if hackers target your hash function (though standard library mitigates this well).
Interview Tips
- Explain the difference: `std::map` uses a Tree (O(log N), sorted). `std::unordered_map` uses a Hash Table (O(1) average, unsorted). In interviews (e.g., Two Sum), always use `unordered_map` for speed unless you specifically need the keys sorted.
Real-World Example
O(1) Fast lookup caching (Memoization).
example
cpp
#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<int, int> cache;
int fib(int n) {
if (n <= 1) return n;
// Fast O(1) lookup
if (cache.count(n)) return cache[n];
cache[n] = fib(n-1) + fib(n-2);
return cache[n];
}