# 第5章 序列式容器
标准的 STL 关联式容器分为 set（集合）和 map（映射表）两大类，以及这两大类的衍生体 multiset（多键集合）和 multimap（多键映射表）。这些容器的低层机制均以 RB-tree（红黑树）完成。RB-tree 也是一个独立容器，但并不开放给外界使用。
SGI STL 还提供了一个不在标准规格之列的关联容器：hast table。
所谓关联式容器（associative containers），每笔数据都有一个键值（key）和一个实值（value）。当元素被插入到关联式容器中时，容器内部结构便依照其键值大小，以某种特定规则将这个元素放置于适当位置。
## 5.1 树的导览
树由节点（nodes）和边（edges）构成，整棵树有一个最上端的节点，称为根节点（root）。每个节点可以拥有具方向性的边（directed edges），用来和其它节点相连。相连节点中，在上者称为父节点（parent），在下者称为子节点（child）。无子节点者称叶节点（leaf）。子节点可以存在多个，如果最多只允许两个子节点，即所谓二叉树（binary tree）。不同的节点如果拥有相同的父节点，则彼此互为兄弟节点（siblings）。根节点至任何节点之间有唯一路径（path），路径所经过的边数，称为路径长度（length）。根节点至任一节点的路径长度，即所谓该节点的深度（depth）。根节点的深度永远为0。某节点至其最深子节点的路径长度，称为该节点的高度（height）。整棵树的高度，便以根节点的高度来代表。节点 `A -> B` 之间如果存在一条路径，那么 A 称为 B 的祖代（ancestor），B 称为 A 的子代（descendant）。任何节点的大小（size）指其所有子代（包括自己）的节点总数。
**二叉搜索树（binary search tree）**：所谓二叉树（binary tree），其意义：“任何节点最多只允许两个子节点”。这两个子节点称为左子节点和右子节点。
二叉搜索树的节点放置规则是：任何节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中的每一个节点的键值。插入新元素时，可从根节点开始，遇键值较大者就向左，遇键值较小者就向右，一直到尾端，即插入点。
欲删除旧节点 A，情况可分两种。如果 A 只有一个子节点，就直接将 A 的子节点连至 A 的父节点，并将 A 删除。如果 A 有两个节点，就以右子树内的最小节点取代 A。注意，右子树的最小节点极易获得：从右子节点开始，一直向左走至底即是。
**平衡二叉搜索树（balanced binary search tree）**：二叉搜索树可能失去平衡，造成搜寻效率低落的情况。“平衡”的大致意义是：没有任何一个节点过深。一般而言其搜寻时间可节省 25% 左右。
**AVL tree（Adelson-Velskii-Landis tree）**：AVL tree 于是退而求其次，要求任何节点的左右子树高度相差最多1。
## 5.2 RB-tree（红黑树）
所谓 RB-tree，不仅是一个二叉搜索树，而且必须满足一下规则：
1. 每个节点不是红色就是黑色；
2. 根节点为黑色；
3. 如果节点为红，其子节点必须为黑；
4. 任一节点至 NULL 的任何路径，所含之黑节点数必须相同；
RB-tree 所定义的专属空间配置器 `rb_tree_node_allocator`，每次可恰恰配置一个节点。
## 5.3 set
set 的特性是，所有元素都会根据元素的键值自动排序。set 元素的键值就是实值，实值就是键值。set 不允许两个元素有相同的键值。不能通过迭代器改变 set 的元素值。
当客户端对它进行元素新增操作（insert）或删除操作（erase）时，操作之前的所有迭代器，在操作完成之后都依然有效。
标准的 STL set 即以 RB-tree为底层机制。
## 5.4 map
map 的特性是，所有元素都会根据元素的键值自动被排序。map 的所有元素都是 pair，同时拥有实值（value）和键值（key）。pair 的第一元素被视为键值，第二元素被视为实值。map 不允许两个元素拥有相同的键值。不能通过迭代器改变 map 的键值，但是可以修改实值。
当客户端对它进行元素新增操作（insert）或删除操作（erase）时，操作之前的所有迭代器，在操作完成之后都依然有效。
标准的 STL map 即以 RB-tree为底层机制。
**subscript操作符**会先根据键值和实值做出一个元素，由于实值未知，所以产生一个与实值型别相同的暂时对象代替，再将该元素插入到 map 里面去，插入操作返回一个 pair，其第一元素是个迭代器，指向插入妥当的新元素，或指向插入失败点的旧元素（键值重复）。
```c++
template <class Key, class T, class Compare = less<Key>, class Alloc = alloc>
class map {
typedef Key key_type;
typedef pair<const Key, T> value_type;
public:
T& operator[](const key_type& k) {
return (*((insert(value_type(k, T()))).first)).second;
}
```
## 5.5 multiset
multiset 的特性以及用法和 set 完全相同，唯一的差别在于它允许键值重复。
## 5.6 multimap
multimap 的特性以及用法和 map 完全相同，唯一的差别在于它允许键值重复。
## 5.7 hashtable
hash table 可提供任何有名项（named item）的存取操作和删除操作。负责将某一元素映射为一个“大小可接受之索引”，这样的函数称为 hash function（散列函数）。
使用 hash function 会带来一个问题：可能有不同的元素被映射到相同的位置，称为”碰撞（collision）”。解决碰撞问题的方法有许多种，包括线性探测（linear probing）、二次探测（quadratic probing）、开链（separate chaining）。
**负载系数（loading factor）**指元素个数除以表格大小。
**线性探测（linear probing）**：循序往下一一寻找（如果到达尾端，就绕到头部继续寻找），直到找到一个可用空间为止。
这种方法的问题在于：平均插入成本的成长幅度，远高于负载系数的成长幅度。这种现成称为主集团（primary clustering）。
**二次探测（quadratic probing）**：为解决碰撞问题的方程式 `F(i) = i ^2`，依次尝试 `H + 1^2`, `H + 2^2`, ..., `H + i^2`，计算下一次位置可以使用公式 `H(i) = H(i-1) + 2i-1 (mod M)`。
这种方法可以消除主集团，却可能造成次集团（secondary clustering）：两个元素 hash function 计算出来的位置若相同，则插入时所探测的位置也相同，形成浪费。
**开链（separate chaining）**：一个表格元素维护一个 list，每次在list 上执行元素的插入、搜寻、删除等操作。
hash table 表格内的元素为桶子（bucket），buckets 聚合体以 vector完成，以利动态扩展。
hash table 迭代器前进操作是首先尝试从所指的节点出发，前进一个位置，由于节点被安置 list 内，所以利用节点的 next 指针即可轻易达成前进操作。如果目前节点正巧是 list 的尾端，就跳至下一个 bucket 上。hashtable 的迭代器没有后退操作。
SGI STL 仍以质数来设计表格大小，并且先将28个质数计算好，同时提供一个函数，用来查询在这28个质数中，“最接近某数并大于某数”的质数。
**插入操作与表格重整**：
1、判断是否需要重建表格；
2、判断标准：拿元素个数（把新增元素计入后）和 bucket vector 的大小比较，如果前者大于后者，就重建表格；
3、找出下个质数重建表格，并处理每一个旧的bucket；
SGI hashtable 针对 char、int、long 等整数型别实现了hash function，大部分的 hash functions 什么也没做，只是返回原值，但对于字符串就设计了转换函数：
```c++
inline size_t __stl_hash_string(const char* s) {
unsigned long h = 0;
for (; *s; ++s)
h = 5 * h + *s;
return size_t(h);
}
```
## 5.8 hash_set
SGI 则是在STL标准规格之外另又提供了一个所谓的 `hash_set`，以 hashtable 为底层机制。RB-tree 有自动排序功能而 hashtable 没有，反应出的结果就是，`set` 的元素有自动排序功能而 `hash_set`。
## 5.9 hash_map
RB-tree 有自动排序功能而或是 hashtable 没有，反应出来的结果就是，map 的元素有自动排序功能而 `hash_map` 没有。
map 的特性是，每一个元素都同时拥有一个实值（key）和一个键值（key）。
## 5.10 hash_multiset
`hash_multiset` 的特性与 `multiset` 完全相同，唯一的差别在于它的底层机制是 hashtable。
## 5.11 hash_multimap
`hash_multimap` 的特性与 `multimap` 完全相同，唯一的差别在于它的底层机制是 hashtable。
