C++ STL六大组件核心原理
空间配置器(Allocator)
空间配置器的作用就是内存管理，主要用在容器中元素的空间分配和回收，基本上所有的容器都带有一个指定空间配置器的模板参数，默认情况下标准库提供了一份实现，如果有需要，使用者可以用自己实现的内存管理策略来代替标准库的实现。那么空间配置器的标准接口长什么样子呢？
allocator接口
// 这五个类型名是用作类型萃取
allocator::value_type
allocator::pointer
allocator::const_pointer
allocator::reference
allocator::const_reference
allocator::size_type
allocator::difference_type
// nested class template，用作迭代器萃取
allocator::rebind
// default constructor
allocator::allocator()
// copy constructor
allocator::allocator(const allocator&)
// 泛化的copy constructor
template<class U> allocator::allocator(const allocator<U>&)
// default destructor
allocator::~allocator()
// 取址操作
pointer allocator::address(reference x) const
const_pointer allocator::address(const_reference x) const
// 配置空间，大小为 n * sizeof(T) 字节
pointer allocator::allocate(size_type n, const void* = 0)
// 回收空间
void allocator::deallocate(pointer p, size_type n)
// 返回剩余可配置空间大小
size_type allocator::max_size() const
// 等同于 new((const void*) p) T(x)，相当于以x为模板调用构造函数
void allocator::construct(pointer p, const T& x)
// 等同于 p->~T()，相当于调用析构函数
void allocator::destroy(pointer p)
SGI空间配置器的实现
设计哲学
- 向系统堆区申请空间
- 考虑多线程状态
- 考虑内存不足时的应变措施
- 考虑过多小型区块可能造成的内存碎片问题
考虑到内存碎片问题，SGI空间配置器设计了双层配置器，即当配置区块大小超过128字节时，使用第一级配置器，直接调用malloc()和free()来分配内存；当配置区块小于128字节时，使用第二级配置器，使用内存池的方式来分配内存。
第二级配置器具体来说，就是它会维护一个数组，数组每个元素是一个链表，每个链表节点是固定大小可使用的内存空间，其中每个链表对应大小分别为8, 16, 24, …, 128字节的可用空间集合。当使用者申请空间大小小于128字节时，就可以直接从链表上取一个节点即可。当链表节点没有可用的时候，先去空间较大的链表找空节点，找到了就借用过来，否则直接用malloc()分配内存。