C++ Sorted vs Unordered Associative Containers
In C++, associative containers store elements using key-based lookup,
but the standard library divides them into two distinct categories:
sorted associative containers (std::set,
std::map, std::multiset,
std::multimap) and unordered associative containers
(std::unordered_set, std::unordered_map,
std::unordered_multiset,
std::unordered_multimap). The primary differences between
these two families stem from their underlying data structures, which
dictate their element ordering, algorithmic time complexity, memory
footprint, and the requirements imposed on the stored key types.
Underlying Data Structures
- Sorted Containers: Implemented using self-balancing binary search trees, typically Red-Black trees. Every element is allocated as an individual tree node linked by pointers.
- Unordered Containers: Implemented using hash tables. They consist of an array of "buckets" containing linked lists or arrays to handle collisions.
Element Ordering
- Sorted Containers: Elements are always stored in a
strictly defined order based on a comparison criterion (by default,
std::lessusingoperator<). Iterating over a sorted container traverses elements from lowest to highest. - Unordered Containers: Elements are placed based on their hash values. There is no guaranteed order, and the sequence of elements can change unpredictably when insertions trigger a rehashing of the table.
Time Complexity
The architectural divergence leads to different performance characteristics for search, insertion, and deletion operations:
| Operation | Sorted Containers (Tree-based) | Unordered Containers (Hash-based) |
|---|---|---|
| Search / Lookup | Guaranteed \(O(\log n)\) | Average \(O(1)\), Worst-case \(O(n)\) |
| Insertion | Guaranteed \(O(\log n)\) | Average \(O(1)\), Worst-case \(O(n)\) |
| Deletion | Guaranteed \(O(\log n)\) | Average \(O(1)\), Worst-case \(O(n)\) |
Sorted containers provide consistent, predictable performance without worst-case degradation. Unordered containers provide faster average lookups, but poor hash functions or frequent collisions can degrade operations to linear time \(O(n)\).
Requirements on Key Types
- Sorted Containers: The key type must support strict
weak ordering. This requires an overload for
operator<or a custom comparator functor. - Unordered Containers: The key type requires an
equality operator (
operator==) to resolve hash collisions and a specialization ofstd::hash<Key>(or a custom hash function object) to map the key to a size integer.
Iterators and Traversal
- Sorted Containers: Provide bidirectional iterators.
They natively support range queries and boundary lookups using member
functions like
lower_bound()andupper_bound(). - Unordered Containers: Provide forward iterators. Because elements are scattered across buckets without global ordering, range queries (such as finding all keys between value \(A\) and value \(B\)) are not supported efficiently and require a full scan of the container.
Memory and Overhead
- Sorted Containers: Allocate memory node-by-node. Each node carries the overhead of three pointers (parent, left child, right child) and a color bit for the Red-Black tree mechanics.
- Unordered Containers: Require continuous memory for the bucket array in addition to the memory for node lists. When the load factor exceeds a threshold, the bucket array is dynamically reallocated and all elements are rehashed, causing temporary memory spikes and latency.