2.1 空间配置器的标准接口

根据 STL 规范，以下是 allocator 的标准接口：

allocator::value_type
allocator::pointer
allocator::const_pointer
allocator::reference
allocator::const_reference
allocator::size_type
allocator::difference_type
allocator::rebind        //一个嵌套的模板类，class rebind<U>拥有唯一成员other
                        //是一个typedef，代表allocator<U>
allocator::allocator()
allocator::allocator(const allocator&)
template<class U>allocator::cllocator<const allocator<U>&)    //泛化的拷贝构造
allocator::~allocator()
pointer allocator::address(reference x)const    //返回某个对象的地址
const_pointer allocator::address(const_reference x)const    //返回某个const对象的地址
//配置空间，足以存储n个T对象，第二个参数是个提示。
pointer allocator::allocate(size_type n, const void* = 0)
void allocator::deallocate(pointer p, size_type n)
size_type allocator::max_size()const    //返回可配置的最大容量
//等同于 new((void*)p) T(x)
void allocator::construct(pointer p, const T& x)
//等同于p->~T()
void allocator::destroy(pointer p)

2.2 具备次配置力的 SGI 空间配置器

SGI STL 的配置器与众不同也与规范不同，其名称是alloc而非allocator，而且不接受任何参数：

vector<int, std::allocator<int>>iv;        //in VC or CB
vector<int, std::alloc>iv;                //in GCC

因为 SGI STL 在声明时已经为每个容器都指定了其默认的空间配置器为alloc，e.g.

template<class T, class Alloc = alloc>
class vector{};

2.2.2 SGI 空间配置器 std::alloc

allocator只是基层内存配置/释放行为，即::operator new和::operator delete的一层薄薄的封装，效率不佳。SGI 采用的实际上是std::alloc。

• 内存配置由alloc::allocate()负责，
• 内存释放由alloc::deallocate()负责，
• 对象构造由::construct()负责，
• 对象析构由::destroy()负责。

2.2.3 构造和析构基本工具

#include <new.h>        //欲使用placement new，需先包含此文件
template cclass T1,class T2>
inline void construct ( T1* p, const T2& value) {
    new (p)T1(value);     //placement new;调用Tl::T1(value) ;
}
//以下是destroy ()）第一版本，接受一个指针
template <class T>
inline void destroy (T* pointer) {
    pointer->~T ();//调用dtor ~T()
}
//以下是 destroy ()第二版本，接受两个迭代器。
//此函数设法找出元素的数值型别,进而利用_type_traits<>求取最适当措施
template <class ForwardIterator>
inline void destroy (Forwarditerator first，ForwardIterator last){
    __destroy (first, last, value_type(first));
}
//判断元素的数值型别(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());
}
//如果元素的数值型别（ value type)有non-trivial destructor
template <class ForwardIterator>
inline void
__destroy_aux (Forwardlterator 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){}
//以下是destroy ( )第二版本针对迭代器为char*和wchar_t*的特化版
inline void destroy(char* , char* ) { }
inline void destroy ( wchar_t* , wchar_t* ) { }

construct()接受一个指针 p 和一个初值 value，该函数的用途就是将初值设定到指针所指的空间上，C++的placement new运算子可以完成这一任务。

destroy()有两个版本：

• 第一版本：接受一个指针，将该指针所指之物析构掉，直接调用析构函数即可；
• 第二版本：接受first和last两个迭代器，准备将[first, last)范围内的所有对象析构掉。我们不知道该范围有多大，如果范围很大而每个对象的析构函数都是 trivial 的，那么调用这些 trivial 的构造函数效率很低。所以要先利用value_type()获得迭代器所指对象的型别，再利用__type_traits<T>判断该型别的析构函数是否 trivial：
  • 是 trivial 的(__true_type)，则什么也不做，空函数体；
  • 不是 trivial 的(__false_type)，以循环方式遍历整个范围并对每个对象调用第一个版本的destroy()。

2.2.4 空间的配置与释放，std::alloc

