（源码很重要，只有熟悉源码，才能知道怎么用）

源码分布（VC , GCC）

OOP vs GP

OOP:数据放在class里面，操作这些数据的函数也放在class里面 为什么list不能用::sort排序呢？ 因为::sort的在设计中采用了随机访问迭代器（由下图红色部分）， 而list（类似链表）是不支持这个操作的

iterator迭代器是泛化指针，借助迭代器可以算法可以实现对数据的操作

操作符重载和模板（泛化，全特化，偏特化）

这一集再看看，尤其是关于模板部分

这里的特化说的很清楚

分配器

所有的内存分配动作最终都会到malloc，这个malloc它就会根据不同的操作系统调用API，从而拿到真正的内存 在标准层面上，大家都最终跑到malloc上

从上图中可以看到operator new调用malloc 右图为malloc调用的内存（详情见内存管理）

由上图可知allocate调用_Allocate，而_Allocate又调用operator new，然后由前面可知，operator new是调用malloc的 结论：在VC所提供的分配器allocate，当它要分配内存的时候，它是一层一层下去最终调用的是malloc函数 malloc对应free 而VC的deallocate调用的是operator delete，而operator delete它又是调用的free 上图中的allocate<int>()表示的一个临时对象object 注意这里deallocate在归还内存的时候是还512个，这件事是很费心的，所以还是容器好 string是个指针？？？？ 结论：**VC**的分配器没有独特设计，它就是调用c的malloc和free函数来分配和释放内存，而且它的接口设计对我们不友好， 但是如果是容器去用就没问题

BC的分配器

困扰：我的容器如果放100万个元素，而且每个元素是小小的，由于这些元素的内存分配都是用malloc得到的，所以额外开销就会很大（由于区块是小小的）

GNC分配器

结论：上面三种分配器都是使用malloc和free来分配/释放内存，会造成大量的额外开销 下面这个分配器是比较好用的，可以解决上面三种分配器的问题 分配器用的是alloc√（这是G2.9版本）

注意G4.9又恢复到前面三种的用法，调用malloc，造成额外开销

想要用回G2.9的那个，见下面的用例和分析

容器之间的实现与分类

分配器是为容器服务的

上面的复合表示的是拥有的意思 这里的缩排表示的是复合的关系 rb_tree就是红黑树的意思，这里就相当于说map/set里面有一个红黑树帮它管理支撑 在标准库里，尽量用复合而非继承

探索list

再看一遍，尤其是关于迭代器的部分

list容器不是最简单的，但是是最具代表性的容器

注意先+和后+的返回值类型，一个有&，一个没有（原因见上图的左下角的++++i和i++++）

这里的*node就是获取node所指向的整个节点 所有容器的迭代器iterator都有两代部分：1、typedef 2、操作符重载

注意G2.9到G4.9的改进，正好解决了G2.9的三处问题，见上图

iterator需要遵守的原则

和模板联系紧密，回头再看看

下面是其他的traits

vector深度扩充

vector不能原地扩充

三个指针控制容器的大小，三个指针所以前面展示的是12字节 上图中size()的实现是调用两个函数相减实现的，为什么不直接用finish-start呢？？？ 首先直接减快不了多少，其实这么做是为了应对里面不是finish，start这种情况

上图呈现出两次检查，为什么呢？ 那是因为insert_aux不仅会被push_back调用，可能还会被其他函数调用

假设现在是第8个元素，当放了第9个元素的时候，vector要做两倍增长，于是在空间中找出一个16个元素的大小， 然后把原来的8个元素copy到这个16处，再把第9个元素放入新的内存中去

注意上面的第二次copy（可能是在中间插入值的时候发生了扩充，所以安插点之后的值也要copy） 注意：每次只要增长，就会有大量的元素拷贝动作，元素的拷贝会引发拷贝构造函数，拷贝之后，原来的元素也要被删除，要调用析构函数，这是一个大的成本

vector的迭代器

链表的迭代器是需要单独设计成一个class（节点是分离的） 而vector中的元素是连续的，设计成指针即可

这里的设计和前面list的设计基本一样（不熟悉）

