空间配置器allocator的作用是为容器配置空间。
在这里以SGI的空间配置器alloc进行分析。
一般而言，C++的内存分配操作是这样的：
|
1 2 |
Foo* pf = new Foo; //配置内存，然后构造对象 delete pf; //将对象析构，然后释放内存 |
所以我们可以看到
new的两段操作：(1)调用operator new配置内存;(2)调用Foo的构造函数。
delete的两段操作：(1)调用Foo的析构函数;(2)调用operator delete释放内存。
在STL的配置器中，这两部分是分开操作的：
内存配置由allocate()函数负责，内存释放由deallocate()函数负责。
对象构造由construct()函数负责，对象析构由destroy()函数负责。
STL的配置器定义于<memory>头文件中。
里面包含了<stl_construct.h> 和 <stl_alloc.h> 两个头文件
|
1 2 |
#include <stl_alloc.h> //负责内存空间的配置和释放 #include <stl_construct.h> //负责对象内容的构造和析构 |
对象构造操作：
|
1 2 3 4 5 |
template <class T1, class T2> inline void construct(T1* p, const T2& value) { new(p) T1(value); //placement new;调用T1::T1(value); } |
要使用placement new，则要包含 <new.h>头文件。
对象析构操作：有两个版本
第一个版本接受一个指针，将指针所指之物析构掉。
第一个版本较为简单，直接析构即可。
第二个版本接受first和last迭代器，将 [first,last) 范围内的对象析构掉。
由于我们不知道这个范围有多大（可能非常大），而每一个对象的析构函数都无关痛痒（trivial destructor），那么一次次地调用这些无关痛痒的函数，会降低效率。
因此这里先使用value_type()或则迭代器所指对象的类型，然后再利用__type_traits<T>判断该类型的析构函数是否无关痛痒，微不足道。若是(__true_type)，则什么也不做就结束；若不是(__false_type)，这才以循环方式访问这个范围，并对每一个对象调用第一个版本的destroy();
空间的配置与释放：std::alloc
对象构造前的空间配置与对象析构后的空间释放由<stl_alloc.h>负责。
SGI 以 malloc() 和 free() 完成内存的配置与释放。
同时考虑到小型区块可能造成的内存破碎问题，SGI设计了双层级配置器。
第一级配置器使用 malloc() 和 free()，第二级配置器则视不同情况采用不同的策略。
当配置区块超过128bytes时，被视为足够大，直接调用 第一级配置器。
当配置区块小于128bytes时，视为小区块，采用复杂的内存池(memory pool)整理方式。
第一级配置器与第二级配置器的关系：↓（下图）
第一级配置器与第二级配置器的包装接口和运用方式：↓（下图）
从上图可以看到，实际使用第一级配置器还是第二级配置器取决于__USE_MALLOC是否被定义。
实际上我们可以轻易检测出来SGI STL并未定义它，所以使用的是第二级配置器。
第一级配置器：
第一级配置器以 malloc(), free(), realloc() 等C函数执行实际的内存配置、释放、重配置 操作，并实现出类似于C++的new-handler 的机制。即：要求系统在内存配置需求无法被满足时，调用一个你所指定的函数。
SIG第一级配置器的 allocate() 和 realloc() 都是在调用 malloc() 和 realloc() ，如果不成功，则该调用 oom_malloc() 和 oom_realloc()（oom：out of memory）。后两者都有内循环，不断调用“内存不足处理例程”，期望某次调用后获得足够的内存而圆满完成任务。但如果未设置内存处理例程，则直接调用__THROW_BAD_ALLOC，丢出bad_alloc异常，或者利用exit(1)退出程序。
第二级配置器：
为避免太多小额区块造成内存碎片问题，我们定义了第二级配置器。
第二级配置器的做法是，如果区块够大，就移交第一级配置器处理，如果区块小于128bytes，则以内存池管理。
这种方法又叫做次级配置：每次配置一大块内存，并维护对应之自由链表(free-list)。若下次再有相同大小的内存需求，就直接从free-list中拨出。如果客户端释放归还小额区块，就由配置器回收到free-list中（配置器除了负责分配，也负责回收…）。为方便管理，SGI二级配置器会主动将小额区块的内存需求上调为8的倍数，并共维护16个free-list，以分别对应不同的大小（8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128 bytes）的小额区块。
free-list的节点结构如下：
|
1 2 3 4 |
union obj{ union obj * free_list_link; char client_data[1]; }; |
这里使用的是共用体结构，以第一字段来看是一个指针，指向下一个obj，以第二字段来看是一个指针，指向实际区块。一物二用的结果是，不会为了维护链表所必须的指针而造成内存浪费。
第二级配置器的allocate()
首先判断区块大小，大区块(大于128Bytes)直接调用第一级配置器，小区块就检查对应的free-list。如果有可用区块，就拿来直接用，如果没有就调用refill()获得区块。
第二级配置器的deallocate()
首先判断区块大小，大区块(大于128Bytes)直接调用第一级配置器，小区块就用对应的 free-list 将区块回收。
第二级配置器的refill()
使用 chunk_malloc() 取的20个新区块，如果空间不足则可能小于20个，然后将第0个返回给客户端，从第一个开时将剩下的串起来，放入free-list。通过传引用得知获得区块的大小。
第二级配置器的chunk_malloc()
首先判断内存池是否有空间，如果足够供应一个及以上区块，就将这不足20个区块的空间分配出去。如果一个区块都不足以供应，则调用malloc从内存中获得空间（为需求区块数量的2倍）。如果heap的空间也不够了，那就再free-list内找有没有没用的，大小足够的的交出去，如果还是没有，就调用一级配置器期待oom处理机制能否成功，若不成功则发出bad_alloc异常。
以上就是 SGI STL 第一级配置器 和 第二级配置器 的工作原理。
若有不妥之处，望指正。
参考学习：侯捷——STL源码剖析。