参考《STL源码剖析-侯捷》一书 (SGI版本STL)

前置

六大组件

空间配置器实现

SGI版本的空间配置器有两个，一个名为allocator，一个名为alloc。前者符合部分标准，但效率不好，只是对operator new和operator delete进行了封装，没有做过多的处理。
而普通的内存申请方式会导致几个问题：

  1. 内存碎片的问题
    首先对于内存碎片的问题，很好理解。use代表已经分配了的内存，free代表空闲空间。此时如果用户要求分配4kb的内存，会发现找不到满足条件的内存块，尽管总体剩下了5kb，但是他们不是连续的
  2. 效率问题
    假设用户当前需要1kb，那么OS就给用户1kb，然后待会又想要1kb，OS又得跑去分配1kb的大小空间给用户，这样就很头疼了。主要是因为，每一次系统分配空间是需要从用户态转变为内核态的，因为每一次分配空间都需要触发缺页中断(具体内容见内存管理之虚拟内存)
  3. 直接使用malloc与new进行申请，每块空间前有额外空间浪费，具体看Glibc之malloc实现原理
  4. 如果申请失败没有处理方案等等问题

所以，为了解决上述问题，STL采取了使用alloc来为容器管理空间。

具体实现思想

只贴少量代码，具体代码看侯捷老师的书，结合SGI版本的源码看，这里主要理清楚思想

首先，alloc主要分为两级空间配置器

一级空间配置器(__malloc_alloc_template)

思路非常简单，大于128字节的内存申请，使用一级空间配置器。其内部使用malloc()和free()两个C式接口完成内存开辟与释放。
开辟内存失败，仿写了C++中的set_new_handle()，即自定义自己的out-of-memory handler。这个handle是函数指针，作为回调函数的方式使用，当要求内存配置需求无法被系统满足时，在抛出bad_alloc异常之前，调用一个你指定的函数，也就是该handle指针指向的函数。

在当前SGI的处理中，如果内存申请失败，malloc返回NULL，则会进入OOM_malloc函数，也就是out_of_memory时的处理函数，该函数不断内循环以期成功获取内存，但如果没有自定义的内存获取失败处理函数也就是没有new_handle的话，就直接抛异常。

template <int inst>//该非类型参数没派上用场，所以在代码的最后一行，直接传了0class __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;

二级空间配置器(__default_alloc_template)

小额区块带来的不仅是内存碎片，配置时的额外负担也是一个大问题，额外负担永远无法避免，但是区块越小，额外负担所占的比例就越大，愈显得浪费——《STL源码剖析》

二级空间配置器的实现要比一级空间配置器复杂得多。
之所以采用小于等于128字节大小的空间使用二级空间配置器，是因为SGI对于小块内存的定义为小于128字节。为了降低小块内存频繁申请的问题，故采用二级空间配置器。
其内部最主要的实现思路就是内存池。另：alloc默认采用二级空间配置器的模式进行内存分配。
在内存池中，采用哈希桶的方式来提高用户获取空间的速度与高效管理。

哈希桶：

当用户所需内存不满足哈希桶内的8的倍数的内存大小时，SGI二级空间配置器将会将内存需求量上调至8的倍数。
其中，每一个区块的节点如下方代码中union obj来维护，第一个字段用来指向下一个相同大小的区块的指针，第二个字段用来指向自己，因此通过使用union的方式来节省维护链表的空间；
分配策略如下：

enum { __ALIGN = 8 }; // 如果用户所需内存不是8的整数倍，向上对齐到8的整数倍enum { __MAX_BYTES = 128 }; // 大小内存块的分界线enum { __NFREELISTS = __MAX_BYTES / __ALIGN }; // 采用哈希桶保存小块内存时所需桶的个数template <bool threads, int inst>//第一参数是多线程环境下使用的，不做讨论，太复杂，第二参数没排上用场class __default_alloc_template{private:// 如果用户所需内存块不是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];};private:static obj* free_list[__NFREELISTS];// 哈希函数，根据用户提供字节数找到对应的桶号static size_t FREELIST_INDEX(size_t bytes){return (((bytes)+__ALIGN - 1) / __ALIGN - 1);}static void*refill(size_t n);// start_free与end_free用来标记内存池中大块内存的起始与末尾位置static char* start_free;static char* end_free;// 用来记录该空间配置器已经想系统索要了多少的内存块static size_t heap_size;public://在下面的代码块中展示，就不放在一起了static void* allocate(size_t n);static void deallocate(void* p, size_t n);static void* reallocate(void* p,size_t old_sz,size_t new_sz);};
// 函数功能：向空间配置器索要空间// 参数n: 用户所需空间字节数// 返回值：返回空间的首地址//该函数是空间配置器的标准接口函数->allocatestatic 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);};static void* deallocate(void* p, size_t n);//头插到哈希桶，具体不展示了，不然太长了。可以查看相关源码

