STL 剖析：关联式容器（associative containers）

 
 
C++
 6.2k
 

在实现 TinySTL 过程中对思路的一些梳理，并不涉及代码（大概），如有兴趣可以跳至相关实现。关联式容器每个元素都有一个键值（key）和一个实值（value），当插入元素时，容器内部结构（可能是 RB-tree，也可能是 hashtable）便依照其键值大小，以某种特定规则将这个元素放置于适当位置😉

2024-08-26 16:37:52

目录：

1 RB-tree

​ 1.1 概述

​ 1.2 迭代器

​ 1.3 数据结构

​ 1.4 元素操作与空间配置

2 hashtable

​ 2.1 概述

​ 2.2 开链

​ 2.3 迭代器

​ 2.4 数据结构与空间配置

标准的 STL 关联式容器分为 set（集合）和 map（映射表），以及这两大类的衍生体，其实都是 adapter（配接器），其底层机制可能是 RB-tree（红黑树），也可能是 hashtable（散列表）。RB-tree 和 hashtable 也是独立容器，只是并不对外开放。说白了，理解关联式容器就在于对于 RB-tree 和 hashtable 这两种容器的探究

adapter 修改某个容器的接口而成就出另一种容器风格，如果后续有时间的话会深入阐述这个东西，现在你大致了解这一点就行了

1 RB-tree

1.1 概述

红黑树其实本质就是一个平衡二叉搜索树，只是添加了一些需要满足的规则：

  1. 每个节点都有颜色，非红即黑
  2. 根节点是黑色
  3. 父子节点不可以同时为红
  4. 任一节点至 NULL（一般视 NULL 为黑节点）的任意路径上所包含的黑节点数必须相同

红黑树的主要操作（如插入和删除）在维护二叉搜索树的基础性质（左子树的节点值小于根节点，右子树的节点值大于根节点）的同时，还会通过旋转和重新着色来调整树形以保持红黑树的平衡

为了理解红黑树的性质，接下里会以分解成图的形式来展示红黑树的插入操作，以下示例图讨论了各种情况下的插入节点：

17242462508851724246250057.png

这里为了方便讨论，为一些特殊节点命名别名，假设新节点为 X，其父节点为 P，祖父节点为 G，伯父节点为 S，曾祖父节点为 GG。根据二叉搜索树规则，新节点 X 必为叶节点。根据红黑树规则4，X 必为红。若 P 也为红（这违反了规则3，因此接下来必须调整树形），则 G 必为黑。于是根据 X 的插入位置及外围节点（S 和 GG）的颜色，有了以下四种考虑：

  • 状况1：S 为黑且 X 为外侧插入

    17242350058851724235005603.png

  • 状况2：S 为黑且 X 为内侧插入

    17242440628851724244062240.png

    如果你仔细观察的话，你就会发现这里的旋转过程很不符合逻辑，首先就是在左旋（第一个单旋转）的过程中节点的颜色改变，这个颜色改变是不符合规则4的，其次是经过左旋的颜色改变后实则就不再需要调整树形了。出于逻辑的考虑，这里应该是在双旋转过程中，左旋不改变颜色，这样才会因为不满足规则3，继而右旋并改变颜色。实际上这是因为代码实现的问题，在元素操作的调整树形函数中会有所体现

  • 状况3：S 为红且 X 为外侧插入，如果 GG 为黑

    17242451498851724245149369.png

  • 状况4：S 为红且 X 为外侧插入，如果 GG 此时为红，情况就比较复杂了

    17242450968851724245096037.png

为了避免状况4 “父子节点均为红色” 需要持续向上发展的处理，这里采用了一个由上而下的程序：假设新增节点为 A，那么沿着 A 的路径由上而下修改节点颜色，如果某个节点 X 的两个子节点均为红色，就把 X 改为红色，并把两个子节点改为黑色

17242470538851724247053203.png

1.2 迭代器

RB-tree 迭代器的实现被分为两层，以下示例图展示了双层节点结构和双层迭代器结构之间的关系：

17244016731161724401673079.png

这样的设计在保持接口简洁的同时，隐藏了红黑树内部的复杂性，从而为用户提供一个功能强大又便于使用的迭代器。RB-tree 的迭代器属于双向迭代器，但不具备随机定位能力。其中特殊的是operator++和operator--()，它们分别调用的是基类迭代器的increment()和decrement()。这两个函数的实现有一些特殊技巧，稍后会说明