C++的内存配置和释放基本操作是::operator new和::operator delete，相当于 C 的malloc()和free()，所以 SGI 以**malloc()**和**free()**完成内存的配置和释放。

考虑到小型区块可能造成内存碎片问题，SGI 设计了双层配置器：

• 第一级配置器直接使用**malloc()**和**free()**；
• 第二级配置器视情况采用不同策略：
  • 当配置区块超过 128 bytes 时，视为足够大，便调用第一级配置器；
  • 当配置区块小于 128 bytes 时，视为过小，为了降低额外负担，采用复杂的 memory pool 整理方式。

整个配置器系统设计究竟只开放第一级配置器，或是同时开房第二级配置器，取决于__USE_MALLOC是否被定义。
无论alloc被定义为第一级或第二级配置器，SGI 还为它包装了一个接口如下：

template<class T, class Alloc>
class simple_alloc{
public:
    static T *allocate (size_t n){
        return 0 == n? 0 : (T*) Alloc::allocate(n * sizeof (T));
    }
    static T *a1locate (void){
        return (T*) Alloc::allocate(sizeof(T));
    }
    static void deallocate (T *p, size_t n){
        if （0 != n)
            Alloc::deallocate(p, n*sizeof(T));
    }
    static void dea11ocate (T *p){
        Alloc : :deallocate(p, sizeof(T));
    }
};

其内部四个成员其实都是单纯的转调用，调用传递给配置器(可能是一级或二级)的成员函数。该接口使得配置器的配置单位从 bytes 转为个别元素的大小：**sizeof(T)**。SGI STL 容器全部采用这个simple_alloc接口：

2.2.5 第一级配置器 __malloc_alloc_template

template<int inst>
class _malloc_alloc_template
{
    /* oom_alloc为静态函数成员,用于处理malloc时的内存不足问题
       oom_realloc为静态函数成员，用于处理realloc时的内存不足问题
       _malloc_alloc_handler为静态数据成员,为void(*)()类型的函数指针,用于用户自
       己制定内存分配策略
       oom = out-of-memory
    */
    static void * oom_malloc(size_t);//out_of_memmory malloc
    static void * oom_realloc(void *, size_t);
    static void(*_malloc_alloc_oom_handler)();
public:
    static void * allocate(size_t n)
    {
        void * result = malloc(n);//请求内存
        if (result == nullptr)//如果内存不足
            result=oom_malloc(n);//调用oom_malloc
        return result;
    }
    static void * reallocate(void * p, size_t n)
    {
        void *result = realloc(n);
        if (result == nullptr)
            result = oom_realloc(p, n);
        return result;
    }
    static void deallocate(void * p)
    {
        //使用free函数释放p地址后所分配的内存块
        free(p);
    }
    /*此静态成员函数接受一个void(*)()类型的函数指针作为参数,返回
    void(*)()类型的函数指针。其作用为用用户自己定制的内存调度方法替换
    _malloc_alloc_handler,由此实现类似C++的set_new_handler方法。
    */
    static void(* set_malloc_handler(void(*f)()))()
    {
        void(*old)() = _malloc_alloc_oom_handler;
        _malloc_alloc_oom_handler = f;
        return old;
    }
};
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_oom_handler)();
    void * result;
    //无限循环，直至成功分配内存或用户没有定制内存分配策略
    for (;;)
    {
        my_oom_handler = _malloc_alloc_oom_handler;
        if (my_oom_handler == nullptr)//如果用户没有定制内存分配策略
            exit(1);
        (*my_oom_handler)();//使用用户定制的方法
        result = malloc(n);
        if (result)
            return result;
    }
}
template<int inst>
void * _malloc_alloc_template<inst>::oom_realloc(void * p, size_t n)
{
    //此函数的设计思路与oom_malloc如出一辙
    void(*my_oom_handler)();
    void * result;
    for (;;)
    {
        my_oom_handler = _malloc_alloc_oom_handler;
        if (my_oom_handler == nullptr)
            exit(1);
        (*my_oom_handler)();
        result = realloc(p,n);
        if (result)
            return result;
    }
}

