在STL的使用者层面上，空间配置器一般是隐藏的，使用者不需要知道其具体实现细节即
可进行使用；但是从STL的实现角度来说，由于整个STL的操作对象都存放在容器之内，而容器
需要配置一定的空间来进行存放数据，因此，想要实现或者说深入了解STL的第一步便是掌握
空间配置器的原理。
目录
主要还是说说SGI版本的STL的配置器
我们知道，stl有容器，空间配置器，适配器，迭代器，仿函数以及算法这6个组件：他们之间的运行关系大概是：容器通过配置器去获得数据和存储空间，算法通过迭代器获取容器内容,仿函数可以协助算法完成不同的策略变化,配接器可以修饰或套界仿函数。
allocator是STL的重要组成，但是一般用户不怎么熟悉他，因为allocator隐藏在所有容器（包括vector）身后，默默完成内存配置与释放，对象构造和析构的工作。
首先我们知道c++中内存分配和释放操作是由new和delete去完成的
class A {};A* p = new A;//...执行其他操作delete p;在我们使用new来建造一个对象的时候，一般是分为两个步骤的：1.调用::operator new()来构建空间；2.调用对象的构造函数。注：::operator new内部由malloc实现、省略指针转换这步。同理，当我们使用delete函数的时候：1.调用对象的析构函数2.调用::operator delete()释放空间。注：::operator delete内部由free实现在STL的实现中，为了精细分工、STL allocator决定将上述步骤的两阶段操作分开来，内存
配置操作由alloc::allocate()负责，内存释放由alloc::deallocate负责，对象构建
操作由construct负责，对象析构操作由destroy负责。对于实现我就不过多赘述了
下面主要还是说说SGI版本的STL的配置器
对于SGI STL的实现来说、他这里含有了两个不同的空间配置器
第一个是一个符合部分标准、名为allocatr的配置器std::allocator
仅仅是将::operator new()和::operator delete()做了一层简单的封装，因此效率比较差。它存在的意义仅在于为用户提供一个兼容老代码的折衷方法，我们不建议使用，而且SGI内部也不使用这种标准的配置器，看一下了解一下
#ifnedf DEFALLOC_H#define DEFALLOC_H#include #include #include #include #include #include template inline T* allocate(ptrdiff_t size, T*) {set_new_handler(0);T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));if (tmp == 0) {cerr << "out of memory" << endl;exit(1);}return tmp;}template inline void deallocate(T* buffer) {::operator delete(buffer);}template 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;pointer allocate(size_type n) { return ::allocate((difference_type)n, (pointer)0); }void deallocate(pointer p) { ::deallocator(p); }pointer address(reference x) { return (pointer)&x; }const_pointer const_address(const_reference x) { return (const_pointer)&x; }size_type init_page_size() {return max(size_type(1), size_type(UINT_MAX/sizeof(T)));}};class allocator {public:typedef void* pointer;}；第二个是我们需要重点掌握的特殊配置器 std::alloc
这个配置器是SGI STL的默认配置器，它在中实现。
中包含三个文件：
：定义了全局函数construct()和destroy()，负责对象构造和析构。：内存配置和释放在此处实现，其内部有两级配置器，第一级结构简单，封装malloc()和free()，第二级实现了自由链表和内存池，用于提升大量小额内存配置时的性能。：一些用于用于填充和拷贝大块内存的全局函数。
对象构造和/析构，与内存配置/释放是分离实现的。
SGI对于alloc函数的要求如下所示：1.向system heap要求空间2.考虑多线程状态3.考虑内存不足的应变措施4.考虑过多“小型区块”可能造成的内存碎片问题。
两层配置器的关系如下：
根据情况来判定，如果配置区块大于128bytes，说明“足够大”，调用第一级配置器，而小于等于128bytes，则采用复杂内存池（memory pool）来管理。
同时为了自由选择，STL又规定了 __USE_MALLOC 宏，如果它存在则直接调用第一级配置器，不然则直接调用第二级配置器。SGI未定义该宏，也就是说默认使用第二级配置器
由于一级配置器存在内存碎片的问题，所以有了二级配置器
转自《STL源码剖析》的SGI STL特殊配置器的内部实现图
图示左边是用户代码，右边是STL的内部。
我们可以看到，用户代码实例化一个vector对象，vector对象调用alloc的接口，注意，不同于之前标准的allocator，这里不需要实例化一个空间配置器，只需要调用alloc的静态函数就行了。
std::alloc的接口与标准非常相似：
static T* allocate()函数负责空间配置，返回一个T对象大小的空间。static T* allocate(size_t)函数负责批量空间配置。static void deallocate(T*)函数负责空间释放。static void deallocate(T*,size_t)函数负责批量空间释放。
在接口之下，我们看到还有两级配置器，上面的接口根据情况调用这两个配置器，第二级配置器实现了内存池和自由链表，当程序多次进行小空间的配置时，可以从内存池和自由链表中获取空间，减少系统调用，提升性能。当进行大空间的配置时，上面的接口直接调用第一级配置器。最终，它们都是用malloc()和free()来配置和释放空间。
一般C++开发者了解到此已经足够应付大多数开发场景了。
这样看起来std::alloc的结构还算清晰，但是实际实现还会出现多种边界情况，比如，当系统调用malloc()空间不足时，我们需要让第一级配置器来处理，这可能涉及从第二级配置器中回收已经缓存但还未使用的空间，事情就变得繁琐了。
下面来手撕两层配置器的实现：
- 一级空间配置器
一级配置器直接用C中的malloc()以及free()函数来进行处理，当我们的内存分配不足的时候，我们调用oom_malloc()函数和oom_realloc进行处理,这两个函数里面都有循环，不断地去调用“内存不足，要调用例程”，去处理。
#if 1#include#define __THROW_BAD_ALLOC throw bad_alloc#else !defined(__THROW_BAD_ALLOC)#define __THROW_BAD_ALLOC cerr<<"out of memory"<<endl;#endiftemplateclass __malloc_alloc_template{private:static void* oom_malloc(size_t);//malloc--指针函数static void* oom_realloc(void*, size_t);//realloc--指针函数static void(*__malloc_alloc_oom_handler)();//函数指针public:static void* allocate(size_t n)//申请空间{void* result = malloc(n);//第一级配置器直接使用malloc//如果无法满足需求，费用oom_malloc()if (result == 0) {result == oom_malloc(n);}return result;}static void deallocate(void* p, size_t){free(p);//第一级配置器直接使用free()}static void* reallocate(void* p, size_t)//不够了追加,是对allocate的补救{void* result = realloc(p, new_sz);//第一级配置器直接使用realloc//无法满足需求，改用oom_realloc()if (result == 0) {result = oom_realloc(p, new_sz);return result;}} //下面这个可以通过他去指定自己的//out-of-memory handlerstatic void (*set_malloc_handler(void(*f)()))(){void (*old)() = __malloc_alloc_oom_handler;__malloc_alloc_oom_handler = f;return old;}};//初始值为0，可以在客户端自己设定templatevoid(*__malloc_alloc_template::__malloc_alloc_oom_handler)() = 0;templatevoid* __malloc_alloc_template::oom_malloc(size_t n){void (*my_malloc_handler)();void* result;for (;;)//死循环，不断尝试释放，配置，释放，配置。。{my_malloc_handler = __malloc_alloc_oom_handler;if (0 == my_malloc_handler){__THROW_BAD_ALLOC;}(*my_malloc_handler)();//调用处理例程，企图释放内存result = malloc(n);//尝试配置内存if (result)return result;}}templatevoid* __malloc_alloc_template::oom_realloc(void* p, size_t n){void (*my_malloc_handler)();void* result;for (;;){ //不断尝试释放、配置、再释放、再配置。。my_malloc_handler = __malloc_alloc_oom_handler;if (0 == my_malloc_handler){__THROW_BAD_ALLOC;}(*my_malloc_handler)();//调用处理例程、企图释放释放内存result = realloc(p, n);//再次尝试配置内存if (result)return result;}}typedef __malloc_alloc_template malloc_alloc;void Out_Of_Memory()//测试{cout << "this is out of memory" << endl;// exit(1);}//测试int main(){__malloc_alloc_template::set_malloc_handler(Out_Of_Memory);int* p = (int*)__malloc_alloc_template::allocate(sizeof(int) * 536870911);return 0;}- 二级空间配置器
第二级空间配置器多了一些机制，避免太多小额区块造成的内存的碎片，小额区块带来的其实
不仅是内存碎片，配置时的额外负担也是一个大问题(cookie)，SGI第二级配置器的做法是，
如果区块够大，超过4096bytes时，就移交第一级配置器，否则就以内存池的方式管理：每次
配置一大块内存，并维护对应的自由链表，下次若再有相同大小的内存需求，就直接从free list
中拔出。如果请求端释放小额内存，就由配置器回收到free list中，为了方便管理，SGI第二级
配置器会主动将任何小额区块的内存需求量上调至8的倍数。
typedef __malloc_alloc_template malloc_alloc;enum { __ALIGN = 8 };//小区块的上调边界enum { __MAX_BYTES = 128 };//小型区块的上线enum { __NFREELISTS = __MAX_BYTES / __ALIGN };//自由链表个数templateclass __default_alloc_template{private://把ROUND_UP上调到8的倍数static size_t ROUND_UP(size_t bytes){return (((bytes)+__ALIGN - 1) & ~(__ALIGN - 1));}private:union obj//共用体{union obj* free_list_link;char client_data[1];};private://16个自由链表static obj* free_list[__NFREELISTS];//下面根据区块的大小，决定使用第n号free_list，n从1开始算static size_t FREELIST_INDEX(size_t bytes){return ((bytes)+__ALIGN - 1) / __ALIGN - 1;}//返回一个大小为n的对象，并可能加入大小为n的其他区块到 free liststatic void* refill(size_t n){int nobjs = 20;char* chunk = chunk_alloc(n, nobjs);obj** my_free_list;obj* result;char* current_obj, * next_obj;int i;if (1 == nobjs)return chunk;my_free_list = free_list + FREELIST_INDEX(n);result = (obj*)chunk;*my_free_list = next_obj = (obj*)(chunk + n);for (i = 1;; i++)//把free list各个节点串起来{current_obj = next_obj;next_obj = (obj*)((char*)next_obj + n);if (nobjs - 1 == i){current_obj->free_list_link = 0;break;}else{current_obj->free_list_link = next_obj;}}return result;}//配置一大块空间，可以容纳nogjs个大小为size的区块//内存池static char* chunk_alloc(size_t size, int& nobjs){char* result;size_t total_bytes = size * nobjs;//8*20size_t bytes_left = end_free - start_free;if (bytes_left >= total_bytes){//内存池剩余空间完全满足需求量result = start_free;start_free += total_bytes;return result;}else if (bytes_left >= size){//不完全满足，但够一个以上的区块nobjs = bytes_left / size;total_bytes = size * nobjs;result = start_free;start_free += total_bytes;return result;}else{//一个区块也无法提供//320size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);if (bytes_left > 0){obj** my_free_list = free_list + REFFLIST_INDEX(bytes_left);((obj*)start_free)->free_list_link = *my_free_list;*my_free_list = (obj*)start_free;}start_free = (char*)malloc(bytes_to_get);if (0 == start_free){int i;obj** my_free_list, * p;for (i = size; i free_list_link;start_free = (char*)p;end_free = start_free + i;return chunk_alloc(size, nobjs);}}end_free = 0;start_free = (char*)malloc_alloc::allocate(bytes_to_get);}heap_size += bytes_to_get;end_free = start_free + bytes_to_get;return (chunk_alloc(size, nobjs));}}static char* start_free;//内存池起始位置static char* end_free;//内存池结束位置static size_t heap_size;public://空间申请的接口//首先判断区块的大小，如果大于 128bytes –> 调用第一级配置器；//小于128bytes–> 就检查对应的 free_list（如果没有可用区块，就将区块上调至 8 倍数的边界，//然后调用 refill(), 为 free list 重新填充空间。static void* allocate(size_t n){obj** my_free_list;obj* result;if (n > (size_t)__MAX_BYTES)//如果>128 调用一级{return (malloc_alloc::allocate(n));}//寻找16个free list的适合的一个my_free_list = free_list + FREELIST_INDEX(n);result = *my_free_list;if (result == 0){//没有找到可用的，准备重新填充free listvoid* r = refill(ROUND_UP(n));return r;}*my_free_list = result->free_list_link;return result;}//释放空间static void deallocate(void* p, size_t n){obj* q = (obj*)p;obj* volatile* my_free_list;if (n > (size_t)__MAX_BYTES){malloc_alloc::deallocate(p, n);return;}}static void* reallocate(void* p, size_t old_sz, size_t new_sz);};templatechar* __default_alloc_template::start_free = 0;templatechar* __default_alloc_template::end_free = 0;templatesize_t __default_alloc_template::heap_size = 0;template__default_alloc_template::obj*__default_alloc_template::free_list[__NFREELISTS] = { 0,0,0,0,0,0 }推荐阅读：_herongweiV的博客-CSDN博客
二级空间配置器的原理剖析和简单实现_