1.3 数据结构

RB-tree 只以三笔数据表现表现整棵树

1
2
3
size_type node_count; // 追踪记录树的大小，也就是节点数量
link_type header; // 实现上的特殊技巧
Compare key_compare; // 节点间的键值大小比较准则，应该是个 function object

RB-tree 以节点大小为配置单位

1.4 元素操作与空间配置

树状结构的各种操作，最需要注意的就是边界情况的发生，也就是到根节点时要有特殊处理。这里 SGI STL 采用了哨兵节点的方法简化处理，为根节点在设计一个父节点，命名为 header，并令其初始状态为示例图所示：

17244039175571724403916941.png

header 和 root 互为对方的父节点，这是一种实现技巧

每次插入节点时，不仅要调整树形来符合红黑树的规则，还要维护 header 的正确性，使其父节点指向根节点，左子节点指向最小节点，右子节点指向最大节点。树形调整稍后会说明

RB-tree 提供两种插入操作：insert_unique()和insert_equal()，前者要求被插入节点的键值在整棵树中必须独一无二，后者表示被插入节点的键值在整棵树中可以重复，这也是容器 set 和 map 的立身之本

在前文插入节点的状况2中我们产生过疑惑，这里粘贴一下调整树形的函数代码就能理解这其中的缘由了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
inline void rb_tree_rebalance(rb_tree_node_base *x, rb_tree_node_base *&root) {
  x->color = rb_tree_red; // 新节点 X 必为红 
  while (x != root && x->parent->color == rb_tree_red) { // 父节点 P 为红
	if (x->parent == x->parent->parent->left) { // P 为祖父节点 G 的左子节点
	  rb_tree_node_base *y = x->parent->parent->right; // 令 y 为伯父节点 S
	  if (y && y->color == rb_tree_red) { // S 存在并且为红
		x->parent->color = rb_tree_black; // 更改 P 为黑
		y->color = rb_tree_black; // 更改 S 为 黑
		x->parent->parent->color = rb_tree_red; // 更改 G 为红
		x = x->parent->parent; // 向上层检测
	  } else { // S 不存在，或者为黑
		if (x == x->parent->right) { // 如果 X 为 P 的右子节点，左旋
		  x = x->parent;
		  rb_tree_rotate_left(x, root); // 第一参数为左旋点
		}
		x->parent->color = rb_tree_black; // 改变颜色
		x->parent->parent->color = rb_tree_red;
		rb_tree_rotate_right(x->parent->parent, root); // 右旋
	  }
	} else { // P 为祖父节点 G 的右子节点 
	  rb_tree_node_base *y = x->parent->parent->left; // 令 y 为伯父节点 S
	  if (y && y->color == rb_tree_red) { // S 存在并且为红
		x->parent->color = rb_tree_black; // 更改 P 为黑
		y->color = rb_tree_black; // 更改 S 为 黑
		x->parent->parent->color = rb_tree_red; // 更改 G 为红
		x = x->parent->parent; // 向上层检测
	  } else { // S 不存在，或者为黑
		if (x == x->parent->left) { // 如果 X 为 P 的左子节点，右旋
		  x = x->parent;
		  rb_tree_rotate_right(x, root); // 第一参数为右旋点
		}
		x->parent->color = rb_tree_black; // 改变颜色
		x->parent->parent->color = rb_tree_red;
		rb_tree_rotate_left(x->parent->parent, root); // 左旋
	  }
	}
  }
  root->color = rb_tree_black;
}

注意，涉及向上检测的处理情况就是之前提到的由上而下的程序

2 hashtable

2.1 概述

