STL——空间配置器

空间配置器是STL六大组件之一，它和其他五个组件相互配合，起着很关键的作用。

• 容器：各种数据结构、如vector、list、stack、deque、queue、set、map、unordered_map等等
• 算法：各种算法，如sort、serach、copy、erase 提供了对容器的增删查改等等
• 迭代器：迭代器通常用于遍历容器元素的时候，扮演者容器和算法之间的胶合剂，它封装了底层实现的细节、给用户提供了统一的接口去调用，极大的降低了成本。
• 适配器：stack/queue/priority_queue中就有涉及到适配器，它们的默认配接的就是deque，像map和list中的反向迭代器也是适配器
• 仿函数：是实现了operator()的类，这个类对象可以像函数一样去使用
• 空间配置器：顾名思义，空间配置器就是给各个容器高效的管理空间的。

其实看源码的时候，其中alloc就是空间配置器，有了它就可以解决一下几个问题

• 频繁的像系统申请小块的内存，这样容易造成内存碎片
• 如果直接使用malloc new，内存就可能有浪费
• 申请空间失败
• 在多线程中，线程不安全的问题...

SGI-STL空间配置器中，主要是解决了频繁的像系统申请小块内存

在SGI版本中，是以128为小块空间的边界，将大于128的称之为一级空间配置器，小于128的称为二级空间配置器

一级空间配置器（__malloc_alloc_template）

一级空间配置器其实就是对malloc和free的封装，并增加了C++中set_new_handle思想

如果申请成功了就直接返回，失败就交给oom_malloc处理，其中for里面就是检测用户是否设置了空间不足的应对措施，如果没有设置，抛异常模式为new方式

deallocate就是对free的封装

二级空间配置器（__default_alloc_template）

二级空间配置器专门负载处理小于128字节的小内存块，在SGI版本中采用了内存池的方式去申请空间和释放空间。

其中有以下四个成员函数，之所以定义为static，是因为所有容器都是向同一块内存池中申请和释放的，所以是共享的同一块空间。

可以发现SGI采用了哈希桶的方式提高用户获取空间的速度与高校管理。

内存池：会先申请一块大的内存作为备用，当需要的内存小于128的时候，就会直接向哈希桶里面申请内存和释放内存，这样就避免了频繁的向系统申请小内存所造成的内存效率低，内存碎片的问题

SGI版本中内存池技术其实并没有以链表的方式对用户已经归还的空间进行管理，因为用户申请内存的时候在查找方面其效率比较低，所以采用了哈希桶的方式。在查找方面平均就做到了O（1）。但其实SGI中并没有用到128个桶，它用到的是8 16 24...，8的倍数。

那么这时候就有一个疑问：

用户申请的空间通常是4的倍数，为什么要内存对齐到8呢？

我们设想这样一个场景，如果我们申请40字节的空间，但是二级空间配置器没有了，malloc也失败了，那么它就会像下一个有空间的内存，比如64字节来用，将64字节分为40和24，分别挂到哈希桶中。  这也是为什么要对齐到8的一个优势

template <bool threads, int inst>
class __default_alloc_template {

private:
    enum {__ALIGN = 8}; //如果用户需要的内存不是8，对齐到8
    enum {__MAX_BYTES = 128}; //内存块的边界
    enum {__NFREELISTS = __MAX_BYTES/__ALIGN}; //采用哈希桶保存小块内存映射时桶的个数

   //如果用户所需要的每次块不是8的倍数，对齐到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];    /* The client sees this.        */
  };
private:
# ifdef __SUNPRO_CC
    static obj * __VOLATILE free_list[]; 

    static obj * __VOLATILE free_list[__NFREELISTS]; 
    //哈希函数，根据用户提供的字节数找到对应的桶号
  static  size_t FREELIST_INDEX(size_t bytes) {
        return (((bytes) + __ALIGN-1)/__ALIGN - 1);
  }
    
  static void *refill(size_t n);
  static char *chunk_alloc(size_t size, int &nobjs);

 //start_free和end_free用来标记内存池中大块内存的起始和末尾
  static char *start_free;
  static char *end_free;
    //用来记录该空间配置器已经向系统索要了多少的内存
  static size_t heap_size;

二级空间配置器的逻辑如下

可以看到耳机空间配置器申请空间的时候，会根据空间是否大于128来进行划分，如果小于128字节，那么就会根据申请字节找到对应的哈希桶中去申请内存，如果没有就向内存池中申请内存。

static void * allocate(size_t n)
{
    obj * __VOLATILE * my_free_list;
    obj * __RESTRICT result;
    // 检测用户所需空间释放超过128(即是否为小块内存)
    if (n > (size_t) __MAX_BYTES) 
   {
        // 不是小块内存交由一级空间配置器处理
        return (malloc_alloc::allocate(n));
   }
    
    // 根据用户所需字节找到对应的桶号
    my_free_list = free_list + FREELIST_INDEX(n);
    result = *my_free_list;
    
    // 如果该桶中没有内存块时，向该桶中补充空间
    if (result == 0)
   {
        // 将n向上对齐到8的整数被，保证向桶中补充内存块时，内存块一定是8的整数倍
        void *r = refill(ROUND_UP(n));
        return r;
   }
    
    // 维护桶中剩余内存块的链式关系
    *my_free_list = result -> free_list_link;
    return (result);
};

可以看到refill函数中，当哈希桶中没有了内存块的时候，这时候就需要向哈希桶中补充内存。我们会向内存池中一次性申请20个n字节的小内存，这时有两个策略

1）、如果我们只要了一块，那么我们就直接给用户。

2）、剩余的内存挂到哈希桶中

template <int inst>
void* __default_alloc_template<inst>::refill(size_t n)
{
    // 一次性向内存池索要20个n字节的小块内存
    int nobjs = 20;
    char * chunk = chunk_alloc(n, nobjs);
    
    obj ** my_free_list;
    obj *result;
    obj *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++) 
     {
        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);
}

二级空间配置器的回收

可以看到如果空间没有大于128，那么就会去找到对应的哈希桶中，将内存挂到对应的下标中。

static void deallocate(void *p, size_t n)
{
obj *q = (obj *)p;
obj ** my_free_list;
// 如果空间不是小块内存，交给一级空间配置器回收
if (n > (size_t) __MAX_BYTES)
 {
     malloc_alloc::deallocate(p, n);
     return;
 }
// 找到对应的哈希桶，将内存挂在哈希桶中
my_free_list = free_list + FREELIST_INDEX(n);
q -> free_list_link = *my_free_list;
*my_free_list = q;
}

最后：空间配置器是将容器结合起来的，所有STL中的容器共用一份空间配置器，都可以采用这样的方式来申请内存，所以也可以理解为什么空间配置器都是静态的。