STL allocator是做什么用？
在学习STL中containers会发现C++ STL里定义了很多的容器（containers），每一个容器的第二个模板参数都是allocator类型，而且默认参数都是allocator。但是allocator到底是什么？有什么作用呢？
有关allocator的最重要的事实是它们只是为了一个目的：封装STL容器在内存管理上的低层细节。你不应该在自己的代码中直接调用 allocator 的成员函数，除非正在写一个自己的STL容器。你不应该试图使用allocator来实现operator new[]；这不是allocator该做的。 如果你不确定是否需要使用allocator，那就不要用。
基本上很少有人会自定义一个allocator。一来，默认的allocator已经够用了；二来，确实不知道该怎么用。一般来说，我们没有必要重新定义一个allocator。自定义的方式主要是为了提高内存分配相关操作的性能。而STL提供的方式性能已经足够好了。
浅析STL allocator
一般而言，我们习惯的 C++ 内存配置操作和释放操作是这样的：
class FOO{};
FOO *pf = new FOO;
delete pf;
我们看其中第二行和第三行，虽然都是只有一句，但是都完成了两个动作。但你 new 一个对象的时候两个动作是：先调用::operator new 分配一个对象大小的内存，然后在这个内存上调用FOO::FOO()构造对象。同样，当你 delete 一个对象的时候两个动作是：先调用FOO::~FOO() 析构掉对象，再调用::operator delete将对象所处的内存释放。为了精密分工，STL 将allocator决定将这两个阶段分开。分别用 4 个函数来实现：
1.内存的配置：alloc::allocate();
2.对象的构造：::construct();
3.对象的析构：::destroy();
4.内存的释放：alloc::deallocate();
stl_alloc.h中代码设计的原则如下：
1.向 system heap 要求空间
2.考虑多线程状态
3.考虑内存不足时的应变措施
4.考虑过多“小型区块”可能造成的内存碎片问题。
stl_alloc.h中的代码相当复杂，我们今天只看其中的配置器的工作原理：
考虑到小型区块可能造成内存破碎问题(即形成内存碎片)，SGI STL 设计了双层级配置器。第一层配置器直接使用malloc() 和 free()。第二层配置器则视情况采用不同的策略：当配置区块超过 128 bytes时，调用第一级配置器。当配置区块小于 128 bytes时，采用复杂的 memory pool 方式，需要小的堆在小的存储块的链表上取，需要大的堆在大的存储块的链表上取，某个大小存储块链表预留个数用完后从系统继续申请。
STL 简单 allocator 的实现
其中用到的小知识：
1.ptrdirr_t：
ptrdiff_t是C/C++标准库中定义的一个与机器相关的数据类型。ptrdiff_t类型变量通常用来保存两个指针减法操作的结果。ptrdiff_t定义在stddef.h（cstddef）这个文件内。ptrdiff_t通常被定义为long int类型。
2.non-trivial constructor/destructor：
意思是“非默认构造函数/析构函数”，这里的non-trivial指不是编译器自动生成的（函数）维基百科
我认为trivial更深层次的含义是构造和析构的东西都是在栈上分配的，其内存可以被栈自动回收，所以SGI STL的空间配置器std::alloc在做destroy时会先判断析构对像是不是trivial，如果对象是trivial，证明对象的所有成员分配在栈上，那么为了节省效率，可以不调用析构函数，由栈来自动回收内存。如果对象是non-trivial则需要调用每个对象的析构函数，释放堆上分配的内存。
3.operator new()：
指对new的重载形式，它是一个函数，并不是运算符。对于operator new来说，分为全局重载和类重载，全局重载是void* ::operator new(size_t size)，在类中重载形式 void* A::operator new(size_t size)。还要注意的是这里的operator new()完成的操作一般只是分配内存，事实上系统默认的全局::operator new(size_t size)也只是调用malloc分配内存，并且返回一个void*指针。而构造函数的调用(如果需要)是在new运算符中完成的。
4.由第三点可知，在空间配置器的new操作分为两步：allocate()函数分配内存，construct()函数把分配的内存初始化为一个个的模板类对象。
侯捷老师的书中介绍了空间配置器基本的接口（p43~44）。以下是一个简单的空间配置器实现。
cghAlloc.h：
#ifndef _CGH_ALLOC
#define _CGH_ALLOC
#include <new>
#include <cstddef>
#include <cstdlib>
#include <climits>
#include <iostream>
using namespace std;
namespace CGH {
template<class T>
inline T* _allocate(ptrdiff_t size, T*) {
set_new_handler(0);
T* tmp = (T*) (::operator new((size_t) (size * sizeof(T)))); // size：待分配的元素量，sizeof(T)每个元素的大小
if (tmp == 0) {
cout << "out of memory" << endl;
exit(1);
}
return tmp;
}
template<class T>
inline void _deallocate(T* buffer) {
::operator delete(buffer);
}
template<class T1, class T2>
inline void _construct(T1* p, const T2& value) {
new (p) T1(value); // 调用placement new，在指定的内存位置p处初始化T1对象，初始化T1对象时调用T1的复制构造函数
}
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;
typedef T& reference;
typedef const T& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
template<class U>
struct rebind {
typedef allocator<U> other;
};
pointer allocate(size_type n, const void* hint = 0) {
return _allocate((difference_type) n, (pointer) 0);
}
void deallocate(pointer p, size_type n) {
_deallocate(p);
}
void construct(pointer p, const T& value) {
_construct(p, value);
}
void destroy(pointer p) {
_destroy(p);
}
};
}
#endif
测试空间配置器，allocator.cpp：
// allocator.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "cghAlloc.h"
#include <vector>
#include <iostream>
using namespace::std;
int _tmain(int argc, _TCHAR* argv[])
{
int arr[5] = { 0, 1, 2, 3, 4 };
//unsigned int i;
CGH::allocator<int> test;
CGH::allocator<int> test1;
vector<int, CGH::allocator<int>>iv(arr, arr + 5);
for (int i = 0; i < iv.size(); i++){
cout << iv[i] << ' ';
}
cout << endl;
system("pause");
return 0;
}
