Hello! Welcome to our lesson on associative containers.
In our last session, we contrasted the contiguous memory of std::vector with the node-based structure of std::list. The key takeaway was a principle that is fundamental to high-performance C++: memory layout dictates performance. The cache-friendly nature of std::vector often makes it faster in practice, even when std::list has a better theoretical complexity for certain operations.
Today, we will apply this same critical lens to the two primary associative containers, directly addressing the learning outcome: Analyze the internal data structures of std::map (red-black tree) and std::unordered_map (hash table). You'll see how their underlying designs lead to a classic trade-off between order and speed, and once again, how their interaction with the CPU cache plays a crucial role.
std::map: The Ordered Dictionary and Red-Black Trees
A std::map is an associative container that stores elements as key-value pairs, sorted by key. If you iterate through a std::map, you are guaranteed to visit the elements in ascending key order. This ordering is not free; it's maintained by the map's internal data structure: a self-balancing binary search tree, most commonly a Red-Black Tree (RBT).
Why a Self-Balancing Tree?
A simple binary search tree (BST) works well for random data. However, if you insert keys in an already sorted order (e.g., 1, 2, 3, 4, 5...), the tree degenerates into a linked list, and lookup performance degrades from O(log N) to a disastrous O(N).
A Red-Black Tree prevents this by enforcing a set of rules on its nodes (which are colored 'red' or 'black'). After any insertion or deletion, the tree performs a series of color changes and up to three rotations to "rebalance" itself, guaranteeing that the longest path from the root to a leaf is no more than twice as long as the shortest path. This ensures that search, insertion, and deletion operations always maintain their O(log N) worst-case complexity.
Memory Layout and Performance
Just like std::list, a Red-Black Tree is a node-based data structure. Each node is a separate allocation on the heap containing:
- The key-value pair.
- Pointers to the left child, right child, and parent.
- A color value (typically just one bit).
This node-based layout immediately tells us something about its performance, echoing our last lesson. Accessing any element involves pointer chasing from the root down to the target node. Each step in that chase is a potential cache miss, making std::map inherently less cache-friendly than a contiguous container like std::vector.
The article 'Implementing a Red-Black Tree' provides excellent context on why RBTs are used and their characteristics. It will reinforce the concepts we've just discussed.
Read the introduction ('Ordered Set') and the section on 'Algorithms', focusing on the 'Bottom-up Approach'. Notice the description of the three stages (Search, Flip Color, Rotate) and the typical requirement for a parent pointer, which confirms the node-based structure. The discussion of the search stage being the bottleneck due to memory access is particularly relevant.
The std::map Trade-off: You get the powerful feature of sorted keys and guaranteed O(log N) lookups, but you pay for it with higher memory overhead (pointers per node) and suboptimal cache performance due to pointer chasing.
std::unordered_map: The Unordered Dictionary and Hash Tables
What if you don't need your keys to be sorted, and your top priority is raw speed? For this, C++ gives us std::unordered_map. Its goal is to provide average-case O(1) (constant time) complexity for lookups, insertions, and deletions. It achieves this by using a hash table as its underlying data structure.
How a Standard Hash Table Works
The core idea is simple:
- An array of "buckets" is allocated.
- When you insert a key-value pair, a hash function converts the key into an integer hash code.
- This hash code is mapped to an index into the bucket array.
- Collision Handling: What if two different keys hash to the same index? This is called a collision. The C++ standard requires that references and iterators to elements in an
unordered_mapremain valid even if the table is rehashed (resized). This constraint essentially forces standard library implementations to use a technique called separate chaining.
In separate chaining, each bucket in the array is a pointer to the head of a singly-linked list of nodes. If a collision occurs, the new node is simply added to the linked list for that bucket.
This implementation detail is crucial. While lookups in an ideal hash table are O(1), a lookup in std::unordered_map involves:
- Calculating the hash and finding the bucket (O(1)).
- If the bucket is not empty, traversing a linked list to find the correct key. In the worst case (many collisions), this can degrade to O(N).
How libstdc++ `std::unordered_map` implemented?
To see exactly how this is implemented in a major standard library, let's look at a deep dive into GCC's libstdc++.
Read the sections 'Data Layout', 'Hash table', '«Fast» and «slow» hash functions', and 'Closing thoughts'. Focus on understanding the structure of _Hash_node, how _M_buckets is an array of pointers, and the final conclusion about cache-unfriendliness due to pointer chasing. This is a perfect ground-up view of the implementation.
The standard implementation of std::unordered_map is a classic example of design constraints leading to suboptimal performance. That pointer chasing in the collision lists is exactly the kind of cache-hostile behavior we want to avoid.
A Better Way: Open Addressing and Swiss Tables
Given your interest in how things really work, you should know that the std::unordered_map in the standard library is often not what's used in high-performance code. The performance community has developed far superior hash table designs. The most famous is Google's "Swiss Table," which is the basis for Abseil's absl::flat_hash_map.
Instead of separate chaining, these tables use open addressing. All elements are stored in a single, contiguous array. When a collision occurs, the algorithm "probes" for the next available slot in the array. This is far more cache-friendly but invalidates iterators on rehash, which is why it can't be used for the standard std::unordered_map.
The real genius of the Swiss Table is how it finds elements so quickly. It uses a parallel array of 1-byte control codes and leverages SIMD instructions (Single Instruction, Multiple Data) to check 16 buckets at the same time in just a few CPU cycles.
CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step”
This CppCon talk is a masterclass in data structure optimization. It starts by analyzing the flaws of the standard unordered_map and builds a cache-friendly hash table from first principles. This is the ultimate 'under the hood' explanation.
Please watch the following segments: 06:45 to 11:15: This shows the standard unordered_map structure and its performance problems (multiple memory accesses for find). 24:01 to 29:17: This introduces the core idea of the Swiss Table: the parallel metadata array with control bytes. 29:17 to 31:22: This is the key part. See how SSE (a SIMD instruction set) is used to compare 16 control bytes in parallel, dramatically speeding up probes.
This evolution from a pointer-chasing linked list to a SIMD-optimized contiguous array is a perfect case study in modern, hardware-aware C++ development.
Practical Detail: Using Custom Types as Keys
For std::unordered_map to work with your own struct or class as a key, you must provide two things:
- A hash function that can turn your object into a
size_t. - An equality operator (
operator==) so the map can resolve hash collisions.
For std::map, the requirements are simpler: you only need a strict weak ordering, which is usually provided by implementing operator<.
STL std::unordered_map (C++11) | Modern Cpp Series Ep. 129
Let's watch a practical demonstration of how to implement a custom hash function for a user-defined type.
Watch the segment from 30:29 to 39:27. The presenter walks through creating an unordered_map with a custom struct as a key, showing the compiler errors that arise and how to fix them by implementing the necessary hash functor and equality operator.
Test your understanding!
You are building a real-time system for a stock exchange. You need to store the current price of thousands of stocks, identified by their string ticker (e.g., "AAPL", "GOOG"). The system must frequently display the top 10 highest-priced stocks. You will also have millions of lookups per second to get the price of a specific stock by its ticker.
Which container, std::map<std::string, double> or std::unordered_map<std::string, double>, would be more appropriate for the core data store, and why? Consider all requirements.
Show answer
This is a tricky question with a real-world trade-off. A std::map is the better choice here.
While std::unordered_map would provide faster individual lookups (O(1) average), the critical requirement is to frequently display the top 10 highest-priced stocks.
With an std::unordered_map, finding the top 10 would require iterating through all the elements to find the ones with the highest values, which would be an O(N) operation. This is too slow for a real-time system.
With a std::map, the keys (stock tickers) are sorted alphabetically, which isn't what we need. However, we could use std::map<double, std::string> to store the data sorted by price. Or, more flexibly, we can use a std::map<std::string, double> and maintain a separate ordered data structure (like another std::map or a std::set) of the top N stocks.
The key is that std::map's ordered nature is essential for efficiently satisfying the "top 10" requirement. The slightly slower O(log N) lookup is an acceptable trade-off to avoid the O(N) scan that std::unordered_map would necessitate.
Conclusion
Today we dissected two of the most important STL containers and saw how their internal data structures dictate their performance and features.
Key Takeaways:
std::mapis implemented with a Red-Black Tree. It guarantees O(log N) performance and keeps keys sorted. Its node-based structure makes it inherently cache-unfriendly due to pointer chasing.std::unordered_mapis implemented with a hash table, typically using separate chaining (linked lists for collisions) to meet standard requirements. It provides O(1) average performance but with unordered keys. The standard implementation can also be cache-unfriendly.- High-performance hash tables (like Swiss Tables) use open addressing and SIMD instructions to be extremely fast and cache-friendly, but they are not compatible with the
std::unordered_mapstandard specification due to iterator invalidation rules. - The choice is a fundamental trade-off: Sorted Order (
map) vs. Average-Case Speed (unordered_map).
What's Next?
In our exploration of containers, we've seen how they manage memory internally, from std::vector's reallocations to the node-based allocations of list and map. These operations can involve expensive copying of data. In our next lesson, we'll dive into move semantics, a modern C++ feature that allows containers to efficiently transfer ownership of resources instead of copying them. We will then see how you can take ultimate control over a container's memory by implementing a custom allocator.