本文共 9973 字，大约阅读时间需要 33 分钟。

什么是空间配置器

顾名思义，就是帮助各个容器来管理空间的（空间的申请与释放）。虽然但多数情况下我们不会直接使用到空间配置器（比如vector，list都是有空间配置器的，只不过不需要我们来显式给出），但对于我们了解STL的底层代码以及原理还是有帮助的。

为什么要有空间配置器

上面说到，空间配置器就是用来管理空间的，而我们学过C语言中的 malloc–free ，C++中的 new–delete 也都是用来管理空间的，为什么不直接使用？而是重新设计出一个新的内存管理机制。因为使用 new会有以下几个不足：

• 空间的申请和释放都需要用户自己管理，容易造成内存泄露
• 直接使用 malloc 和 new 来申请，每块空间前都有额外的空间浪费
• 频繁的申请小块内存，容易造成内存碎片
• 频繁的申请小块内存，会影响程序运行效率
• 如果申请空间失败，如何处理
• 代码结构比较复杂，复用率不高
• 未考虑线程安全问题

因此需要设计出一种新的高效的内存管理机制。

对于上述所说的几个问题，简单的理解一下：在开辟空间的时候，分配器会去找空闲块分配给用户，找空闲块是需要时间的，尤其是外碎片特别多的情况下。如果分配器找不到，就要考虑处理假碎片的问题（将地址连在一起的空间进行合并），这也是需要时间的。并且malloc在申请空间的时候，不单单是你要申请4个字节，分配器就给你四个字节，实际上，分配器会给多与四个字节的内容，用于检测是否越界。所以说，分配器会给大于申请空间大小的空间，也就造成了资源的浪费。

空间配置器的基本框架

首先，new 申请空间分为两个步骤：1. 申请空间 2. 调用构造函数；

      delete 也分为两个步骤： 1. 调用析构函数 2. 释放空间。      不管是 new 还是 delete 这两个步骤都必须是同时出现的。 同样的，空间配置器也需要两个步骤，但不同的是，空间配置器将这两个步骤分开了，这两个步骤就不必同时出现，而是根据具体的情况再做决定，效率就会提高（一切为了效率）。 STL 空间配置器将这两步分开：

1. 内存配置由alloc::allocate()负责，对象构造由::construct()负责；
2. 对象析构由::destroy()负责内存释放由alloc::deallocate()负责；

因为有些对象构造的时候不需要调用构造函数，析构的时候也不需要调用析构函数

// 归还空间时，先先调用该函数将对象中资源清理掉 template 
   
     inline void destroy(T* pointer) {
       	pointer->~T(); } // 空间申请好后调用该函数：利用placement-new完成对象的构造 template 
    
      inline void construct(T1* p, const T2& value) {
       	new (p) T1(value); }
    
   

空间配置器的原理

上面提到的几处不足，主要还是：频繁的向系统上申请小块内存造成的，到底多大才算是小块内存？？STL中以128个字节作为小块内存与大块内存的分界线，将空间配置器分为两级结构，一级空间配置器负责处理大块内存（大于128字节的），二级空间配置器负责处理小块内存（小于等于128字节的）

一级空间配置器

一级空间配置器的原理比较简单，直接对malloc 和 free 进行了封装，并增加了C++中的set_new_handle的思想

template 
   
      class __malloc_alloc_template  {
     private:  	static void *oom_malloc(size_t);  	static void *oom_realloc(void *, 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的封装     // 这里多了一个参数 size_t，主要是为了接口的统一    static void deallocate(void *p, size_t /* n */)     {
               	free(p);     }     // 对realloc的封装---该函数基本不用     static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)     {
               	void * result = realloc(p, new_sz);            	if (0 == result)                 		result = oom_realloc(p, new_sz);        	    return result;     } 	// 模拟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 
    
      void * __malloc_alloc_template
     
      ::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);      	}  } // 类似oom_malloc template 
      
        void * __malloc_alloc_template
       
        ::oom_realloc(void *p, size_t n) {
       	void (* my_malloc_handler)();    	void *result;     for (;;)         {
               	my_malloc_handler = __malloc_alloc_oom_handler;           		if (0 == my_malloc_handler)           	{
                   		__THROW_BAD_ALLOC;             	}                    	(*my_malloc_handler)();            	result = realloc(p, n);                    	if (result)                 		return(result);        } } typedef __malloc_alloc_template<0> malloc_alloc;
       
      
     
    
   

二级空间配置器

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

内存池

内存池：就是先申请一块较大的空间作为备用，当用户申请内存的时候，直接从内存池中取，当内存池中的空间不够时，再从内存中取一块较大的空间，当用户不用时，直接将空间返回内存池中。避免频繁向系统申请小的空间锁造成的效率低、内存碎片以及额外浪费的问题。

