第二章：空间配置器（allocator）

考虑到小型区块可能造成的内存破碎问题，SGI设计了双层级配置器。

当配置区块超过128bytes时，便调用第一级配置器，即直接使用malloc() free()；

SGI的第一级配置器的allocate()和realloc()都是在调用malloc()和realloc()不成功后，改调用oom_malloc()和oom_realloc()，后两者都有内循环，不断调用“内存不足处理例程“，期望在某次调用后，获得足够的内存而圆满完成任务，但如果“内存不足处理例程”未被客端设定，oom_malloc()和oom_realloc()便不客气的调用__THROW_BAD_ALLOC，丢出bad_alloc异常信息，或利用exit（1）中止程序。

当配置区块小于128bytes时，采用复杂的memory pool整理方式：

每次配置一大块内存，并维护对应之自由链表free-list，下次若再有相同大小的内存需求，就直接从free-list中拨出，如果客端释放小额区块，就由配置器回收到free-list中，为方便管理，第二级配置器主动将任何小额区块的内存需求量上调至8的倍数，并维护16个free-list，各自管理大小分别为8,16,24,32,40,48， 56,64,72,80,88,96,104,112， 120,128bytes的区块

假设程序一开始，客端就调用chunk_alloc(32, 20)，于是malloc()配置40个32bytes区块，其中第一个交出，另19个交给free-list[3]维护，余20个留给内存池，接下来客端调用chunk_alloc(64, 20)，此时free-list[7]空空如也，必须向内存池要求支持，内存池只够供应（32*20）/64=10个64bytes区块，就把这10个区块返回，第一个交给客端，余9个由free-list[7]维护，此时内存池全空，接下来再调用chunk_alloc（96，20），此时free-list[11]空空如也，必须向内存池要求支持，而内存池此时也是空的，于是以malloc()配置40+n(附加量)个96bytes区块，其中第一个交出，另19个交给free_list[11]维护，余20+n个区块留给内存池；

万一整个system heap空间都不够了，malloc()行动失败，chunk_alloc()就四处寻找有无“尚有未用区块，且区块够大”之free-list，找到了就挖一块交出，找不到就调用第一级配置器。第一级配置器也是使用malloc()配置内存，但它有out-of-memory处理机制，或许有机会释放其他的内存拿来此处使用，如果失败，发出bad_alloc异常。

第四章

一，vector

1，vector的内存不是固定的是动态的，每当size()==capacity()，vector会分配一块原来长度两倍的空间，并将原来的每个元素拷贝到新空间中，最后释放旧空间。

2，vector维护的是一个连续的空间，迭代器是元素型别的普通指针。

3，vector类中有三个成员都是迭代器，分别start指向目前使用空间的头，finish指向目前使用空间的尾，end_of_storage指向目前可用空间的尾。

4，对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失败了。

二，list

1，list每次插入或删除一个元素，就配置或释放一个元素空间，不会浪费空间，对于任何位置的元素插入或删除，list永远是常数时间。

2，STLlist是一个双向（环形）链表，insert插入和splice接合都不会造成原有的list迭代器失效，list的erase删除操作，只有被删除的元素的迭代器失效，其他的迭代器不会失效。

三，deque

1，deque是可以在头尾两端分别做元素的插入和删除操作的一种双向开口的分段连续空间。

2，每个deque有一个map，map是一个线性数组，数组的每个元素指向一段连续线性空间，deque中的真正元素保存在每一段连续线性空间中，每个deque都有两个start和finish迭代器结构，该结构有四个成员，cur指向当前被访问到的元素，first指向这段连续空间的第一个元素，last指向这段连续空间的最后一个元素

3，map最小元素个数为8，若空间不够，map可以重置。

4，stack和queue由deque作为底层实现。

四，priority_queue

1，实现机制是heap算法。

2，连续线性空间。