剖析STL内存分配器，让你硬刚面试官

本期主要讲解C++ STL中的内存分配器std::allocator及其特性萃取器__gnu_cxx::__alloc_traits。

为防止混淆，规定如下：

• allocator：泛指内存分配器，仅仅是一个术语。
• std::allocator：是STL实现的内存分配器类std::allocator。

更多硬核知识，微信搜一搜：look_code_art，让你相见恨晚！！！

__gnu_cxx::new_allocator

C++的默认的内存分配器std::allocator，继承至__gnu_cxx::new_allocator。而 __gnu_cxx::new_allocator 主要完成两个任务：

• 分配对象内存、初始化对象
• 析构对象、释放对象内存

__gnu_cxx::new_allocator 是个空类，没有成员变量，主要有四种成员函数完成上述任务：

• allocate 函数，用于分配内存
• construct函数，调用已分配内存对象的构造函数
• destroy函数，调用析构函数
• deallocate函数，用于释放内存

__gnu_cxx::new_allocator 的整体框架大致如下：

  template <typename _Tp>
  class new_allocator
  {
  public:
    typedef size_t      size_type;
    typedef ptrdiff_t   difference_type;
    typedef _Tp*        pointer;
    typedef const _Tp*  const_pointer;
    typedef _Tp &       reference;
    typedef const _Tp & const_reference;
    typedef _Tp         value_type;

    template <typename _Tp1>
    struct rebind
    {
      typedef new_allocator<_Tp1> other;
    };

    new_allocator() _GLIBCXX_USE_NOEXCEPT {}
    new_allocator(const new_allocator &) noexcept {}
    template <typename _Tp1>
    new_allocator(const new_allocator<_Tp1> &) noexcept {}
    ~new_allocator() noexcept {}

    pointer allocate(size_type __n, const void * = static_cast<const void *>(0));

    void deallocate(pointer __p, size_type);

    size_type max_size() const noexcept;

    template <typename _Up, typename... _Args>
    void construct(_Up *__p, _Args &&...__args) 
                      noexcept(noexcept(::new ((void *)__p)_Up(std::forward<_Args>(__args)...)));
    template <typename _Up>
    void destroy(_Up *__p) noexcept(noexcept(__p->~_Up()));
    //...
  };

allocate

allocate函数，用于分配大小为__n个字节内存，返回值是分配所得内存的地址。

• 如果待分配内存大小__n大于当前进程最大可用内存，那么就会抛出bad_alloc异常。
• 再调用operator new来分配内存。operator new对malloc作了一层简单的封装，等效于malloc
• 将指向operator new的返回值类型转换为此次分配对象_Tp的指针类型。

