一、空间配置器概念

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

二、空间配置器的作用

若实现各种STL容器时，所有需要空间的地方都使用new申请，虽然也可以完成基本的功能，但是会存在一些缺点:

1. 空间申请与释放需要使用者自行管理，容易造成内存泄漏

2. 频繁向系统申请小块内存块，容易造成内存碎片

3. 频繁向系统申请小块内存，影响程序运行效率

4. 直接使用malloc与new进行申请，每块空间前有额外空间浪费

5. 申请空间失败时的应对方式不够合理

5. 代码结构比较混乱，代码复用率不高

6. 未考虑线程安全问题

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

三、内存池技术

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

四、空间配置器的实现原理

3.1 流程概述

使用空间配置器申请空间时，首先直接向二级空间配置器发起请求，请求的空间大于128byte则交由一级空间配置器处理,否则二级空间配置器进行处理。

一级空间配置器适合为容器申请较大的空间，如vector、unordered_map等连续空间的容器。

二级空间配置器适合频繁申请小块内存时使用，如list等容器。

3.2 一级空间配置器

一级空间配置器实现原理较为简单，本质上是直接对malloc与free进行了封装

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;
  }
  static void deallocate(void* p, size_t /* n */)// 对free的封装
  {
    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);
  }
};
template <int inst>
void* __malloc_alloc_template<inst>::oom_malloc(size_t n)// malloc申请空间失败时代用该函数
{
  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.3 二级空间配置器

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

3.3.1 二级空间配置器设计

当用户向二级空间配置器发送第一次申请前，二级空间配置器中并没有我们需要的空间。发出第一次申请后才会一次性申请一块足够大的内存空间(使用两个指针进行维护)。之后我们需要空间时，在这块空间切割即可。可以认为这两个指针维护的即为狭义的内存池。

static char *start_free;
static char *end_free;

但是释放空间的顺序不一定刚好与开辟空间的顺序相反，我们又没有记录每块切割的内存空间的位置，那该如何归还空间呢？

这时就需要用到哈希桶技术

但是并不需要128个桶来进行管理，而是选用1~128之间的所有8的倍数作为key，共有15个桶。

当需申请小块空间时，先将所需空间的大小向上对齐到8的倍数得到一个key，再在该key所对应的桶中查找是否存在内存块。有则将第一块返回给用户；没有则向桶中填充多块内存块(确保之后申请时有内存块)，再将第一块返回给用户。

当狭义内存池中空间不足时，会malloc向堆区申请空间。若malloc失败(即已经没有空间)，这时会向key值更大的桶中寻找是否有内存块(可能之前申请了)。若后面的桶中也没有可用的内存块，则会向一级空间配置器寻求帮助了。

为什么没有采用链表的方式对用户已经归还的空间进行管理？

使用链表的话，用户申请空间时在查找合适的小块内存时效率较低。采用哈希桶更加高效。

每个桶中的内存块是如何连接的呢？

当内存块不使用时，每个内存块前会使用一个指针大小的内存来存储下一个内存块的地址。采用联合体的方式实现。

union obj {
        union obj * free_list_link;
        char client_data[1];    /* The client sees this.        */
  };

为什么key选用8的倍数？

在64位环境下指针的大小为8字节，保证最小的内存块都至少可以存下一个指针。(保证32位、64位系统都可以使用)

可能用户申请的空间并不是8的整数倍，切割的内存块大小会向上对齐到8的整数倍。比如：申请5字节空间，会切割8字节的空间。

注意：

一个进程中只会有一个空间配置器，进程中所有容器需要的空间都到对应空间配置器申请。进程终止，对应空间配置器释放。可以采用单例模式进行实现。

3.3.2 内存碎片问题

内存碎片问题大致可以分为内碎片和外碎片。

外碎片问题

内碎片问题

即实际分配内存数比需要的内存数多，导致空间浪费。二级配置器切割内存块向上对齐8的整数倍，就造成了内碎片问题。