15000w+字详解SGI-STL关联式容器(Associative_Containers)

Dust-Chasing

70人浏览 · 2026-04-04 16:18:12

Dust-Chasing · 2026-04-04 16:18:12 发布

关联式容器(Associative Containers) - SGI STL源码解析

STL中的关联式容器分为两大类：有序关联式容器和无序关联式容器。前者基于红黑树实现，后者基于哈希表实现。
本文将从源码层面剖析SGI STL中关联式容器的设计与实现

红黑树 - 有序关联式容器的基石

set、map、multiset、multimap这四个容器都基于红黑树(Red-Black Tree)实现。红黑树是一种自平衡二叉搜索树，
通过特定的着色规则和旋转操作保证查找、插入、删除操作的时间复杂度为O(log n)。

红黑树的基本特性

// stl_tree.h
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

// 基类 - 不包含值域，只包含三叉链和颜色
struct _Rb_tree_node_base
{
  typedef _Rb_tree_Color_type _Color_type;
  typedef _Rb_tree_node_base* _Base_ptr;

  _Color_type _M_color;   // 节点颜色
  _Base_ptr _M_parent;    // 父节点指针，为了方便红黑树的旋转操作
  _Base_ptr _M_left;      // 左子节点指针
  _Base_ptr _M_right;     // 右子节点指针

  // 寻找以__x为根的子树的最小节点
  static _Base_ptr _S_minimum(_Base_ptr __x)
  {
    while (__x->_M_left != 0) __x = __x->_M_left;
    return __x;
  }

  // 寻找以__x为根的子树的最大节点
  static _Base_ptr _S_maximum(_Base_ptr __x)
  {
    while (__x->_M_right != 0) __x = __x->_M_right;
    return __x;
  }
};

// 模板节点类 - 继承自基类，并添加值域
template <class _Value>
struct _Rb_tree_node : public _Rb_tree_node_base
{
  typedef _Rb_tree_node<_Value>* _Link_type;
  _Value _M_value_field;  // 实际存储的值
};

这里采用了基类+模板子类的设计模式，将与值类型无关的通用结构（指针、颜色）与具体的值域分离，
这样可以复用大部分代码

红黑树迭代器

// stl_tree.h

// 基类迭代器 - 实现递增/递减逻辑
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;  // 当前节点指针

  // 递增操作 - 寻找后继节点
  void _M_increment()
  {
    if (_M_node->_M_right != 0) {
      // 情况1: 有右子树 -> 右子树的最左节点
      _M_node = _M_node->_M_right;
      while (_M_node->_M_left != 0)
        _M_node = _M_node->_M_left;
    }
    else {
      // 情况2: 无右子树 -> 向上回溯，直到成为父节点的左子
      _Base_ptr __y = _M_node->_M_parent;
      while (_M_node == __y->_M_right) {
        _M_node = __y;
        __y = __y->_M_parent;
      }
      // 如果当前节点是右子节点，此时__y是父节点，需要跳过header
      if (_M_node->_M_right != __y)
        _M_node = __y;
    }
  }

  // 递减操作 - 寻找前驱节点
  void _M_decrement()
  {
    // 特殊处理: header节点的情况
    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) {
      // 情况1: 有左子树 -> 左子树的最右节点
      _Base_ptr __y = _M_node->_M_left;
      while (__y->_M_right != 0)
        __y = __y->_M_right;
      _M_node = __y;
    }
    else {
      // 情况2: 无左子树 -> 向上回溯，直到成为父节点的右子
      _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相关的类型定义
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;

  reference operator*() const { return _Link_type(_M_node)->_M_value_field; }
  pointer operator->() const { return &(operator*()); }

  _Self& operator++() { _M_increment(); return *this; }
  _Self& operator--() { _M_decrement(); return *this; }
};

关键理解：红黑树的迭代器是bidirectional iterator（双向迭代器），不支持随机访问，
只能通过递增/递减操作移动。这是红黑树本身的结构特性决定的

旋转与再平衡

// 左旋 - 将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;
  __x->_M_right = __y->_M_left;
  if (__y->_M_left != 0)
    __y->_M_left->_M_parent = __x;
  __y->_M_parent = __x->_M_parent;

  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;
  __x->_M_parent = __y;
}

// 右旋 - 对称操作
inline void
_Rb_tree_rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
  _Rb_tree_node_base* __y = __x->_M_left;
  __x->_M_left = __y->_M_right;
  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;
  __x->_M_parent = __y;
}

旋转操作是红黑树保持平衡的核心手段。左旋和右旋是对称的操作，
用于调整树的平衡性，插入和删除时都需要调用旋转来维持红黑性质

插入后的再平衡