二叉搜索树具有对数平均时间（O(log n）），但这样的表现需要建立在输入的数据要有足够的随机性。这里就要引出一种名为hashtable的数据结构，它具有常数平均时间（O(n)），而且这种表现是以统计为基础的，并不依赖输入数据的随机性

如果输入的数据为有序，那么在插入时，每次新元素都会倾向树的某一侧，从而导致树失去平衡。RB-tree 具有自平衡机制，所以对于输入的数据并没有过多的要求

hashtable被视为一种字典结构，因为它的操作对象是有名项。关于hashtable的实现，可以从一个简单粗暴的想法开始：

如果插入的元素都是 16-bits 且不带正负号的整数，我们可以申请一个拥有 65535 的 array，初值全为 0，每个元素的值表示该元素出现的次数

17246424575101724642456764.png

这种解法存在两个问题，一是如果元素是 32-bits，我们不可能去准备一个大小为 232 = 4 GB 的 array，二是如果元素为字符串或者其他而非整数。第二个问题比较好解决，那就是使用 ASCII 编码，这样字符就能转换成一个 7-bits 的数值来表示。但是这样又会回到第一个问题：array 的大小，因为字符串稍长就会导致很大的索引值。怎么解决呢？办法之一就是采用某种映射函数，将大数映射为小数，即所谓的哈希函数（hash function）

但是使用 hash function 一样会带来问题：可能会有不同的元素被映射到相同的位置，即有相同的索引。这便是碰撞（collision）问题。解决碰撞问题的方法有很多种，如线性探测（linear probing）、二次探测（quadratic probing）、开链（separate chaining）等

碰撞 是无法避免的，毕竟元素个数是大于 array 的容量的。

这里这会简单提及一下线性探测和二次探测，不会做过多的讲述：

线性探测：当 hash function 计算出某个元素的插入位置，而该位置上的空间已被占用，那就循环往下一一寻找。线性探测会存在主集团（primary clustering）问题，感兴趣的你可以去网上了解😉

17246429165101724642916161.png

如果到达尾端，就绕到头部继续寻找

二次探测：当 hash function 计算出某个元素的插入位置 H，而该位置上的空间已被占用，那么就依次尝试 H + 12，H + 22，H + 32，… ，H + i2。二次探测主要用来解决主集团问题，但却可能造成次集团（secondary clustering）问题，解决的办法也有，例如复式散列（double hashing）

17246436985101724643698377.png

2.2 开链

SGI STL 中的hashtable就是采用开链实现的，所谓开链，就是在每一个表格元素中维护一个 list

17246445225101724644522293.png

注意，bucket 维护的 linked list，并不采用 STL 的 list 或 slist，而是自行维护的 hashtable node。至于 buckets 聚合体则以 vector 完成的，以便有动态扩充能力

1
2
3
4
5
template <typename Value>
struct hashtable_node {
    hashtable_node* next;
    Value val;
};

2.3 迭代器

hashtable的迭代器必须永远维系着与整个 “buckets vector” 的关系，并且记录目前所指的节点。需要注意的是，其前进操作的边界问题，如果目前节点正巧是 list 的尾端，就跳至下一个 bucket 身上，那正是指向下一个 list 的头部节点。hashtable的迭代器没有后退操作，hashtable也没有定义所谓的逆向迭代器（reverse iterator）

1
2
node* cur; // 迭代器目前所指的节点
hashtable* ht; // 保持对容器的连结关系（因为可能需要从当前 bucket 跳到下一个 bucket）

2.4 数据结构与空间配置

虽然开链法并不要求表格大小必须为质数，但 SGI STL 仍然以质数来设计表格大小，并且将 28 个质数（逐渐呈现大约两倍的关系）计算好，以备随时访问，同时提供一个函数，用来查询在这 28 个质数之中，”最接近某数并大于某数” 的质数，这里只用文字描述叙述比较苍白，以下粘贴了相关代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static const int tinystl_num_primes = 28;
static const unsigned long tinystl_prime_list[tinystl_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
};

inline unsigned long tinystl_next_prime(unsigned long n) {
  const unsigned long *first = tinystl_prime_list;
  const unsigned long *last = tinystl_prime_list + tinystl_num_primes;
  const unsigned long *pos = std::lower_bound(first, last, n);
  // lower_bound() 是泛型算法，序列需先排序
  return pos == last ? *(last - 1) : *pos;
}

hashtable以节点大小为配置单位

表格是否需要重建的判断原则是拿元素个数（把新增元素计入后）和 bucket vector 的大小来比。如果前者大于后者，就重建表格。由此可知，单个 bucket list 的理论最大容量就是 buckets vector 的大小。重建表格的操作分解成图说明，如下示例图所示：

17246601655101724660164592.png

buckets[ ] 是原有的 buckets，tmp[ ] 是新建的 buckets，最后会将这两个 buckets 对调，如果对调双方大小不同，大的会变小，小的会变大，然后会释放 tmp[ ]

Comments