1 准备工作

在准备工作中，我们需要找到六大部件的源代码，源代码一般在include这个文件夹中，如下所示。

其次我们需要了解OOP和GP的区别，在上一讲中，我们已经有简单介绍。

从上图可知，vector和deque这两个容器本身就是一个类，他们通过RandomAccessIterator这中类型迭代器来使用sort排序这个算法。这些排序算法，均为模板函数。其次我们可以看到，这两个排序算法有些不一样，一个就是有两个参数，一个就是有三个参数，前面两个参数为指向头和尾。第一个函数选择默认的比大小，而第二个函数中_comp,则是如何比大小，需要用户提供一种标准，比如石头如何比大小，是根据重量呢，还是体积呢，这就是一种标准，需要用户自己指定。

下同：

其次所有的算法，最终就是比大小，比如查找，就是比等不等，排序也是比大小，就好像处理数据最终涉及的就是处理0，1.如下所示。

其次操作符重载，操作符重载是一个很重要的课题。比如迭代器必须实现如下的操作符重载。如iterator需要实现取元素，所以他要提供*重载，需要提供前加价，后加加，所以也要重载，总之，对指针要做的动作，iterator全部要重新定义一便，因为他的身份就是像一个指针，他要实现指针所有的功能。

类模板，如下所示：那个T就是我们要放的类的型别。

函数模板，如下，比大小，这是个什么类型呢，无所谓，因为编译器会做实参推导，你知道告诉编译器该如何比大小即可。

泛化与特化，泛化就是说，我们的类型，可以接受任意的类型，特化就是说，我指定的那个T，可能是一个独特的类型，此时可能有一个更好的做法。显示生活中，这种事情很常见，这个时候我们就需要定义一种独特的做法。下图可以表现特化的语法形式。

2  分配器

其实分配器很重要，因为他直接影响到容器的效率，主要是表现在时间，空间上，如下位VC98版本的编译器的allocator.

我们来看allocators中的operate new() 这个函数。在C++所有的分配空间动作，最终一层一层的执行必定会执行到C中的malloc()函数，然后这个malloc()函数再根据操作系统的不同，根据操作系统所提供的API，再去拿到真正的内存。operate new会调用malloc()函数，上述就是VC版本的operate new（）函数。其次解释一下右边的那个格子，右边的格子就是malloc()函数分配内存的结果，需要强调的是这是在debug模式下所分得的内存，红色部分为cookie，他记录分配内存的大小，有两个部分，一共八个字节，灰色部分是在debug模式得到的固定的大小他是36个字节，这是固定的，绿色部分是填充的大小，他为了达到某一个边界，蓝色部分才是真正所需要的内存大小。也就是说，你所得到的东西，远比你要的东西多。也就是malloc函数会让我们的额外开销很大。如果我们存取的区块很小，那我们的额外开销的比例会越大。这个有点不能忍受。

我们再依次来看看，VC6.0，BC编译器。我们会发现，虽然写法不一样，但是几乎没有什么特殊设计，都是去调用C里面的malloc()函数来得到内存，和free（）来释放内存。

让我们再来看看gnu C编译器。如下所示：我们发现gnu2.9也是如此。但是这里需要提到，gnu 2.9还有一个叫alloc的分配器。

前面提到gnu 2.9有一个alloc的分配器，我们看看他有什么独特设计。先看用法，如下

再看看他是如何实现的，如下

由于malloc()是给各式各样的人用的，所以内存有大有小，所以需要cookie来记录，但是容器不一样不管有几个容器，容器里的元素大小是固定的，因此似乎可以不用把每个元素的大小在每个cookie里附带着记着，比如说如果我们有100万个元素，每个元素是8个字节，前头却还要带着一小块东西去记着这一块是8个字节，这就没有必要。所以在容器的应用之下，可以不要cookie，所以gnu c2.9就从这里入手。她不要cookie，它要尽量减少malloc的次数。因此，它设计了16条链表，每一条链表负责某一种特定大小的区块，第一条负责8个字节大小，第二个负责16个字节大小，依次类推，第16条负责128字节大小。因此这样的设计方式会节省很多内存，但是有一个缺陷，我也不知道缺陷，只是听说貌似不重要。

但是在gnu 4.9中，却不是用的这个上面那个很好的分配器，不过他还在，它在扩充库里面。并且改了名字叫做pool_alloc.如下。我们可以从这个源代码中，他的结构的确是上面的那种链表结构。

3 序列式容器

我们首先通过下面一张图来了解容器的整体结构。我们可以发现stack和queue虽然也被称为容器，但是他也可以说是一种容器适配器，因为他是有deque实现的，所以说他只是实现了容器的功能，所以我们称之为容器适配器。从下图还可以看出，他们在不同版本的gnu 编译器下，所占用的内存不一样。