SGI 以**malloc()**而非**::operator new**来配置内存，因为 C++ 并未提供相应于**realloc()**的内存配置操作。因此 SGI 不能直接使用 C++ 的**set_new_handler()**在内存配置需求无法被满足的时候调用处理函数，而只能通过函数指针模拟出这一行为。

HINT：SGI 的第一级配置器的allocate()和realloc()都是在调用malloc()和realloc()不成功后，改调用**oom_malloc()**和**oom_realloc()**。后两者内部都有循环，不断调用内存不足处理例程，期望在某次调用之后获得足够的内存完成任务。但是如果客户没有设定内存不足处理例程，这二者就会调用**__THROW_BAD_ALLOC**，丢出**bad_alloc**异常信息，或利用**exit(1)**终止程序。

2.2.6 第二级配置器 __default_alloc_template

第二级配置器增加了一些机制，避免太多小额区块造成内存碎片。配置空间时会有一个额外区块用于管理配置出来的内存，这是无法避免的，但是配置的区块越小，额外区块占比就越大，越显得浪费：

SGI 第二级配置器的做法是：

• 如果区块超过 128 bytes，就移交第一级配置器处理；

• 如果区块小于 128 bytes时，则以内存池(memory pool)管理，又称次级配置：每次配置一大块内存，并维护对应的 free-list。下次若再有相同大小的内存需求，直接从 free-lists 中拨出。如果释放了小额区块，由配置器回收到 free-lists 中。SGI 第二级配置器会自动将任何小额区块的内心需求量调整为 8 的倍数，并维护 16 个 free-lists，各自管理大小分别为8,16,24, 32, 40, 48, 56, 64, 75, 80, 88, 96, 104, 112, 120,128 bytes 的小额区块。

  free-lists 的结构如下：

  //一物两用，保存下一个free_list的指针,也保存实际区块的内容
  union obj
  {
    union obj * free_list_link;
    char client_data[1];
  }

  
  这种实现原理有独特的艺术：由于 free-lists 中维护的是空闲节点，所以一旦被使用(不再空闲)就是以第二行的形式出现，当是空闲的时候就以第一行的形式出现作为链表中的节点(指针)。所以同一时刻只能是二者之一。 ```cpp enum{ALIGN = 8}; //小型区块的上调边界 enum{MAX_BYTES = 128}; //小型区块的上限 enum{NFREELISTS = MAX_BYTES/__ALIGN}; //free-lists 个数

//以下是第二级配置器 //notice:没有”template”类型参数，第二个参数没有派上用处 //第一个参数用于多线程环境下,目前不讨论 template class default_alloc_template { private: //ROUND_UP()将bytes提升至8的倍数 static size_t ROUND_UP(size_t bytes) { return ((bytes + ALIGN - 1) & ~(ALIGN - 1)); } private: union obj //free_lists节点构造 { union obj free_list_link; char client_data[1]; }; private: //16个free_lists static obj volatile free_list[NFREELISTS]; //根据区块大小，决定使用第n号free-list, n从1算 static size_t FREELIST_INDEX(size_t bytes) { return (((bytes) + ALIGN - 1) / ALIGN - 1); } //返回一个大小为n的对象，并可能加入大小为n的其他区块到free list 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;    //内存池起始位置
static char *end_free;      //内存池结束位置
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); }; template char *__default_alloc_template::start_free = 0;

template char *__default_alloc_template::end_free = 0;

template size_t __default_alloc_template::heap_size = 0;

template typename default_alloc_template::obj * volatile default_alloc_template::free_list[__NFREELISTS] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};

<a name="T9gqI"></a>
## 2.2.7 空间配置函数 allocate()
作为一个配置器，`__default_alloc_template`拥有配置器的标准接口函数`allocate()`。此函数首先判断区块大小，大于 128 bytes 就调用第一级配置器，小于 128 bytes 就检查对应的 free-lists。若有可用区块就拿来用，若没有则将区块大小上调至 8 倍数边界，然后调用`refill()`，准备为 free-lists重新填充空间。
```cpp
static void* allocate(size_t size){
    // 如果大于128bytes，交给第一级配置器
    if (size > (size_t)__MAX_BYTES){
        return malloc_alloc::allocate(size);
    }
    obj* result = nullptr;
    obj* volatile* my_free_list = nullptr;
    //寻找 16 个 free-lists 中合适的一个
    my_free_list = free_list + FREELIST_INDEX(size);
    result = *my_free_list;
    if (nullptr == result){
        //没有找到合适的，准备重新填充 free-list
        void* r = refill(ROUND_UP(size));
        return r;
    }
    //    调整 free-list
    *my_free_list = result->free_list_link;
    return result;
}

2.2.8 空间释放函数 deallocate()

作为一个配置器，__default_alloc_template拥有配置器的标准接口函数deallocate()。首先判断区块大小，大于 128 bytes 就调用第一级配置器，小于 128 bytes 就找出对应的 free-lists，将区块回收

static void deallocate(void* p, size_t n){
    if (n > (size_t)__MAX_BYTES){
        return malloc_alloc::deallocate(p, n);
    }
    obj* q = (obj*)p;
    obj* volatile* my_free_list = nullptr;
    // 寻找相应的free_list
    my_free_list = free_list + FREELIST_INDEX(n);
    // 头插法，回收区块
    q->free_list_link = *my_free_list;
    *my_free_list = q;
}

2.2.9 重新填充 free lists

当allocate()发现 free-lists 中没有可用区块时，就调用**refill()**，为 free-list 重新填充空间，新的空间将取自内存池(经过**chunk_alloc()**完成)，默认获得 20 个新区块，如果内存池空间不足也可能小于 20。

template<bool threads, int inst>
static void* __default_alloc_template<thread, inst>::refill(size_t n){
    int nobjs = 20;
    //调用chunk_alloc()，尝试获得nobjs个区块作为free-list的新节点
    //注意参数是引用传递
    char* chunk = chunk_alloc(n, nobjs);
    obj* volatile* my_free_list = nullptr;
    obj* result = (obj*)chunk;
    obj* current_obj = nullptr;
    obj* next_obj = nullptr;
    int i = 0;
    //如果只获得一个区块，就分配给调用者使用，free-list无新增节点
    if (1 == nobjs) return chunk;
    //得到不止一个区块，准备调整free-list，纳入新节点
    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 (i == nobjs - 1)
        {
            current_obj->free_list_link = nullptr;
            break;
        }
        current_obj->free_list_link = next_obj;
    }
    return (result);
}

2.2.10 内存池(memory pool)

chunk_alloc()负责从内存池中取空间给 free-list 使用：

// 配置一大块空间，可以容纳nobjs个size大小的区块
// 如果配置nobjs个区块有所不便，nobjs会做出相应改变
static char* chunk_alloc(size_t size, int& nobjs){
    char* result = nullptr;
    // 需要空间的总大小
    size_t total_bytes = size * nobjs;
    // 内存池剩余空间
    size_t bytes_left = end_free - start_free;
    // 如果内存池剩余空间满足需要空间
    if (bytes_left >= total_bytes){
        result = start_free;
        start_free = start_free + total_bytes;
        return (result);
    }else if (bytes_left >= size){
        // 如果剩余空间只够1个以上的块（但小于总需求）
        //就修正nobjs(得益于传引用)只返回当前能提供的区块数
        nobjs = bytes_left / size;
        result = start_free;
        start_free = start_free + total_bytes;
        return result;
    }else{
        // 如果连一块空间都不够，先声明一个将要向堆区申请的变量
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        // 尝试将剩下的一点点空间再利用
        if (bytes_left > 0){
            // 将剩余空间配置给合适的free_list
            // 声明了一个指针，指向了一个 volatile 指针，该指针指向 obj
            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;
        }
        // 配置heap空间，补充内存池
        start_free = (char*)malloc(bytes_to_get);
        if (nullptr == start_free){
            //堆内存无法满足分配，检查free-lists中有没有空闲节点，将它释放并用作分配
            obj* volatile* my_free_list = nullptr;
            obj* p = nullptr;
            for (int i = size; i <= __MAX_BYTES; i += __ALIGN){
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;
                if (nullptr != p){
                    *my_free_list = p->free_list_link;
                    start_free = (char*)p;
                    end_free = start_free + i;
                    //递归调用自己，以修正nobjs
                    return chunk_alloc(size, nobjs);
                }
            }
            end_free = 0;//到处都没有内存可用了，调用第一级配置器看oom是否有用
            start_free = (char*)malloc_alloc::allocate(bytes_to_get);
        }
        // 修正内存池的结束位置和总大小
        end_free = start_free + bytes_to_get;
        heap_size += bytes_to_get;
        // 递归调用自己，修正nobjs
        return chunk_alloc(size, nobjs);
    }
}

e.g. 见图，假设程序一开始，客端就调用chunk_alloc(32,20)，于是malloc()配置 40 个 32 bytes区块，其中第 1 个交出，另 19 个交给free_list[3]维护，余 20 个留给内存池。接下来客端调用chunk_alloc(64,20)，此时free_list [7]空空如也，必须向内存池要求支持。内存池只够供应(32*20)/64=10 个 64 bytes 区块，就把这 10 个区块返回，第 1 个交给客端，余9个由free_list [7]维护。此时内存池全空。接下来再调用chunk_alloc( 96，20)，此时**free_list[11]**空空如也，必须向内存池要求支持，而内存池此时也是空的，于是以malloc()配置 40+n(附加量)个96 bytes区块，其中第 1 个交出，另 19 个交给free_list[11]维护，余 20+n(附加量)个区块留给内存池

2.3 内存基本处理工具

STL 有五个全局函数作用于未初始化空间上：

• construct()
• destroy()
• uninitialized_copy()——copy()
• uninitialized_fill()——fill()
• uninitialized_fill_n()——fill_n()
• 
  ```cpp template ForwardIterator uninitialized_copy(InputIterator first,

                              InputIterator last, ForwardIterator result);

template ForwardIterator uninitialized_fill(ForwardIterator first, ForwardIterator last, const T& x);

template ForwardIterator uninitialized_fill_n(InputIterator first, Size n, const T& x);

三者都可以将**内存配置**与**对象构造行为**分离开。
<a name="Bbzod"></a>
## 2.3.1 uninitialized_fill_n 实现
```cpp
template<class ForwardIterator, class Size, class T>
ForwardIterator uninitialized_fill_n(InputIterator first, Size n, const T& x){
    return __uninitialized_fill_n(first, n, x, value_type(first));
}

首先萃取处迭代器first的value type，然后判断该型别是否是 POD 型别。
POD 型别：Plain Old Data，即标量型别或传统 C struct 型别。
POD 型别必然拥有trivial ctor/dtor/copy/assignment 函数。因此可以针对 POD 型别采用最有效率的初值填写手法，而且 non-POD 型别采取最保险安全的做法：

• 针对 POD 型别：调用高阶函数fill_n()；
• 针对非 POD 型别：使用循环针对每个变量调用construct()->placement new~

2.3.2 uninitialized_copy 实现

大致与uninitialized_fill_n()相同，只不过在value_type为 POD 型别时，调用的是copy()函数。
而且针对**char***和**wchar_t**，可以采用最具效率的**memmove()**直接移动内存内容来执行复制行为，所以针对这两种类型有特化版本。

2.3.3 uninitialized_fill 实现

在value_type为 POD 型别时，调用的是fill()函数。

HINT：注意uninitialized_fill()的两个特化版本中用的是memmove()而不是memcpy()。这两者的功效是一样的，区别在于memcpy()的第二个参数有restrict限定词(意即memcpy()假定两块内存区域没有重叠)，导致memcpy()在两个参数有重叠部分时结果不可预知，而memmove()可以保证完成任务。