vector的大小就是_vector_base的大小，而_vector_base的大小就是数据_M_impl的大小，而数据_M_impl的大小就得看它的类型_Vector_impl, 而这个类型的大小三个指针这么大（12），然而这个类型还有父类，在计算大小的时候也应当把父类加进去（父类是子类的一部分），然而这里的父类是一个allocator,没有大小（没有data），所以vector的大小为12 G 4.9这个没有G 2.9好用 老师认为这里不应该用public，而应该是用private public有is a的含义，这里只是使用而已

这里老师疯狂diss为什么要G 4.9要设计的这么复杂

容器array

array就是数组，但是为什么要把array包装成容器来用呢？？？ 因为变成容器之后，它就要遵循容器的规律，规则，要提供iterator迭代器，而迭代器又要提供5种相应的类型， 以便于可以让算法去询问必要的信息，算法就可以决定采取最优化的动作，如果没有这么包装的话，array就会被摒弃在六大部件之外，他就不能享受仿函数，算法等和它的交互关系 TR1:技术报告1 其他容器都是可扩充的，但是array要指定大小 array没有构造函数和析构函数 是连续的地址空间，迭代器可以用指针，不需要另外设计class

forward_list是单向链表，具体实现参考前面的list(双向链表)

deque，queue和stack深度探索

deque对外号称连续，其实它是分段的（不同段是用vector来串接起来，vector里面存的是指针，这些指针分别指向各个缓冲区buffer（所以上图五个buffer的次序就是看五个指针的次序）） 如果我们push_back放入元素，把尾端buffer用光，它要怎么扩充呢？？？ deque就会新分配一个缓冲区，并且串接到vector的末端 这里有一个疑问？老师说是vector，但是当vector的头部存满了，怎么扩充？？？ deque的迭代器是一个class，这个class内部有四个元素，其中node指向控制中心 控制中心就是map所指的东西，其实是一个vector 当创建一个deque的时候，这个对象本身40个字节（16+16+4+4）

首先定义五个相关的类型

deque有个很聪明的地方，这里用insert函数举例，比如deque中有1万个元素，现在要在第5位插入元素， deque会选择通过移动头部的前4个元素来实现插入操作（而不是移动1万-5个元素），每次移动时都会调用拷贝构造函数和析构函数

通过和中间位置的长度相比，来判断是在前面插入还是在后面插入

deque怎么模拟连续空间

关键在于迭代器的加加减减，加等于，减等于这些动作上，还一定要能检查边界，判断跳到另一个缓冲区去

上图中的finish-start怎么实现的？ 3*8+3+0

怎么跳到下一个缓冲区？？ 先回到控制中心，然后移动到下一个位置（存的指针），这个指针指向另一个缓冲区

在+n的时候，有一个判断，判断是否还在该缓冲区内（如上图注解）

只要连续空间这种，或者假象，都应该提供[]中括号这种操作符

这里解释了，在copy的过程时，比如8->16，会把8 copy 到16的中端，使它可以向左或者向右扩充缓冲区

所以说stack和queue内含一个deque

编译器对模板不会进行全面检查，比如上面的pop()，当没有用到pop()操作的时候queue就可以用vector做底层结构

rb_tree容器

有点疑问

红黑树设计成高度平衡的树，有利于查找 不能用迭代器改变元素的值，因为会破坏排序树 红黑树是按照key来排序的

C++中空类占一个字节，上面的rb_tree其实是4+4+1（仿函数为1，因为里面没有数据，又不能弄成0）,凑成4的倍数到12

疑问：为什么key和value都设置成int，就相当于没有data了？？？？ value不是包含key和data嘛？

这里老师终于说了为啥G 4.9要设计成这种复杂难用的形式，handle 和 body这种设计模式（桥接模式） 上图为啥是24个字节？？？ color这里怎么看

这里说set有规定，value就是key，但是不知道为什么？？？

像上诉这种，自己不做事情，把全部事情都交给底层去实现的，一般称为容器适配器（功能使用上市容器，但是技术分类上不是）

map的迭代器只能改data，不能改key（注意上图中的key是const类型）

这里的中括号[]的实现，找到就返回，找不到就插入

hashtable容器

hash表的扩容，打散，篮子2倍 （元素个数大于篮子个数就需要扩容）

把对象object反射为一个编号 上面1+1+1+12+4=19（调整为4的倍数），对齐操作 上面的迭代器设计可以看看deque（这里走到边界后，要有能力回到篮子，走到下一个位置）

这里用的是C风格的字符串，没有针对C++的字符串定义，需要自己设计

篮子个数一定大于元素个数

参考