3.1 序列式容器（list）

从上图可知，他是一个双向链表，我们首先看他的数据部分，就是那个node，从上面看，发现他是一个指针，所以在32位电脑上就是4个字节，回到上面那张图他的确是4个字节。但是在4.9版本中却是8个字节，等下再说。其次那个void pointer其实写的不够好，虽然可以运作，但却需要向上转型，后面再4.9版中改了过来。其次iterator是一个聪明的指针，他必须是一个class。除了vector和array之外，所有容器的iterator都必须是一个class，它才能成为一个智能指针。其实那个list_iterator没有必要传三个模板参数的。

接下来我们来看看iterator的使用，如下第一个函数返回数据，第二个函数通过调用第一个函数并进行进一步操作返回数据地址。

我们接下来看看list_iterato如何实现,就像前面讲的，iterator这个“像指针的东西”必须实现指针的所有功能。其次几乎所有容器的iterator都至少会定义下面5个typedf,这5个typedf有何作用，后面讲解。

下面我们来举个例子来讲解operator++()和operator++(int)这两个操作符重载函数。为了区分前加加和后加加就在后加加括号加上一个参数，其实这个参数没什么意义。

（1）首先来看看为啥一个返回引用，另一个并不返回引用，这是为了向经典致敬，因为整数不允许后加加，加两次，所以指针也不允许后加加加两次，所以他不能返回引用，而前加加可以允许加两次，所以指针也允许前加加加两次。故返回引用。（2）来看一下这条语句 node=(list_type)((*node).next),相当于把node的next指针取出来然后赋给node本身，这就相当于让node那个泡泡的那一块指到下一个节点了。对于后加加，那些“=”，“++”可能是经过了操作符重载的，所以不容易理解。

另外，iterator除了要进行加加，减减操作符重载，还有一个重要的动作，即取值。如下所示：

如下为gnu4.9版的list_iterator,我们看到4.9版有改进，其参数只有一个了，并且那个指针的类型也有改进，从pointer to void 改成了 pointer to self。指针应该指向自己这个类型。

其次我们刚刚讲到gnu2.9版本list是4个字节大小，而gnu4.9版本则是8个字节大小，如下所示。我们发现这个list实现得很复杂，在2.9版中list只是一个类，而在这里，他却继承了乱七八糟一大堆东西。其次我们看list大小，list本身没有数据，但是继承了base，base也没有数据，他继承了impl，，impl也没有数据，他继承了node_base,node_base为两根指针，所以是8个字节。

3.2 序列式容器（vector）

我们首先来序列式容器vector的源代码，如下。首先谈谈vector如何自动扩充。他扩充两倍并不是在原地扩充，是因为我们要到一块内存之后，这块内存后面的地方可能就被别的东西用了，所以无法在原地扩充。事实上，几乎没有任何一个东西可以在原地扩充。所以扩充就是在内存的另一个地方找到两倍空间的大小，然后将数据拷贝到两倍空间大小的地方。从下图可知，在vector中有三个变量记录着vector，一个start起点，finsh终点，end_of_storage整个空间的终点。注意一个细节，这是gnu2.9版本，我们看到默认分配器为alloc,就是那个由16快链表组成的结构。因为它由3根指针控制整个空间，所以其大小为12个字节。再看看vector的那些函数，那些函数还是挺简单的，主要挑operator[]和back()函数来讲，一般来说只要是连续空间，都会提供中括号操作。back()函数取最后一个元素，我们提到前闭后开区间，所以其必须减1才能取到最后一个元素。如果直接取end()可能会报莫名错误。

我们再来看看两倍增长是怎么回事，源代码如下两张幻灯片：

具体分析一下：当我们调用push_back()函数时。他会判断是否有剩余空间，如果没有执行insert_aux()这个函数，然后又一次判断，这似乎有重复，主要是因为insert_aux()有可能还会被别的函数调用。在这里会执行else部分。然后判断size是否为0，如果为0，则置为1，否则两倍增长。两倍增长之后，开始将原数据copy到新空间中。按理说copy完之后应该没事了，但是后面又有几条语句，也是复制。还是因为insert_aux不仅仅被push_back()调用，他还可能被insert调用，所以就有安插点之前和安插点之后，有可能在前面安插，也导致vector扩充，所以安插点之后的数据也要copy。所以vector比较简单，但是需要注意的是由于每次成长，都要拷贝，所以会大量调用拷贝构造函数和析构函数，这个时间成本还是蛮大的。

接下来我们来看看vector的iterator迭代器，源代码如下