inline void
_Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root)
{
  __x->_M_color = _S_rb_tree_red;  // 新节点必为红
  while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red) {
    // 如果父节点是红（违背了性质3），需要调整
    if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) {
      _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right;
      // 情况1: 叔叔节点存在且为红 -> 变色即可
      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 {
        // 情况2: 叔叔为黑或不存在
        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;
      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;  // 根节点必为黑
}

插入操作的时间复杂度为O(log n)，其中再平衡过程是主要的开销

红黑树的数据结构

// stl_tree.h

template <class _Key, class _Value, class _KeyOfValue, class _Compare, class _Alloc>
class _Rb_tree : protected _Rb_tree_base<_Value, _Alloc> {
protected:
  typedef _Rb_tree_node_base* _Base_ptr;
  typedef _Rb_tree_node<_Value> _Rb_tree_node;

  // 模板参数说明:
  // _Key: 键类型
  // _Value: 值类型（对于map是pair，对于set是Key本身）
  // _KeyOfValue: 从Value中提取Key的函数对象
  // _Compare: 键比较函数

private:
  size_type _M_node_count;    // 节点数量
  _Compare _M_key_compare;     // 键比较函数

  // 维护三个特殊指针（header节点的设计）
  _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; }

  // 静态方法用于节点操作
  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函数对象
  static const _Key& _S_key(_Link_type __x)
    { return _KeyOfValue()(_S_value(__x)); }
};

header节点的设计

SGI STL的红黑树实现中，引入了一个header节点（不存储实际数据），这是一个巧妙的设计：

header的parent指向根节点
header的left指向最小节点（最左子）
header的right指向最大节点（最右子）
begin()返回最左子节点，end()返回header节点

这样设计使得：

begin()操作可以在O(1)时间内完成
end()操作可以用header直接表示
迭代器的++/–操作更容易实现

_KeyOfValue与_Select1st

在分析set和map之前，必须理解这两个函数对象的作用

// stl_function.h

// _Identity: 返回自身，用于set - key就是value
template <class _Tp>
struct _Identity : public unary_function<_Tp,_Tp> {
  const _Tp& operator()(const _Tp& __x) const { return __x; }
};

// _Select1st: 提取pair的第一个元素，用于map - 从pair中取出key
template <class _Pair>
struct _Select1st : public unary_function<_Pair, typename _Pair::first_type> {
  const typename _Pair::first_type& operator()(const _Pair& __x) const {
    return __x.first;
  }
};

set - 键值集合

set是最简单的关联式容器，其特点是：键即值，键唯一，自动排序

set的实现

// stl_set.h

template <class _Key, class _Compare __STL_DEPENDENT_DEFAULT_TMPL(less<_Key>),
          class _Alloc = __STL_DEFAULT_ALLOCATOR(_Key) >
class set {
  // requirements:
  __STL_CLASS_REQUIRES(_Key, _Assignable);
  __STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Key, _Key);

public:
  typedef _Key     key_type;      // 键类型
  typedef _Key     value_type;     // 值类型（与键相同）
  typedef _Compare key_compare;   // 键比较函数
  typedef _Compare value_compare; // 值比较函数（与键比较相同）

private:
  // 关键: _Identity意味着key就是value
  typedef _Rb_tree<key_type, value_type,
                  _Identity<value_type>, key_compare, _Alloc> _Rep_type;
  _Rep_type _M_t;  // 内部真正存储数据的红黑树

public:
  // 所有迭代器都是const的 - set不允许修改元素
  typedef typename _Rep_type::const_iterator iterator;
  typedef typename _Rep_type::const_iterator const_iterator;
  ...
};

核心理解：set的_Identity<value_type>表示"从value中提取key的方式就是返回value本身"，
这意味着set的键和值是同一个东西

set的插入操作

// set中唯一允许的插入方式是insert_unique
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);
}

insert_unique保证了set中不会有重复的元素。如果插入的键已存在，insert_unique会返回{existing_iterator, false}

set与multiset的区别

set使用insert_unique，multiset使用insert_equal

// multiset使用insert_equal，允许重复键
iterator insert(const value_type& __x) {
  return _M_t.insert_equal(__x);
}

map - 键值对容器

map的特点是：键唯一，自动排序，每个键对应一个值

map的实现

// stl_map.h

template <class _Key, class _Tp,
          class _Compare __STL_DEPENDENT_DEFAULT_TMPL(less<_Key>),
          class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class map {
public:
  typedef _Key                  key_type;
  typedef _Tp                   data_type;
  typedef _Tp                   mapped_type;  // 与data_type同义
  typedef pair<const _Key, _Tp> value_type;   // 键值对

  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
  typedef _Rb_tree<key_type, value_type,
                   _Select1st<value_type>, key_compare, _Alloc> _Rep_type;
  _Rep_type _M_t;
  ...
};

核心理解：map使用_Select1st<value_type>从pair中提取键（first），这样红黑树在比较时可以只比较键

map::operator[]

operator[]是map中最特别的一个函数

// stl_map.h
_Tp& operator[](const key_type& __k) {
  iterator __i = lower_bound(__k);
  // __i->first is greater than or equivalent to __k.
  if (__i == end() || key_comp()(__k, (*__i).first))
    __i = insert(__i, value_type(__k, _Tp()));  // 插入默认值
  return (*__i).second;  // 返回值的引用
}

特性：

如果键不存在，会插入一个默认值（value_type的默认构造）
返回的是值的引用，所以可以用于修改
这也是map不能用const map调用的原因

