【C++】STL空间配置器

一、什么是空间配置器

STL 有六大组件分别是：容器，算法，迭代器， 空间配置器，适配器，仿函数。

在我们日常使用STL中的容器时，我们是几乎感受不到空间配置器的存在，因为他一直在默默工作，整个STL的操作对象都存放在容器之中，而容器需要配置内存空间的，这个内存空间的配置就是空间配置器的作用：为各个容器进行高效的内存管理(内存的申请与回收)的。

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

对于STL中的容器在申请内存时当然可以选择new，malloc 来进行内存的申请，但是有以下不足之处：

• 空间申请与释放需要用户自己管理，容易造成内存泄漏
• 频繁向系统申请小块内存块，容易造成内存碎片，而且影响程序运行效率
• 直接使用malloc与new进行申请，每块空间前有额外空间浪费
• 代码结构比较混乱，代码复用率不高

因此STL需要设计一块高效的内存管理机制，于是就有了空间配置器，空间配置器是专门针对STL设计的一个小型内存池。

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

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

• 一级空间配置器处理大块内存。
• 二级空间配置器处理小块内存。

下面是空间配置器的宏观结构，我们在后面会一点一点丰富该结构：

1、 一级空间配置器

一级空间配置器原理非常简单，直接对maloc，free，realloc等C函数进行封装，并增加了C++中set_new_handle思想，形成了allocate、deallocate、reallocate 等函数用于来用于内存分配。

• set_new_handler 是 C++ 中的一种机制，用于在内存分配失败时指定一个处理函数。这个处理函数可以尝试释放一些资源，以便内存分配操作能够成功，或者采取其他适当的措施。
  
• 当使用 new 运算符分配内存时，如果内存分配失败，默认情况下会抛出 std::bad_alloc 异常。然而，通过 std::set_new_handler 函数，你可以指定一个自定义的处理函数，当内存分配失败时，这个处理函数会被调用。

一级空间配置器中大致过程是：

1. 直接allocate分配内存，其实就是malloc来分配内存，成功则直接返回，失败就调用处理函数。
2. 如果用户自定义了内存分配失败的处理函数就调用，没有的话就抛出一个异常
3. 如果自定义了处理函数就进行处理，处理以后再继续尝试分配内存。

以下是一级空间配置器的核心部分的源码：

2、二级空间配置器

二级空间配置器专门负责处理小于128字节的小块内存，如何才能提升小块内存的申请与释放的方式呢？

1. SGI-STL采用了内存池的技术来提高申请空间的速度以及减少额外空间的浪费。
2. 采用哈希桶的方式来管理从内存池中申请的空间，来提高用户获取空间的速度与高效管理。

• 内存池
  内存池就是：先申请一块比较大的内存块已做备用，当需要内存时，直接到内存池中去取，当池中空间不够时，再向内存中去取，当用户不用时，直接还回内存池即可。避免了频繁向系统申请小块内存所造成的效率低、内存碎片以及额外浪费的问题。
  
• SGI-STL中二级空间配置器设计
  二级空间配置器的设计是采用了哈希桶的方式来管理从内存池中得到的内存，其中桶的哈希值都是8的整数倍，SGI-STL将用户申请的内存块向上对齐到了8的整数倍。

问题： 内存块为什么必须要以8位单位呢，为什么不把1作为单位？

因为用户申请的空间基本都是4的整数倍，其他大小的空间几乎很少用到，还有就是由于了空间配置器中的内存块是像链表一样连接起来的，这样就必然需要指针来维护， 32位平台下指针4字节，64位平台下指针8字节，所以内存块最小的节点也要能存放一个指针。

1. 二级空间配置器内部维护16条自由链表，分别是0-15号链表，最小8字节，以8字节逐渐递增，最大128字节，当你传入一个字节参数，表示你需要多大的内存时，在二级空间配置器内部会自动帮你对齐到第几号链表(如需要12bytes空间，二级空间配置器会分配16bytes大小)

2. 在找到对应的哈希桶以后，二级空间配置器会先查看链表是否为空，如果不为空，直接从对应的free_list中取出内存节点，然后哈希桶的指针指向下一个节点。

3. 如果哈希桶对应的free_list为空，先看其内存池是不是空时，如果内存池不为空：

   • 先检验它剩余空间是否够20个节点大小($即所需内存大小提升后的大小\times 20$)，若足够则直接从内存池中拿出20个节点大小空间，将其中一个分配给用户使用，另外19个当作自由链表中的区块挂在相应的free_list下，这样下次再有相同大小的内存需求时，可直接取出。
   • 如果不够20个节点大小，则看它是否能满足1个节点大小，如果够的话则直接拿出一个分配给用户，然后从剩余的空间中分配尽可能多的节点挂在相应的free_list中。
   • 如果连一个节点内存都不能满足的话，则先将内存池中剩余的空间挂在相应的free_list中，然后再给内存池申请内存。

4. 内存池为空时，此时二级空间配置器会使用maloc从堆上申请内存，(一次所申请的内存大小为：$2\ast 提升后所需节点内存大小\ast 20+一段额外空间$)，一共申请40块，一半拿来用，一半放内存池中等待备用。

5. 如果二级空间配置器malloc没有成功，说明heap上没有足够空间分配给我们了，此时，二级空间配置器会从比所需节点空间大的free_list中一 一搜索，从比它所需节点空间大的free_list中拔除一个节点来使用，如果这也没找到，说明比其大的free_list中都没有自由区块了，那就要调用一级空间配置器了（因为一级空间配置器内部可能设置的有内存分配失败的处理函数，通过该处理函数可能能够得到内存），如果第一级配置器的 malloc() 也失败了，就发出 bad_alloc 异常。

• 释放时调用deallocate函数，若释放的n>128，则调用一级空间配置器，否则就直接将内存块挂上自由链表的合适位置。

四、优缺点分析

STL二级空间配置器虽然解决了外部碎片与提高了效率，但它同时增加了一些缺点:

1. 因为自由链表的管理问题，它会把我们需求的内存块自动提升为8的倍数，这时若你需要1个字节，它会给你8个字节，即浪费了7个字节，所以它又引入了内部碎片的问题，若相似情况出现很多次，就会造成很多内部碎片，降低了内存的利用率。
2. 二级空间配置器是在堆上申请大块的狭义内存池，然后用自由链表管理，供STL容器进行使用，在程序执行过程中，它将申请的内存一块一块都挂在自由链表上，即不会还给操作系统，并目它的实现中所有成员全是静态的（为了让空间配置器在整个进程中自由一个实例），所以它申请的所有内存只有在进程结束才会释放内存，还给操作系统，由此带来的问题有：
   • 如果不断的开辟小块内存，最后会导致整个堆上的空间都被挂在自由链表上，此时如果想开辟大块内存就会失败。
   • 若自由链表上持很多内存块没有被使用，当前进程的空间配置器又占着内存不能释放，这时其它的进程申请不到空间，也不可以使用当前进程的空闲内存，由此就会引发多种问题。

在gcc 4.9之后对于STL空间配置器就没有一级了，只有第二级。