Unordered Containers
Overview
While std::map ($O(log N)$) is incredibly fast, sometimes it isn't fast enough. If you are building a server handling millions of network packets, you need instantaneous $O(1)$ lookups.
C++11 introduced Unordered Containers (std::unordered_map and std::unordered_set). Instead of a Tree, these are physically built using Hash Tables. When you insert a Key, a complex mathematical 'Hash Function' instantly converts that Key into a pure integer, and uses that integer as the direct memory array index. This provides blazing fast, constant $O(1)$ lookup times, at the cost of the data being completely randomized (unsorted) in memory.
Syntax
#include <iostream>
#include <unordered_map>
#include <string>
int main() {
// 1. Creation (Hash Table)
std::unordered_map<std::string, int> inventory;
// 2. Insertion (O(1) time - Blazing fast!)
inventory["Swords"] = 5;
inventory["Potions"] = 20;
// 3. Lookup (O(1) time - Blazing fast!)
std::cout << "Potions: " << inventory["Potions"] << "\n";
return 0;
}Common Pitfalls
- Using custom objects as Keys in an unordered_map.
std::unordered_mapnatively knows how to hash strings and ints. If you try to use a customPlayerobject as a key, the compiler will violently crash because it has no idea how to mathematically calculate a Hash for aPlayer. You must write a custom Hash struct to allow this.
Interview Questions
unordered_map provides $O(1)$ lookups, why would a professional C++ engineer ever choose to use a standard std::map ($O(log N)$)?1. std::map keeps data perfectly sorted. If you need to print a leaderboard from highest to lowest, a Hash Table is useless because its data is completely randomized.
2. Hash Tables suffer from 'Collisions' (when two keys generate the exact same Hash integer). If a Hash Table gets too full, resolving collisions can temporarily degrade performance to a horrific $O(N)$, whereas a Tree is mathematically guaranteed to always remain $O(log N)$.
Real-World Example
Using an unordered_set for ultra-high-speed duplicate detection. (e.g., Filtering out IP addresses that have already been banned).
#include <iostream>
#include <unordered_set>
#include <string>
int main() {
std::unordered_set<std::string> bannedIPs;
// O(1) Insertions
bannedIPs.insert("192.168.1.100");
bannedIPs.insert("10.0.0.5");
std::string incomingIP = "192.168.1.100";
// O(1) Lookup - Instant rejection!
if (bannedIPs.count(incomingIP) > 0) {
std::cout << "Connection Dropped. IP Banned.\n";
}
return 0;
}Check Your Knowledge
Test your understanding of Unordered Containers with these quick questions.