10.了解allocator的约定与限制

Posted on | In

（本节内容并未完全掌握，建议学习STL源码剖析相关章节后再次复习本章）
allocator最初作为内存模型的抽象而产生，但最终失败了。后来又被设计成促进全功能内存管理器，但又发现可能会造成效率低下，最终，allocator被弱化成为了对象。

allocator的特点

类似于operator new 和operator new[]，allocator也负责分配和回收内存，但其接口和new，new[],或者malloc毫无相似之处。并且，大部分容器从未向它们相关的allocator索取内存。这是相当奇怪的一点。

正如前文提到的，allocator最初作为内存模型的抽象而产生，那么它必须为其所定义的内存模型中的指针和引用提供类型定义，一般而言，一个类型为T的对象，它的默认allocator提供了allocator::pointer与allocator::reference;

如果你对C++十分了解，你会发现其实我们无法模拟一个引用。这需要重载operator. （该操作符禁止重载）而且模拟引用最好的方式是使用代理对象（proxy object详见More Effective C++ 30),代理对象会带来许多问题。

c++标准明确指出，允许库实现者假定每个分配子的指针等价于T*，而其引用等价于T&.也就是说，库实现可以忽视typedef并直接使用原始指针和引用。

allocator是对象这一性质意味着它可以拥有成员函数、嵌套类型和类型定义（如reference与pointer）。同时c++标准再一次规定，STL的实现可以假定所有属于同一种类型的allocator对象等价，且比较结果相等，这非常很奇怪，但是是可以理解并接受的，举例如下：

1
2
3
4
5
6
7
template<typename T> // 一个用户定义的分配器模板
class SpecialAllocator {...};
typedef SpecialAllocator<Widget> SAW;
list<Widget, SAW> L1;
list<Widget, SAW> L2;
...
L1.splice(L1.begin(), L2); // 把L2的节点移到L1前端

众所周知，当list的元素从一个list链接到另一个时，并没有复制任何东西，而是仅仅调整了一些指针。当L1被析构时，L1的allocator必须析构自己的所有节点并释放内存，但其现在包含了L2的节点，所以它必须释放最初由L2的allocator分配的节点，这也就是allocator同类型等价的原因，允许一个allocator对象分配的内存可以由另一个allocator对象安全删除。
这一点也禁止了allocator不允许存在自己的state，更直白的说，allocator不允许有任何non-static成员，如果存在则无法等价。

allocator与内存分配

allocator与new在分配内存上有一点相似之处：

1
2
void* operator new(size_t bytes);
pointer allocator<T>::allocate(size_type numObjects);//pointer 等价于T*

对于new而言，它的参数是所需字节的大小，而allocator的参数是分配多少个对象。它们的返回值也不同，operator new返回void*，而allocator::allocate则是返回T*，而且这个返回值并没有指向某个T对象，因为根本还没有构造。

容器与它们对应的allocator

大多数标准容器从未单独调用过对应的allocator，这种情况普遍发生于基于节点的容器：

1
2
list<int,allocator<int> > L; //allocator<int>从未分配内存
set<Widget, SAW> s; //SAW从未分配内存

list<T>的一个可能实现如下：
1
2
3
4
5
6
7
8
9
10
11
template<typename T,typename Allocator = allocator<T> >
class list{
private:
    Allocator alloc; // 用于T类型对象的分配器
    struct ListNode{ // 链表里的节点
        T data:
        ListNode *prev;
        ListNode *next;
    };
    ...
}

当添加一个node到list时，我们需要从分配器为其获取内存，我们要的并非是T的内存，而是包含了一个T的ListNode的内存。那allocator<T>基本上就是废了。
list需要的是从他的分配器类型那里获取用于Listnode的对应分配器的方法。按照协定，分配器需要提供完成那部分工作的typedef，实际上这个东西叫other.是嵌入一个叫做rebind的结构体的typedef，rebind自己是一个嵌入分配器的模板—分配器自己也是一个模板。
1
2
3
4
5
6
7
8
9
template<typename T> 
class allocator {// 分配器模板
public: 
    template<typename U>
    struct rebind{
        typedef allocator<U> other;
    }
    ...
};

在list的实现代码里，需要确定我们持有的T的分配器所对应的ListNode的分配器类型，所以，list的allocator类型为：
1
Allocator::rebind<ListNode>::other

总结：

如果你需要自己实现一个allocator，你需要明确：

  1. allocator是一个模板
  2. 提供pointer与reference的typedef
  3. 不要给allorator分配state，通常不含有non-static成员
  4. 传给allocate的是对象个数而非字节数，同时记得其返回T*指针。
  5. 一定要提供标准容器依赖的内嵌rebind模板