空间配置器
最后更新于：2022-04-01 19:54:42
STL定义了两种空间配置器：
- allocator：位于
- alloc：在包含以下头文件，将功能分离：
-
- 全局函数construct()/destroy()：位于，用于构造/析构对象。
- 配置器alloc：位于，用于空间配置，分为一级配置器和二级配置器。
- uninitialized_copy/uninitialized_fill/uninitialized_fill_n：位于，用于填充或复制大块数据。
allocator配置器在分配空间时使用标准库函数operator new/operator delete。处于效率考虑，STL没有使用这个allocator，而是使用了更为精细的alloc配置器，将空间管理和对象管理两个阶段分离开来。
这样是为了解决内存碎片问题，TSL的空间配置器分两级。当申请空间大于128bytes时，使用第一级配置器；当申请空间小于128bytes时，使用第二级配置器。
- 第一级：__malloc_alloc_template，直接使用malloc、realloc、free管理内存。
- 第二级：__default_alloc_template，采用memory pool，由free-list维护。总共有16个free-list，每个free-list串联了一个个的内存块，当申请内存时就从一个适当的free-list中拔出一个区块给用户，用完后在返还给free-list。
两个空间配置器都是通过标准接口allocate()、deallocate()进入空间分配和空间释放的过程的。
无论alloc被定义为第一级或第二级配置器，SGI还为它再包装一个接口simple_alloc，每一个容器都直接包含这个类，当需要配置空间时，再由此类转调用allocate或deallocate：
~~~
template
class simple_alloc { // 对配置器alloc再进行一次封装，容器就使用这个类进行空间管理
public:
static T *allocate(size_t n)
{ return 0 == n? 0 : (T*) Alloc::allocate(n * sizeof (T)); }
static T *allocate(void)
{ return (T*) Alloc::allocate(sizeof (T)); }
static void deallocate(T *p, size_t n)
{ if (0 != n) Alloc::deallocate(p, n * sizeof (T)); }
static void deallocate(T *p)
{ Alloc::deallocate(p, sizeof (T)); }
};
~~~
容器内部直接使用这个类分配空间，例如在vector中：
~~~
typedef T value_type;
typedef simple_alloc data_allocator;
~~~
注意只是定义了空间分配器的类型，并没有定义实际对象。
当要分配或删除节点时：
~~~
iterator new_start = data_allocator::allocate(len); // 分配元素空间
data_allocator::deallocate(new_start, len); // 删除元素空间
~~~
利用类型限定符进行空间分配和释放。
参考：
《STL源码剖析》第二章。
';