在完成了STL与泛型编程第一周的学习之后，有一些总结和心得在这里通过学习笔记的方式分享出来，笔记我是跟着老师在视频中所讲的内容按照顺序记录的，也不能说是流水账，对课程中的一些问题还是添加了自己的理解和分析，供也在学习C++的小伙伴用作学习交流，如有理解不到位的地方，欢迎批评指正。

上周对于STL，老师做了一个大概的介绍，本周接着上周的内容继续学习了分配器以及各类容器的结构与分类。

一．OOP与GP的区别

OOP（Object-Oriented programming）企图将datas和methods关联在一起

GP（Generic Programming）却是将datas和methods分开来，如下图所示：

采用GP，Containerns和Algorithms两个团队可以闭门造车，其间以Iterator沟通即可。Algorithms通过Iterators确定操作范围，并通过Iterators取用Container中的元素。

二．特化（Specialization）和偏特化（Partial Specialization）

C++源码中运用了大量的操作符重载（Operator Overloading）以及模板（Templates），操作符重载的相关规则这里就不再赘述，模板的运用分为类模板（Class Templates）、函数模板（Function Templates）和成员模板（Member Templates），之前的课程有详细讲过，老师也进行了复习，这里也不再赘述。

我的理解是，特化就是泛化的反面，常规的模板都是泛化的，所谓特化，就是当模板替代类型中的一个类型有它特有的处理方法时，我们可以将template< >中的内容抽离出来，即为这个类型定义它特有的方法，如下代码所示：

偏特化分为个数上的偏和范围上的偏。

个数上的偏很好理解，就是具有多个模板参数时，将一部分模板参数特化，其他模板参数保持泛化，如下代码所示：

这里值得注意的是，特化部分参数只能从左至右特化，也就是说，不能第一个模板参数泛化，而将第二个模板参数特化。

我理解的范围上的偏就是模板参数的类型是一个指针，那么模板参数所代表的类型就是这个指针所指向的类型。如下代码所示：

这里值得注意的是，该指针指向什么由程序员自己定义。

三．分配器（allocators）

分配器最重要的两个函数：allocate（）和deallocate（）

VC6所附的标准库，其分配器的实现只是以：：operator new（）和：：operator delete（）来完成allocate（）和deallocate（），并没有任何特殊的设计。

而operator new（）和operator delete（）本质上还是调用基本的内存分配函数malloc（）和内存释放函数free（）：

BC++与VC6一样，最终还是调用malloc（）和free（），并且也是分配512ints，但是分配多少内存就要还多少内存，因此其接口设计非常不利于直接使用。

G2.9并没用使用分配器allocator，而创造了另一个分配器alloc，

alloc的实现如下图所示：

用链表的方式来分配内存，尽量减少调用malloc的次数，这样程序运行效率更高，节省了额外的开销。

但是之后的G4.9并没有使用这种高效率的alloc分配器（原因不得而知），而是改用了new_allocator分配器，这又与之前提到的VC/BC一致了，本质上还是调用malloc和free。但是G4.9所附的标准库中，有许多extention allocators，其中_pool_alloc就是G2.9中的alloc

四．容器——结构与分类

先来一张老师整理出的各种容器类型和所占字节数的图：

1.容器list

List其实是一个环状双向链表，用双向指针串起来，如下图所示：

List的iterator是一个类，G2.9中，这个类与list是包含关系。

这里值得注意的是，除了array和vector之外，所有容器的iterator都必须是class

之前说到过GP的好处就是将data和algorithm分开，那么iterator就是它们之间的桥梁，算法提出的问题，iterator要必须都能回答，这是iterator必须遵循的原则。

Iterators的五个associated types：

①Iterator_category（）分类

②Difference_type（）距离

③Value_type（）指向值的类型

④Reference

⑤Pointer

后面两个目前还未使用。

萃取机（Iterator Traits）用以分离class iterators（直接问）和non-class iterators（间接问）

加入中间层traits，利用偏特化回答non-class类型

2.容器vector

Vector是一种单向开口先进后出的容器，它所占用的是连续内存空间，因此它不能原地扩充，一旦空间不够，它必须寻找新的空间扩充，并且二倍增长，整个搬离到新开辟的两倍空间。

Vector靠3根指针控制整个容器：

因其是占用连续内存空间，所以它的iterator不必设计成class

3.容器array

Arry跟vector一样，也是占用连续的内存空间，其iterator是native pointer

4.容器forward_list

Forward_list是一种线状单向串列，与双向链表list差不多