《STL源码剖析》读书笔记

转载：https://www.cnblogs.com/xiaoyi115/p/3721922.html

直接逼入正题。 Standard Template Library简称STL。STL可分为容器(containers)、迭代器(iterators)、空间配置器(allocator)、配接器(adaptors)、算法(algorithms)、仿函数(functors)六个部分。

迭代器和泛型编程的思想在这里几乎用到了极致。模板或者泛型编程其实就是算法实现时不指定具体类型，而由调用的时候指定类型，进行特化。在STL中，迭代器保证了STL中算法的连续性和紧密型，使得各算法不需要考虑具体的数据结构。

 仿函数的实质就是在结构体中重载operator ()、<、>等操作符。仿函数实际上更多的是一种概念和思想性的东西，而非一种物质上的实际提升。

容器和算法是STL中最为核心的部件，一切工作的铺垫(例如迭代器、空间配置器等)都是根据他们而展开的。下面概要的讲一下容器和算法的主要内容。

   容器：

   1、vector

vector其实是一种顺序性的容器，当然这里的顺序不是说排好序，而是说操作的时候按照一定的次序关系。另外，vector和数组array是非常相似的，最大的不同是array是静态的，而vector是动态，这就是为什么大部分时候使用vector的原因了，因为我们往往不知道数组开多大比较合适，开大了浪费，开小了保存不下来，选择vector是一个比较优的选择。其实vector本质上就是一个array,只不过它是一个变化的array,那么一个固定大小的array怎么变成vector的呢？我们看一下它的数据结构或许会更加明白一些。

 1 template<class T,class Alloc=alloc>
 2 class vector{
 3 public:
 4     typedef T  value_type;
 5     typedef value_type* point;
 6     typedef value_type* iterator;
 7     typedef value_type& reference;
 8     typedef size_t size_type;
 9 ...
10 protected:
11     iterator start;//目前使用空间的头部
12     iterator finish;//目前使用空间的尾
13     iterator end_of_storage;//能够使用空间的尾
14 ...
15 };

我们注意到vector中的start,finish,end_of_storage。

好了，有了这三个变量，一切就有了答案。比如我们初始化vector的大小为10，那么end_of_storage=start+10了。我们可以通过维护finish这个变量来使得它看起来是动态的，比如我们插入5个值，那么通过计算finish与start的差值就能得到size()为5了。我们还可以继续插入，只不过此时需要finish向后移动一位就OK。但是，随之而来的问题又来了，当finish等于end_of_storage之后怎么办呢？显然，如果要继续插入的话，不能进行操作啊。

莫慌，请别怀疑程序猿是智商最高的那一类，我们新建一个array,这次申请的空间比上一个大那不就OK了吗？同时把旧的array复制到newarray中去，同时delete掉old array。这样就保证了还可以继续添加。但是有时候申请资源会不成功哦，所以插入操作并不总是OK的啦。程序猿的世界，bug总是无处不在。这个时候需要重回old array,同时delete 掉新申请的array.

我们已经解决掉了怎么使一个固定大小的array变成一个动态vector的问题，就是建一个更大的array。那么更大到底是多大呢？STL中把这个更大定义为两倍的当前SIZE.这个可能是根据经验得到的数据，两倍会是一个比较优的解。

vector中提供了insert,erase,pushback还有重载操作符等方法。其实insert就是在后面添加一个值，vector容量不够了先扩容再insert.

erase也就是擦掉某个值的操作其实就是删除某个值，然后后面的值前移，vector中erase效率极其低下，如果需要频繁的erase操作，建议还是换一个数据结构会比较好。

还有例如begin(),end(),size().这些其实都是通过维护start,finish,end_of_storage得到的。

  2、list

在STL中list表示的是一种环状的双向链表(带头)，相比vector需要维护start finish end_of_storage,list只需要维护一个node指针结点(头结点)就可以了。

双向环状链表的初始过程如下：

1     node=getNode();//新建一个结点
2     node->next=node;//后一结点是node
3     node->pre=node;//前一结点是node

其他插入、删除、取值等操作只需要了解链表的操作都是非常easy了。

3、deque（双端队列，两边都可进可出）

