空间配置器也是STL的六大组件之一，它主要服务于容器，用来提高效率

STL的容器用new来获取空间资源，而new的底层是调用operator new全局函数，operator new函数再去使用malloc函数来获取空间资源
那么在STL容器用new来获取空间资源的方式，就不如用空间配置器获取空间资源方式更高效

---

1、 什么是空间配置器

空间配置器，顾名思义就是为各个容器高效的管理空间(空间的申请与回收)的，在默默地工作。虽然在常规使用STL时，可能用不到它，但站在学习研究的角度，学习它的实现原理对我们有很大的帮助。

2、为什么需要空间配置器

前面在模拟实现vector、list、map、unordered_map等容器时，所有需要空间的地方都是通过new申请的，虽然代码可以正常运行，但是有以下不足之处：

空间申请与释放需要用户自己管理，容易造成内存泄漏
频繁向系统申请小块内存块，容易造成内存碎片
频繁向系统申请小块内存，影响程序运行效率
直接使用malloc与new进行申请，每块空间前有额外空间浪费 (malloc和new的时候,自动开辟了一块空间记录了本次malloc和new的大小,所以我们free和delete的时候不需要指名释放空间的大小)
申请空间失败怎么应对
代码结构比较混乱，代码复用率不高
未考虑线程安全问题

因此需要设计一块高效的内存管理机制

3、SGI-STL空间配置器实现原理

以上提到的几点不足之处，最主要还是：频繁向系统申请小块内存造成的。那什么才算是小块内存？SGI-STL以128作为小块内存与大块内存的分界线，将空间配置器其分为两级结构，一级空间配置器处理大块内存，二级空间配置器处理小块内存。

内存大于128使用一级空间配置器,直接调用malloc,失败抛异常;内存小于128使用二级空间配置器

3-1、一级空间配置器

一级空间配置器原理非常简单，直接对malloc与free进行了封装，失败了抛异常,增加了C++中set_new_handle思想

