Allocator简介

    分配器（配置器，allocator）是STL中六大组件（容器、算法、迭代器、仿函数、适配器、分配器）之一，用于分配管理内存空间。其实我们可以把allocator看成一个简易的内存池，其主要适用于在使用容器时，对内存空间的动态分配，如果是我们平常要申请一块动态内存时，不推荐使用allocator，应该使用new-delete（malloc-free），主要原因是allocator不好用（使用不方便，容器例外），在内存释放的时候还需要提供对象的个数，因为我们在动态分配内存时候基本上都是对指针所指向的内存空间进行操作，而不会去记录空间中构造了多少个对象。

    allocator的特点是将内存分配(allocate)与对象构造(construct)分离，这样使得对内存的管理更加灵活，性能较高。

简单使用

#include <iostream>
#include <memory>
using namespace std;
//先熟悉一下提供的allocator用法
int main(int argc, char const *argv[])
{
    allocator<int> a;
    int *ptr=a.allocate(5);
    a.construct(ptr,3);
    a.construct(ptr+1,-3);
    a.construct(ptr+2,3);
    a.construct(ptr+3,-3);
    a.construct(ptr+4,3);
    for(int i=0;i<5;i++)
    {
        cout<<*(ptr+i)<<" ";
        a.destroy(ptr+i);
    }
    a.deallocate(ptr,5);
    return 0;
}

原理分析

   一个分配器中一定要有allocate、deallocate、construct、destroy四个函数，分别表示内存分配，内存释放、对象构造、对象析构。在一般的allocator中allocate直接是调用::operator new()，deallocate直接调用::operator delete()，没有什么性能上的优化。

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

    而在SGI STL中的某个版本中，实现了_pool_alloc，指的是运用内存池来进行内存分配，对于容器的第二个参数默认为alloc。这主要是为了解决小型区块从而造成的内存碎片问题，以此来提升性能。

    采用了双层分配器策略，第一级分配器直接使用malloc和free，第二级分配器根据分配区块的大小采取不同的策略：分配区块若大于128字节，则调用第一级分配器，否则用内存池的方式分配管理内存。

    第一级分配器__malloc_alloc_template需要注意的是，其在allocate中直接调用malloc，当调用不成功时候，会转入一个循环，不断地尝试调用内存（内存不足处理例程），期望在某次调用后可以得到足够的内存而终止，否则丢出异常。这里注意一下，只有第一级分配器有内存申请异常处理，也可以用set_new_handle来设置异常处理。

  因为malloc出来的内存都会带一些“额外的记录”，当申请的内存较小时，额外的负担所占的比例就很大，就会很浪费内存空间。所以当申请的区块小于128字节，则会每次申请一块大内存，并维护对应着自由链表free-lists。首先其是一个16节点的数组，数组中的每一个元素是一个指针，指向一个链表free-list，链表中的每一个节点当有相同大小的内存需求时，直接从free-list中取出，如果释放小内存时，也会放到相应的free-list中。对于一整块内存，只有最上面才有记录（用于记录内存大小），因此减小了开销。

    SGI第二级分配器总共管理16个free-list（8 bytes ~ 128 bytes），因此会将任何小区块的需求上调至8的整数倍。

    具体的申请内存和释放内存操作其实就是链表中的插入和删除操作，当发现free-list中没有可用的区块时候，就要向内存池申请新的内存加到free-list中。

    除此之外，还有三个内存处理工具，uninitialized_copy、uninitialized_fill、uninitialized_fill_n，分别对应于算法中的copy、fill、fill_n。前提是这三个都是利用已经申请好的但未初始化的内存。

1. uninitialized_copy将输入范围内的每一个对象产生一个复制品，放进输出范围中
2. uninitialized_fill在范围内[first,second)都会产生单个值的复制品
3. uninitialized_fill_n在范围内[first,first+n)都会产生单个值的复制品

Allocator注意事项

1. Allocator是一个函数模板，模板参数T表示你要分配内存的对象的类型，所以函数参数是分类对象的个数，而不是字节大小。
2. 一定不能让模板随着对象的不同而有不同的状态，因此，Allocator不应该有非静态成员变量。
3. Allocator的使用是分步骤的，首先要申请内存，再在申请好的内存上进行对象构造，顺序不能反（释放对象的时候是先析构对象，再释放内存）。
4. rebind模板的作用。Allocator模板中有一个rebind类模板，用于重新将类型进行一次绑定。比如在创建ListNode<T>节点时，传进Allocator的参数可能是T，但是真正要申请的空间大小是ListNode<T>，所以可以用Allocator::rebind<ListNode> ::other进行转换，就可以得到ListNode<T>的分配器。但是实际上，也可以直接给Allocator的是ListNode<T>，直接构造一个节点大小的空间也行。

参考 《STL源码剖析》、《C++ Primer》 、《Effective STL》