前言

分配器（Allocator）是对堆内存管理的方法进行封装的类，在整个C++标准库，尤其是STL容器中被广泛使用。绝大数情况下，我们都是使用默认的分配器std::allocator，但其实我们可以自定义分配器，并将其应用到容器中。自定义分配器的理由可能有以下几种：

有些嵌入式平台没有提供默认的malloc、free等底层堆内存管理函数，你需要继承std::allocator，并封装自定义版本的malloc、free等底层堆内存管理函数；
std::allocator的性能表现不能满足具体场景的需求；

类型别名

定义类型别名，可以根据需要自行定义：

using value_type = T;
using pointer = T *;
using const_pointer = const T *;
using reference = T &;
using const_reference = const T&;
using size_type = size_t;
using difference_type = ptrdiff_t;
using const_void_pointer = const void *;

内置绑定机制

分配器类包含一个名为rebind的结构体成员，其构成如下：

template <typename T>
class MyAllocator {
public:
    ...
    template <typename U>
    struct rebind {
        using other = MyAllocator<U>;
    };
    ...
}

其作用是为与类型T有关但又不同的类型U提供相同的（同族）分配器。需要提供rebind的理由大概有如下三点：

给到容器的分配器是一个模板的实例，如std::list<int, std::allocator<int>> l;，容器本身不知道（也不应该知道）分配器的基础模板（base templates）是什么，具体是怎么实现的也不需要关心；
而容器中很多时候不只是会对类型T分配内存，还需要对与T相关的类型U分配内存，如链表std::list<int> 还需要对结点类型Node<int>分配内存；
而容器希望对类型U分配内存的操作可以和类型T使用相同的分配器；

这时候rebind的作用就体现出来了，对于一个std::allocator<T>和一个相关类型U，有std::allocator<U>与std::allocator<T>::rebind<U>::other 相当。我们常为U的分配器定义这样的类型别名：

using U_alloc_type = typename std::allocator<T>::template rebind<U>::other;

这里的语法有几点需要解释一下：

rebind是类模板std::allocator的从属名称，为了表征rebind也是一个模板，需要在其前加上template关键字；
other是模板rebind的从属名称，所以是类模板std::allocator的嵌套从属名称，为了表明嵌套从属名称是一个类型，需要使用typename关键字。详见这里；

必要的接口实现

内存分配/释放接口

pointer allocate(size_type n);
pointer allocate(size_type n, const_void_pointer hint = 0);
void deallocate(pointer p, size_type n);

这里allocate函数有两种重载方式（如用不到hint，可任选其一进行实现），其中hint参数可以传入一个已经分配内存的堆指针，在某些情况下可以用于优化已分配内存的释放，比如可以将已经pop的元素的内存回收到一个缓存的池子中，新分配的内存尺寸如果合适，就使用缓存池中的内存块，而不需要重新分配。

可选的接口实现

分配器的构造/析构

可以选择实现分配器的构造函数和析构函数，以用于必要的初始化操作。若未实现，则会适用默认的构造/析构函数：

template <typename T>
class MyAllocator {
public:
   	...
    MyAllocator() {}					// ctor
    MyAllocator(const MyAllocator&) {}	// copy ctor
    ~MyAllocator() {}					// dtor
    ...
}

容器元素的构造/析构

template <typename T>
class MyAllocator {
public:
   	...
    template <typename U, typename... Args>
    void construct(U *p, Args &&...args) {
        new (p) U(std::forward<Args>(args)...);
    }
    template <typename U>
    void destroy(U *p) {
        p->~U();
    }
    ...
}

construct用于在分配器分配的内存（指针p所指）上（使用placement-new）构造类型T的实际对象（构造所需的参数通过完美转发传递），而destroy则用于析构T对象。

这两个接口在C++20中已经被移除。

其他

pointer address(reference x) const {
	return &x;
}
const_pointer address(const_reference x) const {
    return &x;
}

address用于将对象引用转换为指针，在C++20中被移除。

size_type max_size() const {
	return std::numeric_limits<size_type>::max();
}

max_size用于返回最大支持的元素个数，在C++20中被移除。

自定义示例

这里将实现一个简陋的预分配内存的线性分配器：

