本周课程主要讲解了OOP（面向对象）与GP（泛型编程）的对比、source code所涉及到的基础知识（包括运算符重载、各种模板等）以及利用标准库中的源代码讲解分配器allocators、迭代器iterator和容器list、vector、array、forword_list。
1、OOP（面向对象）与GP（泛型编程）
本节主要介绍了OOP和GP的对比。
总结该节内容如下：
（1）OOP是将datas和methods关联在一起，而GP是将两者分开；
（2）GP的好处是使得容器和算法团队可以各自“闭门造车”，其间以迭代器沟通就行，同时，算法通过迭代器确定操作范围，并通过迭代器取用容器元素；
（3）list不能调用::sort()，因为只有随机访问的迭代器才能调用::sort()，list不支持随机访问。所以list只能用自己的sort；
（4）所有算法涉及元素本身的操作，最终就是比大小。
2、源码之必要基础
本节简单回顾了之前学习的操作符重载、各类模板，其中介绍了类模板分为泛化、特化、偏特化（局部特化，个数和范围上），这里不再复述。
3、分配器allocators
本节介绍了各种编译器环境下的分配器的实现过程，包括VC6、BC5、G2.9和4.9。
总结该节内容如下：
（1）VC6和BC5的分配器只是利用::operator new和::operator delete实现allocate和deallocate的，都没有任何特殊设计。
（2）G2.9也是利用::operator new和::operator delete实现allocate和deallocate的，但是G2.9在容器中采用的不是allocator，而是alloc。在扩展空间时，尽量减少malloc次数，做法是创建16条链表，每条链表存放的字节是以8的倍数增长，第0条链表存放8字节，第1条链表存放16字节...。容器会和分配器要内存，容器中元素的大小会被调整为8的倍数，分配器会找到相应的链表上，再调用malloc分配内存，一个链上的每个内存块不带有上下cookie（8字节），只在链的头尾带有cookie，从而大幅节省额外空间开销。
（3）G4.9使用的是std::allocator, 继承于new_allocator, 且又是采用和VC6和BC5一样的分配和回收方法。G4.9中有许多extention allocators，其中_pool_alloc就是alloc。
4、容器的结构与分类
容器之间是复合的关系，而不是继承的关系，heap中拥有vector，priority-queue中拥有heap, stack和queue都拥有deque. 关联容器set、map、multiset、multimap都拥有rb_tree(红黑树)。
5、容器list
本节深度探讨了容器list。
总结该节内容如下：
（1）容器list为双向链表，提供迭代器和一系列操作符重载，迭代器内部要定义迭代器相关的5种typedef；
（2）容器list为前闭后开，最后一个有数据的节点的下一个节点是空的，end()指向的就是这个节点，begin()指向第一个元素；
（3）容器list中++操作符实现过程为记录原值，进行操作和返回原值，其中前++没有参数，后++是有一个函数参数的，为了与前++进行区分。后++首先会用tmp记录原有的指针，再对原有的指针自加，最后返回tmp；
（4）对于int变量，前++可以加两次，后++则不行；
（5）G4.9相对于G2.9过于复杂，G2.9中list只有一个class。
6、iterator需要遵循的原则
总结该节内容如下：
（1）rotate()函数萃取iterator_category（迭代器的分类，有的只能++，有的可以--，有的可以跳跃计算），萃取difference_type（两个iterator之间的距离）和value_type（容器中元素类型），和迭代器相关的还有两种typedef，分别是reference和pointer，但是从没有在标准库中使用过；
（2）迭代器内部定义的5种迭代器相关的typedef是为了给算法调用的；
（3）iterator_traits用以分离class iterators和non-class iterators，如果iterator是class，那么会使用泛化的类模板，如果iterator是non-class，那么使用两个偏特化类模板，一个模板参数特化为T，另一个特化为const T，所以无论iterator是类还是指针，都可以萃取其中的5种类型。
7、容器vector
本节深度探讨了容器vector。
总结该节内容如下：
（1）容器vector是前闭后开设计，在各种编译器环境中大小均是2倍增加；
（2）容器vector中有三个iterator(start指向第一个元素的位置，finish指向当前存放的最后一个元素的下一个位置，end_of_storage指向可以容纳最后一个元素的位置)；
（3）push_back()首先会利用finish和end_of_storage指针判断是否还有空闲位置，如果有，则插入元素，finish自加；如果没有，那么会调用辅助函数insert_aux(end(), x)，其内部会再次判断是否还有剩余空间，因为其他函数也可以调用这个函数，如果没有剩余空间，那么会分配原有空间大小的二倍，之后将原有的元素拷贝到新的空间，再将新的元素放进去，finish自加，之后会在新元素后面将剩余的原有元素拷贝过来，因此，每次空间成长均会大量调用元素的拷贝构造函数和析构函数，造成成本大；
（4）32位下sizeof(vector) = 12（有3个指针）。
8、容器array和容器forward_list
总结该节内容如下：
（1）容器array内部是用数组实现的，大小不能扩充，所以定义时要声明大小；
（2）容器forward_list与容器list类似，只是forward_list是单向的，而容器list是双向的。
9、课后补充学习
（一）各类容器对比
1、vector（连续的空间存储，可以使用[ ]操作符）可以快速的访问随机的元素，快速的在末尾插入元素，但是在序列中间随机的插入、删除元素要慢。而且，如果一开始分配的空间不够时，有一个重新分配更大空间的过程。
2、deque（小片的连续，小片间用链表相连，实际上内部有一个map的指针，因为知道类型，所以还是可以使用[ ]，只是速度没有vector快）快速的访问随机的元素，快速的在开始和末尾插入元素。随机的插入删除元素要慢，空间的从新分配空间后，原有的元素不需要备份。对deque的排序操作，可将deque先复制到vector，排序后再复制回deque。
3、list（每个元素间用链表相连）访问随机元素没有vector快，随机地插入元素要比vector快，对每个元素分配空间，不存在空间不够，重新分配的情况。
4、set内部元素唯一，用一棵平衡树结构来存储，因此遍历的时候就排序了，查找也比较快。
5、map一对一地映射结合，key没有重复。
6、queue的声明queue > s是受限的队列，存储的空间由第二个参数的容器确定，第一个参数在没有第二个参数的情况下，决定存储空间类型，第二个参数存在的情况下，第一个类型参数无效。默认情况下是deque类型的，因此可以如此声明queue s1，这样，声明的队列存储空间就是默认的deque。另外，queue第二个参数可以选择的容器类型包括deque、list，其余的如果声明，操作受限。
7、stack的默认存储空间也是deque，其他的声明和queue差不多，可以使用的容器类型包括deque、vector、list，stack是先进后出栈。
（二）作业问题
本周作业中有几个主要的地方：
1、变量的申明，采用老师上课所讲的方式，不在前面同一申明而是在使用的之前再申明，并采用缩排形式，这样便于查看。
2、从后向前打印容器元素，采用反向容器迭代器 MYLIST::reverse_iterator ri。
3、元素求和，采用accumulate算法，int sum=accumulate(l.begin(),l.end(),0)，这里需要增加头文件#include <numeric>。
accumulate带有三个形参：头两个形参指定要累加的元素范围，第三个形参则是累加的初值。
accumulate函数将它的一个内部变量设置为指定的初始值，然后在此初值上累加输入范围内所有元素的值。accumulate算法返回累加的结果，其返回类型就是其第三个实参的类型。
accumulate对要累加的元素类型一无所知，这个事实有两层含义。首先，调用该函数时必需传递一个初始值，否则，accumulate将不知道使用什么初始值。其次，容器内的元素类型必须与第三个实参的类型匹配，或者可转换为第三个实参的类型。在accumulate内部，第三个实参用作累加的起点；容器内的元素按顺序连续累加到综合之中。因此，必须能够将元素类型加到总和类型上。
