# 第2章 空间配置器
## 2.1 空间配置器第标准接口
根据 STL 的规范，以下是 allocator 的必要接口：
```c++
#include <cstddef> // for ptrdiff_t, size_t
template <class T>
class allocator {
public:
typedef T value_type;
typedef T* pointer;
typedef const T* const_pointer;
typedef T& reference;
typedef const T& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
// 一个嵌套的class template
template <class U>
struct rebind {
typedef allocator<U> other;
};
// 返回某个对象的地址，算式 a.address(x) 等同于 &x
pointer address(reference x) const;
// 返回某个 const 对象的地址，算式 a.address(x) 等同于 &x
const_pointer address(const_reference x) const;
// 配置空间，足以储存 n 个 T 对象，第二个参数是个提示
pointer allocate(size_type n, const void* = 0);
// 归还先前配置的空间
void deallocate(pointer p, size_type n);
// 返回可成功配置的最大量
size_type max_size() const;
// 等同于 new((void*)p) T(x)
void construct(pointer p, const T& x);
// 等同于 p->~T()
void destroy(pointer p);
};
```
## 2.2 具备次配置力（sub-allocation）的 SGI 空间配置器
SGI 的配置器与众不同，也与标准规范不同，其名称是 alloc 而非 allocator，而且不接受任何参数：
```c++
vector<int, std::allocator<int> > iv; // in VC or CB;
vector<int, std::alloc> iv; // in GCC
```
### 2.2.1 SGI 标准的空间配置器，std::allocator
SGI 也定义有一个符合部分标准、名为 allocator 的配置器，但 SGI 从未使用过，主要原因是效率不佳，它只是把 C++ 的 `::operator new` 和 `::operator delete` 做了一层薄薄的包装。
### 2.2.2 SGI 特殊的空间配置器，std::alloc
通常 C++ 内存配置操作和释放操作通过 `new` 和 `delete` 两个运算符实现，而 `new` 算式内含两阶段操作：(1) 调用 `::operator new` 配置内存；(2) 调用对应对象的构造函数构造对象内容。 `delete` 算式也内含两个阶段操作：(1) 调用对应对象的析构函数将对象析构；(2) 调用 `::operator delete` 释放内存。
为了精密分工，STL allcoator 将两阶段操作区分开。内存配置操作由 `alloc::allocate()` 负责，内存释放操作由 `alloc::deallocate()` 负责，对象构造由 `::construct()`负责，对象析构 `::destroy()` 负责。
### 2.2.3 构造和析构基本工具：construct() 和 destroy()
`costruct()` 接受一个指针 `p` 和一个初值 `value`，该函数的用途就是将初值设定到指针所指空间上。
``` c++
template <class T1, class T2>
inline void construct(T1* p, const T2& value) {
new (p) T1(value);
}
```
`destroy()` 有两个版本，第一个版本接受一个指针，准备将该指针所指向的对象析构，第二个版本接受 `first` 和 `last` 两个迭代器，准备将 `[first, last)` 范围内的所有对象析构掉。
```c++
template <class T>
inline void destroy(T* pointer) {
pointer->~T();
}
template <class ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last) {
__destroy(frist, last, value_type(first));
}
```
其中第二版本的 `destroy()` 会先通过 `value_type()` 判断当前类型不调用析构函数是否有影响，如果无影响则不调用，否则逐一调用对象的析构函数。
### 2.2.4 空间的配置与释放，std::alloc
对象构造前的空间配置和对象析构后的空间释放有以下要求：
* 向 system heap 要求空间；
* 考虑多线程（multi-threads）状态；
* 考虑内存不足时的应变措施；
* 考虑过多“小型区块“可能造成的内存碎片（fragment）问题；
考虑到小型区块可能造成的内存破碎问题，SGI 设计了双层级配置器，第一级配置器直接使用 `malloc()` 和 `free()` ，第二级配置器则视情况采用不同策略：当配置区块超过 128 bytes 时，便调用第一级配置器；当配置块小于 128 bytes 时，为了降低额外负担，便采用复杂的 memory pool整理。
### 2.2.5 第一级配置器 __malloc_alloc_template 剖析
第一级配置器以 `malloc()`，`free()`，`realloc()` 等 C 函数执行实际的内存配置、释放、重配置操作，并实现出类似 C++ new-handler 的机制。
### 2.2.6 第二级配置器 __default_alloc_template 剖析
次级配置（sub-allocation）每次配置一块大内存，并维护对应的自由链表（free-list）。为了方便管理，SGI 第二级配置器会主动将任何小额区块的内存需求量上调至8的倍数，并维护 16 个 free-list，各自管理 8、16、24、32、40、48、56、64、72、80、88、96、104、112、128 bytes 的小额区块。
### 2.2.7 空间配置函数 allocate()
```c++
static void* allocate(size_t n);
```
* 首先判断区块大小是否大于128 bytes，如果大于则使用第一级配置器；
* 如果小于128bytes，寻找16个free-list中适当的一个，如果对应free-list有可用区块，则使用该区块；
* 如果没有可用区块，就将区块上调至8的倍数边界，然后调用 `refill()` 准备为 free-list 重新填充空间。
### 2.2.8 空间释放函数 deallocate()
```c++
static void deallocate(void* p, size_t n);
```
* 首先判断区块是否大于 128 bytes，如果大于则使用第一次配置器释放对应空间；
* 如果小于 128 bytes，则将空间归还给对应的free-list；
### 2.2.9 重新填充 free lists，refill()
调用 `chunk_alloc()` 获取新的空间，然后将新获取的空间装入对应的free-list。
``` c++
template <bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n);
```
### 2.2.10 内存池（memory pool）
```c++
template <bool threads, int inst>
char* __default_alloc_template<threads, inst>::chunk_alloc(size_t size, int& nobjs);
```
* 内存池中剩余空间完全满足，则从剩余空间中分配；
* 内存池中剩余空间只够满足部分区块，则从剩余空间中分配可满足的数量；
* 内存池中剩余空间连一个区块也无法满足：
* 将剩余的空间（零头）分配给适当的free-list；
* 从heap中获取空间补充内存池；
* 如果从heap中配置失败，则从尝试从更大的free-list中“借用“空间；
* 如果free-list中也无合适的空间，则分配失败；
## 2.3 内存基本处理工具
```c++
template <class InputIterator, class ForwardIterator>
ForwardIterator uninitialized_copy(InputIterator first, IntputIterator last, ForwardIterator result);
```
`uninitialized_copy()` 针对输入范围内的每一个迭代器 `i`，该函数会调用 `construct(&*(result+(i-frist)), *i)`，产生 `*i` 的复制品。
```c++
template <class ForwardIterator, class T>
void uninitialized_fill(ForwardIterator first, ForwardIterator last, const T&x);
```
`uninitialized_fill()` 针对操作范围内的每个迭代器 `i`，调用 `construct(&*i, x)`。
```c++
template <class ForwardIterator, class Size, class T>
ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n, const T& x);
```
`uninitialized_fill_n()` 面对 `[first, first+n)` 范围内的每个迭代器，调用 `construct(&*i, x)`。
