SGI stl中容器默认使用的空间配置器是alloc。
空间:可以存储数据的地方，可以是内存，磁盘，甚至设备等，能读写就行
内存:字面意思
空间配置器分两种:一级配置器(__malloc_alloc_template)和二级配置器(__default_alloc_template)。当请求的空间大于128byte时使用一级配置器，小于128byte时则使用二级配置器。
一级配置器底层是对malloc和free的简单封装。
二级配置器维护一个内存池和空闲链表，当内存池的内存不足以满足需求时将使用malloc分配内存。
为什么使用二级配置器？
我们知道二级配置器的使用场景是需要小块内存时。如果直接向系统申请小块内存的话，由于操作系统在管理和回收内存时需要知道内存的长度等信息，而对于c++用户而言需要的是一段内存的起始地址而包含任何头部信息。所以系统在分配内存时将多分配一段用以保存长度信息的内存，然后将剩余的内存返回给用户。也就是说用户申请n bytes,假如操作系统用一个struct __head_t保存信息，则需要在空闲列表中寻找一块长度大于等于(n+sizeof(__head_t))的内存，假如这段内存起始于p,则将长度自己及下一节点等信息放在(_head_t*)p中，然后返回(void*)(p+sizeof(__head_t))给用户，如果我们申请的小块内存越多则花费也更多，除此之外也将完成更多内存碎片。
而二级配置器维护十六个不同区块大小的空闲链表，这些链表节点都来源于配置器一次性申请的一大片内存里面，当内存不足时也将按照所需要内存的2倍进行申请，这将减少系统分配的花销。
一级配置器
一级配置器(__malloc_alloc_template)提供的allocate和deallocate是对malloc()函数，realloc()函数和free()函数的简单封装。除此之外它的内部还拥有一组用于处理申请内存时碰到oom情况的函数指针，并提供set_new_handler接口来达成类似c++ set-new-handler的效果。
二级配置器
二级配置器(__default_alloc_template)主要由两个部分组成:空闲链表和内存池。
空闲链表
空闲链表的部分是一个16个元素的数组，每个元素就是一个空闲链表。每个链表用来保存不同大小的空闲区块，分别是8,16,24,32,40,....,128。空闲链表每个节点要保存下一个节点的信息，为了节省空间这里使用这样一种类型来作为节点:
union obj
{
obj * free_list_link;
char data[1];
};
原理是，当区块被使用时，假如链表头为free_list,则可以将它的data字段保存，将free_list赋值为free_list->free_list_link，返回保存的data即可。
区块回收时将回收的内存当成obj指针看待，将其free_list_link赋值为当前free_list,再将其赋值给free_list即可。
整个过程实际上是出栈入栈
内存池
内存池使用两个指针表示开始和结束，当前剩下的大小可以用指针相减计算出来。
内存池用于当链表区块不足时添加新的区块，也就是直接"回收"进去。空闲链表在申请空间时通常使用SxN的形式，也就是N和S大小的块。内存池对于这些请求，分三种情况处理:
剩余空间大于等于SxN,直接返回给空闲链表。
不足SxN，但是大于等于SxM,1≤M<N。这种情况下将返回SxM的空间，并通过N的引用传回实际大小。
不足N。这个情况下，首先检查自身剩下的空间，将它填充到合适的空闲链表。然后用malloc分配新的内存，大小是当前请求的两倍，然后调用自己。如果malloc分配失败，意味着系统内存也不足，则通过遍历空闲链表来寻找空闲的，足够大的块返回给空闲链表。比如申请8x2，内存池为0了，而空闲链表(区块大小为64)还有没用的块，也可以拿来使用。如果也没，就直接调用一级配置器，触发异常，兴许系统会整理内存，然后就有了。
这一整个就是stl中空间配置器alloc的行为了。
网友评论