std::unordered_map is an associative container that stores elements formed by the combination of a key value and a mapped value. Unlike std::map, it uses a Hash Table and does not maintain any specific order.

Use std::unordered_map when you need fast lookups, insertions, and deletions, and you don't care about the order of keys. This is the most common container used for frequency counting and caching in interviews.

• Insertion: $O(1)$ average, $O(N)$ worst case (collisions).
• Search: $O(1)$ average, $O(N)$ worst case.
• Deletion: $O(1)$ average.

cpp Standard
#include <unordered_map>

std::unordered_map<std::string, int> counts;
counts["apple"] = 5;
counts["banana"] = 10;

std::cout << counts["apple"]; // 5

• Hash Collisions: Not realizing that worst-case performance is $O(N)$, which can be exploited in competitive programming if a custom hash is not used.
• Using it when you need keys to be sorted (use std::map instead).
• Forgetting that the keys must be hashable—custom types require a custom hash function.