deque在这里其实也是一个array,只不过是分段而已，所谓分段在这里的意思就是。deque可能连续第一组有连续十个空间存放值，第二组也有十个空间存放值，但是这两组空间不是连续的，也就是说第一组空间的尾+1，不等于第二组空间的头。这两组空间的组织和管理是通过链表(在STL中称为map,(这个map翻译成地图更合适,而非数据结构中的map))的方式形成的。

4、stack(先进后出的数据结构)，queue(先进先出的数据结构)

他们的底层实现都是list,只是根据List做一些量身定制而已。就比如都是一件衣服，不同人穿的时候，稍微在外表上做点修饰，本质不改变。

上面说的都是顺序性的容器，当然顺序性容器中海油优先队列，slist等，它们其实都是大同小异，不具体阐述了。

  5、set、map、multiset、multimap

 set和map的最大不同就是set是单值，而map是键值对，当然set也可以理解成键值对相等的特殊键值对。这样讲的话，我们大概就知道了，它们的底层实现就是一个东西。那么multiset和set有什么区别呢？主要值能不能重复的问题，如果可以保存多个相同值的话就使用multiset否则就使用set。因为插入的时候，它们分别调用的是insert和unique_insert；同理，map和multimap也是这个意思。

map有排序的功能，并且能够快速的插入和查找，甚至删除。它是怎么做到的呢？

这就要看的底层实现了。它们的底层都是基于红黑树，请看博主这篇文章：map,set的底层实现：红黑树[多图，手机慎入]

博文已经讲得非常清楚了，这里不再累述。

  6、hashtable、hashset、hashmap、hash_multiset,hash_multimap

其实这里面主要是讲了一个东西，就是hashtable，同样hashset和hashmap的问题是是否是键值对的问题。而mullti..是是否是多值的问题。

hash的最重要的功能就是插入和查找相当迅速，我们使用hash更多的是看中他查找的时间复杂度几乎是O(1).那么hash是怎么实现如此高效的查找呢？

我们需要看他的数据结构，其实hash是一个array，通过某个合理的方式把值映射到array某个array[i]中。这就是hash的最核心思想了。说的简单，我们这里有几个问题需要解决：

   a、如何才是高效的映射？  

    b、如果两个不同的元素映射到同一个array[i]中又怎么办？

     c、数据量太小，array太大，会造成浪费；如果数据量太大,array太小，查找效率会非常低下，怎么解决？

我们一个一个来看。首先会到a.这里映射关系需要用到某个合适哈希函数，实验说明质数是一个非常好的选择，比如(value)mod(某个质数)。

b,提到的其实就是冲突处理的问题，冲突一般有以下方式，线性探测：冲突之后把元素放到下一个位置，下一个也有元素继续后面。二次探测：即一个哈希函数冲突了之后，用下一个哈希函数；开链法：就是在该array[i]下用一个链表表示。冲突了就放到链表中。STL中选择的是开链法。

对于问题c,STL中的解决方法是，选择某个质数K作为N，当K小于hash中的元素个数之后，用更大的质数代替N，同时对之前的每一个元素重构hash.

 其他算法：

其他例如find,accumulate...等算法，其实就是维护迭代器，一般都是fistIterator,lastIterator,operatorValue.这种架构。

从始至终，迭代器和泛型在几乎每一个STL容器或算法中都有出现、这才是精髓！

  

空间配置器

     这里在STL中说的空间配置器更多的是指内存的申请和释放。在STL中，一般拥有两级空间配置器，其中第一级配置器更像我们传统意义上的申请；而第二级配置器是一个池，一般称为内存池。

这里对空间配置器进行一个简短的综述，空间配置器管理存储资源的申请和释放的策略是当申请的资源较大时，这里说的较大时大于126BYTES时，调用第一级配置器，采用malloc和free的方式申请和释放；当小于126BYTES时，调用第二级配置器，第一级配置器实际上是由一个链表进行维护，但freeList中找到了合适大小的内存，直接给申请者使用，如果实在不够的话，就只能用部分，甚至再用堆申请一部分，即用malloc申请。释放的时候加入到freeList中。

采用二级配置器的一个利好就是，能够较大程度上减少碎片化，提高内存内部的使用率，减少资源浪费。

参考文献：STL源码剖析