返回
学习

【STL源码剖析】allocator_traits

本篇不对应《STL源码剖析》中的章节，而是作为承上启下的一篇，介绍当代cpp中将 allocator 和 type_traits 这两个前面提过的概念组合而得到的 allocator_traits 。这个东西在后面展开的 容器 相关实现中太过于常见，且相比于最早看过的 allocator 又确实又些新东西在里面，值得单开一篇予以记录。

GCC

bits/allocator_traits.h 当中，一上来先完成基类定义：

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

    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;
  };

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

这里 protected 部分都是些定义，没什么看头，比较显眼的是这里的 rebind 操作，这个东西实际上来自于 allocator ，但我们在早先阅读的时候并没有深究，现在是时候展开看看了。

说起来也简单，实际上 Allocator<T>::rebind<U>::other 就 等价于 Allocator<U> 。

这个 rebind 是 std::list 正常工作的必要条件，因为 std::list<T> 的实际底层数据类型（真正决定内存分配的东西）并不单单是 T ，而是链表的一个 Node<T> ，而容器声明的时候默认的缺省模板参数 Allocator = allocator<T> 在这里就需要 rebind ，才能执行正确的内存动作 1 。

还有一个令我困惑的逻辑点就是，既然有上述的等价关系存在，为什么需要绕一圈走 Allocator<T>::rebind<U>::other 而不是直接用 Allocator<U> 呢？这里个人思考后认为实际上是通过这种写法来适应 用户自定义 的Allocator：只要大家都实现 rebind ，STL就能无感兼容。例如，假如用户实现了一个 CacheAlignedAllocator 2 并把 CacheAlignedAllocator<T> 作为容器的Allocator参数，这时由于我们的模板已经实例化了，没法在容器内部再感知到模板原型并重新创建 CacheAlignedAllocator<U> 了，但此时如果自定义的Allocator实现了 rebind ，那么还是通过 CacheAlignedAllocator<T>::rebind<U>::other 来重新获取新的Allocator即可。

回到我们正在看的 __allocator_traits_base ，这里假如我们的Allocator没有定义 rebind 方法，那么外面在调用 rebind 获取 other 的时候就会报未定义错误。

再往下来到真正的 allocator_traits ，这里不展开看一大堆的类型定义（ 看不明白 ），直接关注都实现了哪些接口。

allocate

公有部分，实现两个 allocate 接口：

    public:

      /**
       *  @brief  Allocate memory.
       *  @param  __a  An allocator.
       *  @param  __n  The number of objects to allocate space for.
       *
       *  Calls @c a.allocate(n)
      */
      _GLIBCXX_NODISCARD static _GLIBCXX20_CONSTEXPR pointer
      allocate(_Alloc& __a, size_type __n)
      { return __a.allocate(__n); }

      /**
       *  @brief  Allocate memory.
       *  @param  __a  An allocator.
       *  @param  __n  The number of objects to allocate space for.
       *  @param  __hint Aid to locality.
       *  @return Memory of suitable size and alignment for @a n objects
       *          of type @c value_type
       *
       *  Returns <tt> a.allocate(n, hint) </tt> if that expression is
       *  well-formed, otherwise returns @c a.allocate(n)
      */
      _GLIBCXX_NODISCARD static _GLIBCXX20_CONSTEXPR pointer
      allocate(_Alloc& __a, size_type __n, const_void_pointer __hint)
      { return _S_allocate(__a, __n, __hint, 0); }

这里的第一个接口，传入的显然是一个 allocator ，实现上就是直接调用 allocator.allocate 方法，再往下就是对 operator new 的封装或编译器内部内存管理的封装，没有太多可讲。

第二个接口比第一个接口多传了一个 const_void_pointer ，实现上就额外封装了一层内部接口，展开看看：

      template<typename _Alloc2>
	static constexpr auto
	_S_allocate(_Alloc2& __a, size_type __n, const_void_pointer __hint, int)
	-> decltype(__a.allocate(__n, __hint))
	{ return __a.allocate(__n, __hint); }

      template<typename _Alloc2>
	static constexpr pointer
	_S_allocate(_Alloc2& __a, size_type __n, const_void_pointer, ...)
	{ return __a.allocate(__n); }

参数 __hint 直到这里仍没什么用处，并且官方文档也并未指出明确用途 3 ，真的是生草…… 为了证实这玩意儿到底有没有用，我重温了一下GCC对 allocator 的实现，由 allocator 摸到 __allocator_base 再最后摸到 __gnu_cxx::new_allocator ，然后发现它的第二个参数居然直接是一个未命名参数 🤔 😇

