Boolan STL 第二周

OOP与GP区别：OOP总是将data与methods关联在一起，GP则是将data与methods分开。

使用GP的好处：

algorithms的本质：最终都是元素之间比大小。

list为什么不能使用::sort()?:因为list内部元素是分开的，它的iterator不是random access iterator，无法使用algorithm提供的sort()。

无法被overload的符号："::",".",".*"

allocator中的operator new（）实现：调用malloc（），会额外占用空间记录申请内存大小（cookies）和填充pad到16的倍数，所以申请小块空间相较于申请大块空间的空间利用率会小的多。

G2.9的alloc优点：分成16块空间，从8byte开始每块空间存放的元素递增8byte，第16块空间存放元素为128byte，每块空间后面存放的元素之间没有cookies，只在整块前后有cookies，大大减少系统开销。

容器结构再分类：

list（双向循环链表结构）：

list的iterator的实现：

iterator的实现的区别：除vector、array直接使用其指针外其他容器的iterator都是由smart pointer实现。

iterator必须提供的五种供algorithms的associated type：

iterator traits的用途：区分class iterator和non-class iterator，利用偏特化来实现5种associated type的提供，主要是为pointer类型提供typedef的功能。

完整的iterator_traits:

vector的代码实现：

vector的push_back实现：

vector的iterator实现：

array实现：