1 简述
STL其他组件都是存放在空间配置器配置的空间中，此处空间可以是内存，也可以是磁盘或其他辅助存储介质。
allocator负责内存的分配和释放，以及负责对象的构造和析构,两个操作时分开的。
每个容器都已经制定了默认的空间配置器Alloc，如下图所示。
若要使用自己的空间配置器则必须vector<int,my_alloc> mv;
2 标准接口
// 以下几种自定义类型是一种type_traits技巧，暂时不需要了解
allocator::value_type
allocator::pointer
allocator::const_pointer
allocator::reference
allocator::const_reference
allocator::size_type
allocator::difference
allocator::rebind
// 一个嵌套的(nested)class template，class rebind<U>拥有唯一成员other，那是一个typedef，代表allocator<U>
allocator::allocator() // 默认构造函数
allocator::allocator(const allocator&) // 拷贝构造函数
template <class U>allocator::allocator(const allocator<U>&) // 泛化的拷贝构造函数
allocator::~allocator() // 析构函数
pointer allocator::address(reference x) const
// 返回某个对象的地址，a.address(x)等同于&x
const_pointer allocator::address(const_reference x) const
// 返回某个const对象的地址，a.address(x)等同于&x
pointer allocator::allocate(size_type n, const void* = 0)
// 配置空间，足以存储n个T对象。第二个参数是个提示。实现上可能会利用它来增进区域性(locality)，或完全忽略之
void allocator::deallocate(pointer p, size_type n)// 释放先前配置的空间
size_type allocator:maxsize() const// 返回可成功配置的最大量
void allocator::construct(pointer p, const T& x)
//在p指向位置 调用对象的构造函数，等同于 new((void*)p) T(x)
void allocator::destroy(pointer p)// 调用对象的析构函数，等同于 p->~T()
3 空间配置器申请的空间均仅仅是空间（如仅分配内存而未构造对象）
这里说明几种申请内存的区别
A *a = (A*)(::operator new A ((size_t) (size * sizeof(A)));
调用全局operator new(size_t size)仅仅申请内存，然后返回指针。allocate中使用。void *mem = operator new A (sizeof(T1),p);
借用p指向的内存处大小为sizeof(T1)的内存，返回void*指针。A *a = new A (...);
①申请内存（与operator new相同）
②调用A(…)构造对象
③返回指针
//Complex* pc=new Complex(1,2)相当于
try{
void* mem = operator new(size(Complex));
Complex* pc=static_case<Complex*>(mem);
pc->Complex()::Complex(1,2);
}
catch(std::bad_alloc){ ... }
new(p) T1(value);
为已申请内存*p构造T1。construct时使用。相当于
try{
void* mem = operator new(size(T1),p);
p* pc=static_case<T1*>(mem);
pc->T1()::T1();
}
catch{ ... }
4 SGI空间配置器
SGI的空间配置器名称为alloc，而非allocator，不接受任何参数。
vector<int,allocator<int>> iv;
vector<int,alloc> iv;
我们所习惯的c++内存配置操作和释放操作是使用new和delete来完成的：
class Foo { ... };
Foo* pf = new Foo; // 配置内存，然后构造对象
delete pf; // 将对象析构，然后释放内存
如上一部分所说，其中的new 操作符（new operator）包含两阶段操作：
（1）调用operator new配置内存
（2）调用Foo::Foo( )构造函数构造对象内容。
delete操作符同样也包含两阶段操作：
（1）调用Foo::~Foo( )析构函数将对象析构。
（2）调用operator delete释放内存
STL allocator 将这两阶段操作区分开来。
内存配置操作由 alloc::allocate() 负责，内存释放操作由 alloc::deallocate() 负责；
对象构造操作由 ::construct() 负责，对象析构操作由 ::destroy() 负责。
//负责内存空间的配置与释放;
<stl_alloc.h>//文件中定义了一、二两级配置器，彼此合作，配置器名为alloc。
//负责对象内容的配置与释放
<stl_construct.h>//全局函数construct()和destroy()，负责对象的构造和析构。
//用来填充fill或复制copy大块内存数据
<stl_uninitialized.h>//uninitialized_copy();uninitialized_fill();uninitialized_fill_n
uninitialized_copy(first, last, result) //将[first,last)范围内的对象复制到result处；
uninitiated_fill(first, last, X) //将[first,last)范围内的内存用对象X的副本填充；
uninitiated_fill_n(first, n, X) //将first开始的n个连续的内存空间用X的副本填充；
4.1 构造与析构工具：construct()和destroy()
- construct()仅仅负责构造对象，需要提前用allocate()申请内存。两操作合起来相当于new。
construct()接受一个指针p和初值value，该函数将初值设定到所指空间上； - destroy()仅仅负责析构对象，需要之后用deallocate()释放内存。两操作合起来相当于delete。
destroy()有两个版本：
1、接收一个指针，准备将该指针所指之物析构掉。直接调用该对象的析构函数；
2、接收first和last两个迭代器，准备将[first,last)范围内的所有对象析构掉。
利用value_type()获取迭代器所指对象的类型，利用__type_traits判断该类型的析构函数是否无关痛痒。若是__true_type,则什么也不做，反之若是__false_type则循环访问，对每个对象调用析构函数。
#ifndef __SGI_STL_INTERNAL_CONSTRUCT_H
#define __SGI_STL_INTERNAL_CONSTRUCT_H
#include <new.h> // 欲使用 placement new，需先含入此檔
template <class T1, class T2>
inline void construct(T1* p, const T2& value) {
new (p) T1(value); // placement new; 调用 T1::T1(value);
}
// 以下是 destroy() 第一版本，接受一個指標。
template <class T>
inline void destroy(T* pointer) {
pointer->~T(); // 喚起 dtor ~T()
}
// 如果元素的數值型別（value type）有 non-trivial destructor…
template <class ForwardIterator>
inline void
__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {
for ( ; first < last; ++first)
destroy(&*first);
}
// 如果元素的數值型別（value type）有 trivial destructor…
template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}
// 判斷元素的數值型別（value type）是否有 trivial destructor
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() 第二版本，接受兩個迭代器。此函式是設法找出元素的數值型別，
// 進而利用 __type_traits<> 求取最適當措施。
template <class ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last) {
__destroy(first, last, value_type(first));
}
// 以下是destroy() 第二版本針對迭代器為 char* 和 wchar_t* 的特化版
inline void destroy(char*, char*) {}
inline void destroy(wchar_t*, wchar_t*) {}
__STL_END_NAMESPACE
#endif /* __SGI_STL_INTERNAL_CONSTRUCT_H */
值得注意的是，关于trivial_destructor()，该函数相当于__type_traits::has_trivial_destructor。
如果用户不定义析构函数，而是用系统自带的，则说明，析构函数基本没有什么用（但默认会被调用）我们称之为trivial
destructor。反之，如果特定定义了析构函数，则说明需要在释放空间之前做一些事情，则这个析构函数称为non-trivial
destructor。 通过has_trivial_destructor()返回值的不同，调用不同的函数。
使用上述trait变成技法的原因是我们不知道first到last的范围有多大，若很大，而每个对象的析构函数是无关痛痒的（即trivial destructor），那么会极大的降低效率。
4.2 空间的配置和释放：std::alloc
SGI STL在<stl_alloc.h>中定义了两级配置器。默认使用的是一级空间配置器。
第一级空间配置器__malloc_alloc_template使用malloc/free函数，当分配的空间大小超过128 bytes的时候使用第一级空间配置器；
第二级空间配置器__default_alloc_template使用了内存池技术，当分配的空间大小小于128 bytes的时候，将使用第二级空间配置器。
关于一级空间配置器宇二级空间配置器的封装方式与使用方式如下图：
4.3 第一级配置器 __malloc_alloc_template
第一级其实没什么好说的，都是直接使用malloc(), free(), realloc()等C函数执行实际的内存配置、释放、重配置.
比较值得讲一下的是对C++的new-handler机制进行模拟的部分，即在内存分配失败时调用指定函数。
失败时调用的函数是static void (* __malloc_alloc_oom_handler)() 所指向的指针，当然再失败时先调用static void *oom_malloc(size_t);或static void *oom_realloc(void *, size_t);，然后再此函数中再进一步调用static void (* __malloc_alloc_oom_handler)() 。
对该函数指针进行设置要使用static void (* set_malloc_handler(void (*f)()))() {/*...*/ }，这也是个函数指针，同时它的参数也是函数指针，传入新的函数指针。
// 以下是第一級配置器。
// 注意，無「template型別參數」。「非型別參數」inst完全沒派上用場。
template <int inst>
class __malloc_alloc_template {
private:
static void *oom_malloc(size_t);
static void *oom_realloc(void *, size_t);
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
static void (* __malloc_alloc_oom_handler)();//分配失败后调用函数指针指向的函数
#endif
public:
static void * allocate(size_t n)
{
void *result = malloc(n); // 第一級配置器直接使用 malloc()
if (0 == result) result = oom_malloc(n);
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 (0 == result) result = oom_realloc(p, new_sz);
return result;
}
// 以下類似 C++ 的 set_new_handler().，可以通过它指定自己的out-of-memory hander
//设置分配失败后调用函数
static void (* set_malloc_handler(void (*f)()))()
{
void (* old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = f;
return(old);
}
};
// malloc_alloc out-of-memory handling
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
template <int inst>
void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;
#endif
template <int inst>
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 (0 == my_malloc_handler) { __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 (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;
4.4 第二级配置器（默认）
第二级配置器将小于128bytes的区块使用内存池(memory pool)管理【又称层次配置（sub-allocation）】，即每次配置一大块内存，并维护对应的自由链表（free-list），当下次有相同的内存需求就从free-list拨出，释放小区块就回收至free-list。
避免造成太多小额区块的内存碎片，第二级配置器主动将小额区块的内存需求上调至8的倍数，并维护16个free-list,分别是8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128 bytes的小额区块。
free-lists的节点结构如下：
union obj{
union obj* free_list_link;
char client_data[1];
}
可以知道节点是一个联合体，这样可以节省内存开销——free_list_link 和client_data 用的是同一块内存，前者表示指向下一个节点的指针，后者表示一个指向实际内存的指针：不分配的时候，节点就放在空闲链表里面，节点内容是下一个节点的地址，如果被分配了，那么节点内容就是指向一块实际的内存，这样就不用在节点里开两个不同内存的变量。
4.4.1 第二级配置器的部分实现
// 實際上我們應該使用 static const int x = N
// 來取代 enum { x = N }, 但目前支援該性質的編譯器還不多。
enum {__ALIGN = 8}; // 小型區塊的上調邊界,即每块是8的倍数
enum {__MAX_BYTES = 128}; // 小型區塊的上限，即最大块的大学
enum {__NFREELISTS = __MAX_BYTES/__ALIGN}; // free-lists 個數
// 以下是第二級配置器。
// 注意，無「template型別參數」，且第二參數完全沒派上用場。
template <bool threads, int inst>
class __default_alloc_template {
private:
//将bytes上调至8的倍数
static size_t ROUND_UP(size_t bytes) {
return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
}
__PRIVATE:
//free-lists的节点构造
union obj {
union obj * free_list_link;
char client_data[1]; /* The client sees this. */
};
private:
//共16个free-lists
static obj * __VOLATILE free_list[__NFREELISTS];
//根据bytes大小选择合适的第n号free-lists，n从0开始算。
static size_t FREELIST_INDEX(size_t bytes) {
return (((bytes) + __ALIGN-1)/__ALIGN - 1);
}
// 返回一个大小为n的对象，并可能加入大小为n的其他区块到free-lists
static void *refill(size_t n);
// 配置一大块空间，可以容纳nobjs个大小为size的区块
// 如果配置nobjs个区块不便，nobjs可能会降低
static char *chunk_alloc(size_t size, int &nobjs);
// Chunk allocation state.
static char *start_free;//内存池起始位置，只在chunk_alloc()中变化
static char *end_free;//内存池结束位置，只在chunk_alloc()中变化
static size_t 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);
};
解释一下(((bytes) + __ALIGN-1)/__ALIGN - 1)，它其实是把要分配的内存大小提升一个数量级（+7，每间隔8为一个数量级），然后除以8，可以算到要找的内存块下标的下一个下标，减一，刚好久找到合适的下标处，取出一块内存块。
4.4.2 allocate()
①由于第二级配置器是默认配置器，需先判断区块大小，若大于128bytes则调用第一级配置器。
②检查对应的free-list：若有可用的区块则直接使用，否则将区块上调至最近8的倍数边界，然后用refill为free-list重现填充空间。
③返回合适的区块地址指针。
static void * allocate(size_t n)
{
obj * __VOLATILE * my_free_list;
obj * __RESTRICT result;
//若n>128则调用第一级配置器
if (n > (size_t) __MAX_BYTES) {
return(malloc_alloc::allocate(n));
}
//在16个free-list中寻找合适的。
// 通过大小取得free-list数组下标，随后取得对应节点的指针
// 相当于free_list[FREELIST_INDEX(n)]，存着一个未使用的内存块
my_free_list = free_list + FREELIST_INDEX(n);
result = *my_free_list;
if (result == 0) {
//没找到可用的free-list，准备重新填充free-list
void *r = refill(ROUND_UP(n));
return r;
}
//调整free-list，将当前节点移除，并当做结果返回给用户使用
//free_list_link即链表下一块内存，替代存着之前合适的数组里
*my_free_list = result -> free_list_link;
return (result);
};
4.4.3 deallocate()
空间释放时也和分配时相同，需要先判断区块大小。
/* p may not be 0 */
static void deallocate(void *p, size_t n)
{
obj *q = (obj *)p;
obj * __VOLATILE * my_free_list;
//大于128则调用第一级配置器
if (n > (size_t) __MAX_BYTES) {
malloc_alloc::deallocate(p, n);
return;
}
//寻找对应的free-list
my_free_list = free_list + FREELIST_INDEX(n);
//调整free list 回收区块，使数组存这个内存块，且这个内存块指向之前数组内的内存块
q -> free_list_link = *my_free_list;
*my_free_list = q;
}
4.4.4 refill() 重新填充
之前说的allocate()中在free list没有可用的区块时，需要用refill()为其重新填充空间，而新的空间是通过chunk_allol()从内存池获得20或小于20个新的节点。
具体看注释。
//参数n已经上调至8的倍数
//返回大小为n的对象，且有时为free list适当的增加节点
template <bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n)
{
int nobjs = 20;
//调用chunk_alloc，尝试获得nobjs个大小为n的区块作为free list的新节点
//nobjs是引用传入，该值会变成分配到的内存区块数量
char * chunk = chunk_alloc(n, nobjs);
obj * __VOLATILE * my_free_list;
obj * result;
obj * current_obj, * next_obj;
int i;
//如果只获得一个区块，则这个区块就分配给调用者用，free list无新节点
if (1 == nobjs) return(chunk);
//否则准备调整free list，纳入新节点。
my_free_list = free_list + FREELIST_INDEX(n);
//在chunk取得的空间内建立free list
result = (obj *)chunk; //这块准备返回给客端
//以下引导free list指向从内存池新配置的空间
//第一个大小为n的区块需要作为refill返回值给客端，再由allocate()返回，作为已分配空间
//故从chunk+n位置开始作为free list
*my_free_list = next_obj = (obj *)(chunk + n);
//剩下的交给适当的free list进行维护。
//将free list的各个节点串接起来。
for (i = 1; ; i++) {//i从1开始，因为第0个要返回给客端。
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.4.5 内存池（memory pool）
使用chunk_alloc()尝试从内存池获得nobjs个大小为n的区块作为free list的新节点给free list使用。
//nobjs是引用传参，n已经上调至8的倍数。
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;//bytes_left为内存池剩余空间
if (bytes_left >= total_bytes) {
//若内存池剩余空间可以满足需求量
//修改内存池起始指针，直接返回原起始指针即可
result = start_free;
start_free += total_bytes;
return(result);
} else if (bytes_left >= size) {
//size是一个区块的大小
//若内存池剩余空间不能完全满足需求量，但足够供应至少一个区块，返回可以分配的量
nobjs = bytes_left/size;//可以分配的区块数
total_bytes = size * nobjs;
result = start_free;
start_free += total_bytes;
return(result);
} else {
//内存池剩余空间连一个区块的大小都无法提供
//需要补充给内存池的空间，向操作系统申请2倍申请空间加上已分配的heapsize/8的内存到内存池
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
// 试着将内存池残余空间分配给适当的free list
if (bytes_left > 0) {
//寻找适当的free list
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;
}
//向操作系统申请2倍申请空间加上已分配的heapsize/8的内存到内存池
start_free = (char *)malloc(bytes_to_get);
if (0 == start_free) {
//分配失败的情况
int i;
obj * __VOLATILE * my_free_list, *p;
//试图寻找适当的free list，即仍有未用区域且区块勾搭的free list
for (i = size; i <= __MAX_BYTES; i += __ALIGN) {
my_free_list = free_list + FREELIST_INDEX(i);
p = *my_free_list;
if (0 != p) {//该free list中仍有未用区块
//调整free list释放未使用区块
*my_free_list = p -> free_list_link;
start_free = (char *)p;
end_free = start_free + i;
//递归调用自身修正nobjs
return(chunk_alloc(size, nobjs));
//任意参与零头都终将被编入适当的free list中备用
}
}
//若真的是没有任何内存可以用了
//调用第一级配置器，试试out-of-memory是否可以做点事
end_free = 0;
start_free = (char *)malloc_alloc::allocate(bytes_to_get);
// This should either throw an
// exception or remedy the situation. Thus we assume it
// succeeded.
}
heap_size += bytes_to_get;
end_free = start_free + bytes_to_get;
//递归调用自身修正nobjs
return(chunk_alloc(size, nobjs));
}
}
对于代码总结一下：
- 1、 内存池有足够大小的空间，则分配申请的空间；
- 2、 内存池没有足够大小的空间，但是至少还能分配一个节点的空间，则能分多少分多少；
- 3、 内存池一个节点都腾不出来，向系统的heap申请2倍于要求大小的空间，在此之间，如果内存池剩余有空间，则放到free-list中去；
- 4、 如果向heap申请空间失败，那么只能看free-list中更大的节点是否有可用空间了，有则用之，同时递归调用自身修正__nobjs；
- 5、 如果free-list也没有可用节点了，那么转向第一级空间配置器申请空间；
- 6、 再不行，第一级空间配置器就抛出bad_alloc异常。
假设客端调用chunk_alloc(32,20),流程图如下：
5 内存基本处理工具
uninitialized_copy(), uninitialized_fill(), uninitialized_fill_n()分别对应于高层次函数copy(), fill(), fill_n()，包含于<memory>。
这些函数都可以使我们将内存配置与对象的构造行为分离开。
5.1 uninitialized_copy
template<class InputIterator,class ForwardIterator>
ForwardIterator uninitialized_copy(InputIterator first,InputIterator last,ForwardIterator result)
作为输出目的地的 [ result, result + ( last - first ) )范围内的每个迭代器都指向未初始化区域，则uninitialized_copy()调用copy construct，将[ first , last )范围内的每个对象的复制品放入输出范围。
有两个特化版本，分别为char*，wchar_t*。
5.2 uninitialized_fill
template<class ForwardIterator,class T>
void uninitialized_fill(ForwardIterator first,ForwardIterator last,const T& x)
作为输出目的地的[ first , last )范围内的每个迭代器都指向未初始化区域，则uninitialized_fill在该范围内每个迭代器i调用construct(&*i, x),产生x的复制品。
5.3 uninitialized_fill_n
template<class ForwardIterator,class size,class T>
ForwardIterator uninitialized_fill_n(ForwardIterator first,size n,const T& x)
作为输出目的地的 [ first, first + n )范围内的每个迭代器都指向未初始化区域，则uninitialized_fill_n在该范围内每个迭代器i调用construct(&*i, x),产生x的复制品。
在实现代码中，若迭代器first的value_type为POD(Plain Old Data也即是标量型别)型别，则对POD采取高阶函数执行，对non-POD采取保险的安全做法。
京公网安备 11010502036488号