目录

一 什么是空间配置器

二 简易空间配置器的实现

三 ：Construct/Destroy：2个全局接口

四 无论是一级还是二级，SGI会为他封装一层类：simple_alloc

五 下面来看看一级空间配置器的实现：

六 下面看看二级空间配置器的实现：

七 下面在来看看其他3个全局函数：

---

一 什么是空间配置器

空间配置器：字面意思就是管理空间，也就是内存，但这个空间不仅仅指的是内存，比如磁盘等可以进行存储介质的硬件都可以有空间。

都知道C++申请内存的方式是new，但STL容器走的都是空间配置器，为什么不走new？

1. new把申请对象和对象的构造强绑定在一起。

2. new申请内存必须指定类型。

3. new如果在构造的时候抛异常，对象还没初始化完成，需要手动进行释放操作。

4. new只能申请的是堆/共享区的内存，比如 gilic ptmalloc 管理小块内存块调用brk，大块内存块调用mmap。

5. new每一次调用都可能调用malloc，有性能开销，如果没加缓存，这里指的不是malloc内部的缓存，指的是调用malloc之前有无缓存。

说白了空间配置器就是和new的功能一样都是分配内存，但他们之间略有差异，下面来看看空间配置器的实现和new的不同。

二 简易空间配置器的实现

1. 一个简单的空间配置器

#include <new>		// placement new 定位new
#include <cstddef>	// ptrdiff_t,size_t 有符合/无符合整型
#include <cstdlib>	// exit() 终止程序
#include <climits>	// UINT_MAX 无符号整型最大值
#include <iostream> // cerr 错误输出namespace JJ
{template <class T>inline T* _allocate(ptrdiff_t size, T*)			// 手动申请 n个 对象，但不构造，仅分配内存{set_new_handler(0);							// 异常进行捕捉T* tmp = (T*)(::operator new((size_t)(size * sizeof(T)))); // 底层调用mallocif (tmp == nullptr){std::cerr << "out of memory" << std::endl;exit(-1);}return tmp;}template <class T>inline void _deallocate(T* buffer) { ::operator delete(buffer); }	// 底层调用freetemplate<class T1>inline void _construct(T1* p) { new(p) T1; }						// placement new 在已经有的空间上调用对应类型的构造template <class T>inline void _destroy(T* ptr) { ptr->~T(); }							// 手动析构template <class T>class allocator{public:typedef T value_type;				// 对象本身typedef T* pointer;					// 对象指针typedef const T* const_pointer;		// const 对象指针typedef T& reference;				// 对象引用typedef const T& const_reference;	// const 对象引用typedef size_t size_type;			// 无符号整型typedef ptrdiff_t difference_type;	// 有符号整型// 封装 _allocatepointer allocate(size_type n, const void* hint = 0) { return _allocate((difference_type)n, (pointer)0); }// 封装 _deallocatevoid deallocate(pointer p) { _deallocate(p); }// 封装 _constructvoid construct(pointer p) { _construct(p); }// 封装 _destoryvoid destory(pointer p) { _destroy(p); }// 返回对象指针pointer address(reference x) { return (pointer)&x; }// 返回 const 对象指针const_pointer const_address(const_reference x) { return (const_pointer)&x; }// 分配对象的最大个数size_type max_size()const { return size_type(UINT_MAX / sizeof(T)); }};
}

可以看出来上面把申请内存/释放内存/构造对象/析构对象分离出来了，这种是SGI的STD::allocator的实现。

申请/释放内存在 #include<stl_alloc.h>头文件中。

构造/析构对象在 #include<stl_construct.h>头文件中。

下面看看头文件具体部分实现：

三 <stl_construct.h>：Construct/Destroy：2个全局接口

#include <new.h>template<class T1,class T2>inline void construct(T1* p.const T2& value){new(p) T1(value);} // 定位new value 拷贝给Ttemplate<class T>
inline void destroy(T* pointer){pointer->~T();} // 手动调析构template<class ForWardIterator>
inline void destroy(ForWardIterator first,ForWardIterator last)
{ __destroy(first,last,value_type(first)); 
}   // 传入迭代器区间，逐个析构,type(first)传入对象类型template<class ForWardIterator,class T>
inline void __destroy(ForWardIterator first,ForWardIterator last,T*)
{// 判断该类型是否需要析构typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;__destroy_aux(first,last,trivial_destructor()); 
}   // 根据 trivial_destructor() 来判断调用哪个__destroy_aux版本template<class ForWardIterator>
inline void __destroy_aux(ForWardIterator first,ForWardIterator last,__false__type)
{// 需要析构for(;first<last,++first)destroy(&*first);
}// 不需要析构
template<class ForWardIterator>
inline void __destroy_aux(ForWardIterator,ForWardIterator,__true_type){}inline void destroy(char*,char*){}        // 内置类型不需要调析构
inline void destroy(wchar_t*,wchar_t*){}  // 内置类型不需要调析构

