目录

1.什么是空间配置器

2.为什么需要空间配置器

3.SGI-STL空间配置器实现原理

3.1一级空间配置器

3.2二级空间配置器

3.2.1内存池

3.2.2 SGI-STL中二级空间配置器设计

3.3 空间配置器的默认选择

4.空间配置器与容器的结合

---

1.什么是空间配置器

空间配置器，顾名思义就是为各个容器高效的管理空间(空间的申请与回收)的配置器，在默默地工作。下图是空间配置器、malloc的关系图：

空间配置器相当于是小灶，malloc是大食堂。空间配置器会为各个容器管理内存空间，即各个容器不需要去malloc那里拿内存空间。

2. 为什么需要空间配置器

在前面的博文中，我写了vector、list等等的容器的实现，在需要空间的地方都是通过new申请的，虽然在代码完成之后，代码可以正常运行，但是对于其中的内存空间，有以下不足：

①空间申请与释放需要用户自己管理，容易造成内存泄漏。

 

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

 

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

 

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

 

⑤申请空间失败怎么应对。

  

⑥代码结构比较混乱，代码复用率不高。

 

⑦未考虑线程安全问题。

对于这些问题，C++为容器设计了一块高效的内存管理机制----空间配置器。

3.SGI-STL空间配置器的实现原理

以上提到的几点不足之处，最主要还是：频繁向系统申请小块内存造成的。那什么才算是小块内
存？SGI-STL以128字节作为小块内存与大块内存的分界线，将空间配置器其分为两级结构，一级空间配置器处理大块内存，二级空间配置器处理小块内存。即申请的空间大小大于128字节，那么就使用一级空间配置器，小于等于128字节就使用二级空间配置器。

 3.1一级空间配置器

一级空间配置器原理非常简单，直接对malloc与free进行了封装，并增加了C++中set_new_handle思想。一级空间配置器在申请空间的时候，如果失败了会直接抛异常。

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;}// 对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;

3.2 二级空间配置器

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

3.2.1内存池

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

在源码中，是由两个指针指向一块空间，这块空间便是内存池，它是二级配置器向malloc申请出来的。

3.2.2 SGI-STL中二级空间配置器设计

SGI-STL中的二级空间配置器使用了内存池技术，并且为了更方便更好的管理内存，二级空间配置器采用了哈希桶的方式。具体流程是这样的：

当需要申请128字节以内的内存的时候，二级空间配置器就会从内存池中拿到若干块内存，这个内存的大小为8的整数倍。然后分配给需要的地方，当使用完后，归还内存并不是直接归还到内存池中，而是使用哈希桶将内存块链接起来，方便后续的使用！

举个例子：我申请12字节大小的空间若干个，那么二级配置器就会从哈希桶中拿过来，但是如果此时的哈希桶是空的，那么就会去内存池中申请，如果内存池也是空的，内存池会去malloc申请一大块，然后内存池截取诺干个16个字节的内存块分配给用户，剩下的若干个链接到哈希桶中，因为内存池一般会截取几个内存块出来。

然后当用户使用完后，就会将这些内存块重新链接到哈希桶中。

那么为什么内存块都是8的整数倍呢？

当内存池已经空了，但是我需要申请一块空间，大小为16字节的。但是在哈希桶中，没有16字节的内存块，但是内存池已经空了，此时二级空间配置器不会放弃任何给你内存的希望，它会从后面的空闲着的内存块截取16字节拿过来！然剩下的字节的内存块也会被链接到前面对应字节数的桶中。

比如我需要16字节，但是发现哈希桶里没有，于是我拿24字节的，截取了16字节，还剩下8字节，这八字节就会被链接在8字节的桶中！这就是为什么要8的整数倍，因为可以在内存池空了的情况下，通过截取更大字节的内存块来分配给需要较小字节内存块的用户，然后可以将剩下的字节内存块链接去更小的桶中。

3.3 空间配置器的默认选择

GI-STL默认使用一级还是二级空间配置器，通过USE_MALLOC宏进行控制：

#ifdef __USE_MALLOC
typedef malloc_alloc alloc;
typedef malloc_alloc single_client_alloc;
#else// 二级空间配置器定义
#endif

在SGI_STL中该宏没有定义，因此：默认情况下SGI_STL使用二级空间配置器。

4.与容器结合

使用list作为例子，看下面代码：

//typedef __default_alloc_template<__NODE_ALLOCTOR_THREADS, 0> alloc;
template < class T, class Alloc = alloc >
class list
{// ...// 实例化空间配置器typedef simple_alloc<list_node, Alloc> list_node_allocator;// ...
protected:link_type get_node(){// 调用空间配置器接口先申请节点的空间return list_node_allocator::allocate();}// 将节点归还给空间配置器void put_node(link_type p){list_node_allocator::deallocate(p);}// 创建节点：1. 申请空间 2. 完成节点构造link_type create_node(const T& x){link_type p = get_node();construct(&p->data, x);return p;}// 销毁节点： 1. 调用析构函数清理节点中资源 2. 将节点空间归还给空间配置器void destroy_node(link_type p){destroy(&p->data);put_node(p);}// ...iterator insert(iterator position, const T& x){link_type tmp = create_node(x);tmp->next = position.node;tmp->prev = position.node->prev;(link_type(position.node->prev))->next = tmp;position.node->prev = tmp;return tmp;}iterator erase(iterator position){link_type next_node = link_type(position.node->next);link_type prev_node = link_type(position.node->prev);prev_node->next = next_node;next_node->prev = prev_node;destroy_node(position.node);return iterator(next_node);}// ...
};