SGI STL 源码阅读：红黑树、Hashtable 与关联式容器
从红黑树节点、header 设计、旋转再平衡到 hashtable 桶结构，理解 set/map/hash_set/hash_map 的底层实现。
阅读地图：先抓住这篇源码的主线
flowchart TD
A[Associative Containers] --> B[有序关联式容器]
A --> C[无序关联式容器]
B --> D[_Rb_tree]
D --> E[set / map]
D --> F[multiset / multimap]
D --> G[header 节点维护 root/min/max]
C --> H[hashtable]
H --> I[bucket vector]
H --> J[链地址节点]
H --> K[rehash 控制负载]有序容器set/map 家族依赖红黑树，保证中序遍历和 O(log n) 查找。
无序容器hash_set/hash_map 依赖 hashtable，用桶和链表换取平均 O(1)。
header 节点维护根、最小、最大节点，使 begin/end 与 --end() 语义成立。
关联式容器(Associative Containers) - SGI STL源码解析
STL中的关联式容器分为两大类：有序关联式容器和无序关联式容器。前者基于红黑树实现，后者基于哈希表实现。 本文从源码层面剖析SGI STL（v3.3）中关联式容器的设计与实现。
源码目录：
/Users/renhezhang/Source-code/sgi-stl/
核心文件：
stl_tree.h（1366行）、stl_set.h、stl_map.h、stl_hashtable.h（1054行）
---
红黑树 - 有序关联式容器的基石
set、map、multiset、multimap这四个容器都基于红黑树(Red-Black Tree)实现。红黑树是一种自平衡二叉搜索树， 通过特定的着色规则和旋转操作保证查找、插入、删除操作的时间复杂度为O(log n)。
红黑树的基本特性
// stl_tree.h:67-69
typedef bool _Rb_tree_Color_type;
const _Rb_tree_Color_type _S_rb_tree_red = false; // 红色 = false
const _Rb_tree_Color_type _S_rb_tree_black = true; // 黑色 = true
红黑树必须满足以下五条性质：
- 每个节点非红即黑
- 根节点必为黑
- 红节点的子节点必为黑（不能出现两个连续的红节点）
- 任一节点到null路径上的黑色节点数量相同（新插入元素默认为红）
- null节点视为黑
红黑树节点结构
// stl_tree.h:71-99
// 基类 - 不包含值域，只包含三叉链和颜色
struct _Rb_tree_node_base
{
typedef _Rb_tree_Color_type _Color_type;
typedef _Rb_tree_node_base* _Base_ptr;
_Color_type _M_color; // 节点颜色（bool型，false=red, true=black）
_Base_ptr _M_parent; // 父节点指针，用于旋转时更新父子链
_Base_ptr _M_left; // 左子节点指针
_Base_ptr _M_right; // 右子节点指针
// 寻找以__x为根的子树的最小节点（中序遍历最左）
// stl_tree.h:81-85
static _Base_ptr _S_minimum(_Base_ptr __x)
{
while (__x->_M_left != 0) __x = __x->_M_left;
return __x;
}
// 寻找以__x为根的子树的最大节点（中序遍历最右）
// stl_tree.h:87-91
static _Base_ptr _S_maximum(_Base_ptr __x)
{
while (__x->_M_right != 0) __x = __x->_M_right;
return __x;
}
};
// 模板节点类 - 继承自基类，并添加值域
// stl_tree.h:94-99
template <class _Value>
struct _Rb_tree_node : public _Rb_tree_node_base
{
typedef _Rb_tree_node<_Value>* _Link_type;
_Value _M_value_field; // 实际存储的值（set中为Key，map中为pair）
};
设计亮点：基类+模板子类
这里采用了基类+模板子类的设计模式，将与值类型无关的通用结构（指针、颜色）与具体的值域分离。 _Rb_tree_node_base 不依赖 _Value，所以所有旋转、再平衡函数只操作 base 指针， 无需知道具体类型——这是典型的traits手法，复用程度极高。
红黑树迭代器
// stl_tree.h:102-195
// 基类迭代器 - 实现递增/递减逻辑
struct _Rb_tree_base_iterator
{
typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
typedef bidirectional_iterator_tag iterator_category; // 双向迭代器
typedef ptrdiff_t difference_type;
_Base_ptr _M_node; // 当前节点指针
// 递增操作 - 寻找中序后继节点
// stl_tree.h:109-125
void _M_increment()
{
if (_M_node->_M_right != 0) {
// 情况A: 有右子树 → 右子树中最左的节点
_M_node = _M_node->_M_right;
while (_M_node->_M_left != 0)
_M_node = _M_node->_M_left;
}
else {
// 情况B: 无右子树 → 往上回溯，直到成为父节点的左子
_Base_ptr __y = _M_node->_M_parent;
while (_M_node == __y->_M_right) {
_M_node = __y;
__y = __y->_M_parent;
}
// 关键：如果当前节点是右子节点，此时__y是父节点，需要跳过header
// 只有在"不是header本身"的情况下才赋值
if (_M_node->_M_right != __y)
_M_node = __y;
}
}
// 递减操作 - 寻找中序前驱节点
// stl_tree.h:127-146
void _M_decrement()
{
// 特殊处理: header节点递减的情况（这是STL end()的特殊语义）
// stl_tree.h:129-131
if (_M_node->_M_color == _S_rb_tree_red &&
_M_node->_M_parent->_M_parent == _M_node)
_M_node = _M_node->_M_right; // header的右子就是最大节点
else if (_M_node->_M_left != 0) {
// 情况A: 有左子树 → 左子树中最右的节点
_Base_ptr __y = _M_node->_M_left;
while (__y->_M_right != 0)
__y = __y->_M_right;
_M_node = __y;
}
else {
// 情况B: 无左子树 → 往上回溯，直到成为父节点的右子
_Base_ptr __y = _M_node->_M_parent;
while (_M_node == __y->_M_left) {
_M_node = __y;
__y = __y->_M_parent;
}
_M_node = __y;
}
}
};
// 模板迭代器类 - 添加value_type相关的类型定义和操作符
// stl_tree.h:149-185
template <class _Value, class _Ref, class _Ptr>
struct _Rb_tree_iterator : public _Rb_tree_base_iterator
{
typedef _Value value_type;
typedef _Ref reference;
typedef _Ptr pointer;
// 支持const_iterator和iterator两种实例化
typedef _Rb_tree_iterator<_Value, _Value&, _Value*> iterator;
typedef _Rb_tree_iterator<_Value, const _Value&, const _Value*> const_iterator;
typedef _Rb_tree_iterator<_Value, _Ref, _Ptr> _Self;
typedef _Rb_tree_node<_Value>* _Link_type;
_Rb_tree_iterator() {}
_Rb_tree_iterator(_Link_type __x) { _M_node = __x; }
_Rb_tree_iterator(const iterator& __it) { _M_node = __it._M_node; }
reference operator*() const { return _Link_type(_M_node)->_M_value_field; }
pointer operator->() const { return &(operator*()); }
_Self& operator++() { _M_increment(); return *this; }
_Self operator++(int) {
_Self __tmp = *this;
_M_increment();
return __tmp;
}
_Self& operator--() { _M_decrement(); return *this; }
_Self operator--(int) {
_Self __tmp = *this;
_M_decrement();
return __tmp;
}
};
header节点颜色设计的精妙之处
在 _M_decrement 中，第129-131行的条件判断：
if (_M_node->_M_color == _S_rb_tree_red &&
_M_node->_M_parent->_M_parent == _M_node)
_M_node = _M_node->_M_right;
这段代码专门用来处理 --end() 的情况。
当 iterator 指向 end()（即 _M_header）时：
header->_M_color == red（见_M_empty_initialize第676行）header->_M_parent == _M_root_M_root->_M_parent == header
所以 header->_M_parent->_M_parent == header 成立，直接跳到 header->_M_right（最大节点）。
如果 header 是 black 而非 red，这个特殊分支就不会被触发，--end() 的行为就会出错。
旋转与再平衡
左旋与右旋
// stl_tree.h:216-233 - 左旋
// 将x旋转为其右子y的左子：x下降，y上升
inline void
_Rb_tree_rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
_Rb_tree_node_base* __y = __x->_M_right; // y = x的右子
__x->_M_right = __y->_M_left; // x的右指针指向y的左子
if (__y->_M_left != 0)
__y->_M_left->_M_parent = __x; // y左子的父指针更新
__y->_M_parent = __x->_M_parent; // y的父指针指向x的父
// 根据x是左子还是右子，决定父节点的哪个指针指向y
if (__x == __root)
__root = __y;
else if (__x == __x->_M_parent->_M_left)
__x->_M_parent->_M_left = __y;
else
__x->_M_parent->_M_right = __y;
__y->_M_left = __x; // y的左指针指向x
__x->_M_parent = __y; // x的父指针指向y !!!
}
// stl_tree.h:235-252 - 右旋（对称操作）
inline void
_Rb_tree_rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
_Rb_tree_node_base* __y = __x->_M_left; // y = x的左子
__x->_M_left = __y->_M_right; // x的左指针指向y的右子
if (__y->_M_right != 0)
__y->_M_right->_M_parent = __x;
__y->_M_parent = __x->_M_parent;
if (__x == __root)
__root = __y;
else if (__x == __x->_M_parent->_M_right)
__x->_M_parent->_M_right = __y;
else
__x->_M_parent->_M_left = __y;
__y->_M_right = __x; // y的右指针指向x
__x->_M_parent = __y; // x的父指针指向y
}
插入后的再平衡
// stl_tree.h:254-297 - 插入再平衡
inline void
_Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
__x->_M_color = _S_rb_tree_red; // 新节点必为红（性质4保持）
// 当父节点也是红色时，需要调整（性质3被破坏）
while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red)
{
if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left)
{
// 父节点是祖父的左子
_Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right; // uncle
if (__y && __y->_M_color == _S_rb_tree_red) {
// 情况1: uncle存在且为红 → 只需染色，祖父变红，x上移两层
__x->_M_parent->_M_color = _S_rb_tree_black;
__y->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
__x = __x->_M_parent->_M_parent; // 继续向上检查
}
else {
// 情况2: uncle为黑或不存在
if (__x == __x->_M_parent->_M_right) {
// 三角型（内孙女）：先对父节点左旋，变成直线型
__x = __x->_M_parent;
_Rb_tree_rotate_left(__x, __root);
}
// 直线型（外孙女）：直接右旋祖父
__x->_M_parent->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_right(__x->_M_parent->_M_parent, __root);
}
}
else {
// 对称情况，处理右子树的插入
_Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left; // uncle
if (__y && __y->_M_color == _S_rb_tree_red) {
__x->_M_parent->_M_color = _S_rb_tree_black;
__y->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
__x = __x->_M_parent->_M_parent;
}
else {
if (__x == __x->_M_parent->_M_left) {
__x = __x->_M_parent;
_Rb_tree_rotate_right(__x, __root);
}
__x->_M_parent->_M_color = _S_rb_tree_black;
__x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_left(__x->_M_parent->_M_parent, __root);
}
}
}
__root->_M_color = _S_rb_tree_black; // 根节点必为黑（性质2）
}
旋转判断总结
| Uncle颜色 | 插入形状 | 处理方式 | |-----------|---------|---------| | 红色 | 任意 | 只染色（父+叔变黑，祖父变红，x上移两层），不旋转 | | 黑色 | 三角型（内孙女） | 先对父节点单旋（变直线型），再右旋祖父 → 双旋 | | 黑色 | 直线型（外孙女） | 直接右旋祖父 → 单旋 |
三角型 vs 直线型：以祖父为参考，插入节点和父节点方向相同（都在左或都在右）为直线型，方向相反为三角型。
删除后的再平衡
// stl_tree.h:299-429 - 删除再平衡（最复杂的部分）
// 返回实际被删除的节点（可能是z的后继y，而非z本身）
inline _Rb_tree_node_base*
_Rb_tree_rebalance_for_erase(_Rb_tree_node_base* __z,
_Rb_tree_node_base*& __root,
_Rb_tree_node_base*& __leftmost,
_Rb_tree_node_base*& __rightmost)
{
_Rb_tree_node_base* __y = __z;
_Rb_tree_node_base* __x = 0;
_Rb_tree_node_base* __x_parent = 0;
// 确定实际删除节点y（当z有两个子节点时，y是z的后继）
if (__y->_M_left == 0) // z最多只有一个右子
__x = __y->_M_right;
else if (__y->_M_right == 0) // z只有一个左子
__x = __y->_M_left;
else { // z有两个子节点 → 找后继
__y = __y->_M_right; // y = z的后继
while (__y->_M_left != 0)
__y = __y->_M_left;
__x = __y->_M_right;
}
// relink：把y链接到z的位置（但不复制z的value）
if (__y != __z) { // z有两个子节点，y是后继
__z->_M_left->_M_parent = __y;
__y->_M_left = __z->_M_left;
if (__y != __z->_M_right) {
__x_parent = __y->_M_parent;
if (__x) __x->_M_parent = __y->_M_parent;
__y->_M_parent->_M_left = __x; // y必然是左子
__y->_M_right = __z->_M_right;
__z->_M_right->_M_parent = __y;
}
else
__x_parent = __y;
if (__root == __z)
__root = __y;
else if (__z->_M_parent->_M_left == __z)
__z->_M_parent->_M_left = __y;
else
__z->_M_parent->_M_right = __y;
__y->_M_parent = __z->_M_parent;
__STD::swap(__y->_M_color, __z->_M_color); // 交换颜色：y获得了z的颜色
__y = __z; // 实际删除的是y，但返回值告诉调用者原本的z在哪里
}
else { // y == z：直接删除z（最多一个子节点）
__x_parent = __y->_M_parent;
if (__x) __x->_M_parent = __y->_M_parent;
if (__root == __z)
__root = __x;
else
if (__z->_M_parent->_M_left == __z)
__z->_M_parent->_M_left = __x;
else
__z->_M_parent->_M_right = __x;
// 更新leftmost/rightmost（如果删除的是最左/最右节点）
if (__leftmost == __z)
__leftmost = (__z->_M_right == 0) ? __z->_M_parent : _Rb_tree_node_base::_S_minimum(__x);
if (__rightmost == __z)
__rightmost = (__z->_M_left == 0) ? __z->_M_parent : _Rb_tree_node_base::_S_maximum(__x);
}
// 如果删除的是黑色节点，需要调整以保持黑色高度
if (__y->_M_color != _S_rb_tree_red) {
while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black))
if (__x == __x_parent->_M_left) {
// x是左子
_Rb_tree_node_base* __w = __x_parent->_M_right;
if (__w->_M_color == _S_rb_tree_red) {
__w->_M_color = _S_rb_tree_black;
__x_parent->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_left(__x_parent, __root);
__w = __x_parent->_M_right;
}
if ((__w->_M_left == 0 || __w->_M_left->_M_color == _S_rb_tree_black) &&
(__w->_M_right == 0 || __w->_M_right->_M_color == _S_rb_tree_black)) {
__w->_M_color = _S_rb_tree_red;
__x = __x_parent;
__x_parent = __x_parent->_M_parent;
} else {
if (__w->_M_right == 0 || __w->_M_right->_M_color == _S_rb_tree_black) {
if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black;
__w->_M_color = _S_rb_tree_red;
_Rb_tree_rotate_right(__w, __root);
__w = __x_parent->_M_right;
}
__w->_M_color = __x_parent->_M_color;
__x_parent->_M_color = _S_rb_tree_black;
if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black;
_Rb_tree_rotate_left(__x_parent, __root);
break;
}
} else { // 对称：x是右子
// ... 对称逻辑（_M_left <-> _M_right）
}
if (__x) __x->_M_color = _S_rb_tree_black;
}
return __y; // 返回实际被删除的节点
}
删除操作的精妙设计：后继替身
当被删除节点 z 有两个子节点时，实际删除的是 z 的后继 y（中序遍历中紧随 z 的节点）。 删除后，把 y 链接到 z 的位置，并交换颜色。这样做的好处是：
只有指向 z 的迭代器失效，其他迭代器完全不受影响。
因为树的结构没有改变，只是把 y 的位置换了。
红黑树完整数据结构
// stl_tree.h:436-519 - 内存分配基类
template <class _Tp, class _Alloc>
struct _Rb_tree_base
{
typedef _Alloc allocator_type;
allocator_type get_allocator() const { return allocator_type(); }
_Rb_tree_base(const allocator_type&)
: _M_header(0) { _M_header = _M_get_node(); }
~_Rb_tree_base() { _M_put_node(_M_header); }
protected:
_Rb_tree_node<_Tp>* _M_header; // 哨兵header节点
typedef simple_alloc<_Rb_tree_node<_Tp>, _Alloc> _Alloc_type;
_Rb_tree_node<_Tp>* _M_get_node()
{ return _Alloc_type::allocate(1); }
void _M_put_node(_Rb_tree_node<_Tp>* __p)
{ return _Alloc_type::deallocate(__p, 1); }
};
// stl_tree.h:521-757 - _Rb_tree完整类定义
template <class _Key, class _Value, class _KeyOfValue, class _Compare,
class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
class _Rb_tree : protected _Rb_tree_base<_Value, _Alloc> {
typedef _Rb_tree_base<_Value, _Alloc> _Base;
protected:
typedef _Rb_tree_node_base* _Base_ptr;
typedef _Rb_tree_node<_Value> _Rb_tree_node;
typedef _Rb_tree_Color_type _Color_type;
public:
typedef _Key key_type;
typedef _Value value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef _Rb_tree_node* _Link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef typename _Base::allocator_type allocator_type;
private:
size_type _M_node_count; // 节点数量
_Compare _M_key_compare; // 键比较函数（仿函数）
// 三个关键指针的访问器（通过header间接访问）
// stl_tree.h:581-586
_Link_type& _M_root() const
{ return (_Link_type&) _M_header->_M_parent; }
_Link_type& _M_leftmost() const
{ return (_Link_type&) _M_header->_M_left; }
_Link_type& _M_rightmost() const
{ return (_Link_type&) _M_header->_M_right; }
// 静态方法：节点各指针的访问器（重载了Base_ptr和_Link_type两个版本）
// stl_tree.h:588-612
static _Link_type& _S_left(_Link_type __x)
{ return (_Link_type&)(__x->_M_left); }
static _Link_type& _S_right(_Link_type __x)
{ return (_Link_type&)(__x->_M_right); }
static _Link_type& _S_parent(_Link_type __x)
{ return (_Link_type&)(__x->_M_parent); }
static reference _S_value(_Link_type __x)
{ return __x->_M_value_field; }
// 提取键：使用KeyOfValue函数对象从value中提取key
// stl_tree.h:596-597
static const _Key& _S_key(_Link_type __x)
{ return _KeyOfValue()(_S_value(__x)); }
static _Color_type& _S_color(_Link_type __x)
{ return (_Color_type&)(__x->_M_color); }
static _Link_type _S_minimum(_Link_type __x)
{ return (_Link_type) _Rb_tree_node_base::_S_minimum(__x); }
static _Link_type _S_maximum(_Link_type __x)
{ return (_Link_type) _Rb_tree_node_base::_S_maximum(__x); }
public:
typedef _Rb_tree_iterator<value_type, reference, pointer> iterator;
typedef _Rb_tree_iterator<value_type, const_reference, const_pointer> const_iterator;
// ... reverse_iterator定义
private:
iterator _M_insert(_Base_ptr __x, _Base_ptr __y, const value_type& __v);
_Link_type _M_copy(_Link_type __x, _Link_type __p);
void _M_erase(_Link_type __x);
public:
// 构造函数：初始化header
// stl_tree.h:675-681
void _M_empty_initialize() {
_S_color(_M_header) = _S_rb_tree_red; // header为红，区别于root
_M_root() = 0;
_M_leftmost() = _M_header;
_M_rightmost() = _M_header;
}
// 插入操作：两套接口
// stl_tree.h:710-711
pair<iterator,bool> insert_unique(const value_type& __x);
iterator insert_equal(const value_type& __x);
// find/lower_bound/upper_bound
// stl_tree.h:744-752
iterator find(const key_type& __x);
iterator lower_bound(const key_type& __x);
iterator upper_bound(const key_type& __x);
// 调试：验证红黑树性质
// stl_tree.h:756
bool __rb_verify() const;
};
header节点的设计
stl_tree.h:675-681 中的 _M_empty_initialize() 揭示了header节点的精妙设计：
header节点是一个哨兵（不存储真实数据），它的三个指针用途：
header->_M_parent → 指向真实root
header->_M_left → 指向最小节点（begin()返回值）
header->_M_right → 指向最大节点
好处：
1. begin() = O(1)：直接返回 header->_M_left
2. end() = O(1)：直接返回 header 自身
3. ++/-- 迭代器操作更统一：header是循环链表的一部分
模板参数 _KeyOfValue 的核心作用
_KeyOfValue 是一个函数对象，负责从 value 中提取 key：
- set用
_Identity<value_type>：key就是value，直接返回自身 - map用
_Select1st<value_type>：从pair中取出first（key）
这使得同一套 _Rb_tree 代码能同时服务于 set/map，差异只在 KeyOfValue。
红黑树的插入详解：insert_equal vs insert_equal
内部插入函数 _M_insert
// stl_tree.h:854-886 - 内部插入函数
// __x = 新节点插入位置（初始为null），__y = 插入位置的父节点
template <class _Key, class _Value, class _KeyOfValue, class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::_M_insert(_Base_ptr __x_, _Base_ptr __y_, const _Value& __v)
{
_Link_type __x = (_Link_type) __x_;
_Link_type __y = (_Link_type) __y_;
_Link_type __z;
if (__y == _M_header || __x != 0 ||
_M_key_compare(_KeyOfValue()(__v), _S_key(__y))) {
// 条件1: y是header（插入第一个节点）
// 条件2: x非null（hint插入）
// 条件3: 新值 < y的key（应插在y的左子）
__z = _M_create_node(__v);
_S_left(__y) = __z; // 设为左子
if (__y == _M_header) { // 第一个节点
_M_root() = __z;
_M_rightmost() = __z;
}
else if (__y == _M_leftmost())
_M_leftmost() = __z; // 维护最小指针
}
else {
// 新值 > y的key，插入y的右子
__z = _M_create_node(__v);
_S_right(__y) = __z;
if (__y == _M_rightmost())
_M_rightmost() = __z; // 维护最大指针
}
_S_parent(__z) = __y;
_S_left(__z) = 0;
_S_right(__z) = 0;
_Rb_tree_rebalance(__z, _M_header->_M_parent); // 插入后平衡
++_M_node_count;
return iterator(__z);
}
insert_equal — 允许重复键
// stl_tree.h:890-902
template <class _Key, class _Value, class _KeyOfValue, class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::insert_equal(const _Value& __v)
{
_Link_type __y = _M_header;
_Link_type __x = _M_root();
// 从根向下，找到新值应该插入的空位置
while (__x != 0) {
__y = __x;
__x = _M_key_compare(_KeyOfValue()(__v), _S_key(__x)) ?
_S_left(__x) : _S_right(__x); // v < key ? 左 : 右
}
return _M_insert(__x, __y, __v); // __x此时为0，__y为插入位置的父节点
}
insert_unique — 键必须唯一
// stl_tree.h:904-929
template <class _Key, class _Value, class _KeyOfValue, class _Compare, class _Alloc>
pair<typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator, bool>
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::insert_unique(const _Value& __v)
{
_Link_type __y = _M_header;
_Link_type __x = _M_root();
bool __comp = true;
// 搜索路径与insert_equal相同
while (__x != 0) {
__y = __x;
__comp = _M_key_compare(_KeyOfValue()(__v), _S_key(__x));
__x = __comp ? _S_left(__x) : _S_right(__x);
}
iterator __j = iterator(__y);
if (__comp)
if (__j == begin()) // 搜索停在最小位置
return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
else
--__j; // 检查前驱
// 关键：在插入之前，还要确认前驱的key < 待插值
// insert_equal没有这一步，所以允许重复
if (_M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
return pair<iterator,bool>(__j, false); // 键已存在，插入失败
}
核心区别总结
| | insert_equal | insert_unique | |---|---|---| | 返回值 | iterator | pair<iterator, bool> | | 重复键 | 允许 | 拒绝 | | 关键代码 | 找到空位就插（第898-900行） | 多一步前驱检查（第926行）：!_M_key_compare(_S_key(__j), v) | | 调用 | multiset/multimap | set/map |
红黑树的搜索操作
find — 找等于k的节点
// stl_tree.h:1147-1162
template <class _Key, class _Value, class _KeyOfValue, class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
{
_Link_type __y = _M_header; // 记录"最后一个不小于k"的节点
_Link_type __x = _M_root(); // 从root开始
while (__x != 0)
if (!_M_key_compare(_S_key(__x), __k)) // key >= k
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
iterator __j = iterator(__y);
// 最终判断：__y是"不小于k"的第一个，如果"k < __y的key"，说明k不存在
return (__j == end() || _M_key_compare(__k, _S_key(__j._M_node))) ?
end() : __j;
}
lower_bound — 找 ≥ k 的第一个
// stl_tree.h:1197-1211
template <class _Key, class _Value, class _KeyOfValue, class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::lower_bound(const _Key& __k)
{
_Link_type __y = _M_header;
_Link_type __x = _M_root();
while (__x != 0)
if (!_M_key_compare(_S_key(__x), __k)) // key >= k → 记录并继续往左
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
return iterator(__y);
}
upper_bound — 找 > k 的第一个
// stl_tree.h:1233-1247
template <class _Key, class _Value, class _KeyOfValue, class _Compare, class _Alloc>
typename _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::iterator
_Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>
::upper_bound(const _Key& __k)
{
_Link_type __y = _M_header;
_Link_type __x = _M_root();
while (__x != 0)
if (_M_key_compare(__k, _S_key(__x))) // key > k → 记录并继续往左
__y = __x, __x = _S_left(__x);
else
__x = _S_right(__x);
return iterator(__y);
}
三者对比
三个函数的搜索路径完全相同，区别仅在于更新 __y 的条件：
| 函数 | 更新条件 | __y的语义 | |------|---------|-----------| | find | !_M_key_compare(key(x), k) 即 key >= k | 不小于k的节点 | | lower_bound | !_M_key_compare(key(x), k) 即 key >= k | 不小于k的节点（第一个） | | upper_bound | _M_key_compare(k, key(x)) 即 key > k | 大于k的节点（第一个） |
红黑树验证函数
// stl_tree.h:1289-1301 - 黑色节点计数
inline int
__black_count(_Rb_tree_node_base* __node, _Rb_tree_node_base* __root)
{
if (__node == 0)
return 0;
else {
int __bc = __node->_M_color == _S_rb_tree_black ? 1 : 0;
if (__node == __root)
return __bc;
else
return __bc + __black_count(__node->_M_parent, __root);
}
}
// stl_tree.h:1303-1337 - __rb_verify：验证红黑树五大性质
template <class _Key, class _Value, class _KeyOfValue, class _Compare, class _Alloc>
bool _Rb_tree<_Key,_Value,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
{
if (_M_node_count == 0 || begin() == end())
return _M_node_count == 0 && begin() == end() &&
_M_header->_M_left == _M_header && _M_header->_M_right == _M_header;
// 验证：所有路径上黑色节点数量相同
int __len = __black_count(_M_leftmost(), _M_root());
for (const_iterator __it = begin(); __it != end(); ++__it) {
_Link_type __x = (__it._M_node);
_Link_type __L = _S_left(__x);
_Link_type __R = _S_right(__x);
// 性质3：红节点的两个子都是黑
if (__x->_M_color == _S_rb_tree_red)
if ((__L && __L->_M_color == _S_rb_tree_red) ||
(__R && __R->_M_color == _S_rb_tree_red))
return false;
// BST性质：左子 < 当前 < 右子
if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
return false;
if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
return false;
// 黑色高度：每条路径上黑色节点数相同
if (!__L && !__R && __black_count(__x, _M_root()) != __len)
return false;
}
// 验证header指针是否正确
if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
return false;
if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
return false;
return true;
}
---
set - 键值集合
set是最简单的关联式容器，其特点是：键即值，键唯一，自动排序
set的实现
// stl_set.h:58-209
template <class _Key, class _Compare __STL_DEPENDENT_DEFAULT_TMPL(less<_Key>),
class _Alloc = __STL_DEFAULT_ALLOCATOR(_Key) >
class set {
typedef _Key key_type;
typedef _Key value_type; // 键和值类型相同
typedef _Compare key_compare;
typedef _Compare value_compare; // 值比较和键比较相同
private:
// 关键: _Identity意味着key就是value
// stl_set.h:73-74
typedef _Rb_tree<key_type, value_type,
_Identity<value_type>, key_compare, _Alloc> _Rep_type;
_Rep_type _M_t; // 内部真正存储数据的红黑树
public:
// set的迭代器全是const的——不允许修改元素
// stl_set.h:81-82
typedef typename _Rep_type::const_iterator iterator;
typedef typename _Rep_type::const_iterator const_iterator;
// insert操作只能通过insert_unique
// stl_set.h:148-151
pair<iterator,bool> insert(const value_type& __x) {
pair<typename _Rep_type::iterator, bool> __p = _M_t.insert_unique(__x);
return pair<iterator, bool>(__p.first, __p.second);
}
// count只能是0或1，因为键唯一
// stl_set.h:185-187
size_type count(const key_type& __x) const {
return _M_t.find(__x) == _M_t.end() ? 0 : 1;
}
};
set的核心要点
_Identity<value_type>：key的提取方式就是返回value自身（set中key==value）- 迭代器全是
const：set的元素不能被修改，因为修改可能破坏有序性 insert_unique而非insert_equal：set不允许重复键count()返回 0 或 1：因为键唯一
---
map - 键值对容器
map的特点是：键唯一，自动排序，每个键对应一个值
map的实现
// stl_map.h:58-236
template <class _Key, class _Tp, class _Compare __STL_DEPENDENT_DEFAULT_TMPL(less<_Key>),
class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class map {
typedef _Key key_type;
typedef _Tp data_type;
typedef _Tp mapped_type; // 与data_type同义
typedef pair<const _Key, _Tp> value_type; // map的value是pair
class value_compare
: public binary_function<value_type, value_type, bool> {
friend class map<_Key,_Tp,_Compare,_Alloc>;
protected:
_Compare comp;
value_compare(_Compare __c) : comp(__c) {}
public:
// 比较两个pair时，只比较first（键）
bool operator()(const value_type& __x, const value_type& __y) const {
return comp(__x.first, __y.first);
}
};
private:
// 关键: _Select1st用于从pair中提取key
// stl_map.h:87-88
typedef _Rb_tree<key_type, value_type,
_Select1st<value_type>, key_compare, _Alloc> _Rep_type;
_Rep_type _M_t;
public:
// map的迭代器不是const的，可以修改second（值），但不能修改first（键）
// stl_map.h:95-96
typedef typename _Rep_type::iterator iterator;
typedef typename _Rep_type::const_iterator const_iterator;
// operator[]: 找键，找不到则插入默认值
// stl_map.h:165-171
_Tp& operator[](const key_type& __k) {
iterator __i = lower_bound(__k);
if (__i == end() || key_comp()(__k, (*__i).first))
__i = insert(__i, value_type(__k, _Tp())); // 插入默认值
return (*__i).second; // 返回值的引用（可修改）
}
};
map::operator[] 的实现细节
stl_map.h:165-171 的 operator[] 调用链：
m[key] →
1. lower_bound(key) → 找到第一个 >= key 的位置
2. 如果找不到 或 key < 该位置的值 → insert默认pair
3. 返回 (*iterator).second 的引用
注意：
- operator[] 只能用于非const的map
- 找不到键时会插入默认值（value的默认构造），这可能是昂贵的
- 频繁使用operator[]检查存在性是低效的，应该先用find()
set/map vs multiset/multimap 的核心区别
set / map → 使用 insert_unique，键必须唯一
multiset / multimap → 使用 insert_equal，允许重复键
// stl_multiset.h:73-74 - 与set完全相同，但用insert_equal
typedef _Rb_tree<key_type, value_type,
_Identity<value_type>, key_compare, _Alloc> _Rep_type;
// stl_multiset.h:154-156
iterator insert(const value_type& __x) {
return _M_t.insert_equal(__x); // ← 区别在这里
}
// stl_multimap.h:87-88 - 与map相同模板参数
typedef _Rb_tree<key_type, value_type,
_Select1st<value_type>, key_compare, _Alloc> _Rep_type;
// stl_multimap.h:167 - 返回类型也不同
iterator insert(const value_type& __x) { return _M_t.insert_equal(__x); }
// map.insert_unique返回pair<iterator,bool>，multimap.insert_equal返回iterator
multiset/multimap 的 count() 可以大于1
// stl_multiset.h:191 - multiset的count实现
size_type count(const _Key& __x) const { return _M_t.count(__x); }
// stl_tree.h:1185-1193 - _Rb_tree的count实现
size_type count(const _Key& __k) const {
pair<const_iterator, const_iterator> __p = equal_range(__k);
size_type __n = 0;
distance(__p.first, __p.second, __n);
return __n; // 可以返回 >= 0 的数，而不仅是0或1
}
---
哈希表 - 无序关联式容器的基石
C++11引入的unordered_set、unordered_map等容器，在SGI STL中对应的是hash_set、hash_map等。 这些容器基于哈希表实现，查找、插入、删除操作平均时间复杂度为O(1)。
hashtable节点
// stl_hashtable.h:49-54
template <class _Val>
struct _Hashtable_node
{
_Hashtable_node* _M_next; // 指向同桶中的下一个节点（单向链表）
_Val _M_val; // 存储的值
};
与红黑树节点的本质区别：hashtable节点只有单向链表指针（_M_next），没有父/子指针。 因为hashtable是桶数组结构，而非树形结构。
hashtable的核心结构
// stl_hashtable.h:186-568
template <class _Val, class _Key, class _HashFcn,
class _ExtractKey, class _EqualKey, class _Alloc>
class hashtable {
public:
typedef _Key key_type;
typedef _Val value_type;
typedef _HashFcn hasher; // 哈希函数
typedef _EqualKey key_equal; // 键相等判断
private:
hasher _M_hash; // 哈希函数对象
key_equal _M_equals; // 相等判断对象
_ExtractKey _M_get_key; // 从value提取key
vector<_Node*,_Alloc> _M_buckets; // 桶数组
size_type _M_num_elements; // 元素个数
};
关键设计：
_M_buckets是vector<_Node*>，每个元素是一个桶的头指针- 每个桶内是单向链表，相同哈希值的元素链在一起
- 哈希函数
_M_hash用于计算桶编号，key相等判断_M_equals用于比较
素数表与桶数量
// stl_hashtable.h:148-166
enum { __stl_num_primes = 28 };
static const unsigned long __stl_prime_list[__stl_num_primes] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
1610612741ul, 3221225473ul, 4294967295ul
};
// 找到 >= n 的最小素数
inline unsigned long __stl_next_prime(unsigned long __n)
{
const unsigned long* __first = __stl_prime_list;
const unsigned long* __last = __stl_prime_list + (int)__stl_num_primes;
const unsigned long* pos = lower_bound(__first, __last, __n);
return pos == __last ? *(__last - 1) : *pos;
}
为什么用素数作为桶数量？
当除数（桶数量）是素数时，对于哈希值 h，(h % prime) 的结果分布更均匀， 能有效减少冲突。
哈希函数
// stl_hash_fun.h
// 默认hash类：只提供特化版本，不提供通用模板
template <class _Key> struct hash { };
// char* 特化
__STL_TEMPLATE_NULL struct hash<char*> {
size_t operator()(const char* __s) const { return __stl_hash_string(__s); }
};
// 字符串哈希实现
inline size_t __stl_hash_string(const char* __s)
{
unsigned long __h = 0;
for (; *__s; ++__s)
__h = 5*__h + *__s; // h = h * 5 + char_value
return size_t(__h);
}
// 内置类型的特化
__STL_TEMPLATE_NULL struct hash<int> {
size_t operator()(int __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<long> {
size_t operator()(long __x) const { return __x; }
};
// ... 其他内置类型
注意：SGI STL的hash函数只提供了内置类型和char*的特化， 没有提供string的特化（需要用户自己提供）。
哈希表迭代器
// stl_hashtable.h:68-104
template <class _Val, class _Key, class _HashFcn,
class _ExtractKey, class _EqualKey, class _Alloc>
struct _Hashtable_iterator {
typedef _Hashtable_node<_Val> _Node;
typedef forward_iterator_tag iterator_category; // ← 单向迭代器！
_Node* _M_cur; // 当前节点
_Hashtable* _M_ht; // 指向哈希表本体（用于跨桶移动）
// 递增操作
// stl_hashtable.h:572-583
iterator& operator++() {
const _Node* __old = _M_cur;
_M_cur = _M_cur->_M_next; // 先在桶内向后移动
if (!_M_cur) {
// 桶内已到末尾，寻找下一个非空桶
size_type __bucket = _M_ht->_M_bkt_num(__old->_M_val);
while (!_M_cur && ++__bucket < _M_ht->_M_buckets.size())
_M_cur = _M_ht->_M_buckets[__bucket];
}
return *this;
}
};
重要：哈希表迭代器是 forward_iterator（单向迭代器），只能向前移动。 这与红黑树的 bidirectional_iterator 不同。
插入操作
insert_unique — 不允许重复键
// stl_hashtable.h:361-365 (调用层)
// stl_hashtable.h:710-727 (实现层)
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
pair<typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator, bool>
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
::insert_unique_noresize(const value_type& __obj)
{
const size_type __n = _M_bkt_num(__obj); // 计算桶编号
_Node* __first = _M_buckets[__n];
// 在桶内查找是否已存在
for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj)))
return pair<iterator, bool>(iterator(__cur, this), false);
// 头插法插入新节点
_Node* __tmp = _M_new_node(__obj);
__tmp->_M_next = __first;
_M_buckets[__n] = __tmp;
++_M_num_elements;
return pair<iterator, bool>(iterator(__tmp, this), true);
}
insert_equal — 允许重复键
// stl_hashtable.h:367-371 (调用层)
// stl_hashtable.h:729-751 (实现层)
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::iterator
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
::insert_equal_noresize(const value_type& __obj)
{
const size_type __n = _M_bkt_num(__obj);
_Node* __first = _M_buckets[__n];
// 查找是否已存在（允许重复）
for (_Node* __cur = __first; __cur; __cur = __cur->_M_next)
if (_M_equals(_M_get_key(__cur->_M_val), _M_get_key(__obj))) {
// 找到后，在当前位置后插入
_Node* __tmp = _M_new_node(__obj);
__tmp->_M_next = __cur->_M_next;
__cur->_M_next = __tmp;
++_M_num_elements;
return iterator(__tmp, this);
}
// 不存在则头插
_Node* __tmp = _M_new_node(__obj);
__tmp->_M_next = __first;
_M_buckets[__n] = __tmp;
++_M_num_elements;
return iterator(__tmp, this);
}
insert_unique vs insert_equal 的核心区别
| | insert_unique | insert_equal | |---|---|---| | 已存在时的行为 | 返回 {existing_iterator, false} | 在同桶中该键之后插入新节点 | | 均不存在时 | 头插 | 头插 | | 返回值 | pair<iterator, bool> | iterator | | 调用 | hash_set / hash_map | hash_multiset / hash_multimap |
insert_equal找到重复键后是在该节点之后插入，而不是头插——这保证了相同键的元素保持插入顺序。
负载因子与再哈希
// stl_hashtable.h:361-365 - 插入前先检查是否需要rehash
pair<iterator, bool> insert_unique(const value_type& __obj)
{
resize(_M_num_elements + 1); // ← 关键：插入前尝试扩容
return insert_unique_noresize(__obj);
}
// stl_hashtable.h:930-967 - resize实现
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
void hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>
::resize(size_type __num_elements_hint)
{
const size_type __old_n = _M_buckets.size();
if (__num_elements_hint > __old_n) {
// 找到下一个素数作为新桶数
const size_type __n = _M_next_size(__num_elements_hint);
if (__n > __old_n) {
vector<_Node*, _All> __tmp(__n, (_Node*)(0),
_M_buckets.get_allocator());
__STL_TRY {
// 遍历所有旧桶，重新哈希每个元素到新桶
for (size_type __bucket = 0; __bucket < __old_n; ++__bucket) {
_Node* __first = _M_buckets[__bucket];
while (__first) {
size_type __new_bucket = _M_bkt_num(__first->_M_val, __n);
_M_buckets[__bucket] = __first->_M_next;
// 头插到新桶
__first->_M_next = __tmp[__new_bucket];
__tmp[__new_bucket] = __first;
__first = _M_buckets[__bucket];
}
}
_M_buckets.swap(__tmp); // 交换：__tmp是旧桶，__buckets是新桶
}
// 异常处理...
}
}
}
再哈希时机：resize() 在每次 insert 操作前被调用（insert_unique 第363行）。 判断条件是 __num_elements_hint > _M_buckets.size()，即元素数量是否超过桶数量。
删除操作
// stl_hashtable.h:824-856 - 按键删除
template <class _Val, class _Key, class _HF, class _Ex, class _Eq, class _All>
typename hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::size_type
hashtable<_Val,_Key,_HF,_Ex,_Eq,_All>::erase(const key_type& __key)
{
const size_type __n = _M_bkt_num_key(__key);
_Node* __first = _M_buckets[__n];
size_type __erased = 0;
if (__first) {
_Node* __cur = __first;
_Node* __next = __cur->_M_next;
while (__next) {
if (_M_equals(_M_get_key(__next->_M_val), __key)) {
__cur->_M_next = __next->_M_next;
_M_delete_node(__next);
__next = __cur->_M_next;
++__erased;
--_M_num_elements;
}
else {
__cur = __next;
__next = __cur->_M_next;
}
}
// 处理桶的第一个节点
if (_M_equals(_M_get_key(__first->_M_val), __key)) {
_M_buckets[__n] = __first->_M_next;
_M_delete_node(__first);
++__erased;
--_M_num_elements;
}
}
return __erased;
}
删除逻辑：先定位到对应桶，然后遍历该桶的单向链表，删除匹配的节点。
hashtable的find
// stl_hashtable.h:465-474
iterator find(const key_type& __key)
{
size_type __n = _M_bkt_num_key(__key); // 先计算桶编号
_Node* __first;
// 只在对应桶内查找，不用遍历全表
for (__first = _M_buckets[__n];
__first && !_M_equals(_M_get_key(__first->_M_val), __key);
__first = __first->_M_next)
{}
return iterator(__first, this);
}
O(1) 查找的原理：先通过哈希函数直接定位到桶（O(1)），然后只在对应桶的短链表内查找（平均O(1)）。
---
hash_set与hash_map
// stl_hash_set.h
template <class _Value,
class _HashFcn __STL_DEPENDENT_DEFAULT_TMPL(hash<_Value>),
class _EqualKey __STL_DEPENDENT_DEFAULT_TMPL(equal_to<_Value>),
class _Alloc = __STL_DEFAULT_ALLOCATOR(_Value) >
class hash_set {
private:
// 内部使用hashtable，_Identity表示key就是value
typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>,
_EqualKey, _Alloc> _Ht;
_Ht _M_ht;
...
};
// stl_hash_map.h
template <class _Key, class _Tp,
class _HashFcn __STL_DEPENDENT_DEFAULT_TMPL(hash<_Key>),
class _EqualKey __STL_DEPENDENT_DEFAULT_TMPL(equal_to<_Key>),
class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class hash_map {
private:
// 内部使用hashtable，_Select1st从pair中提取key
typedef hashtable<pair<const _Key,_Tp>,_Key,_HashFcn,
_Select1st<pair<const _Key,_Tp> >,_EqualKey,_Alloc> _Ht;
_Ht _M_ht;
...
};
与set/map的结构完全一致：只是底层数据结构从 _Rb_tree 换成了 hashtable， insert_unique 换成了 hashtable::insert_unique，KeyOfValue 换成了 ExtractKey。
---
有序容器 vs 无序容器
时间复杂度对比
| 操作 | 有序容器（RBTree） | 无序容器（HashTable） | |------|-------------------|---------------------| | 查找 | O(log n) | O(1) 平均，O(n) 最坏 | | 插入 | O(log n) | O(1) 平均 | | 删除 | O(log n) | O(1) 平均 | | 遍历（有序） | O(n)，自然有序 | O(n)，遍历后无序 | | lower_bound/upper_bound | O(log n) | 不支持 |
SGI STL的设计模式总结
- 组件复用：set/map/multiset/multimap底层都是
_Rb_tree，只是模板参数不同 - 函数对象适配：
_Identity和_Select1st让同一套树结构适应不同的提取键需求 - hash容器同理：都基于
hashtable - insert_unique vs insert_equal：区分唯一键和可重复键容器的核心
- 基类+模板子类：
_Rb_tree_node_base+_Rb_tree_node<Value>实现值类型与结构分离
---
总结
SGI STL的关联式容器设计体现了STL的核心思想：数据结构和算法分离，通过迭代器粘合。
红黑树和哈希表分别是有序和无序关联式容器的基石， 而set/map/multiset/multimap和hash_set/hash_map/hash_multiset/hash_multimap只是在相同的底层数据结构上，通过不同的模板参数（主要是KeyOfValue/ExtractKey）实现差异化。
理解这一点后，STL关联式容器的实现就变得清晰了。
--- 节选自侯捷《STL源码剖析》，SGI STL v3.3源码对照解析