空间配置器是STL用来分配和管理空间的类型；STL allocator将对象的构造、析构与内存的配置和释放分开 。对象的构造和析构由construct（placement new在指定空间创建对象） 和destroy负责（全局函数）。内存的配置和释放由allocate和deallocate负责。

SGI STL的两级空间配置器

SGI STL 为了避免小型区块的内存碎片（fragment）问题,SGI设计了两级配置器

当配置区块大于128字节时，调用第一级配置器。小于128字节时调用第二级配置器。

第一级配置器（alloc）的allocate()和deallocate()函数只是简单调用malloc()和free()函数；

如果出现了out_of_memory错误，就不断调用__malloc_alloc_oom_handler()错误处理函数，去尝试释放内存，然后重新调用malloc分配。不断循环，直到分配成功。（如果没设置这个处理函数，就抛出bad_alloc异常）

第二级配置器为了降低额外开销（overhead），采用内存池(memory pool)管理内存分配；具体使用的内存块从free-list(自由链表)中提取出。

具体流程为：

1.当需要申请的内存大小N 大于128bytes时，直接使用第一级配置器，使用malloc分配

2.小于等于128bytes时，使用内存池管理。内存池管理步骤为：

a. 首先查看是否有可用的free-list，如果有就直接使用。没有的话，将所需区块大小上调至8的倍数，调用 refill()为free list重新分配空间。

b. 新的空间将取自内存池（经由chunk_alloc()完成），如果内存池不够用，从堆空间（malloc配置空间） 拿来补充内存池。如果堆空间也不够了，就调用第一级配置器来补充内存池。因为第一级配置器有out-of- memory处理机制，看看它能不能释放其它内存然后拿来此处使用（如果可以就成功，否则bad_alloc异常）。

这里要注意一点，最初内存池和free list都为空。

内存池如何refill()链表

当free list中无可用区块，将向内存池申请空间。当内存池空间充足时，新的空间将缺省获得20个新的区块大小N（所需内存空间上调8的倍数）。当内存池空间不满足需求量，先尽可能分配出大小为N的内存块。如果内存池剩余空间小于N，先将内存池的残余分给free list,然后向堆空间申请内存。

内存池以及free list一次配置这么大的空间，是为了不频繁申请内存，减小不必要的开销。

free list

free-list：是有16个大小分别为8，16一直递增到128字节的内存块构成的链表。因此第二级配置器最大只能分配128字节。

free-list相比链表，如何实现减少额外负担？

普通链表不仅要有指针指向实际区块，还要维护指向下一个节点的指针，所以会有额外的负担。

free-list采用的是联合体（union，算是一种数据类型），联合体数据成员共享一块内存。两个数据成员，一个是指向下一个节点的指针，另外一个是指向实际区块的指针。

这两个数据成员在任何时刻只有一个有值，对应于分配的两种情况——分配和不分配。不分配时，使用的是指向下一节点的这一数据成员。分配时（区块拔出，不用指向下一节点），则使用的指向实际区块的这一数据成员。

内存池：是一种内存分配方式，频繁使用new、malloc会造成大量内存碎片。并且频繁分配和回收内存会降低性能。内存池一次申请一定数量的内存块留作备用，因此不用频繁去申请新的资源。

联合体（union）

联合体（union）是一种节省空间的类，其特性是一个union可以有多个数据成员，但是在任意时刻只能有一个数据成员可以有值。联合体的大小为最大数据成员的大小，本质是数据成员共享内存，从而实现节省空间的目的。

联合体与类的区别

• 联合体的数据成员默认为public，与struct相同，而class默认为private。

• 联合体不能作为基类，不能继承，因此数据成员也不能有虚函数

• union的数据成员不能有引用类型（引用必须初始化且不能修改绑定）

• C++11允许union含有定义了构造函数或拷贝控制成员的类类型成员