// /opt/rh/devtoolset-11/root/usr/include/c++/11/ext/new_allocator.h
      _GLIBCXX_NODISCARD _Tp*
      allocate(size_type __n, const void* = static_cast<const void*>(0))
      // ==== snip ====

whatever, 申请内存的接口，就这么封装起来了。

deallocate

相比于内存申请，内存释放的动作就是直接封装 allocator 里的实现：

      /**
       *  @brief  Deallocate memory.
       *  @param  __a  An allocator.
       *  @param  __p  Pointer to the memory to deallocate.
       *  @param  __n  The number of objects space was allocated for.
       *
       *  Calls <tt> a.deallocate(p, n) </tt>
      */
      static _GLIBCXX20_CONSTEXPR void
      deallocate(_Alloc& __a, pointer __p, size_type __n)
      { __a.deallocate(__p, __n); }

回顾一下，也就是 operator delete 啦！

construct

在一块指定内存上构造对象，具体接口为：

      /**
       *  @brief  Construct an object of type `_Tp`
       *  @param  __a  An allocator.
       *  @param  __p  Pointer to memory of suitable size and alignment for Tp
       *  @param  __args Constructor arguments.
       *
       *  Calls <tt> __a.construct(__p, std::forward<Args>(__args)...) </tt>
       *  if that expression is well-formed, otherwise uses placement-new
       *  to construct an object of type @a _Tp at location @a __p from the
       *  arguments @a __args...
      */
      template<typename _Tp, typename... _Args>
	static _GLIBCXX20_CONSTEXPR auto
	construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
	noexcept(noexcept(_S_construct(__a, __p,
				       std::forward<_Args>(__args)...)))
	-> decltype(_S_construct(__a, __p, std::forward<_Args>(__args)...))
	{ _S_construct(__a, __p, std::forward<_Args>(__args)...); }

注释向我们指出，如果 __a.construct 是 well-formed （有定义的意思），那就调用之，否则会使用 placement-new 去把对象创建在 __p 上。实际也正如此：

      template<typename _Tp, typename... _Args>
	static _GLIBCXX14_CONSTEXPR _Require<__has_construct<_Tp, _Args...>>
	_S_construct(_Alloc& __a, _Tp* __p, _Args&&... __args)
	noexcept(noexcept(__a.construct(__p, std::forward<_Args>(__args)...)))
	{ __a.construct(__p, std::forward<_Args>(__args)...); }

      template<typename _Tp, typename... _Args>
	static _GLIBCXX14_CONSTEXPR
	_Require<__and_<__not_<__has_construct<_Tp, _Args...>>,
			       is_constructible<_Tp, _Args...>>>
	_S_construct(_Alloc&, _Tp* __p, _Args&&... __args)
	noexcept(std::is_nothrow_constructible<_Tp, _Args...>::value)
	{
#if __cplusplus <= 201703L
	  ::new((void*)__p) _Tp(std::forward<_Args>(__args)...);
#else
	  std::construct_at(__p, std::forward<_Args>(__args)...);
#endif
	}

这里在CPP 17以后用了 construct_at 来代替 placement new ，说是可以支持编译期常量。内存分配都能编译期搞定，亏贼，暂未调研其细节。

destroy

析构。

      /**
       *  @brief  Destroy an object of type @a _Tp
       *  @param  __a  An allocator.
       *  @param  __p  Pointer to the object to destroy
       *
       *  Calls @c __a.destroy(__p) if that expression is well-formed,
       *  otherwise calls @c __p->~_Tp()
      */
      template<typename _Tp>
	static _GLIBCXX20_CONSTEXPR void
	destroy(_Alloc& __a, _Tp* __p)
	noexcept(noexcept(_S_destroy(__a, __p, 0)))
	{ _S_destroy(__a, __p, 0); }

      template<typename _Alloc2, typename _Tp>
	static _GLIBCXX14_CONSTEXPR auto
	_S_destroy(_Alloc2& __a, _Tp* __p, int)
	noexcept(noexcept(__a.destroy(__p)))
	-> decltype(__a.destroy(__p))
	{ __a.destroy(__p); }

      template<typename _Alloc2, typename _Tp>
	static _GLIBCXX14_CONSTEXPR void
	_S_destroy(_Alloc2&, _Tp* __p, ...)
	noexcept(std::is_nothrow_destructible<_Tp>::value)
	{ std::_Destroy(__p); }