内存池使用两个指针 start、finfish 来标记剩余大块数据的大小 如果仅仅是这样设计，就又会出现几个问题：

1. 用户需要空间时，是直接从内存池的大块空间中获取，还是从规划的空间中获取？？

首先，肯定应该先从归还的空间中选取一块符合用户要求的返回，如果没有，再从大块内存中获取。

2. 用户归还的空间能否直接拼接在大块数据前？？

答案肯定是不能。因为用户归还空间的顺序肯定是不一样的，比如先申请了1，2,3号空间，如果这时候归还2号空间，该如何拼接，地址都没有连在一起，肯定是不行的

3. 对用户归还的空间如何处理？？

链表管理。正如第二题所说，用户归还的空间肯定是不连续的，但又要能够找到用户所归还的空间，所用要通过链式结构来管理起来

4. 不断切割的后果？

如果一直不断切割下去，势必会造成小块内存，因为每次切割都是从比要的空间更大的地方进行切割，切割后肯定会剩余一些小的空间，如果一直切割下去，就会造成有大量的内存碎片

哈希桶

经过上述的分析，不能对用户归还的空间简简单单的通过链式结构来管理，所以就要通过另外一种结构：哈希桶。

但如果要使用哈希桶的话，是否需要128个桶的空间来管理用户已经归还的内存块呢？不需要。因为用户申请的空间绝大多数都是 4 的倍数，其他空间的大小很少用到。因此：STL将用户申请的内存块向上对齐到了 8 的整数倍。

那么问题来了，为什么是8的整数倍，而不是4的整数倍？

因为哈希表中存放的是地址，一个地址的大小在32位系统下是 4 个字节，但如果实在64位系统下尼，地址就是8个字节，所以内存是8的整数倍

实际上，还有另外一个原因，因为我们绝大多数申请空间都是自定义类型的，也就是身体 struct，一个结构体的大小基本是 8 的倍数。

空间申请的流程

1.前期准备

// 去掉代码中繁琐的部分 template 
   
     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];       };    private:       static obj *  free_list[__NFREELISTS];    // 哈希函数，根据用户提供字节数找到对应的桶号       static  size_t FREELIST_INDEX(size_t bytes)       {
              		return (((bytes) + __ALIGN-1)/__ALIGN - 1);       }              // start_free与end_free用来标记内存池中大块内存的起始与末尾位置       static char *start_free;       static char *end_free;              // 用来记录该空间配置器已经想系统索要了多少的内存块       static size_t heap_size;            // ... } ;
   

2.申请空间

// 函数功能：向空间配置器索要空间 	// 参数n: 用户所需空间字节数 	// 返回值：返回空间的首地址 	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); };

3.往哈希桶中填充内存块

// 函数功能：向哈希桶中补充空间// 参数n：小块内存字节数// 返回值：首个小块内存的首地址template 
   
    void* __default_alloc_template
    
     ::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);}
    
   

4.向内存池中索要空间

template 
   
    char* __default_alloc_template
    
     ::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	{
   		// 内存池空间不足，连一块小块村内都不能提供		// 向系统堆求助，往内存池中补充空间		// 计算向内存中补充空间大小：本次空间总大小两倍 + 向系统申请总大小/16		size_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));	}}
    
   

5.空间回收

// 函数功能：用户将空间归还给空间配置器// 参数：p空间首地址 n空间总大小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使用的是二级空间配置器。这个也可以通过 USE_MALLOC 这个红来改变

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

常见的问题

1. 细心的朋友会发现，空间配置器中所有的函数都是静态的，为什么？？如果这些函数不是静态的，如果我们要申请空间，岂不是也要创建一个空间配置器的对象，由对象来调用里面的函数，进而申请空间，如果这样的话，那空间就跟随者空间配置器对象的生命周期，那这个岂不是很麻烦，每次都要额外创建对象。所以把所有的函数都设置为静态的，就不需要创建对象就能够调用函数申请空间，并且可以保证在程序结束的时候空间才会被回收。
2. 由于没有将内存直接还给系统，而是还给内存池，就会出现一些极端情况

• 如果用户不断的开辟小块内存，最后将整个heap上的内存都挂在了哈希桶上，但是都没有用这些空间，再想要开辟一个大块内存的话会开辟失败。
• 再比如不断的开辟char,最后将整个heap内存全挂在了哈希表中第一个地址的后面，这时候再想开辟一个16个字节的内存，也会失败。

3. 二级空间配置器会造成内碎片问题，极端的情况下一直申请char，则就会浪费 7个字节的浪费的空间。但是整体来说，空间配置器的性能还是蛮高的，因为上述都属于一些极端情况。

转载地址：http://jcwdb.baihongyu.com/