#include <vector>

#define ALLOC_ONCE_MAX_SIZE 100

template <typename T>
class AllocOnceAllocator {
public:
    using value_type = T;
    using pointer = T *;
    using const_pointer = const T *;
    using reference = T &;
    using const_reference = const T &;
    using size_type = size_t;
    using difference_type = ptrdiff_t;
    using const_void_pointer = const void *;

    template <typename U>
    struct rebind {
        using other = AllocOnceAllocator<U>;
    };

    // neccessary
    AllocOnceAllocator() {
        init();
    }

    template <typename U>
    AllocOnceAllocator(const AllocOnceAllocator<U> &) {
        deinit();
        init();
    }

    ~AllocOnceAllocator() {
        deinit();
    }

    pointer allocate(size_type n) {
        if (n <= 0)
            return nullptr;
        if (n + size_ > max_size()) {
            printf("AllocOnceAllocator allocate failed, n = %lld, size_ = %lld", n, size_);
            return nullptr;
        }

        printf("allocate %lld elements\n", n);

        pointer p = pool_ + size_;
        size_ += n;

        return p;
    }

    void deallocate(pointer p, size_type n) {
        printf("deallocate %lld elements\n", n);
    }

    // optional
    template <typename U, typename... Args>
    void construct(U *p, Args &&...args) {
        new (p) U(std::forward<Args>(args)...);
    }
    template <typename U>
    void destroy(U *p) {
        p->~U();
    }

    pointer address(reference x) const {
        return &x;
    }
    const_pointer address(const_reference x) const {
        return &x;
    }

    size_type max_size() const {
        return ALLOC_ONCE_MAX_SIZE;
    }

private:
    void init() {
        if (max_size() <= 0) {
            printf("AllocOnceAllocator init failed: max_size must > 0!");
            return;
        }

        pool_ = (pointer)malloc(max_size() * sizeof(T));
        if (!pool_) {
            printf("AllocOnceAllocator init failed: malloc size %d failed!", max_size() * sizeof(T));
            return;
        }

        size_ = 0;
    }

    void deinit() {
        if (pool_) {
            free((void *)pool_);
            pool_ = nullptr;
        }
    }

private:
    pointer pool_ = nullptr;
    size_type size_ = 0;
};

class A {
public:
    A() : val_(0) {
    }

    A(int val) : val_(val) {
        printf("A:A(%d)\n", val);
    }

    void Print() {
        printf("A val : % d\n", val_);
    }

private:
    int val_;
};

int main() {
    const int vecSize = 75;

    std::vector<int, AllocOnceAllocator<int>> intVec;
    std::vector<A, AllocOnceAllocator<A>> classVec;
    intVec.reserve(vecSize);
    classVec.reserve(vecSize);
    for (int i = 0; i < vecSize; ++i) {
        intVec.push_back(i);
        classVec.push_back(i);
    }

    for (int i = 0; i < vecSize; ++i) {
        printf("int val: %d\n", intVec[i]);
        classVec[i].Print();
    }

    return 0;
}

这个简陋的线性分配器只有在搭配reserve使用时（仅在reserve时有一次allocate），才能勉强使用，否则会随着容器的扩容（先allocate新的内存块，拷贝后deallocate旧的内存块），旧的内存块并没有回收，也没有其他策略进行重用，从而产生内存的浪费。

但是线性分配器的初衷一般是为了在程序执行过程中，不会因扩容而产生新的内存申请释放操作，从而提升性能。所以线性分配器多用于一些相对比较固定的场景，且内存空间比较富裕，可以用空间（内存）换时间（申请释放动作）的情况：比如循环调用的函数中的局部vector变量，当你想省去重复的内存申请释放操作，又不想将其放到更大的作用域（循环外，如全局变量或类的成员变量）中（这样会降低封装性，从而降低可读性和可维护性），则可以考虑给这些vector一个线性分配器。但需要在上述基础上稍作修改，比如将pool_改成一个单例类，在程序的初始化阶段完成创建，所有局部vector共用（从同一个池子中allocate）；再比如增加RAII的Guard类，在合适的时间点（比如循环结束或一轮计算结束）重置pool_的size_。