《STL源码剖析》中篇----关联式容器_stl源码剖析说hashtable无法处理string

       最近花了一些时间，把《STL源码剖析》这本书看了一遍，由于之前C++的语法掌握的还可以，所以看的比较快。我在看的时候对于源代码没有仔细看，只是把它的大概实现过程看了一遍，理解了底层是如何组织数据的，以及关联式容器是如何工作的。我个人觉得，对源代码可以不用看的太仔细，当然如果你对这个很有兴趣，看仔细点更好。

      下面我就简单总结一下STL中关联式容器的实现。

一、set、map、multiset和multimap

1.二叉搜索树(BST，binary search tree)

        二叉搜索树的特点是任何节点的键值一定大于其左子树中的每一个节点的键值，并小于右子树中每一个节点的键值。这个特点的最大好处在于搜索时只要搜索不超过树的深度次就能找到我们的需要的数据。即查找的时间复杂度为O(log n)。

        二叉搜索树还有一个特点就是，对它进行中序遍历的结果相当于进行了一个升序排列。

2.平衡二叉树（AVL，平衡的二叉搜索树）

        AVL树是一个“加上了平衡条件”的二叉搜索树，其平衡条件为任何节点的左右字数高度相差最多为1，这是一个较弱的条件，但仍然能够保证“对数深度”平衡状态。

        当对一棵AVL树进行插入删除时，很可能会破坏AVL树的性质（任何节点的左右字数高度相差最多为1），此时就需要惊醒一系列的旋转操作来保证树的平衡性。这里就不介绍具体该如何旋转了，有兴趣的可以自己看看其他博客的介绍。    

3.红黑树

        现在就要介绍我们的王牌二叉树--红黑树，之所以说它是王牌树，原因在于它在实践中应用很广泛，不管是文件系统的索引还是数据库的索引，底层都使用的是红黑树。现在来慢慢解开它神秘的面纱。

(1)本质

        红黑树的本质是一种自平衡的二叉搜索树。

(2)红黑树的五条性质

        a.每个节点要么是红色，要么是黑色；

        b.根节点一定是黑色.

        c.所有的叶子节点是黑色.（这里的叶子节点和我们平时理解的叶子节点有一点不一样，这里的叶子节点包括度为0的节点的NULL指针，也算是一个黑色节点）

        d.如果一个节点是红色的，那么它的两个孩子一定是黑色。即在一条路径上不能出现连续的两个红色节点。

        e.从给定节点到其任何后代NIL节点的每条路径都包含相同数量的黑色节点。

(3)红黑树的操作

        a.变色

        b.左旋

        a.右旋

(4)几个问题

 a.为什么红黑树是自平衡的？

       由红黑树的定义可以知道，从任意给定节点到其后代的NIL节点的每条路径都包含相同的黑色节点，所以最特殊的情况就是，一条路径上全是黑节点，而另一条路径肯定是红黑节点交替，而且是全黑节点组成的路径的长度的两倍，所以会自平衡。

      从根到最远叶的路径不超过从根到最近叶的路径的两倍。红黑树不是完美的二叉平衡树。严格平衡的树是平衡二叉树（AVL）。

b.查询、插入和删除的时间复杂度

    O(log n).

c.已经有了二叉搜索树，为什么会出现红黑树

    二叉搜索树对于插入有序数据时效率会降低到单链表的查询速度，因为此时会变成一棵单支树。

d.和二叉搜索树的区别

       二叉搜索树是个很好的数据结构，可以快速地找到一个给定关键字的数据项，并且可以快速的插入和删除数据项。但是二叉搜索树有个很麻烦的问题，如果树中插入的数据是随机数据，则执行效果很好；但如果插入的数据是有序或者逆序的数据，那么二叉搜索树的执行速度将会变得很慢，接近线性时间O(n)。

       由于红黑树的性质可知，它是带有自平衡的，所以在一定程度上它的平衡性还是比较好的，虽然比不上平衡二叉树。

e.和平衡二叉树的区别

    平衡二叉树（AVL）是一种严格平衡的二叉树，它和红黑树的区别在于插入、删除操作，而对于查询操作两者的性能基本下你相同，时间复杂度均为O(log n)。对于平衡二叉树而言，插入和删除操作会引发树的旋转，而红黑树在插入删除时调整的可能性要小一点，所以说平衡二叉树在插入删除时调用的次数要高于红黑树。这也是我们在实际应用中一般使用红黑树作为文件系统或者数据库的底层数据结构，而不是用平衡二叉树的原因所在。

