unordered_map and unordered_set in C++: Hash-Based Collections
What is unordered_map and unordered_set in C++: Hash-Based Collections? std::unordered_map and std::unordered_set are hash-table containers defined in and . They provide average $O(1)$ constant time complexity for insertions, looku...
How do std::unordered_map and std::unordered_set work using hash tables, and how do they differ in performance from std::map and std::set?
Explanation & In-Depth Details
```text
Key: "user:101" ──► std::hash ──► Hash Code % BucketCount ──► Bucket Index [3]
│
┌─────────────┴─────────────┐
▼ ▼
[ "user:101", Data ] ──► [ Collided Node ]
```
2. Comparison: Map vs Unordered Map:
```text
┌─────────────────────┬───────────────────────────┬───────────────────────────┐
│ Feature │ std::map / std::set │ std::unordered_map / set │
├─────────────────────┼───────────────────────────┼───────────────────────────┤
│ Data Structure │ Red-Black Tree (Balanced) │ Hash Table (Buckets) │
│ Element Ordering │ Strictly Sorted │ Unordered / Arbitrary │
│ Average Lookup Time │ O(log N) │ O(1) │
│ Worst-case Lookup │ O(log N) │ O(N) (Hash Collisions) │
│ Key Requirements │ operator< │ std::hash and operator== │
└─────────────────────┴───────────────────────────┴───────────────────────────┘
```
Code Example
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string>
int main() {
// 1. std::unordered_map (O(1) Hash Map)
std::unordered_map<std::string, double> productPrices = {
{"Keyboard", 79.99},
{"Monitor", 249.50},
{"Mouse", 39.99}
};
// Fast O(1) average lookup
std::string query = "Monitor";
if (productPrices.find(query) != productPrices.end()) {
std::cout << "[Lookup] " << query << " costs $" << productPrices[query] << "\n";
}
// 2. std::unordered_set (O(1) Hash Set)
std::unordered_set<std::string> blacklistedIPs = {
"192.168.1.100", "10.0.0.50", "172.16.0.22"
};
std::string testIP = "10.0.0.50";
if (blacklistedIPs.count(testIP)) {
std::cout << "[Security Alert] IP " << testIP << " is BLACKLISTED!\n";
}
return 0;
}Interview Question & Tips
A: Severe hash collisions where many keys hash to the same bucket index, turning bucket lookup into a linear search down a linked list chain.
Q: What two things must you provide to use a custom class as a key in `std::unordered_map`?
A: 1) A specialization of `std::hash<KeyType>` to compute hash codes. 2) An overloaded `operator==` to check for key equality.
Best Practices
• Call `.reserve(expectedCount)` on unordered containers to pre-allocate hash buckets and avoid costly rehashing.
• Use `std::map` when you need sorted keys or range queries (`lower_bound` / `upper_bound`).
This study reference for unordered_map and unordered_set in C++: Hash-Based Collections is curated and verified against recognized curriculum benchmarks, peer-reviewed textbooks, and official technical documentation: