STL源码分析读书笔记--第二章--空间配置器（allocator）

声明：侯捷先生的STL源码剖析第二章个人感觉讲得蛮乱的，而且跟第三章有关，建议看完第三章再看第二章，网上有人上传了一篇读书笔记，觉得这个读书笔记的内容和编排还不错，我的这篇总结基本就延续了该读书笔记的框架，如果发现有雷同，请勿见怪，这篇文章只是我的个人记录，算不上原创，只是更多的想把概念描述清楚，所以如果您觉得有copy之嫌的话请绕道看您觉得的原链接。在第8部分给出了笔记的参考链接。

1.allocator 作用

STL的组件（容器）都需要配置空间以放置资料。这个就是allocator的作用。很简单，实现起来却是最麻烦的。

2.allocator 的标准接口

相关型别（参考读书笔记第三章相关型别的概念）

allocator::value_type //所指对象的型别

allocator::pointer //指向对象的指针

allocator::const_pointer //指向对象的常量指针

allocator::reference //对所指对象的引用

allocator::const_reference

allocator::size_type //顾名思义，空间度量

allocator::difference_type //距离度量

allocator类本身的构造与析构

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, cosnt void* = 0) --- 配置空间，足以储存n个T对象。第二自变量是个提示。实作上可能会利用它来增进区域性（locality），或完全忽略之。

void allocator::deallocate(pointer p, size_type n) ---归还先前分配的空间。

size_type allocator::max_size() const --- 传回可成功分配的最大量。

construct和destroy函数（获得了空间之后在空间上构建对象）

3.几点说明

STL源码分析分析的是SGI版本，SGI版本有个符合部分标准的名为allocator的不接受任何参数的配置器，但是SGI没用它，因为效率不佳，只是对全局new和全局delete的一个封装而已，此配置器的全貌在书中有，不做说明。SGI特殊的空间配置器是std::alloc，为什么它的效率高，有一个原因就是它将内存的配置和对象的构造区分开来了。我们知道，对于下面代码中的new 和delete，
Class Foo{
......
}
 
Foo *of = new Foo;//配置内存，然后构造对象
Delete pf;//将对象析构，然后释放内存
 
其中的new实际上分两步，delete也分两步，以new为例，先调用::operator new配置空间，然后在空间上面构造对象，现在std::alloc对这两步分别特殊实现，以保证高效。

4.std::allocator总览

这幅图是自解释的，看过源码的都知道，这三个文件在memory中被包含进来了，在第2部分也大概说明了stl_alloc.h和stl_construct.h的作用，但是stl_uninitialized.h的作用却没提，它们不属于配置器的内容，但接下来会讲到它们的重要作用。

5.std::alloc的构造与析构基本工具：construct()和destroy()

construct()

construct()没啥好说的，调用placement new即可。

destroy()

这个就有讲究，讲究是效率，它有两个版本，第一个版本接受一个指针参数，这个版本直接调用该对象的析构函数即可，不管这个对象的析构函数是否为non-trivial，开销影响都不大，但是对于第二个版本，它接受一个迭代器区间，那么就得确定对象的析构函数是否有意义，如果没意义，且区间很长，那么这种浪费是不能容忍的，因此，destroy针对这种情况作了优化，主要方法是先获取迭代器所指对象型别，然后通过traits获得对象的一个相关型别：一个是否有non-trivial析构函数的非独立名字。当然要实现这一功能，类中一定声明了这个内嵌型别声明。具体代码如下：

//以下是destroy()的第二版本，接受两个迭代器，准备将[first, last)范围内的所有物件析    //构掉，因为不知道这个范围有多大，万一很大，但是每个物件的析构函数都是无关痛    //痒的（triaval destructor），那么一次次呼叫这些无关痛痒的析构函数，对效率是一种损    //害，所以此函数设法找出元素的数值类型，进而利用__type_traits<>选    //择适当措    //施

template <class ForwardIterator>

// __false_type表明是具有non trivial destructor，所以要循环调用destroy

inline void  __destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {

  for ( ; first < last; ++first)

    destroy(&*first);

template <class ForwardIterator>

//__true_type表明是具有trivial destructor不需要调用destroy

inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {} //空函数体

//判断元素的型别，是否有trival 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());

template <class ForwardIterator>

inline void destroy(ForwardIterator first, ForwardIterator last) {

  __destroy(first, last, value_type(first));

//以下是destroy()第二版本针对迭代器为char*和wchar*的特化版

Inline void destroy(char*, char*){}

Inline void destroy(wchar_t*, wcht_t*){}

上述代码中，value_type和traits的实现机制在第三章中有描述。可以看到，destroy()只是包装函数而已，实现时在__destroy()那里编译器分流，然后由__destroy_aux来具体实现。

6.空间的配置与释放,std::alloc

空间配置与释放代码在<stl_alloc.h>中

SGI对此的设计哲学：

向system heap申请空间；

考虑多线程情况；--这个书上没多讲

考虑内存不足时的应对措施；

考虑过多小型区块可能造成的内存碎片（fragment）问题；--SGI为此决定设计双层配置器

关于双层配置器

考虑小型区块可能造成的内存碎片问题，SGI设计了双层级配置器，低一级分配器直接使用malloc()和free(), 第二级分配器则视情况采用不同策略：当分配区块超过128bytes，则视之“足够大”，便使用低一级分配器；当分配区块小于128bytes，则视之“过小”，便采用复杂的mempool方式。在mempool里面设计算法以防止内存破碎。
第一级配置器：__malloc_alloc_template
第一级配置器很简单，主要注意两点：其一，它实际上调用C底层那些函数，比如malloc，free,realloc；其二，要用new-handler机制解决内存不足时出现的状况代码如下：
#if 0
#    include<new>
#     define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
#    include <iostream.h>
#    define __THROW_BAD_ALLOC cerr<<"out of memory"<<endl;exit(1)
#endif
 
//注意，无「template 型别参数」。至于「非型别参数」inst，完全没派上用场。 
template <int inst>   
class __malloc_alloc_template { 
 
private: 
//以下都是函数指针，所代表的函式将用来处理内存不足的情况。 
// oom : out of memory. 
static void *oom_malloc(size_t); 
static void *oom_realloc(void *, size_t); 
static void (* __malloc_alloc_oom_handler)();
 
public: 
 
static void * allocate(size_t n) 
{ 
    void  *result =malloc(n);//第一级配置器直接使用 malloc() 
    // 以下，无法满足需求时，改用 oom_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() 
    // 以下，无法满足需求时，改用 oom_realloc() 
    if (0 == result) result = oom_realloc(p, new_sz); 
    return  result; 
} 
 
//以下模拟 C++的 set_new_handler(). 换句话说，你可以透过它， 
//指定你自己的 out-of-memory handler 
static void (* set_malloc_handler(void (*f)()))()//蓝色部分作为参数，最后一个()和void(*)                                    //一起组成void(*)()表示返回值是一个函数指针
{ 
    void  (*  old)()  =  __malloc_alloc_oom_handler; 
__malloc_alloc_oom_handler = f; 
    return(old); 
} 
}; 
 
// malloc_alloc out-of-memory handling 
//初值为 0。有待用户设定。 __malloc_alloc_oom_handler是一个函数指针
template <int inst> 
void (* __malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0; 
 
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); 
    } 
} 
 
//注意，以下直接将参数 inst指定为 0。 
typedef __malloc_alloc_template<0> malloc_alloc;
第二级配置器：
如果区块比较小，就移交第二级配置器，采用内存池的思想管理内存，即每次配置一大块内存，然后维护对应之自由链表（就是可以空间链表）SGI维护16个链表，分别管理大小依次为8,16，24,….,128bytes的小额区块。freelist的结构如下（以union来设计list自然是为了节省空间，原理见书上，略过不谈）：
union obj { 
       union obj * free_list_link; 
       char  client_data[1];   /* The client sees this.标志是否被使用 */ 
 };
很自然一件事就是，如果我们申请空间成功，那么从free-list中拿来即可，如果申请不成功呢？
答案是调用refill() 函数重新分配空间，当要释放空间时，就将空间重现挂接回free-list.
刚才说到refill()，refill函数获得的空间由chunk_alloc()函数经由memory pool获得，缺省取得20个新节点，如果能获得足够的空间，自然是直接返回新节点然后串接到free-list上，如果只获得一个节点，直接返回给需要的地方使用，如果一个都得不到，那么调用malloc从system heap上重新申请空间加入到memory pool中重新chunk，然后返回，调用malloc的次数越多，从system heap 上申请的空间就越多，如果malloc都申请不到，那么看malloc的out of memory机制能否申请到，实在申请不到且从其他大小的free-list上也抠不下来内存的话一般发出bad_alloc异常。

代码比较复杂，见书上。

7.内存处理的基本工具

uninitialized_copy
uninitialized_fill
unintialized_fill_n

这几个函数都是全局的，作用与未初始化的空间之上，这三个函数都满足要么成功构造，要么不构造任何元素这一约束，因此具有一定的安全保证，他们实际都是调用的的其他的函数，比如，uninitialized_copy有一种实现就是是在未初始化内存上调用复制函数constructor(…)复制对象，用它来构造函数具有安全性，防止构造中出现问题。uinitialized_fill的一种实现是是在未初始化内存上调用初始化函数construct（&*i,x),uninitialized_fill_n顾名思义是批量初始化操作。更详细的解释看书上即可。附上书中一张自解释的图吧。

8.参考

源码剖析原书
网传笔记

9.说明