Click the “C++ Players, please get ready” button below, select “Follow/Pin/Star the public account” for valuable content and benefits, delivered to you first!
If you find the content helpful, please consider following and showing some love, thank you. C++ set uses red-black trees, while unordered_set uses hash tables. Why?
This is not a random choice. It involves a trade-off between performance, orderliness, and memory overhead, a balance that has persisted for over 30 years since the inception of the C++ standard. Almost all compilers have adopted the same choice, which itself indicates how stable the design of red-black trees is.
Today, we will delve into why the C++ STL chose red-black trees for set instead of AVL trees, hash tables, or B-trees. After reading, you will understand that this choice is quite significant; it is not just about performance numbers, but also about considerations of generality, predictability, and implementation complexity.
Underlying Structure of Set: Red-Black Tree
In GCC’s libstdc++, the implementation of set is in<span>stl_tree.h</span>, and it is based on red-black trees. A red-black tree is a self-balancing binary search tree that guarantees the time complexity for insertion, deletion, and search is O(log n). Importantly, this O(log n) is not just an average case; it is a worst-case guarantee, which is crucial as it means that regardless of how the data is distributed, performance will not suddenly degrade.
Node Structure of Red-Black Tree (Simplified Version):
struct _Rb_tree_node {
_Rb_tree_node* _M_parent; // Parent node pointer
_Rb_tree_node* _M_left; // Left child node
_Rb_tree_node* _M_right; // Right child node
_Rb_tree_color _M_color; // Color (Red/Black)
_Value_type _M_value; // Actual stored value
};
Node Structure Diagram:
┌─────────────────────────┐
│ _Rb_tree_node │
├─────────────────────────┤
│ _M_parent (8 bytes) ───→│ Parent node
│ _M_left (8 bytes) ───→│ Left child node
│ _M_right (8 bytes) ───→│ Right child node
│ _M_color (1 byte) │ Red/Black
│ _M_value (4 bytes) │ int32_t
│ (padding) (variable) │ Memory alignment (depends on compiler)
└─────────────────────────┘
Approximately 32-48 bytes on a 64-bit system
Note the<span>_M_parent</span> pointer. Why store the parent node pointer? Because the set’s iterator needs to support bidirectional traversal (<span>++it</span><span> and </span><code><span>--it</span><span>), with the parent pointer, iteration can be achieved without modifying the tree structure, and the iterator only needs to store a pointer to the current node, eliminating the need for a stack or other auxiliary structures, making it simple and efficient.</span>
The memory overhead is significant. On a 64-bit system,<span>std::set<int32_t></span><span> typically occupies 32-48 bytes per element (depending on the compiler): 3 pointers (left, right, parent) = 24 bytes, color = 1 byte, int32_t = 4 bytes, plus memory alignment and allocator overhead. This overhead is 8-12 times that of an int itself, which can be quite substantial if you store a large number of small objects. In such cases, you might need to consider other data structures, such as hash tables or B-trees.</span>
Red-Black Tree vs Hash Table: Ordered vs Unordered
Hash tables have a query time of O(1), while red-black trees have O(log n). Why not use hash tables?
Core Difference: Orderliness.
The set guarantees that elements are ordered, allowing for range queries using<span>lower_bound</span><span> and </span><code><span>upper_bound</span><span>. Hash tables cannot achieve this; elements are stored in a disordered manner, making it impossible to traverse an ordered sequence or perform range queries. This distinction defines the difference between set and unordered_set, making them suitable for different scenarios.</span>
Comparison of Red-Black Tree vs Hash Table:
Red-Black Tree (std::set) Hash Table (std::unordered_set)
═══════════════════ ═══════════════════════════
[50] ┌─────────────────┐
/ \ │ Bucket 0: [23] │
[30] [70] ├─────────────────┤
/ \ / \ │ Bucket 1: [70] │
[20][40][60][80] ├─────────────────┤
│ Bucket 2: [30] │
Ordered traversal: 20,30,40,50,60,70,80 ├─────────────────┤
│ Bucket 3: [50] │
Query: O(log n) └─────────────────┘
Insert: O(log n)
Delete: O(log n) Unordered traversal: 23,70,30,50...
Range query: ✅ Supported
Query: O(1) average
Insert: O(1) average
Delete: O(1) average
Range query: ❌ Not supported
When to Use Which?
| Requirement | Choice | Reason |
|---|---|---|
| Need Order | <span>set</span> (Red-Black Tree) |
Supports range queries and ordered traversal |
| Need Range Queries | <span>set</span> (Red-Black Tree) |
<span>lower_bound</span><code><span>, </span><code><span>upper_bound</span> |
| Only Need Deduplication + Fast Queries | <span>unordered_set</span> (Hash Table) |
O(1) query, faster than O(log n) |
| Large Data Volume | <span>unordered_set</span> (Hash Table) |
Hash tables have a smaller constant factor, generally faster |
For example, if you want to store a bunch of student scores and query “how many students scored between 60 and 80?” Using set, you can directly use<span>lower_bound(60)</span><span> and </span><code><span>upper_bound(80)</span><span>, achieving it in O(log n) with just two lines of code. Using unordered_set? You would have to traverse all elements, which takes O(n), much slower, and the performance difference becomes very apparent with larger data volumes.</span>
However, if you only need to check if a student has passed, the O(1) query of unordered_set is faster than the O(log n) of set, and if your dataset is large (like millions of entries), the constant advantage of unordered_set can be very significant, potentially making it several times faster than set.
Red-Black Tree vs AVL Tree: Loose vs Strict
So, why not use AVL trees? AVL trees are also balanced binary trees and are more balanced than red-black trees (AVL trees strictly ensure that the height difference between left and right subtrees is ≤1, while red-black trees only ensure black height balance). Theoretically, queries should be faster with AVL trees, but the C++ STL did not choose AVL trees for several important reasons, which are more significant in practical applications than theoretical numbers.
Why Did C++ STL Choose Red-Black Trees?
The answer is: faster insertions and deletions, and more predictable worst-case performance. This is very important for a general-purpose standard library because you do not know what users will do with set; some may insert and delete frequently, while others may only query occasionally. Red-black trees perform stably across various scenarios, without sudden performance drops in extreme cases.
Balance Comparison
Height Comparison of Red-Black Tree vs AVL Tree (10 Nodes):
AVL Tree (Strictly Balanced) Red-Black Tree (Loosely Balanced)
═══════════════ ═══════════════
[50] ⚫[50]
/ \ / \
[30] [70] ⚫[30] 🔴[70]
/ \ / \ / \ \
[20][40][60][80] 🔴[20] ⚫[40] ⚫[80]
/ \ /
[10][25] ⚫[10]
Height: 3 Height: 4
(1.44 * log₂11 ≈ 4.7) (2 * log₂11 ≈ 6.5)
Query: Up to 3 comparisons Query: Up to 4 comparisons
(Difference of about 33%)
Insert: Up to 2 rotations Insert: Up to 2 rotations
Delete: May require O(log n) rotations Delete: Up to 3 rotations ✅
AVL Tree:
- Strictly balanced (height difference between left and right subtrees ≤1)
- Maximum height of 1.44 * log2(n+1)
- At most 2 rotations during insertion, may require O(log n) rotations during deletion
Red-Black Tree:
- Loosely balanced (black height balance)
- Maximum height of 2 * log2(n+1)
- At most 2 rotations during insertion, at most 3 rotations during deletion
As you can see, AVL trees are shorter (1.44 times vs 2 times), and queries are indeed slightly faster, but deletion operations come at a cost: they may require O(log n) rotations, which involves a lot of pointer modifications and height adjustments across many nodes. This overhead can make AVL tree deletions several times slower than red-black tree deletions. Red-black trees sacrifice a bit of height for the stability of deletion operations (at most 3 rotations), and this “bit” is almost imperceptible in practical applications; the query difference is only about 10-20%, but the improvement in deletion operations can be as much as 50% or more.
Performance Comparison
Let’s look at actual test data:
| Operation | Red-Black Tree | AVL Tree | Difference |
|---|---|---|---|
| Insertion (Random Data) | Comparable | Comparable | Both at most 2 rotations |
| Deletion (Random Data) | ✅ Faster and more stable | Slower | Red-black tree at most 3 rotations, AVL tree may require O(log n) rotations |
| Query | Somewhat slower | ✅ Faster | AVL tree has a lower average height, difference usually 10-20% |
| Balance | Loosely balanced | Strictly balanced | AVL tree is shorter, but rotations during deletion are more frequent |
Note that the “difference usually 10-20%” in query speed sounds good, but C++ STL containers are general-purpose, and the frequency of insertions and deletions is not lower than that of queries. In many application scenarios, insertions and deletions can be even more frequent (like cache eviction, priority queues, etc.). The advantages of red-black trees in insertions and deletions completely offset the disadvantages in queries, making red-black trees faster overall.
Moreover, red-black trees have a key advantage:at most 3 rotations during deletion. This means that the worst-case performance is predictable, avoiding situations where “a particular deletion is especially slow.” For real-time systems or performance-sensitive applications, this predictability is more important than average performance. You would prefer to be slightly slower every time rather than experiencing a sudden lag at some point. AVL trees have insertion speeds comparable to red-black trees (at most 2 rotations), but deletions may require rotations all the way to the root, involving O(log n) rotations, leading to significant fluctuations in worst-case performance.
Why Did STL Choose Red-Black Trees?
STL chose red-black trees for several reasons:
- Faster and more stable deletion operations – STL containers require frequent modifications, and red-black tree deletions take at most 3 rotations, while AVL trees may require O(log n) rotations
- Predictable worst-case performance – The number of rotations for insertions/deletions in red-black trees is constant, while AVL trees may require many rotations during deletions
- Minimal query differences – A 10-20% difference is not significant in practical applications
- Iterator stability – The parent pointer supports bidirectional iteration, making implementation simple
You might wonder, “If I am query-intensive, is red-black tree not suitable?” Theoretically, yes, but in practice, if you are that sensitive to performance and care about that 10-20% difference, you might not use AVL trees but rather go directly for B-trees (cache-friendly, faster queries) or simply use hash tables (O(1) queries). The performance differences between red-black trees and AVL trees are negligible compared to real performance bottlenecks, which often lie in I/O, networking, or databases rather than tree traversal in memory.
Why Not Use B-Trees?
Are B-trees not faster? Google’s Abseil library provides<span>btree_set</span><span>, which performs significantly better than</span><code><span>std::set</span><span>, especially in terms of cache friendliness. B-trees store data contiguously, reducing cache misses, making queries and traversals faster than red-black trees.</span>
Why Doesn’t C++ STL Use B-Trees?
B-trees are indeed faster, especially in terms of cache friendliness (data is stored contiguously, reducing cache misses), but B-trees have a problem:Complex Implementation, much more complex. B-tree nodes contain multiple keys, and during insertions and deletions, nodes need to be split and merged, handling various conditions like half-full, full, underflow, etc. The codebase is several times larger than that of red-black trees and is prone to bugs, leading to high maintenance costs.
B-Tree vs Red-Black Tree (Memory Layout Comparison):
Red-Black Tree (Pointer Jump Access)
═══════════════════
Node 1 [20] ───┐
┌──┘
Node 2 [30] │ ┌─→ Node 3 [40]
└──┘
↑
└─ Pointer jumps, many cache misses
Each node is allocated separately
Queries involve jumping around
B-Tree (Data Stored Contiguously)
═══════════════
┌────────────────────────────┐
│ [20] [30] [40] [50] [60] │ ← A single node contains multiple keys
└────────────────────────────┘
Contiguous memory
Queries keep data in cache
But implementation is complex, requires handling node splits/merges
When the C++ standard committee designed STL (in the 1990s), they prioritized implementation simplicity and portability over extreme performance. During that era, compiler and hardware differences were significant, and a simpler implementation was easier to port across different platforms and easier to verify for correctness. The theoretical foundation of red-black trees is mature, and they are relatively simple to implement with fewer bugs, which is crucial for a standard library.
Moreover, the advantages of B-trees mainly manifest in disk I/O scenarios (like database indexing) because disk reads and writes are block-based. A B-tree node corresponds to a disk block, reducing I/O operations. However, the performance improvement in memory is not as dramatic; modern CPUs have small L1/L2 caches (tens of KB), and if B-tree nodes are too large, they will also frequently miss the cache, limiting performance gains. For most applications, red-black trees are sufficient, as performance bottlenecks usually do not occur here.
If you really need extreme performance, you can use Abseil’s<span>btree_set</span><span>, which is optimized for modern CPUs, aligning node sizes to cache lines. In certain scenarios (large datasets, intensive traversals), it may outperform</span><code><span>std::set</span><span> by 30-50%, or simply use</span><code><span>std::vector</span><span> + </span><code><span>std::sort</span><span>, inserting in bulk and sorting once, using binary search for queries, which may outperform any tree, provided your scenario is suitable for bulk operations and does not require frequent single insertions or deletions.</span>
Five Properties of Red-Black Trees
Red-black trees guarantee O(log n) performance based on five rules:
- Nodes are either red or black
- The root node is black
- All leaves (NIL nodes) are black
- Red nodes must have black children (no consecutive red nodes)
- All paths from any node to its leaves contain the same number of black nodes
Example of a Red-Black Tree (Satisfying the Five Properties):
⚫[50] ← The root node is black
/ \
🔴[30] 🔴[70] ← Red nodes must have black children
/ \ / \
⚫[20] ⚫[40]⚫[60] ⚫[80] ← Black nodes
/
🔴[10] ← Red node
Black height verification (number of black nodes from root to leaf):
- Path 1: [50]→[30]→[20]→[10]→NIL Black nodes: 50,20,NIL = 3 ✅
- Path 2: [50]→[30]→[20]→NIL Black nodes: 50,20,NIL = 3 ✅
- Path 3: [50]→[30]→[40]→NIL Black nodes: 50,40,NIL = 3 ✅
- Path 4: [50]→[70]→[60]→NIL Black nodes: 50,60,NIL = 3 ✅
- Path 5: [50]→[70]→[80]→NIL Black nodes: 50,80,NIL = 3 ✅
All paths have the same number of black nodes (black height = 3)
Rules 4 and 5 are crucial. Rule 4 ensures that there are no “red chains” (consecutive red nodes), while Rule 5 guarantees “black height balance” (the same number of black nodes on all paths). Together, these ensure that the height of the tree does not exceed 2 * log2(n+1), and this upper bound is strict, not just an average case, but a worst-case scenario. This is the fundamental reason for the predictable performance of red-black trees.
Why is it 2 times? Because in the worst case, one path is “black-red-black-red-black-red…” alternating, while another path consists entirely of black nodes. The first path is twice as long as the second, but the number of black nodes is the same, satisfying Rule 5. This represents the most unbalanced state acceptable for red-black trees, but even in this case, the height is only twice that of ordinary balanced trees, leading to negligible differences in query performance.
How to Maintain Balance After Insertion?
When inserting a new node, it is first marked as red (why? Because it will not violate the fifth rule of black height balance). Then, it checks whether it violates the fourth rule (consecutive red nodes). If it does, balance is restored through rotations and recoloring, a process that takes at most 2 rotations, and each rotation only involves constant node pointer modifications, with a time complexity of O(1), making it very efficient.
How to Adjust After Insertion?
Insertion adjustments depend on the color of the uncle node:
- If the uncle node is red → Only recoloring is needed (change the parent and uncle nodes to black, and the grandparent node to red), no rotations required
- If the uncle node is black → Rotation + recoloring (perform left or right rotation as needed, at most 2 times)
The adjustment strategy is complex, but the key is:At most 2 rotations during insertion, at most 3 rotations during deletion, and each rotation only involves constant node pointer modifications, with a time complexity of O(1). This is significantly less than the AVL tree’s deletion, which may require O(log n) rotations, involving many node modifications. This is the fundamental reason why red-black tree deletions are faster, not due to different algorithm complexities (both are O(log n)), but because the constant factors are much smaller.
How to Choose the Right Container?
After all this, how should you choose?
| Requirement | Recommended Container | Reason |
|---|---|---|
| Need Order + Range Queries | <span>std::set</span> |
Red-black trees guarantee order, O(log n) queries |
| Need Deduplication + Fast Queries | <span>std::unordered_set</span> |
Hash tables provide O(1) queries, faster than O(log n) |
| Need Duplicate Elements + Order | <span>std::multiset</span> |
Red-black trees allow duplicates |
| Extreme Performance (Bulk Operations) | <span>std::vector</span> + <span>std::sort</span> |
Bulk insert and sort once, binary search for queries |
| Extreme Performance (Cache Friendly) | <span>absl::btree_set</span> |
B-trees are cache-friendly, but require introducing Abseil |
Red-black trees strike a balance for insertions, deletions, and queries, making them suitable for most scenarios. If your scenario clearly leans towards one end (like only querying, with no insertions or deletions), there may be better choices. However, for general scenarios, red-black trees are the most stable choice, avoiding sudden performance drops in extreme cases, with low performance fluctuations and strong predictability, which is crucial in production environments.
This is the reason why C++ STL chose red-black trees: they may not be the fastest, but they are the most stable; they may not be the most memory-efficient, but they are the most balanced; they may not be the simplest to implement, but they have the fewest bugs. For a general-purpose standard library, this is the most important aspect. Performance is certainly important, but stability, predictability, and portability are equally important, sometimes even more so. This is the difference between engineering and science: science pursues extremes, while engineering seeks balance.
This article is based on a thorough review of relevant authoritative literature and materials, forming a professional and reliable content. All data in the text can be traced back to sources. It is particularly stated that the data and materials have been authorized. The content of this article does not involve any biased viewpoints, but objectively describes the facts with a neutral attitude.