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迭代器，源代码如下