我们知道vector是一个连续空间，所以按理说指针就可以当成一个迭代器。在这里它会把iterator这个东西丢给Traits,因此萃取机他会走入那个偏特化的版本。所以我们看到对于一个指针，他的iterator_category为random_iterator_tag。还要说一下那个difference_type应该是一个unsigned in类型，他表示距离。 

3.3 序列式容器（array）

为什么将array包装成一个容器，因为包装成容器之后，他就需要遵循容器的规则，比如说要提供iterator迭代器，而这个迭代器又要提供5中相应的类型，以便于让算法去询问一些必要的信息，算法就可以选择最优化的策略，如果把它摒弃在六大部件之外，就不可以享受算法，仿函数等交互关系。下面就是TR1（technology report）的版本,如下为array的源代码。

3.4 序列式容器（forword_list）

因为我们前面介绍了list，所以这里不再详细介绍forword_list.如下为源代码

3.5 序列式容器（deque）

如下为deque的结构。其实它里面是一个vector，这个vector里面的每个元素是一个指针，这些指针分别指向各个缓冲区buffer。当最后一个缓冲区用完之后，他只要新分配一个缓冲区并且串接到后面那个指针上去。同理当最前面一个缓冲区用完之后也是如此扩充。first指向一个缓冲区的头，last指向缓冲区的尾，他们是不会变的，他们是标兵。current指向缓冲区的当前元素，node则是指向控制中心。所以deque是一个分段连续空间，连续是假象，分段是事实。

下面看看deque的源代码。我们先简单看下数据。start和finish是一个迭代器。在deque里面一个迭代器本身的大小是16个字节。map指的就是控制中心，而map_size就是控制中心的大小，他是一个vector，是可以增长的。其次旧版本deque允许我们指定缓冲区的大小。

我们接下来看看deque的迭代器，先看看迭代器类型，他是random_access_iterator_tag,他是可以跳的，这也就是为什么他对外声称自己是连续的原因，他需要制造一种假象，这种假象后面讲，先看看他的一部分源代码。

接着看一下deque里面的一个insert函数，这个函数很聪明。他聪明的地方在于，由于他可以往前往后推。所以他会找出你需要安插的元素距离尾端比较近还是首端比较近，因为元素插入进去，需要推动后面或者前面的元素，这时候就会调用构造函数和析构函数。这样就会耗费很长世间，所以当然是选择比较短的那边推，速度才会快，如下所示。

如下，他会首先判断插入的位置是靠近尾端还是首端，进行一个计算。

接下来我们来看看deque是如何模拟连续空间的。他一定要能够检查边界，跳到另一个缓冲区去。先看看一下简单的函数。back（）函数取出最后一个元素，在这里finish指向的是最后一个元素的下一个位置，所以取最后一个元素，需要将finish倒退一下。而在计算size（）时，那个“-”一定是做了操作符重载的。他一定是在看这两个迭代器中间有多少个缓冲区，把这个缓冲区的个数乘以缓冲区中元素的个数。我们后面再看源代码。

deque如何模拟连续空间，全都是deque iterator的功劳。这里就有对“-”的重载。这些操作我们可以结合图来理解。

下面就是“++”和“--”的重载，这里都是移动一个位置。

我们再来看看移动多个位置。因为他说自己是连续空间，所以必须支持移动多个位置。这里需要注意的是我们首先必须判断在“+=”这个操作时是不是要跨越缓冲区，如果不要跨越，直接”+“，如果要跨越，则node先退回控制中心，然后计算需要跨越多少个缓冲区，跨越之后再决定剩下几个要走。”-=“同理。

"-="如下，这里”-=“如此简单是因为他调用了”+=“，因为他相当于+ （-n）如下所示

下面我们再看gnu4.9版本的deque的源代码。如此复杂。在这里我们可以看到，deque已经不允许指定缓冲区的大小了。

再接着看，我们前面讲到deque的控制中心实际上是由vector支持的，也就是说当所有的缓冲区不够之后，他会象vector一样两倍增长。不同的是，vector扩充之后，会将值原先的值复制到vector的前段，而deque则不一样，deque扩充之后，会将原来的值复制到deque的中间，以便让新的deque依然可以在两端进行插入值。如下所示。

3.6 序列式容器（queue and stack）

源代码如下。我们可以感受到其实并不需要重写queue和stack，我们只需要让queue和stack内含deque，然后封掉deque的某些功能即可。就形成了一个新的容器。我们从下面的源代码看到就是如此做的，queue自己不做事，都是调用deque的函数。也因为这样，我们有时候也不把queue和stack称为容器，而把他们称为适配器。

