也谈stl的allocator

时间：2010-07-23 来源：hqin6

也谈stl的allocator 收藏

原文地址：http://blog.csdn.net/hqin6/archive/2010/07/16/5740322.aspx

前些日子，在论坛上看到一个关于map的讨论帖子。主要是讨论如何不使用map的底层内存池机制！有人说可以重新定制map的分配器（也就是 allocator）达到目的。真的可以么？

先说下allocator。。。。

--------------------

《EFFectiveSTL》第十条说到：“大多数标准容器从未向它们相关的分配器索要内存”。注意这里是它们相关！

其理由是：

条款10：注意分配器的协定和约束---STLChina.org 出品

“当添加一个新节点到list时，我们需要从分配器为它获取内存，我们要的不是T的内存，我们要的是包含了一个T的ListNode的内存。那使我们的 Allocator对象没用了，因为它不为ListNode分配内存，它为T分配内存。现在你理解list为什么从未让它的Allocator做任何分配了：分配器不能提供list需要的。”

而书里面也提到了一个网站：

http://www.josuttis.com/cppcode/myalloc.hpp.html

可以看到，这里有个简单的allocator的实现。但是里面有些细节容易误导人，有地方也有不妥。

写自己的allocator，需要注意几点：

1、typedef：

          typedef T* pointer;
          typedef const T* const_pointer;
          typedef T& reference;
          typedef const T& const_reference;

以上的四个typedef，是在底层stl的容器中使用到的，没有这些定义，会编译出错。list里有源码：

63 typedef typename _Allocator::pointer pointer;
64 typedef typename _Allocator::const_pointer const_pointer;

2、rebind::other的定义：

template<typename U>
          struct rebind
          {
              typedef MyAlloc<U> other;
          };

这里简单说一下，其实list等容器里对内存的分配，是通过这个other来分配的。也就是说，对于list<T, allocator<T> >的内存分配，不是由allocator<T>来分配的，而是通过 allocator<ListNode<T>＞来分配的，现在明白了“大多数标准容器从未向它们相关的分配器索要内存”这句话中的“它们相关”了吧？所以这里需要定义为模板。而list的源代码中，有：

typedef typename _Alloc::template rebind<_List_node<_Tp> >::other _Node_Alloc_type;
如果你不定义rebind，那么在编译list相关代码时，会出错。。。当然，对于vector，可能不会！

3、对于allocate和deallocate函数的定义：

          pointer allocate(size_t num)
          {
              cout << " allocate: " << num << endl;
              return (pointer)::operator new(num*sizeof(T));
          }
          void deallocate(pointer p, size_t num)
          {
              cout << "deallocate: " << typeid(p).name() << " " << num << endl;
              ::operator delete ((void*)p);
          }

注意，这里使用的是pointer ret = (pointer)(::operator new(num*sizeof(T))); 即只分配内存，不初始化，而实际的初始化new操作（构造函数调用）则是在一个叫做 std::_Construct 的函数中而不是在上面网址的construct函数中。stl中的容器会在调用allocator后再去调用std::_Construct函数！

309 _List_node<_Tp>*
      310 _M_get_node()
      311 { return _M_impl._Node_Alloc_type::allocate(1); }
      312
      ……
      432 _Node*
      433 _M_create_node(const value_type& __x)
      434 {
      435 _Node* __p = this->_M_get_node();
      436 try
      437 {
      438 std::_Construct(&__p->_M_data, __x);
      439 }
      440 catch(...)
      441 {
      442 _M_put_node(__p);
      443 __throw_exception_again;
      444 }
      445 return __p;
      446 }

4、构造函数

MyAlloc()throw(){cout << "myalloc()" << endl;}
template<typename U>
MyAlloc(const MyAlloc<U>&) throw(){cout << "myalloc(const&" << typeid(U).name() << ")" << endl;}

