好了，经过之前的铺垫，我们终于要正式开始完成Allocator的代码了。在之前，我们先来看一下到底什么是Allocator。
Allocator(分配器)是一个用来管理容器内存的类，由它来负责一个容器内部的内存的分配与释放。
举个例子：
std::vector的完整声明为：
template<typename T, typename Alloc = allocator<T>>
class vector;
可以看到， std::vector有两个模板参数，T代表元素类型， Alloc代表分配器类型。
我们平时使用vector之所以不需要指明Alloc参数是因为它已有默认值。默认的分配器std::allocator<T>负责容器的内存分配与释放。
一个Allocator在C++中必须满足下列条件：
- 内部有一个value_type的类型定义，用来表示元素类型
- 一个构造函数
- 一个template构造函数， 用来实现当类型改变时，内部状态的复制
- 一个成员函数allocate()， 分配内存
- 一个成员函数deallocate(), 释放内存
- 提供分配器的操作符 == 与 !=
可能这些条件看起来有些抽象， 那么我们赶快来实践一下吧。
我们这个STL项目实现的分配器为free_list_allocator，而free_list_allocator由另一个分配器malloc_allocator组成。我们先来实现malloc_allocator，再实现free_list_allocator。顾名思义，malloc_allocator是借助malloc实现的allocator。
template<typename T>
class malloc_allocator
{
public:
typedef T value_type;
private:
//oom: out of memory
static T *oom_malloc(size_t n);
static T *oom_realloc(T *p, size_t n);
static void (*oom_handler)();
public:
malloc_allocator() {}
template<typename U>
malloc_allocator(const malloc_allocator<U>&) {
//no state to copy
}
static T *allocate(std::size_t num);
static T *reallocate(T *p, std::size_t num);
static void deallocate(T *p, std::size_t num);
void (*set_oom_handler(void (*handler)()))();
};
以上是malloc_allocator声明的代码， 我们一步一步分析。
根据上面提到的Allocator的要求， 我们定义类型value_type为T，代表值类型。同时实现分配器的构造函数与模板构造函数，这两个构造函数没有任何代码，因为malloc_allocator没有需要维护的状态。
那么静态变量oom_handler是用来干什么的？
static void (*oom_handler)();
oom 是 out of memory 的缩写，故oom_handler即为一个指向内存不足处理函数的指针。这个内存不足处理函数由分配器的使用者提供，借助分配器的成员函数set_oom_handler()设置。 set_oom_handler声明如下:
void (*set_oom_handler(void (*handler)()))();
set_oom_handler的声明的确有点复杂，实际上set_oom_handler是一个函数，它接受一个函数指针，并且返回一个函数指针。
set_oom_handler实现：
template<typename T>
void (*malloc_allocator<T>::set_oom_handler(void (*handler)()))()
{
auto old_handler = oom_handler;
oom_handler = handler;
return old_handler;
}
set_oom_handler内部逻辑很简单，即接受新的函数指针同时返回旧指针。通过调用它来设置不同的函数来处理内存不足。
接下来我们再来看oom_malloc函数，它用来在内存不足(out of memory)的情况下通过使用oom_handler申请内存。实现如下:
template<typename T>
T *malloc_allocator<T>::oom_malloc(std::size_t n)
{
T *result = static_cast<T*>(malloc(n));
while (result == nullptr)
{
if (oom_handler == nullptr)
throw std::bad_alloc();
oom_handler();
result = static_cast<T*>(malloc(n));
}
return result;
}
oom_malloc首先尝试使用malloc申请 n bytes 的空间，并且将指针转化为T *类型。当结果为 nullptr , 即内存不足时，调用处理函数来获取内存(如果有的话)，否则抛出 bac_alloc 异常。
同理， oom_realloc的实现:
template<typename T>
T *malloc_allocator<T>::oom_realloc(T *p, std::size_t n)
{
T *result = static_cast<T*>(realloc(p, n));
while (result == nullptr)
{
if (oom_handler == nullptr)
throw std::bad_alloc();
oom_handler();
result = static_cast<T*>(realloc(p, n));
}
return result;
}
至此， 我们已经实现了oom_malloc与oom_realloc, 我们现在通过它们实现Allocator最重要的几个函数: allocate(), deallocate()。我们一个一个来。
- allocate(std::size_t num)
template<typename T>
T *malloc_allocator<T>::allocate(std::size_t num)
{
T *result = static_cast<T*>(malloc(num * sizeof(T)));
if (result == nullptr) {
result = oom_malloc(num * sizeof(T));
}
return result;
}
allocate(num)分配num个元素的空间， 如果内存不足就调用oom_malloc。
- reallocate(T *p, std::size_t num)
template<typename T>
T *malloc_allocator<T>::reallocate(T *p, std::size_t num)
{
T *result = static_cast<T*>(realloc(p, num * sizeof(T)));
if (result == nullptr) {
result = oom_realloc(p, num * sizeof(T));
}
return result;
}
我们调用reallocate在指针p所指的区域重新分配num个元素的空间， 如果空间不足则调用oom_realloc。
- deallocate(T *p, std::size_t num)
template<typename T>
void malloc_allocator<T>::deallocate(T *p, std::size_t num)
{
free(p);
}
deallocate负责回收指针p所指的num个元素的内存空间， 其中num参数在此无需使用，我们直接free(p)就好了。
最后一步，我们还需提供 == 与 !=
template<typename T1, typename T2>
bool operator==(const malloc_allocator<T1>&, const malloc_allocator<T2>&)
{
return true;
}
template<typename T1, typename T2>
bool operator!=(const malloc_allocator<T1>&, const malloc_allocator<T2>&)
{
return false;
}
我们将 == 的比较结果一直设为true, 因为我们只关心两个分配器是否采用同一种内存分配策略，而不在乎具体的元素类型。
至此，我们已经实现了自己的第一个分配器了。我们现在可以调用malloc_allocator的allocate()与deallocate()来分配释放内存。
下一篇文章就开始进入free_list_allocator了， 这个分配器的确十分复杂，预计要花很久的时间才能写完。而malloc_allocator 是 free_list_allocator的基础，理解malloc_allocator十分有利于我们接下来的学习。
下一篇 STL in C++11 (Allocator 4)
P.S 谢绝转载，谢谢
