STL——空间配置器（构造和析构基本工具）

以STL的运用角度而言，空间配置器是最不需要介绍的东西，它总是隐藏在一切组件（更具体地说是指容器，container）的背后，默默工作，默默付出。但若以STL的实现角度而言，第一个需要介绍的就是空间配置器，因为整个STL的操作对象（所有的数据）都存放在容器之内，而容器一定需要配置空间以置放资料。

为什么不说allocator是内存配置器而说它是空间配置器呢？因为空间不一定是内存，空间也可以是磁盘或其它辅助存储介质。是的，你可以一个allocator，直接向硬盘取空间，以下介绍的是SGI STL提供的配置器，配置的对象是内存。

空间配置器的标准接口

根据STL的规范，以下是allocator的必要接口：

allocator::value_type
allocator::pointer
allocator::const_pointer
allocator::reference
allocator::const_reference
allocator::size_type
allocator::difference_type

allocator::rebind
一个嵌套的class template，class rebind<U>拥有唯一的成员other，那是一个typedef，代表allocator<U>

allocator::allocator()
default constuctor

allocator::allocator(const allocator&)
copy constructor

template<class U>allocator::allocator(const allocator<U>&)
泛化的copy constructor

allocator::~allocator()
destructor

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对象，第二参数是个提示，实际上可能会利用它来增进区域性，或完全忽略之

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

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

void allocator::construct(pointer p,const T& x)
等同于 new((void*)p) T(x)     placement new

void allocator::destroy(pointer p)
等同于p->~T()

SGI 空间配置器

SGI STL的配置器与众不同，它与标准规范不同。如果要在程序中明白采用SGI配置器，那么应该这样写：

vector<int, std::alloc> iv; //gcc编译器

配置器名字为alloc,不接受任何参数。标准配置器的名字是allocator，而且可以接受参数。比如VC中写法：

vector<int, std::allocator<int> > iv; //VC编译器

SGI STL的每一个容器都已经指定了缺省配置其alloc。我们很少需要自己去指定空间配置器。比如vector容器的声明：

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

SGI标准的空间配置器allocator

其实SGI也定义了一个符合部分标准，名为allocator的配置器，但是它自己不使用，也不建议我们使用，主要原因是效率不佳。它只是把C++的操作符::operator new和::operator delete做了一层简单的封装而已。下面仅仅贴出代码：

#ifndef DEFALLOC_H
#define DEFALLOC_H

#include <new.h>
#include <stddef.h>
#include <stdlib.h>
#include <limits.h>
#include <iostream.h>
#include <algobase.h>

//仅仅是简单的封装了operator new
template <class T>
inline T* allocate(ptrdiff_t size, T*) {
    set_new_handler();
    T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));
    if (tmp == ) {
    cerr << "out of memory" << endl;
    exit();
    }
    return tmp;
}

//仅仅是简单的封装了operator::delete
template <class T>
inline void deallocate(T* buffer) {
    ::operator delete(buffer);
}

template <class T>
class allocator {
public:
    typedef T value_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;

    pointer allocate(size_type n) {
    return ::allocate((difference_type)n, (pointer));
    }
    void deallocate(pointer p) { ::deallocate(p); }
    pointer address(reference x) { return (pointer)&x; }
    const_pointer const_address(const_reference x) {
    return (const_pointer)&x;
    }
    size_type init_page_size() {
    return max(size_type(), size_type(/sizeof(T)));
    }
    size_type max_size() const {
    return max(size_type(), size_type(UINT_MAX/sizeof(T)));
    }
};

class allocator<void> {
public:
    typedef void* pointer;
};

#endif

SGI特殊的空间配置器alloc

一般而言，我们所习惯的C++内存配置器操作和释放操作时这样的：

class FOO { ...};
FOO* pf=new FOO;  //配置内存，然后构造对象
delete pf;  //将对象析构，然后释放内存

这其中的

new算式内含两个阶段操作：

（1）调用::operator new 配置内存

（2）调用FOO::FOO()构造对象内容

delete算式也内含两个阶段操作：

（1）调用FOO::~FOO()对对象析构

（2）调用::operator delete释放内存

为了精密分工，SGI allocator将两个阶段分开：

内存配置操作由alloc:allocate负责，内存释放由alloc:deallocate负责；对象构造操作由::contructor()负责，对象析构由::destroy()负责。

STL标准告诉我们，配置器定义在头文件<memory>中，它里面又包括两个文件：

#include <stl_alloc.h>		// 负责内存空间的配置和器释放
#include <stl_construct.h>		// 负责对象的构造和析构

内存空间的配置/释放与对象内容的构造/析构，分别落在这两个文件身上。其中<stl_construct.h>定义了两个基本函数：构造用的construct()和析构用的destroy().

下图显示了其结构：

图一 头文件 <memory>结构

构造函数析构的基本工具：construct()和destroy()

下面是<stl_constuct.h>的部分内容：

函数construct()使用了定位new操作符，其源代码：

template <class T1, class T2>
inline void construct(T1* p, const T2& value) {
  new (p) T1(value);     // 定为new操作符placement new; 在指针p所指处构造对象
}

函数destroy则有两个版本。

第一个版本较简单，接受一个指针作为参数，直接调用对象的析构函数即可，其源代码：

template <class T>
inline void destroy(T* pointer) {
    pointer->~T();    // 调用析构函数
}

第二个版本，其参数接受两个迭代器，将两个迭代器所指范围内的所有对象析构掉。而且，它采用了一种特别的技术：依据元素的型别，判断其是否有trivial destructor（无用的析构函数）进行不同的处理。这也是为了效率考虑。因为如果每个对象的析构函数都是trivial的，那么调用这些毫无作用的析构函数会对效率造成影响。

下面看其源代码：

// 以下是 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）有 trivial destructor…
template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator, ForwardIterator, __true_type) {}//不调用析构函数

// 如果元素的数值型別（value type）有 non-trivial destructor…
template <class ForwardIterator>
inline void
__destroy_aux(ForwardIterator first, ForwardIterator last, __false_type) {
  for ( ; first < last; ++first)
    destroy(&*first);//调用析构函数
}

第二版本还针对迭代器为char*和wchar_t*定义了特化版本：

inline void destroy(char*, char*) {}
inline void destroy(wchar_t*, wchar_t*) {}

图二显示了这两个函数的结构和功能。他们被包含在头文件stl_construct.h中。

图二 函数construct()和destroy()示意图

这两个座位构造、析构之用的函数被设计为全局函数，符号STL的规范。此外，STL还规定配置器必须拥有名为construct()和destroy()的两个成员函数。

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

destroy()有两个版本，第一版本接受一个指针，准备将该指针所指之物析构掉。这很简单，直接调用该对象的析构函数即可。第二版本接受first和last迭代器，准备将[first,last)范围内的所以对象析构掉。我们不知道这个范围有多大，万一很大，而每个对象的析构函数都无关痛痒（所谓的trivial destructor），那么一次次调用这些无关痛痒的析构函数，对效率是一种伤害。因此，这里先利用value_type()获得迭代器所指对象的型别，再利用_type_traits<T>判断该型别的析构函数是否无关痛痒。若是（_true_type），则什么也不做就结束；若否，（_false_type），这才以循环方式巡访整个范围，并在循环中每经历一个对象就调用一个版本的destroy().