在前文中介绍了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源码剖析--侯捷》