std::map vs. std::unorderedmap — trade-offs and when to use each.
C++Level: IntermediateSTL Containers & Iterators
std::map vs. std::unordered_map — trade-offs and when to use each.
Hints
- Identify types, object lifetimes and compile-time decisions.
- Separate language guarantees from a particular compiler's behavior.
Answer
Ordered vs Unordered Containers
:header-rows: 1
-
- Feature
- set/map
- unordered_set/map
-
- Implementation
- Red-black tree
- Hash table
-
- Lookup
- O(log n)
- O(1) average, O(n) worst
-
- Insert/Delete
- O(log n)
- O(1) average, O(n) worst
-
- Ordered iteration
- Yes
- No
-
- Key requirement
- Comparable (<)
- Hashable + equality (==)
-
- Memory overhead
- Tree pointers
- Hash buckets
When to use ordered (set/map):
- Need sorted iteration or range queries
- Keys are not easily hashable
- Predictable worst-case performance required
When to use unordered (unordered_set/map):
- Performance is critical and dataset is large
- Don't need sorted order
- Keys have good hash distribution
Source and licence: C/C++ Interview Cheatsheet — Chang Ning Tsai · MIT