4.set和multiset

        set的特性是所有元素都会根据元素的键的键值自动被排序。set的元素不想map那样可以同时拥有key和value,set元素只有key。set不允许两个元素有相同的键值。

        当客户端对它进行元素新增操作或删除操作时，操作之前的所有迭代器，在操作之后依然有效，原因在于迭代器底层是指针，只要内存空间存在，迭代器就不会失效。当然，被删除的那个元素的迭代器那才会失效。

        由于RB-tree是一种平衡二叉搜索树，自动排序的效果很不错，所以标准STL set即以RB-tree为底层机制。又由于set所开放的各种操作接口，RB-tree也都提供了，所以几乎所有的set操作行为，都只是转调用RB-tree的操作行为而已。

        multiset和set本质是一样的，两者唯一的区别在于使用的插入函数不同；对于set而言，使用insert_unique()作为插入函数，这个函数不允许在树中出现重复的元素；而multiset，使用的是insert_equal()作为插入函数，允许插入重复的元素。

注意：

        不能通过set的迭代器改变set的元素，原因在于，set元素是按一定规则进行组织的，如果通过迭代器修改set的元素，可能会破坏这种规则，所以不允许通过迭代器改变set元素，在底层也利用const_iterator进行了限制。

5.map和multimap

        map的特性是所有元素都会根据元素的键值自动被排序。map的所有元素都是pair，同时拥有key和value。pair的第一个元素被视为key，第二个元素被视为value。map中不允许拥有相同的key。

        本质上map和set是一样的，底层都是使用RB-tree组织起来的。只不过把set中元素仅由key组成的结构体，换成了map中由pair组成的结构体，从而使map看起来和set不一样。

        同样的，不能通过map的迭代器改变map元素的key值，原因和上面set提到的一样。

        对于map和multimap的区别也和set与multiset一样，就是两者使用的插入函数不一样。

二、hash_set、hash_map、hash_multiset和hash_multimap

1.hashtable

        hashtable是一种字典结构，这种结构的用意在于提供常熟时间之基本操作。其实hash操作的本质是利用空间换时间的一种的策略。

(1)哈希函数(散列函数)

        哈希函数的定义是负责将一个元素映射为一个“大小可接受的索引”的函数。

        但是对于哈希函数而言，会出现不同的元素通过哈希函数会映射到同一个位置，这就会导致冲突。目前提出了一些解决冲突的办法，如线性探测、二次探测、开链等方法。

(2)桶（buckets）

        在SGI STL中，hashtable是利用桶子来实现的，hash table表格内的元素称为桶子，此名称的大约意义是，表格内的每个单元，涵盖的不只是一个元素，而是一个桶节点，将所有映射到同一个位置的元素放在同一个“桶”里面。

        桶底层是以链表的形式将映射到该桶的元素组织起来。如下图所示：

(3)重整问题

        由于hashtable底层使用的vector作为bucket的容器，所以会发生重整问题，即需要为桶重新分配内存空间。

(4)处理类型

        hashtable无法处理string、double和float等类型，如果要处理这些类型，用户必须自行为它们定义hash function。

2.hash_set和hash_multiset

        hash_set以hashtable为底层机制。由于hash_set所提供的的操作接口，hashtable都提供了，所以几乎所有的hash_set操作行为，都只是转调用hashtable的操作行为而已。

        所以可以将hash_set理解为底层使用hash_table组织的一种数据结构，和hashtable本质没有什么区别，唯一的区别在于hashtable中允许插入重复元素，而hash_set中不允许插入重复元素。hash_set就是对hash_table的一种简单封装。

        hash_multiset和hash_set本质上也是一样的，两者底层都是hashtable，区别在于hash_set不能插入重复元素，而hash_multiset可以插入重复元素。

3.hash_map和hash_multimap

        hash_map和hash_set的本质都是相同的，只不过hash_map中用pair--<key， value>代替了hash_set中key。而hash_multimap和hash_map就类似于hash_set于hash_multiset之间的关系。没什么太多可说的。