可以看出来，构造直接调用placemewnt new，在已有的空间上手动调用拷贝构造函数。

而析构提供了4个版本，单个对象的，迭代器区间的，char*的，wchar_t*的，其中后2个内置类型无需调用析构，而迭代器区间如果是内置类型则会调用匹配的__destroy_aux()什么也不干，否则调用匹配__destroy_aux()进行for循环调用单个对象的析构版本。

再来看看<stl_alloc.h>：申请内存和释放

这里采用了双层空间配置器，二级用来管理小块对象，说白了就是缓存一些小块对象。

如果申请的大小超过128字节，则调用一级，否则调用二级。

实际一级和二级是否都启用取决于 __USE_MALLOC 这个宏。

# ifdef __USE_MALLOC
...
typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc;# else
...
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS,0> alloc;# endif

其中如果 __USE_MALLOC 启用，则调用一级空间配置器，否则调用二级。

这里 alloc 是不带模板的，和 alloctor是不一样的。

四 无论是一级还是二级，SGI会为他封装一层类：simple_alloc

template<class T,class Alloc>
class simple_alloc
{    // 申请n个对象大小static T* allocate(size_t n){return 0 == 0 ? 0:(T*)Alloc::allocate(n * sizeof(T));}// 申请一个对象大小static T* allocate(void){return (T*)Alloc::allocate(sizeof(T));}// 释放n个对象static void deallocate(T* p,size_t n){if(n!=0)Alloc::deallocate(p,n*sizeof(T));}// 释放一个对象static void deallocate(T* p){Alloc::deallocate(p,sizeof(T));}
}

不管 alloc 是一级还是二级，在simple_alloc的封装下，是几级就调几级，并通过静态通过类名就能分配内存大小了。

比如：

template <class T,class Alloc = alloc>
class vector
{typedef simple_alloc<T,Alloc> data_alloctor;data_alloctor::alloc(n);data_alloctor::deallocate(T*,n);
}

五 下面来看看一级空间配置器的实现：

__malloc_alloc_template：

