STL关联式容器介绍

在前文中介绍了STL的序列式容器；

STL序列式容器之vector-CSDN博客

STL序列式容器之list-CSDN博客

STL序列式容器之deque-CSDN博客

STL序列式容器之stack-CSDN博客

STL序列式容器之queue-CSDN博客

STL序列式容器之heap（堆）-CSDN博客

STL序列式容器之priority_queue-CSDN博客

STL序列式容器之slist-CSDN博客

接下来对关联式容器（associative containers）进行学习及分享；

        根据“数据在容器中的排列”特性，容器可概分为序列式（Sequence）和关联式（associative）两种。

        标准的STL关联式容器分为set(集合)和map（映射表）两大类，以及两大类的衍生体multiset(多键集合）和multimap(多键映射表)。这些容器底层机制均以RB-tree（红黑树）完成。RB-tree也是独立容器，但并不开放给外界使用。

        此外，SGI STL还提供了一个不在标准规格之类的关联式容器：hash table（散列表），以及以此hash table为底层机制完成的hash_set(散列集合)、hash_map（散列映射表）、hash_mulitset(散列多键集合)、hash_mulitmap（散列多键映射表）。

关联式容器，观念上类似关联式数据库：每条数据（每个元素）都有一个键值(key)和实值（value）。当元素被插入到关联式容器中时，容器内部结构便依据其键值大小，以某种特定规则将这个元素放置于适当位置。关联式容器没有所谓头尾、所以不会有push_back,push_front,pop_back,pop_front这样的操作行为。

        begin()、end()可以在遍历时使用

        一般而言，关联式容器的内部结构是一个balanced binary tree (平衡二叉树)，以便获得良好的搜索效率。balanced binary tree有许多种类型，包括AVL-tree，RB-tree，AA-tree，其中最被广泛运用于STL的是RB-tree(红黑树)。为了探讨STL的关联式容器，我们必须先探讨RB-tree。

        进入RB-tree主题之前，让我们先对tree的来龙去脉有个概念。以下讨论都和最终目标RB-tree有密切关联。

        树因为耳熟能详此处就不做过多的解释了；

二叉搜索树（binary search tree）

        所谓二叉树，其意义是：“任何节点最多只允许两个子节点”。这两个子节点称为左子结点和右子节点。如果以递归方式来定义二叉树，我们可以说：“如果一个二叉树不为空，便是由一个根节点和左右两子树构成；左右子树都有可能为空”。二叉树的应用极广；

        所谓二叉搜索数（binary search tree）,可提供对数时间（logarithmic time）的元素插入和访问。二叉搜索树的节点放置规则是：任何节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中的每一个节点的键值。因此，从根节点一直往左走，直到无左路可走，即得最小元素；从根节点一直往右走，直至无右路可走，即得最大元素。下图即为一颗二叉搜索树

现在简要介绍二叉搜索树的插入节点及删除节点；

对于插入节点，首先进行查找，将插入值与当前节点key进行比较，如果比当前节点大就进入左子树，如果比当前节点大进入右子树，如果和当前节点key相等，则退出（找到了key值相同的节点说明节点已经存在则不进行插入操作），直到叶子节点后，将节点插入；比如插入节点11，则其查找路径（沿着淡蓝色箭头往下）如下所示：

沿着10->20->14的路径向下，发现14为叶子节点，然后将11加入到其左子树。

对于删除操作，分为三种情况；1，删除节点为叶子节点，2：删除节点只有一个子节点，3：删除节点由两个子节点。

对于情况1：直接将节点移除出即可；比如删除节点为9；则删除节点后，状态为：

为了演示方便，在8和9之间新增了一个虚线箭头，事实上8的右节点置为了空，此时9节点将会被删除。最终节点状态为：

对于情况2，比如删除节点8，此时8正好有一个子节点；将8的子节点替换掉待删除的节点，即可完成删除操作；如下图所示

节点6将替换节点8

最后树将变成：

再来看情况3；比如删除节点key为20，此时节点20，存在两个节点，首先找到20，右子树的最小节点，21，而后，将21替换到20；过程如下

第一步定位到节点20，发现节点20存在两个子节点；然后查找右子树的最小节点，并将最小节21点替换当前节点20；如下所示：

最终二叉搜索树转换为：

参考文档《STL源码剖析--侯捷》