我们再看看stack的源代码，他跟上面几乎一样。

在由于queue和stack的特性，所以他们是不允许有迭代器的，如下。

其次来看看queue和stack不能选择某些容器做底部支撑。

4. 关联式容器

介绍关联式容器之前我们先简单了解一下红黑树和哈希表。

来看看标准库对红黑树的实现。首先红黑树5个参数，其次看一下value，他是由key和data合在一起的。第三个参数keyOfValue需要我们告诉红黑树这个key该如何拿出来。第四个参数compare则是要求我们告诉红黑树该如何比大小，如果key是一个整数好说，直接比大小，如果key是石头呢，需要我们告诉红黑树该如何比大小。第五个当然是分配器。在这里说一下identity是gnuc独有的，而less是标准库的函数。也就是说如果不是用的gnuc的编译器，我们就必须写自己的identity模板。

红黑树的用例如下（基于gnuc2.9）：

红黑树的用例如下（基于gnuc4.9）：我们发现红黑树名字变了而且identity也变了。

gnuc4.9版本红黑树的结构如下

4.1 关联式容器（set和multiset）

有了红黑树做基础我们就可以很轻松的理解set和multiset了。

set的源代码如下，我们可以看到set里面有一颗红黑树。然后我们普通的用户只需要在set里面设置一个参数即可，因为set的其他两个参数有默认值。其次我们刚刚讲到由于set的底部是一颗红黑树，他是有一定的排列次序的，也就是说我们不能轻易的去改变迭代器的内容，所以在这里我们看到这棵红黑树的iterator是一个const类型的，他表示我们不可以改变迭代器的内容。这样的设计是很好的，以避免使用者搞不清楚状况，去改变iterator的值。还有我们需要知道set的所有操作都是转调用红黑树的，他自己不做事，跟前面的queue和stack类似。所以从这角度来说我们也可以认为set是一个container adapter.其次在set当中key就是value，value就是key，所以他一定是调用identity函数的。

前面讲过vc6不提供identity函数，所以他们如何使用红黑树呢，源代码如下：它实现了一个Kfn函数功能和identity函数完全相同。

4.2 关联式容器（map 和multimap）

map和multimap同样是以红黑树做支撑的，他和set和multiset的区别是，set中的key就是value，value就是key，而map，每个元素是个value，value中包含key和data两部分。

下面看看map的源代码，我们知道元素的合成一定是key放前面data放后面，所以selectlst就是取出key，根据key来查找，其次我们发现key和value被包装成了一个pair。前面讲过key是不可以被修改的，而data是可以改的，所以这里的pair将key设置为const。而这个pair又被定义为value_type，并被设置为红黑树的第二个参数。其次这个selectlst是gnuc独有的，在其他平台上要如何实现？

vc6版本的map如下：他也是实现一个kfn函数，作用和selectlst函数相同。

最后看看map一个独有的特性，multimap是不存在这样的特性的。

接着我们介绍底部是有hashtable做支撑的关联式容器。先来了解hashtable。散列表中篮子的个数一般为素数，如果元素的个数大于篮子的个数我们就做rehashing操作，此时篮子的个数大约增长两倍。

hashtable的源代码如下：我们看第三个参数，我们知道每个元素都应该有个编号，如果这些元素本身是数值，那他可以直接把他们当作编号，但是这个太玩具了，我们一般会放东西，放对象，一个对象怎么折射为号码编号呢，我们要传一个function告诉hashtable。这个function就是HashFcn。这个HashFcn算出来的那个编号叫做hashcode。第四个参数ExtractKey就是萃取出key。第五个参数EqualKey，就是我们要告诉他什么叫做key是相等的。我们再来看看一个hashtable里面有多少data。首先有三个函数对象，理论值为0，但是由于某些原因实际大小为1，然后一个vector，vector里面有三个指针大小为12，然后一个unsigned 类型的变量大小为4个字节，共19个字节，由于应该是4的倍数，所以一个hashtable的大小为20个字节。

接下来我们看看如何使用hashtable。其实最重要的是如何实现我们自己的hashFun，因为我们要根据自己数据的分布来设计hashFun。

下面来看看hashFun提供的一些版本。这里我们可以看到如果放进去的使一些数值，就把数值当作编号。

如果是一个字符串呢，那怎么转化为编号呢，看下标准库提供的版本。这里是将字符的ACCSI转化为编号。

最后看看是如何决定放在哪个篮子的，代码如下。根据源代码我们发现最后都是去调用hash（key）%n这种方法来决定放入那个篮子。

到了C++11，上述那些以hash开头的名字统统改为以unordered为开头的名字。但是只是换了名字，功能一点没有换。