如果不添加这俩函数，那么在你编译的时候，可能会出现类似：
`std::list<_Tp, _Alloc>::list(const typename std::_List_base<_Tp, _Alloc>::allocator_type&) [with _Tp = Elem, _Alloc = MyAlloc<Elem>]'
这样的出错信息。原因很简单，
代码：

295 typedef typename _Alloc::template rebind<_List_node<_Tp> >::other
      296
      297 _Node_Alloc_type;
      ……
      299 struct _List_impl
      300 : public _Node_Alloc_type {
      301 _List_node_base _M_node;
      302 _List_impl (const _Node_Alloc_type& __a)
      303 : _Node_Alloc_type(__a)
      304 { }
      305 };
      ……
      ……
      476 explicit
      477 list(const allocator_type& __a = allocator_type())
      478 : _Base(__a) { }

478行：_Base接收的参数类型是_Node_Alloc_type（也就是MyAlloc<_List_node<_Tp>> 但是参数_a的类型是MyAlloc<Elem>
所以，其复制构造函数需要使用模板的方式定义。当然，如果只有复制构造函数没有默认构造函数，你能编译过么？

注：vector里可以不需要这些，因为vector里存储的Node和Elem无异，Elem即是Node，没有附加的数据字段。而 rebind::other也不需要了。。。毕竟，vector的Node内存分配器就是Elem分配器。

有了上面的知识，那么程序基本成型：

#include <iostream>
#include <list>
#include <vector>
using namespace std;
class Elem
{
        public:
                Elem(){cout << "Elem()" << endl;}
                Elem(const Elem&){cout << "Elem(const Elem&)" << endl;}
                ~Elem(){cout << "~Elem()" << endl;}
                int m_i;
                float m_f;
};
template<typename T>
class MyAlloc
{
        public:
                typedef T* pointer;
                typedef const T* const_pointer;
                typedef T& reference;
                typedef const T& const_reference;
                template<typename U>
                struct rebind
                {
                        typedef MyAlloc<U> other;
                };
                pointer allocate(size_t num)
                {
                        cout << " allocate: " << num << endl;
                        return (pointer)::operator new(num*sizeof(T));
                }
                void deallocate(pointer p, size_t num)
                {
                        cout << "deallocate: " << typeid(p).name() << " " << num << endl;
                        ::operator delete ((void*)p);
                }
                MyAlloc()throw(){cout << "myalloc()" << endl;}
                template<typename U>
                MyAlloc(const MyAlloc<U>&) throw(){cout << "myalloc(const&" << typeid(U).name() << ")" << endl;}
};
template<typename T1, typename T2>
bool operator == (const MyAlloc<T1>& , const MyAlloc<T2>&)
{
        return true;
}
int main()
{
        //vector<Elem, MyAlloc<Elem> > vec;

        Elem e;
        //vec.push_back(e);

        list<Elem, MyAlloc<Elem> > li;
        li.push_back(e);
// li.begin()->m_i = 10;

// list<Elem, MyAlloc<int> > lii;

// lii.insert(lii.begin(),li.begin(), li.end());

// cout << typeid(Elem).name() << endl;

        //li.insert(li.begin(),vec.begin(), vec.end());

        //cout << li.size() << endl;

        return 0;
}

ok，现在可以很清楚的看到vector等容器的内存再分配了！！

如果你细心，可以发现bool operator == (const MyAlloc<T1>& , const MyAlloc<T2>&)这个函数！

《effective STL》条款十中有这么一段话：
“当L1被销毁时，当然，它必须销毁它的所有节点（以及回收它们的内存），而因为它现在包含最初是L2一部分的节点，L1的分配器必须回收最初由L2的分配器分配的节点。现在清楚为什么标准允许STL实现认为相同类型的分配器等价。所以由一个分配器对象（比如L2）分配的内存可以安全地被另一个分配器对象（比如L1）回收。如果没有这样的认为，接合操作将更难实现。显然它们不能像现在一样高效”
所以，需要这么一个operator==的操作符重载。当然，我在测试的时候，没有这个操作符重载，也没发现异常。。。

------------------------

好，明白上面的原理后，回到最初的问题，map的底层内存池机制，能通过修改allocator来改变么？我想应该不可以。map的内存池机制根本就不会去调用allocator的deallocate函数。如果还不明白，可以改改程序试试~~~