template <int inst>
class __malloc_alloc_template
{private:// 以下 3个函数 保证分配内存失败的情况 而调用他们static void *oom_malloc(size_t);static void *oom_realloc(size_t);static void (*__malloc_alloc_oom_handler)();public:static void* allocate(size_t n){void* result = malloc(n);                 // 直接调用 mallocif(result == 0)result = oom_malloc(n);    // 失败调用 oom_mallocreturn result;}static void deallocate(void* p,size_t /* n */){free(p); // 直接调用 free}static void* reallocate(void* p,size_t /* old_sz */,size_t new_sz){void* result = realloc(p,new_sz);                // 直接调用 reallocif(result == 0)result = oom_realloc(p,new_sz);   // 直接调用 oom_reallocreturn result;}static void (* set_malloc_handler(void (*f)()))(){void (*void)() = __malloc_alloc_oom_handler;   // 保存旧的 函数指针__malloc_alloc_oom_handler = f;                // 让传入的f赋给成员对象这个函数指针retrurn (old);                                 // 返回旧的函数指针}
};template <int inst>
// 初始化成员对象函数指针为0
void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;template<int inst>
// 成员对象 oom_malloc 的实现
void *__malloc_alloc_template<inst>::oom_malloc(size_t n)
{void (*my_malloc_handler)();void *result;for(;;){my_malloc_handler = __malloc_alloc_oom_handler;    if(my_malloc_handler == 0){ __THROW_BAD_ALLOC; }   // 如果函数指针为空，直接抛异常(*my_malloc_handler)();                            // 否则调用result = malloc(n);                                // 进行分配if(result) return (result);                        // 有内存返回，否则死循环}
}template<int inst>
void* __malloc_alloc_template<inst>::oom_realloc(void *p,size_t n)
{void (*my_malloc_handler)();void* result;for(;;){my_malloc_handler = __malloc_alloc_oom_handler;    if(my_malloc_handler == 0){ __THROW_BAD_ALLOC; }   // 如果函数指针为空，直接抛异常(*my_malloc_handler)();                            // 否则调用result = realloc(p,n);                             // 进行分配if(result) return (result);                        // 有内存返回，否则死循环}        
}typedef __malloc_alloc_template<0> malloc_alloc;

可以看出来 一级空间配置器底层其实就是调用的 malloc/realloc，但如果申请内存失败则调用用户自定义的处理函数，然后在进行malloc/realloc，直到申请到内存为止，或者抛出异常，和operator new 不一样，operator new 有自己的set_new_handler。

六 下面看看二级空间配置器的实现：

__default_alloc_template：

二级空间配置器主要管理小于 128字节的 小块内存。

enum { __ALIGN = 8 };                               // 对齐数
enum { __MAX_BYTES = 128 };                         // 管理的最大字节
enum { __NFREELISTS = __MAX_BYTES / __ALIGN   };    // 根据最大字节和对齐数算出要多少个下标temlpate <bool threads,int inst>
class __default_alloc_template
{private:// 根据传入的字节算出对齐数static size_t ROUND_UP(size_t bytes) { return (((bytes) + __ALIGN - 1 & ~(__ALIGN)-1));private:// 这里用了联合体，并非结构体，为了进行空间复用// 如果用结构体，用户空间 + 管理内存块的指针// 如果用联合体，2个字段共享，空闲时用内存块的指针，分配出去就用用户的空间// 换回来把用户的空间强转成 obj* 类型，并且直接根据用户内存块的大小挂到桶里，并用第   一个字段指针指向桶，在让他当桶的头union obj    {union obj* free_list_link;char client_data[1];};private:// 定义 16个桶 并用volatile修饰，防止编译器优化static obj* volatile free_list[__NFREEKISTS];// 根据对齐数算出下标static size_t FREELIST_INDEX(size_t bytes) { return (((bytes)+__ALIGN-1)/__ALOGN-1); }static void* refill(size_t n);static char* chunk_alloc(size_t size,int &nobjs);static char* start_free;    // 整个内存池的起始地址static char* end_free;      // 整个内存池的结束地址static char* 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);   // 申请对象
};// 下面对静态对象进行初始化为0
template <bool threads,int inst>
char* __default_alloc_template<thread,inst>::start_free = 0;template <bool threads,int inst>
char* __default_alloc_template<thread,inst>::end_free = 0;template <bool threads,int inst>
char* __default_alloc_template<thread,inst>::heap_size= 0;template <bool threads,int inst>
_default_alloc_template<threads,inst>::obj* volatile _default_alloc_template<threads,inst>::free_list[__NFREELISTS]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}// 分配内存
static void* allocate(size_t n)
{obj* volatile *my_free_list;    // 指向 obj* 的指针obj* 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)                               // 如果头为空，则该下标一个内存块也没有{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)
{obj* q = (obj*)p;                // 要释放的内存块obj* volatile* my_free_list;     // 指向 obj* 的指针if(n > (size_t) __MAX_BYTES)     // 如果内存块大于 128 调用一级空间配置器进行释放{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;                               // 让释放的内存块成为这个桶的头
}template <bool threads,int inst>
// 如果对应的桶位置没有内存块则去内存池分配内存块
void* __default_alloc_template<threads,inst>::refill(size_t n)
{int nobjs = 20;                        // 默认拿20个用户要的内存块char* chunk = chunk_alloc(n,nobjs);    // 从内存池拿内存块，后面讲obj* volatile* my_free_list;           // 指向桶的指针obj* result;                           // 给用户返回的内存块obj* current_obj,*next_obj;            // 当前内存块的指针和下一个内存块的指针，用来衔接分配的20个内存块的链接关系int i;                                 // 用来衔接分配的20个内存块链接关系的变量if(nobjs == 1)return chunk;                    // 如果只有一个直接返回给用户my_free_list = free_list + FREELIST_INDEX(n);  // 否则先算出对应的桶result = (obj*)chunk;                          // 让大内存块的前 用户需要的内存块给用户*my_free_list = next_obj = (obj*)(chunk + n);  // 让桶指向剩余的19个块，此时并未链接起来for(int i = 1;;i++)    // 进行链接{current_obj = next_obj;                    // 记录当前内存块的地址next_obj = (obj*)((char*)next_obj + n);    // 记录下一个内存块的地址if(nobjs -1 == i)                          // 如果 i == 19 则表示最后一个内存块了，{                                          // 指向空并结束退出current_obj -> free_list_link = 0;break;}    else current_obj -> free_list_link = next_obj;    // 进行衔接}return (result);                                // 把头部的内存块返回个用户
}// 桶位置一个也没有
template <bool threads,int inst>
char* __default_alloc_template<threads,inst>::chunk_alloc(size_t size,int& nobjs)
{char* result;                                 // 实际返回的大内存块的起始地址size_t total_bytes = size * nobjs;            // 实际可能要多个，并计算总的字节大小size_t bytes_left = end_free - start_free;    // 算出内存池剩余的字节大小if(bytes_left >= total_bytes)                 // 如果足够，切割返回{result = start_free;                      // 等于未分配的起始地址start_free += total_bytes;                // 跳过要分配的大小return (result);                          // 返回}else if(bytes_left >= size)           // 如果不够预期想要的大小，但至少有一个完整的内存块{nobjs = bytes_left / size;        // 根据剩余的内存大小除以完整的内存大小得到实际的                // 要分配的内存块数量total_bytes = size * nobjs;       // 重新算总的内存块大小result = start_free;              // 等于未分配的起始地址start_free += total_bytes;        // 跳过更新后的要分配的大小return (result);                  // 返回}else    // 如果一个完整的也没有{// 重新分配内存池内存：2倍的预期内存块总的大小 + 当前内存池大小除以16//                   如果1倍则可能少了，可能频繁扩容消耗性能，根据当前内存池内存的大 动    //                   态扩展一定的内存，类似渐近式扩容size_t bytes_to_get = 2 * total_bytes + ROUND_UP(head_size >> 4);if(bytes_left > 0)                 // 如果原内存池还有一点点内存，则挂到桶里去{// 得到对应的桶头obj* volatile* my_free_list = free_list + FREELIST_INDEX(bytes_left)'// 让原内存池剩余的内存指向桶头((obj*)start_free) -> free_list_link = *my_free_list;// 并让他当桶头*my_free_list = (obj*)start_free;}start_free = (char*)malloc(bytes_to_get);        // 开始申请内存，直接调用mallocif(start_free == 0)                              // 如果失败，{int i;                                       // 下面的for循环把自由链表里的桶管// 理的内存块取头归还到内存池里面  obj* volatile* my_free_list,*p;              // 定义桶指针for(i = size;i <= __MAX_BYTES;i += __ALIGN)  // size已经的对齐后的大小{                                            // 从这个大小开始的桶进归还my_free_list = free_list + FREELIST_INDEX(i);    // 得到具体的桶p = *my_free_list;                               // 赋值给pif(p != 0)                                       // 不为空则取出来{*my_free_list = p -> free_list_link;start_free = (char*)p;end_free = start_free + i;return (chunk_alloc(size,nobjs));            // 为空则递归看下一个桶}}end_free = 0;                                        // 如果malloc成功则重置整// 个内存池的结束地址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));                         // 递归重新进行分配}
}

可以看出来二级空间分配器：

主要用来管理 <= 128字节的内存块，按8字节对齐，算出总共又16个桶位置。

分配逻辑：根据传入的大小向上取整，然后算出对应的桶下标，在进行分配，如果有直接取头返回，否则去内存池里拿，这里默认拿20个，为了后续还有这样的需求避免频繁的去内存池里拿，相当于缓存，如果有20个直接切割并返回，否则如果够一个切割返回，否则一个也没有则直接malloc，如果失败则看自由链表里从一个块的大小开始的桶进行取头部，然后挂到内存池里，并递归后续进行切割返回出去，如果malloc失败则调用一级分配器的接口，其实也是malloc，只不过他内部有个自定义处理函数，malloc失败则执行他，然后在malloc，也就是个死循环。

释放逻辑：根据传入的指针和大小，如果大于128字节则调用一级分配器的释放，否则归还到二级分配器的自由链表对应的桶里，这里并不涉及合并内存块或者归还到内存池里。

七 下面在来看看其他3个全局函数：

前面说了2个全局函数：Construct/destroy：对象的构造/析构。

template <class InputIt, class ForwardIt>
ForwardIt uninitialized_copy(InputIt first, InputIt last, ForwardIt d_first);template <class ForwardIt, class T>
void uninitialized_fill(ForwardIt first, ForwardIt last, const T& value);template <class ForwardIt, class Size, class T>
ForwardIt uninitialized_fill_n(ForwardIt first, Size n, const T& value);

第一个则是给一个单向迭代器，用前2个迭代器的范围来构造初始化这个单向迭代器，

第二个则是给2个迭代器区间，用一个固定的值进行构造初始化他。

第三个和第二个类似，给一个单向迭代器，不过结束是用n来标识，在用一个固定的值进行构造初始化他。

上面待构造的迭代器都是指向的是未初始化的内存空间。

具体实现：

uninitialized_fill_n

template <class ForwardIterator,class Size,class T,class T1>
inline ForwardTierator uninitialized_fill_n(ForwardTierator first,Size n,const T& x)
{// 调用下一个函数，, value_type 取迭代器具体的类型return __uninirialized_fill_n(first,n,x,value_type(first));
}template <class ForwardIterator,class Size,class T,class T1>
inline ForwardTierator __uninitialized_fill_n(ForwardTierator first,Size n,const T& x，T1*)
{// 根据这个迭代器类型执行具体的函数，如果是内置类型则不需要构造，否则构造typedef typename __type_traits<T1>::is_POD_type is_POD;return __uninitialized_fill_n_aux(first,n,x,is_POD());
}// 是内置类型则不调用构造
template <class ForwardIterator,class Size,class T>
inline ForwardIterator __uninitialized_fill_n_aux(ForwardIterator first,Size n,const T& x,__true_type)
{return fill_n(first,n,x);
}// 不是内置类型则调用构造
template <class ForwardIterator,class Size,class T>
inline ForwardIterator __uninitialized_fill_n_aux(ForwardIterator first,Size n,const T& x,__false_type)
{ForwardIterator cur = first;for(;n > 0;--n,++cur) construct(&*cur,x);return cur;
}

uninitialized_copy

// 让一个单向迭代器构造初始化一段未初始化的迭代器区间
template <class InputIterator,class ForwardIterator>
inline ForwardIterator uninitialized_copy(InputIterator first,InputIterator last,InputIterator result)
{// 判断迭代器实际的类型return __uninitialized_copy(first,last,result,value_type(result));
}// 根据是内置类型还是自定义类型选择是否需要调构造
template <class InputIterator,class ForwardIterator,class T>
inline ForwardIterator __uninitialized_copy(InputIterator first,InputIterator last,InputIterator result,T*)
{typedef typename __type_traits<T>::is_POD_type is_POD;return __uninitialized_copy_aux(first,last,result,is_POD());
}// 是内置类型不调用构造
template <class InputIterator,class ForwardIterator>
inline ForwardIterator __uninitialized_copy_aux(InputIterator first,InputIterator last,InputIterator result,__true_type)
{return copy(first,last,result);
}// 不是内置类型调用构造
template <class InputIterator,class ForwardIterator>
inline ForwardIterator __uninitialized_copy_aux(InputIterator first,InputIterator last,InputIterator result,__false_type)
{for(;first != last;++first,++cur) construct(&*cur,*first);;return cur;
}

uninitialized_fill

// 给一个固定的值来构造初始化一段迭代器区间
template<class ForwardIterator,class T>
inline void uninitialized_fill(ForwardIterator first,ForwardIterator last,const T& x)
{__uninitialized_fill(first,last,x,value_type(first));
}// 判断是否是内置类型
template<class ForwardIterator,class T,class T1>
inline void __uninitialized_fill(ForwardIterator first,ForwardIterator last,const T& x,T1*)
{typedef typename __type_traits<T1>::is_POD_type is_POD;return __uninitialized_fill_aux(first,last,x,is_POD());
}// 是内置类型不调用构造
template<class ForwardIterator,class T>
inline void __uninitialized_fill_aux(ForwardIterator first,ForwardIterator last,const T&,__true_type)
{fill(first,last,x);
}// 是自定义类型调用构造
template<class ForwardIterator,class T>
inline void __uninitialized_fill_aux(ForwardIterator first,ForwardIterator last,const T&,__false_type)
{ForwardIterator  cur = first;for(;cur != last,++cur) construct(&*cur,x);
}