allocate发现 free list 中没有可用区块了时
就调用 refill()，准备为 free list 重新填空间。新的空间将由内存池(经chunk alloc()完成)。默认取得20 个新节点(新区块)，但万一内存池空间不足，获得的节点数 (区块数)可能小于 20。
refill流程图：

refill代码：

template <int inst>char *__default_alloc_template<inst>::chunk_alloc(size_t size, int & nobjs){// 计算nobjs个size字节内存块的总大小以及内存池中剩余空间总大小char *result;size_t total_bytes = size * nobjs;size_t bytes_left = end_free - start_free;// 如果内存池可以提供total_bytes字节，返回if (bytes_left >= total_bytes){result = start_free;start_free += total_bytes;return (result);}else if (bytes_left >= size){ // nobjs块无法提供，但是至少可以提供1块size字节内存块，提供后返回nobjs = bytes_left / size;total_bytes = size * nobjs;result = start_free;start_free += total_bytes;return (result);}else{// 内存池空间不足，连一块小块内存都不能提供// 向系统堆求助，往内存池中补充空间// 计算向内存中补充空间大小：本次空间总大小两倍 + 向系统申请总大小/16size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);// 如果内存池有剩余空间(该空间一定是8的整数倍)，将该空间挂到对应哈希桶中if (bytes_left > 0){// 找对用哈希桶，将剩余空间挂在其上obj **my_free_list = free_list + FREELIST_INDEX(bytes_left);((obj *)start_free)->free_list_link = *my_free_list;*my_ree_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 <= __MAX_BYTES; i += __ALIGN){my_free_list = free_list + FREELIST_INDEX(i);p = *my_free_list;// 如果有，将该内存块补充进内存池，递归继续分配if (0 != p){*my_free_list = p->free_list_link;start_free = (char *)p;end_free = start_free + i;return (chunk_alloc(size, nobjs));}}// 山穷水尽，只能向一级空间配置器求助// 注意：此处一定要将end_free置空，因为一级空间配置器一旦抛异常就会出问题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));}}

上述的 chunk_alloc() 函数以 end_free – start_free 来判断内存池的剩余容量。如果剩余容量充足，就直接调出 20 个块返给free list。如果剩余容量不足以提供 20个区块，但还足够供应一个以上的区块，就拨出这不足 20 个区块的空间出去。这时候其 nobjs 参数将被修改为实际能够供应的区块数，如果内存池连1个区块空间都无法供应，此时便利用 malloc()从 heap 中配置内存，为内存池分配更多空间以应付需求。新容量的大小为需求量的两倍，再加上一个随着配置次数增加而愈来愈大的附加量。

  • 举个例子，假设调用 chunk_alloc(32，20)(即需要20个32字节的区块)，于是 malloc() 配置 40 个 32 bytes 区块，其中第1个交出，另19 个交给 free_list[3]维护，余20个留给内存池。

  • 调用chunk_alloc(64,20)，此时 free list对应桶没有足够对应区块，必须向内存池要求支持。
    内存池只够供应10个64 bytes 区块，就把这10个区块返回，第1个交给用户，余 9个由 free lst[7] 维护。此时内存池全空。接下来再调用

  • 调用chunk_alloc(96，20），此时 free_list对应桶空空如也，必须问内存池要求文持
    而内存池此时也是空的，于是以 malloc()配置40+n (附加量)个96 bytes 区块，其中第1个交出，另19 个交给 free list[11] 维护，余 20+n (附加量)个区块，留给内存池

以上差不多就是SGI空间配置器的基本原理，想看详细分析的参见《STL源码剖析》。