整个过程如下：

    pointer allocate(size_type __n, const void * = static_cast<const void *>(0))
    {
      if (__n > this->max_size())
        std::__throw_bad_alloc();

#if __cpp_aligned_new
      if (alignof(_Tp) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
      {
        std::align_val_t __al = std::align_val_t(alignof(_Tp));
        return static_cast<_Tp *>(::operator new(__n * sizeof(_Tp), __al));
      }
#endif
      return static_cast<_Tp *>(::operator new(__n * sizeof(_Tp)));
    }

deallocate

deallocate函数，使用operator delete来释放地址__p指向的内存。

    void deallocate(pointer __p, size_type)
    {
#if __cpp_aligned_new
      if (alignof(_Tp) > __STDCPP_DEFAULT_NEW_ALIGNMENT__)
      {
        ::operator delete(__p, std::align_val_t(alignof(_Tp)));
        return;
      }
#endif
      ::operator delete(__p);
    }

construct

上面的allocate函数相当于malloc函数，只是分配__n个字节的内存，但是并未对这片内存进行初始化。对allocate 函数分配的内存__p进行初始化的任务，交给construct函数来完成。

constuct函数，使用了new表达式的另一种形式，叫做placement new，使用方式如下注释：

    template <typename _Up, typename... _Args>
    void construct(_Up *__p, _Args &&...__args) 
                      noexcept(noexcept(::new ((void *)__p)_Up(std::forward<_Args>(__args)...)))
    {
        // 表示在 地址 _p 上调用对象 _Up的构造函数
        // 其中，__args是构造函数的参数
        ::new ((void *)__p) _Up(std::forward<_Args>(__args)...);
    }

destroy

deallocate函数，是完成了释放内存，但是在释放内存之前一般需要先调用对象的析构函数，完成相关的资源的释放、关闭操作。因此在destoy函数中，直接调用了类型_Up的析构函数。

   template <typename _Up>
    void destroy(_Up *__p) noexcept(noexcept(__p->~_Up()))
    {
      __p->~_Up();
    }

std::allocator

类std::allocator 继承__gnu_cxx::new_allocator。

template<typename _Tp>
using __allocator_base = __gnu_cxx::new_allocator<_Tp>;


  template <typename _Tp>
  class allocator : public __allocator_base<_Tp>
  {
  public:
    typedef size_t      size_type;
    typedef ptrdiff_t   difference_type;
    typedef _Tp*        pointer;
    typedef const _Tp*  const_pointer;
    typedef _Tp&        reference;
    typedef const _Tp&  const_reference;
    typedef _Tp         value_type;

    template <typename _Tp1>
    struct rebind
    {
      typedef allocator<_Tp1> other;
    };

    allocator() noexcept {}
    allocator(const allocator &__a) noexcept : __allocator_base<_Tp>(__a) {}
    allocator &operator=(const allocator &) = default;

    template <typename _Tp1>
    allocator(const allocator<_Tp1> &) _GLIBCXX_NOTHROW
    { }

    ~allocator() _GLIBCXX_NOTHROW {}

    //...
    // Inherit everything else.
  };

rebind

在__gnu_cxx::new_allocator、std::allocator中都有一个rebind函数，其主要作用：获得类型_Tp1的内存分配器allocator<_Tp1>。

   template <typename _Tp1>
    struct rebind
    {
      typedef allocator<_Tp1> other;
    };

这个函数在容器中被STL中被广泛使用。比如，在std::list<_Tp, std::allocator<_Tp>>中，std::allocator不仅要为_Tp类型的对象分配内存，还要为存储_Tp对象的节点list_node<_Tp>分配内存。但是std::list<_Tp, std::allocator<_Tp>>的类模板参数中只是传入了用于分配_Tp类型的内存分配器std::allocator<_Tp>，那么怎么获得list_node<_Tp>类型的内存分配器呢？

答案就是依靠rebind函数：allocator<_Tp>::rebind<list_node<_Tp>>::other，获得的就是用于分配list_node<_Tp>类型的内存分配器 allocator<list_node<_Tp>>。

在list中的实现如下：

    template<typename _Tp, typename _Alloc>
    class _List_base
    {
    protected:
      // 用于分配 _Tp 类型的内存分配器: _Tp_alloc_type
      // _Tp_alloc_type 实际上就是 std::allocator
      typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template rebind<_Tp>::other _Tp_alloc_type;
      // 用于分配 List_node<_Tp> 类型的内存分配器：_Node_alloc_type
      typedef typename _Tp_alloc_traits::template rebind<_List_node<_Tp> >::other _Node_alloc_type;        
      //...
    };

    template<typename _Tp, typename _Alloc = std::allocator<_Tp> >
    class list : protected _List_base<_Tp, _Alloc>
    {
    protected:
      typedef _List_node<_Tp>                 _Node;
      //...
    };

std::__allocator_traits_base

上面的list中使用到了用于萃取内存分配器属性的类__gnu_cxx::__alloc_traits。

__gnu_cxx::__alloc_traits 继承自 std::allocator_traits
std::allocator_traits       继承自 std::__allocator_traits_base

类__allocator_traits_base，用于获取内存分配器_Alloc的属性，这个分配器_Alloc不一定是上面所述的std::allocator，可以是自定义的。

  struct __allocator_traits_base
  {
    template <typename _Tp,
              typename _Up,
              typename = void>
    struct __rebind : __replace_first_arg<_Tp, _Up>
    { };  

    // __rebind 特化版本：当分配器 _Tp 有成员函数 rebind 时调用此特化版本
    template <typename _Tp, typename _Up>
    struct __rebind<_Tp,
                    _Up,
                    __void_t<typename _Tp::template rebind<_Up>::other>>
    {
      using type = typename _Tp::template rebind<_Up>::other;
    };

  protected:
    template <typename _Tp> using __pointer     = typename _Tp::pointer;
    template <typename _Tp> using __c_pointer     = typename _Tp::const_pointer;
    template <typename _Tp> using __v_pointer     = typename _Tp::void_pointer;
    template <typename _Tp> using __cv_pointer     = typename _Tp::const_void_pointer;
    template <typename _Tp> using __pocca = typename _Tp::propagate_on_container_copy_assignment;
    template <typename _Tp> using __pocma = typename _Tp::propagate_on_container_move_assignment;
    template <typename _Tp> using __pocs  = typename _Tp::propagate_on_container_swap;
    template <typename _Tp> using __equal = typename _Tp::is_always_equal;
  };

__rebind

类__allocator_traits_base 中最重要的是成员函数__rebind。 __rebind的模板参数_Tp是分配器类型，根据_Tp来实现重载：

• 当传入的内存分配器类型_Tp，实现了rebind成员函数时，比如上面的std::allocator，那么就调用__rebind的特化版本：

    template <typename _Tp, typename _Up>
    struct __rebind<_Tp,
                    _Up,
                    __void_t<typename _Tp::template rebind<_Up>::other>>
    {
      using type = typename _Tp::template rebind<_Up>::other;
    };

  以std::allocator<int>为例，获取Node<int>类型的内存分配器：

  __allocator_traits_base::__rebind<std::allocator<int>, Node<int>>::type  
  // 等价于 
  std::allocator<Node<int>>

• 当传入的分配器_Tp没有实现rebind成员函数时，就调用普通__rebind版本：

      // _Tp需要是分配器
      template <typename _Tp,
                typename _Up,
                typename = void>
      struct __rebind : __replace_first_arg<_Tp, _Up>
      { };  

  其中__replace_first_arg实现如下。此时，需要自定义一个内存分配器模板_Template，

    template <typename _Tp, typename _Up>
    struct __replace_first_arg
    { };
  
    // _Template 是个类模板
    template <template <typename, typename...> class _Template, 
              typename _Up,
              typename _Tp, 
              typename... _Types>
    struct __replace_first_arg<_Template<_Tp, _Types...>, _Up>
    {
      using type = _Template<_Up, _Types...>;
    };

by the way

在此，补充点模板的一点知识：

1. 模板参数模板

   在__replace_first_arg类中，使用了一个类模板参数模板_Template，这表示模板参数_Template本身就是个类模板。

    template <typename, typename...> class _Template

2. ::template

   在__rebind函数体中，在::后面有个template关键字，这是用于告诉编译器 template后面的 < 不是比较符号，而是模板参数符号。就是类似于_Tp前面的typename是告诉编译器::后面的是类成员函数，而不是static函数。

    using type = typename _Tp::template rebind<_Up>::other;

__alloc_rebind

全局函数__alloc_rebind，是std::__allocator_traits_base的wrapper，用于获取为_Up类型分配内存的内存分配器_Alloc<_Up>

 template <typename _Alloc, typename _Up>
 using __alloc_rebind = typename __allocator_traits_base::template __rebind<_Alloc, _Up>::type;

std::allocator_traits

类std::allocator_traits，继承于std::__allocator_traits_base，用于获取内存分配器allocator的各个属性。

  template <typename _Alloc>
  struct allocator_traits : __allocator_traits_base
  {
    typedef _Alloc allocator_type;                      /// The allocator type
    typedef typename _Alloc::value_type value_type;      /// The allocated type
    //...
  };

当_Alloc是std::allocator时，有个特化版本：

  template <typename _Tp>
  struct allocator_traits<allocator<_Tp>>
  {
    using allocator_type = allocator<_Tp>;  // 分配器类型
    using value_type = _Tp;                 // 待分配内存的对象类型
    using pointer = _Tp *;                 // 对象指针
    using const_pointer = const _Tp *;
    //...  using 
    using is_always_equal = true_type;

    // 使用allocator为_Up分配内存
    template <typename _Up>
    using rebind_alloc = allocator<_Up>;

    template <typename _Up>
    using rebind_traits = allocator_traits<allocator<_Up>>;

    // 下面是 std::allocator<_Tp> 成员函数的 wrapper
    static pointer allocate(allocator_type &__a, size_type __n)
    {
      return __a.allocate(__n);
    }

    static pointer allocate(allocator_type &__a, size_type __n, const_void_pointer __hint)
    {
      return __a.allocate(__n, __hint);
    }

    static void deallocate(allocator_type &__a, pointer __p, size_type __n)
    {
      __a.deallocate(__p, __n);
    }

    template <typename _Up, typename... _Args>
    static void construct(allocator_type &__a, _Up *__p, _Args &&...__args) 
                noexcept(noexcept(__a.construct(__p, std::forward<_Args>(__args)...)))
    {
      __a.construct(__p, std::forward<_Args>(__args)...);
    }

    template <typename _Up>
    static void destroy(allocator_type &__a, _Up *__p) noexcept(noexcept(__a.destroy(__p)))
    {
      __a.destroy(__p);
    }

    static size_type max_size(const allocator_type &__a) noexcept
    {
      return __a.max_size();
    }
  };

gnu_cxx::alloc_traits

__gnu_cxx::__alloc_traits类，也大都是std::allocator_traits的wrapper，

template<typename _Alloc, typename = typename _Alloc::value_type>
struct __alloc_traits : std::allocator_traits<_Alloc> { 

    typedef _Alloc                                  allocator_type;
    typedef std::allocator_traits<_Alloc>        _Base_type;

    typedef typename _Base_type::value_type      value_type;
    typedef typename _Base_type::pointer         pointer;
    typedef typename _Base_type::const_pointer   const_pointer;
    typedef typename _Base_type::size_type       size_type;
    typedef typename _Base_type::difference_type difference_type;

    typedef value_type &                           reference;
    typedef const value_type&                      const_reference;

    using _Base_type::allocate;
    using _Base_type::construct;
    using _Base_type::deallocate;
    using _Base_type::destroy;
    using _Base_type::max_size;

  private:

    // 当 _Ptr 不是个标准指针，但是 _Ptr 和 value_type* 相同
    // __is_custom_pointer 才是 true，即 _Ptr 是个自定义指针
    // 即 _Ptr 可转换为 pointer
    template <typename _Ptr>
    using __is_custom_pointer 
        = std::__and_<std::is_same<pointer, _Ptr>, std::__not_<std::is_pointer<_Ptr>>>;

  public:
    // overload construct for non-standard pointer types
    // 重载非标准类型的指针，调用构造函数
    template <typename _Ptr, typename... _Args>
    static typename std::enable_if<__is_custom_pointer<_Ptr>::value>::type
    construct(_Alloc &__a, _Ptr __p, _Args &&...__args) noexcept(...) // 省略了noexcept中的表达式
    {
      // 使用分配器 __a , 在地址 __p 调用构造函数
      _Base_type::construct(__a, 
                            std::__to_address(__p),
                            std::forward<_Args>(__args)...);
    }

    // overload destroy for non-standard pointer types
    // 重载非标准类型指针，调用析构函数
    template <typename _Ptr>
    static typename std::enable_if<__is_custom_pointer<_Ptr>::value>::type
    destroy(_Alloc &__a, _Ptr __p) noexcept(...) 
    {
      _Base_type::destroy(__a, std::__to_address(__p));
    }

    /*** 对于标准的指针，会直接调用父类的constuct、destroy ***/

    // wrapper
    template <typename _Tp>
    struct rebind
    {
      typedef typename _Base_type::template rebind_alloc<_Tp> other;
    };
    //...
}

总体来说，__gnu_cxx::__alloc_traits提供了一个顶层的内存分配器萃取器，可以使用 _Alloc 的 allocate、 deallocate、construct 以及 destroy等函数来完成对象构造和析构等任务。

而类std::allocator_traits 是底层直接获取内存分配器_Alloc属性的类，其中std::allocator_traits有个特化版本，即使_Alloc是std::allocator，因为std::allocator是STL的容器默认的内存分配器。

如果想将自定义的内存分配器Custome_Alloc融入到STL体系中，那么也需要像std::allocator一样完成相应的接口设计、以及rebind函数。这样，容器就能通过__gnu_cxx::__alloc_traits<Custome_Alloc>使用自定义的内存分配器Custome_Alloc。

好嘞，到此完成了本期的目标，即讲解完毕C++ STL内存分配器的设计。