侯捷《STL源码剖析》 | 容器详解 RBTree 和 HashTable(史上最简明介绍)

RBTree

Red-Black tree(红黑树）是一种节点有特定颜色的平衡二叉搜索树(balanced binary search tree)，其特点如下:

• 节点有颜色，红黑色有关系（具体可自己搜索）
• 拥有平衡二叉搜索树的所有性质
• rb_tree提供遍历操作，按照正常规则遍历（++ite),能获得排序状态
• 不应使用re_tree的ite改变元素值，因为元素有其严瑾的排列规则
• rb_tree用两种插入操作：insert_unique()和insert_equal(),后者key可以重复
• rb_tree节点拥有双向指针，因为要前后遍历
• 将rb_tree的node的数据称为value，它包括key和data

rb_tree的实现

rb_tree只以三笔资料表现自己：

• node_count 节点的个数
• header 指向tree_node的指针，此node下一个节点为head
• key_compare key大小的比较规则

rb_tree实际大小为12（1 + 4 + 4 = 9，找到最近的4的倍数为12）

• KeyOfValue的函数实现

identity函数，它继承自unary_function，返回传入元素自身。

• Compare的函数实现
  传入一个function object，其内部重载操作符"()".

Set/Multiset

Set/Multiset以rb_tree为底层结构，其特点如下:

• set、multiset排序依据为key，且其value和key合一，value就是key
• set的key必须唯一，其insert为rb_tree的insert_unique();multiset的key可以重复，其insert是rb_tree的insert_equal();

set的实现

set相当于一种适配器模式，其所有操作转移到底层容器t。

• VC6中的set实现
  VC6中没有identity()，自己实现一个仿函数_Kfn;

Map/Multimap

Map/Multimap以rb_tree为底层结构，其特点如下:

• Map、Multiset排序依据为key;
• map的key必须唯一，其insert为rb_tree的insert_unique();multimap的key可以重复，其insert是rb_tree的insert_equal();
• map将key_type设置为const，禁止用户修改key，允许用户修改data;
• multimap不可使用[ ]做insertion

map的实现

底层调用rb_tree

• VC6中的map实现
  VC6中没有select1st()，自己实现一个仿函数_Kfn;

HashTable

hashtable是使用hash function实现元素的散列放置。

hash table空间不足、元素冲突问题

将元素编号H对空间大小M取模，得到元素在hash table的位置。

• separate chaining 链式解决冲突

将发生冲突的元素使用链表进行串接

• rehash的触动

当hash table的总元素个数大于bucket（用来装物体的篮子）的个数时，进行rehash操作，即将bucket的数量增大到下一个选定的质数大小M，重新计算该放到哪个篮子。

hash table在STL中的实现

hash table中的数据：

• HashFcn：hash（object）
• EqualKey: equals(object)
• ExtractKey: get_key(object);此三个为函数对象, 总大小为3
• __hashtable_node: node
• vector buckets;vector含三根指针，大小12
• size_t: num_elements；unsigned_int, 大小为4

hash table大小为20(19调整为20)

模板hashtable中需要传入的模板参数：

• Value 一种组合类型，包含key和data
• Key
• HashFcn 将元素散列到hash table中编号的函数
• ExtractKey 元素可能是pair，此函数用于萃取key
• EqualKey 用于指定key怎样为相等的函数
• Alloc

hash table的某种实现：

hash function、hash code

• hash(函数对象)的特化

• string对象的hash实现：没有特定方法，够乱够随机即可。

string为C++的字符串，stl对于此种对象没有实现hash;对于C的字符串char*,实现了hash。

• modlus运算，取余

unordered容器

过了C++11，以hash开头的容器改名为unordered（不定序）。
unordered_set, unordered_map;unordered_multiset, unordered_multimap;也都相当适配器，底层以hash_table为容器，功能和以rb_tree为容器的set，map相同。

---

更多精彩文章，欢迎关注公众号“Li的白日呓语”。