template <int inst>
class __malloc_alloc_template
{
private:
static void *oom_malloc(size_t);
public:
// 对malloc的封装
static void * allocate(size_t n)
{// 申请空间成功，直接返回，失败交由oom_malloc处理
void *result = malloc(n);
if (0 == result)result = oom_malloc(n);
return result;
}
// 对free的封装
static void deallocate(void *p, size_t /* n */)
{ free(p);}
// 模拟set_new_handle
// 该函数的参数为函数指针，返回值类型也为函数指针
// void (*    set_malloc_handler( void (*f)() ) )()
static void (* set_malloc_handler(void (*f)()))()
{
void (* old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = f;
return(old);
}
};
// malloc申请空间失败时代用该函数
template <int inst>
void * __malloc_alloc_template<inst>::oom_malloc(size_t n)
{
void (* my_malloc_handler)();
void *result;
for (;;)
{// 检测用户是否设置空间不足应对措施，如果没有设置，抛异常，模式new的方式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);
}
}
typedef __malloc_alloc_template<0> malloc_alloc;

3-2、二级空间配置器

二级空间配置器专门负责处理小于128字节的小块内存。如何才能提升小块内存的申请与释放的方式呢？SGI-STL采用了内存池的技术来提高申请空间的速度以及减少额外空间的浪费，采用哈希桶的方式来提高用户获取空间的速度与高效管理

STL容器申请空间小于128字节时,使用二级空间配置器,刚开始时,内存池也是没有空间的,所以是先malloc一块内存空间,然后给给内存池

3-2-1、内存池

内存池就是：先申请一块比较大的内存块已做备用，当需要内存时，直接到内存池中去去，当池中空间不够时，再向内存中去取，当用户不用时，直接还回内存池即可。避免了频繁向系统申请小块内存所造成的效率低、内存碎片以及额外浪费的问题

这里的内存池很简单,提前就有一块内存空间,用两个指针管理,专门给STL容器且小于128字节需求服务

请大家思考一下几个问题：

1. 当用户需要空间时，能否直接从内存池中大块空间中直接截取？为什么？
2. 对用户归还的空间能否直接拼接在大块内存前？
3. 对用户归还的空间如何进行管理？
4. 不断切割会有什么后果？

问题

问题1:我们申请空间很容易,但是使用结束,释放空间怎么释放呢,怎么还给内存池呢?(1,2,3…多块空间,按顺序被申请出去,有可能我3号空间被释放还给内存池,2号空间还在使用…)
问题2:我们可以采用链表等方法将每次释放的空间链起来.但是,内存池是可以被重复使用的,我们STL容器需求的空间不一样,下次需求来了之后要遍历链表找到对应大小的内存池空间块太麻烦了

所以,我们的二级空间配置器除了有内存池以外,还要有用来管理内存池的方法----哈希桶

3-2-2、哈希桶

SGI-STL中的二级空间配置器使用了内存池技术，但没有采用链表的方式对用户已经归还的空间进行管理(因为用户申请空间时在查找合适的小块内存时效率比较低)，而是采用了哈希桶的方式进行管理。那是否需要128桶个空间来管理用户已经归还的内存块呢？答案是不需要，因为用户申请的空间基本都是4的整数倍，其他大小的空间几乎很少用到。因此：SGI-STL将用户申请的内存块向上对齐到了8的整数倍

小于128字节使用二级空间配置器,要使用到我们的哈希桶,但是哈希桶开128个空间不太现实,太浪费了,所以哈希桶采用了一种方法----8字节对齐

只是浪费了不到8个字节

所以我们后续再要16字节空间的时候,就不去内存池了,而是直接由对应的哈希桶给一块链接的空间,然后对哈希桶下面的链表进行头删就行!

优势

当我们STL容器释放资源的时候,STL要给给二级空间配置器本次的申请空间大小,然后在哈希桶找到对应的桶号,进行头插!,这样就将拿走的空间给挂回原文中了!

优势1 : 所以!当我们哈希桶的下面挂着空间的时候,STL使用二级空间配置器申请释放空间就是对单链表进行头插头删----效率就是O(1)
优势2 : 使用哈希桶,当STL容器申请空间需求来的时候,可以非常高效的找到对应的桶,然后拿到空间资源

当我们有了新的申请资源需求时候,哈希桶对应的桶进行头删,链接到第二个空间,把第一个空间给给需求,这个时候第一个空间所有的空间资源(包括前8个字节)STL容器都能使用,就不需要前4/8个字节的地址了 当STL释放空间的时候,哈希桶头插第一个空间,然后再将第一个空间的前4/8个字节存放第二个空间的地址

所以,不用4字节对齐作为哈希桶构建是因为64位平台下面,指针大小是8个字节,4字节存不下指针!

机制

当我们对应的桶下面没有空间了,内存池也没有空间了,malloc也失败了,这个时候对应桶去内存更大的桶进行查看,看看有没有多余的更大桶的下面有没有空间,如果有就将大空间切割成为两份分别链在对应的桶号下面

所以!每个桶按8字节对齐,就使得每个桶下面链接的空间可以被切割为1个/2个/多个空间,然后这些切割空间分别链接到对应桶的下面
并且,只要我们的需求是在对应桶的空间范围内(比如12字节,13字节,16字节),都是可以重复用1号桶下面的空间的

总之8字节对齐来构建哈希桶好处非常多

4、内存碎片问题

内存碎片：内存碎片化了，不能很好高效的利用
内存碎片问题又分为内碎片和==外碎片=问题=

1、内碎片问题

内存挂起来管理，按一定规则对齐，就会导致内碎片问题

内碎片问题不是太严重——因为虽然我给了你16个字节，但是你使用完了就会把16字节全部还回来，不存在多余的4字节不释放
2、外碎片问题

频繁向系统申请小块内存就会导致外碎片问题

小结

1、空间配置器适用于频繁的申请小块内存
2、效率高，时间为O(1)，哈希桶下面挂着内存，在哈希桶查找对应字节的时间平均为O(1)（不用像new一样一直调用malloc）
3、一定程度缓解了内存碎片的问题
4、一个进程中,只有一个空间配置器,并且空间配置器里面的数据全是静态的,存在静态区中.非常类似与单例模式,只有一份

5、STL容器使用空间配置器

#6、 结论

仿函数可以控制容器与算法的一些规则
容器适配器：通过将一种不同类型的容器转换成为另一种类型的容器的功能，从而体现了代码复用的思想