目录
四 无论是一级还是二级，SGI会为他封装一层类：simple_alloc
一 什么是空间配置器
空间配置器：字面意思就是管理空间，也就是内存，但这个空间不仅仅指的是内存，比如磁盘等可以进行存储介质的硬件都可以有空间。
都知道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)))); // 底层调用malloc
if (tmp == nullptr)
{
std::cerr << "out of memory" << std::endl;
exit(-1);
}
return tmp;
}
template <class T>
inline void _deallocate(T* buffer) { ::operator delete(buffer); } // 底层调用free
template<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; // 有符号整型
// 封装 _allocate
pointer allocate(size_type n, const void* hint = 0) { return _allocate((difference_type)n, (pointer)0); }
// 封装 _deallocate
void deallocate(pointer p) { _deallocate(p); }
// 封装 _construct
void construct(pointer p) { _construct(p); }
// 封装 _destory
void 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 拷贝给T
template<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); // 直接调用 malloc
if(result == 0)result = oom_malloc(n); // 失败调用 oom_malloc
return 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); // 直接调用 realloc
if(result == 0)result = oom_realloc(p,new_sz); // 直接调用 oom_realloc
return 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); // 开始申请内存，直接调用malloc
if(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; // 赋值给p
if(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);
}