map与multimap的区别

与set/multiset相同，map使用insert_unique，multimap使用insert_equal

multiset与multimap

multiset和multimap与set和map几乎完全相同，唯一的区别是：

使用insert_equal而非insert_unique
允许键重复

例如multimap的count()可以返回大于1的值，而map的count()只能是0或1

哈希表 - 无序关联式容器的基石

C++11引入的unordered_set、unordered_map等容器，在SGI STL中对应的是hash_set、hash_map等。
这些容器基于哈希表实现，查找、插入、删除操作平均时间复杂度为O(1)

hashtable节点

// stl_hashtable.h

template <class _Val>
struct _Hashtable_node
{
  _Hashtable_node* _M_next;  // 指向同桶中的下一个节点
  _Val _M_val;              // 存储的值
};

与红黑树的节点不同，哈希表节点只有单向链表指针，没有父指针和子指针，
因为哈希表是桶数组的结构，而非树形结构

hashtable的核心结构

// stl_hashtable.h

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，存储每个桶的头指针
每个桶内是单向链表，相同哈希值的元素链在一起
_M_hash用于计算哈希值，_M_equals用于比较键是否相等

素数表与桶数量

// stl_hashtable.h

// 28个素数，用于确定桶的数量
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, 4294967291ul
};

// 找到 >= 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

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
  return size_t(__h);
}

// 内置类型的特化
__STL_TEMPLATE_NULL struct hash<int> {
  size_t operator()(int __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<unsigned int> {
  size_t operator()(unsigned int __x) const { return __x; }
};
__STL_TEMPLATE_NULL struct hash<long> {
  size_t operator()(long __x) const { return __x; }
};
// ... 其他内置类型

注意：SGI STL的hash函数只提供了内置类型和char的特化，
没有提供string的特化。用户需要自己提供或使用标准库的unordered_

哈希表迭代器

// stl_hashtable.h

template <class _Val, class _Key, class _HashFcn,
          class _ExtractKey, class _EqualKey, class _Alloc>
struct _Hashtable_iterator {
  typedef hashtable<_Val,_Key,_HashFcn,_ExtractKey,_EqualKey,_Alloc>
          _Hashtable;
  typedef _Hashtable_iterator<_Val, _Key, _HashFcn,
                              _ExtractKey, _EqualKey, _Alloc>
          iterator;
  typedef forward_iterator_tag iterator_category;  // 向前迭代器
  typedef _Val value_type;
  typedef ptrdiff_t difference_type;
  typedef size_t size_type;
  typedef _Val& reference;
  typedef _Val* pointer;

  _Node* _M_cur;      // 当前节点
  _Hashtable* _M_ht; // 指向哈希表本体

  // 递增操作
  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（单向迭代器），只能向前移动

插入操作

// stl_hashtable.h

// insert_unique - 不允许重复键
pair<iterator, bool> 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 - 允许重复键
iterator 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);
}

头插法的原因：

头插O(1)，尾插需要遍历
新插入的元素被访问的概率更高（局部性原理）

负载因子与再哈希

// stl_hashtable.h

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);
      }
      // 异常处理...
    }
  }
}

什么时候再哈希？
当元素数量接近桶数量时（负载因子过高），冲突会加剧，性能下降。
SGI STL在insert操作前会调用resize，扩展桶数量

hash_set与hash_map

hash_set和hash_map是SGI STL对无序关联式容器的实现

// 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;
  ...
};

hash_multiset和hash_multimap使用insert_equal，与hash_set/hash_map的区别相同

有序容器 vs 无序容器

时间复杂度对比

操作	有序容器（RBTree）	无序容器（HashTable）
查找	O(log n)	O(1) 平均，O(n) 最坏
插入	O(log n)	O(1) 平均
删除	O(log n)	O(1) 平均
遍历（有序）	O(n)，自然有序	O(n)，遍历后排序

选择建议

需要有序遍历 → 选择有序容器（set/map）
查找性能要求极高 → 选择无序容器（hash_set/hash_map）
需要范围查找（如lower_bound/upper_bound）→ 选择有序容器
自定义类型作为键 → 需要提供比较函数（有序）或哈希函数（无序）

SGI STL的设计模式总结

组件复用：set/map/multiset/multimap底层都是_Rb_tree，只是模板参数不同
函数对象适配：_Identity和_Select1st让同一套树结构适应不同的提取键需求
hash容器同理：都基于hashtable
insert_unique vs insert_equal：区分唯一键和可重复键容器的核心

总结

SGI STL的关联式容器设计体现了STL的核心思想：数据结构和算法分离，通过迭代器粘合。

红黑树和哈希表分别是有序和无序关联式容器的基石，
而set/map/multiset/multimap和hash_set/hash_map/hash_multiset/hash_multimap只是
在相同的底层数据结构上，通过不同的模板参数（主要是KeyOfValue/ExtractKey）实现差异化。

理解这一点后，STL关联式容器的实现就变得清晰了。

— 节选自侯捷《STL源码剖析》