std::_Destroy 在 bits/stl_construct.h 中，本质上就是调了指针指向对象的析构函数而已。

max_size

返回能够分配多少份内存（注意，应按 value_type 为单位），实现简单，此处略。

select_on_container_copy_construction

查了下资料4 ，感觉本质上还是希望 allocator 能感知到容器拷贝，对于一些特殊的 allocator 可能是需要的，对于常用的标准的 new_allocator 来说没有实现这么个接口，因此会直接返回原本的 allocator 。

对于内置类型和 void ， allocator_traits 分别进行了偏特化，其中 allocator_traits<allocator<void>> 本身只允许部分操作（比如 construct ），其他的都 delete 掉了。

Clang

可读性赞爆，但实际上没有什么新东西，直接简单摘录。

allocate

    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
    static pointer allocate(allocator_type& __a, size_type __n) {
        return __a.allocate(__n);
    }

    template <class _Ap = _Alloc, class =
        _EnableIf<__has_allocate_hint<_Ap, size_type, const_void_pointer>::value> >
    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
    static pointer allocate(allocator_type& __a, size_type __n, const_void_pointer __hint) {
        _LIBCPP_SUPPRESS_DEPRECATED_PUSH
        return __a.allocate(__n, __hint);
        _LIBCPP_SUPPRESS_DEPRECATED_POP
    }
    template <class _Ap = _Alloc, class = void, class =
        _EnableIf<!__has_allocate_hint<_Ap, size_type, const_void_pointer>::value> >
    _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
    static pointer allocate(allocator_type& __a, size_type __n, const_void_pointer) {
        return __a.allocate(__n);
    }

这里也对 hint 做了一些区分，实际上没有太大用处。

deallocate

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

construct

    template <class _Tp, class... _Args, class =
        _EnableIf<__has_construct<allocator_type, _Tp*, _Args...>::value> >
    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
    static void construct(allocator_type& __a, _Tp* __p, _Args&&... __args) {
        _LIBCPP_SUPPRESS_DEPRECATED_PUSH
        __a.construct(__p, _VSTD::forward<_Args>(__args)...);
        _LIBCPP_SUPPRESS_DEPRECATED_POP
    }
    template <class _Tp, class... _Args, class = void, class =
        _EnableIf<!__has_construct<allocator_type, _Tp*, _Args...>::value> >
    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
    static void construct(allocator_type&, _Tp* __p, _Args&&... __args) {
#if _LIBCPP_STD_VER > 17
        _VSTD::construct_at(__p, _VSTD::forward<_Args>(__args)...);
#else
        ::new ((void*)__p) _Tp(_VSTD::forward<_Args>(__args)...);
#endif
    }

逻辑和GCC差不多，如果 allocator 定义了 construct 就调用，否则直接用 placement new 。

// __has_construct
template <class, class _Alloc, class ..._Args>
struct __has_construct_impl : false_type { };

template <class _Alloc, class ..._Args>
struct __has_construct_impl<decltype(
    (void)declval<_Alloc>().construct(declval<_Args>()...)
), _Alloc, _Args...> : true_type { };

template <class _Alloc, class ..._Args>
struct __has_construct : __has_construct_impl<void, _Alloc, _Args...> { };

destroy

    template <class _Tp, class =
        _EnableIf<__has_destroy<allocator_type, _Tp*>::value> >
    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
    static void destroy(allocator_type& __a, _Tp* __p) {
        _LIBCPP_SUPPRESS_DEPRECATED_PUSH
        __a.destroy(__p);
        _LIBCPP_SUPPRESS_DEPRECATED_POP
    }
    template <class _Tp, class = void, class =
        _EnableIf<!__has_destroy<allocator_type, _Tp*>::value> >
    _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
    static void destroy(allocator_type&, _Tp* __p) {
#if _LIBCPP_STD_VER > 17
        _VSTD::destroy_at(__p);
#else
        __p->~_Tp();
#endif
    }

参考资料

  1. https://www.codeproject.com/articles/4795/c-standard-allocator-an-introduction-and-implement ↩︎

  2. https://thealexcons.github.io/custom-memory-allocators/index.html ↩︎

  3. allocator | gcc ↩︎

  4. select_on_container_copy_construction | cppreference ↩︎

技术
最后更新于 Mar 31, 2024
© 2020 - 2024 XR_G's Blog
有朋自远方来，不亦说乎？
Built with Hugo
Theme Stack designed by Jimmy