前言：之前看过侯老师的《STL源码剖析》但是那已经是多年以前的，现在工作中有时候查问题和崩溃都需要了解实际工作中使用到的STL的实现。因此计划把STL的源码再过一遍。
  摘要：本文描述了llvm中libcxx的allocator的实现。
  关键字：allocator
  其他：参考代码LLVM-libcxx
  注意：参考代码时llvm的实现，与gnu和msvc的实现都有区别。

1 allocator

1.1 简介

  allocator是STL中对一个堆内存分配器，是对内存申请工作的一个封装，将内存的申请和成员的构造抽象开来方便控制。基本上，C++标准库中的容器的默认分配器都是allocator。在C++中分配器是通过模板参数的方式指定给对应的容器，默认就是allocator，用户自己也可以实现自己的内存管理类，对堆的内存进行有效的管理也可以将对应的分配器指定给容器使用（前提是接口保持一致）。

    std::allocator alloc1;// demonstrating the few directly usable membersstatic_assert(std::is_same_v);int* p1 = alloc1.allocate(1); // space for one intalloc1.deallocate(p1, 1);     // and it is gone

1.2 allocator的实现

  先简单看下allocator的声明，其中_LIBCPP_TEMPLATE_VIS是不同版本编译期的可见性宏，标准库的源码中有大量类似的宏，我们大概直到意思即可不用深究。

template 
class _LIBCPP_TEMPLATE_VIS allocator: private __non_trivial_if::value, allocator<_Tp> >

  allocator继承的__non_trivial_if是一个空类，该类利用cpp的CRTP实现编译期的多态。该类由一个偏特化版本区别是带有non-trivial的构造函数。在allocator中非void类型都是匹配第二个，void类型匹配第一个。而模板的第二个参数_Unique是为了保持菱形继承过程中的ABI稳定而设置的。

template 
struct __non_trivial_if { };template 
struct __non_trivial_if {_LIBCPP_INLINE_VISIBILITY_LIBCPP_CONSTEXPR __non_trivial_if() _NOEXCEPT { }
};

allocate函数
  allocate函数是用来分配堆内存，可以看到内部实现调用了operator new。该函数实现的基本逻辑就是检查当前希望分配的大小是否可满足（allocator_traits下面会详细描述，暂时就理解为一个类型系统），不满足就会抛出异常，否则会调用对应的分配函数进行分配。__libcpp_is_constant_evaluated用来判断当前函数是否为constexpr。libcpp_alocate的区别内部依然调用了::operator new实现，只是有内存对齐。另外，这里不用new，而是使用::operator new应该是为了避免用户承载了new```的实现而导致无法真正分配到内存。

  _VSTD类似于std，也是一个名字空间。
  _VSTDis now an alias for stdinstead of std::_LIBCPP_ABI_NAMESPACE.
This is technically not a functional change, except for folks that might have been
using _VSTDin creative ways (which has never been officially supported). ————来源libcxx/docs/ReleaseNotes.rs

_LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20_Tp* allocate(size_t __n) {if (__n > allocator_traits::max_size(*this))__throw_bad_array_new_length();if (__libcpp_is_constant_evaluated()) {return static_cast<_Tp*>(::operator new(__n * sizeof(_Tp)));} else {return static_cast<_Tp*>(_VSTD::__libcpp_allocate(__n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp)));}}

deallocate
  deallocate是用来释放内存的，其实现和allocate基本类似。

_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20void deallocate(_Tp* __p, size_t __n) _NOEXCEPT {if (__libcpp_is_constant_evaluated()) {::operator delete(__p);} else {_VSTD::__libcpp_deallocate((void*)__p, __n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp));}}

construct和destroy
  construct（仅仅在对应内存上构造对象）和destroy（仅仅调用析构函数）函数的实现比较简单就是直接显式调用构造函数和析构函数。

template _LIBCPP_DEPRECATED_IN_CXX17 _LIBCPP_INLINE_VISIBILITYvoid construct(_Up* __p, _Args&&... __args) {::new ((void*)__p) _Up(_VSTD::forward<_Args>(__args)...);}_LIBCPP_DEPRECATED_IN_CXX17 _LIBCPP_INLINE_VISIBILITYvoid destroy(pointer __p) {__p->~_Tp();}

rebind
  获取另一个类型的allocator，对于带有节点的数据结构，当前allocator只能管理节点数据的内存但是对于节点本身是无法管理的，使用这样的方式能够让二者的管理统一。

template struct _LIBCPP_DEPRECATED_IN_CXX17 rebind {typedef allocator<_Up> other;};

2 allocator特化版本

2.1 const allocator

  const特化版本主要是allocate时返回的是const的函数指针，且在释放时会通过const_cast去除const进行释放。

const _Tp* allocate(size_t __n) {if (__n > allocator_traits::max_size(*this))__throw_bad_array_new_length();if (__libcpp_is_constant_evaluated()) {return static_cast(::operator new(__n * sizeof(_Tp)));} else {return static_cast(_VSTD::__libcpp_allocate(__n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp)));}
}void deallocate(const _Tp* __p, size_t __n) {if (__libcpp_is_constant_evaluated()) {::operator delete(const_cast<_Tp*>(__p));} else {_VSTD::__libcpp_deallocate((void*) const_cast<_Tp *>(__p), __n * sizeof(_Tp), _LIBCPP_ALIGNOF(_Tp));}
}

2.2 void allocator

  allocator的void特化版本就是一个空壳子，什么也没有。

template <>
class _LIBCPP_TEMPLATE_VIS allocator
{
#if _LIBCPP_STD_VER <= 17 || defined(_LIBCPP_ENABLE_CXX20_REMOVED_ALLOCATOR_MEMBERS)
public:_LIBCPP_DEPRECATED_IN_CXX17 typedef void*             pointer;_LIBCPP_DEPRECATED_IN_CXX17 typedef const void*       const_pointer;_LIBCPP_DEPRECATED_IN_CXX17 typedef void              value_type;template  struct _LIBCPP_DEPRECATED_IN_CXX17 rebind {typedef allocator<_Up> other;};
#endif
};

3 类型萃取allocator_traits

  allocator_traits将当前类型的类型抽象到一个类中，其实现就是一个类型集合。allocator_traits额外提供了一些关于内存分配的函数，比如max_size等。

template 
struct _LIBCPP_TEMPLATE_VIS allocator_traits
{using allocator_type = _Alloc;using value_type = typename allocator_type::value_type;using pointer = typename __pointer::type;using const_pointer = typename __const_pointer::type;using void_pointer = typename __void_pointer::type;using const_void_pointer = typename __const_void_pointer::type;using difference_type = typename __alloc_traits_difference_type::type;using size_type = typename __size_type::type;using propagate_on_container_copy_assignment = typename __propagate_on_container_copy_assignment::type;using propagate_on_container_move_assignment = typename __propagate_on_container_move_assignment::type;using propagate_on_container_swap = typename __propagate_on_container_swap::type;using is_always_equal = typename __is_always_equal::type;
};

    template ::value> >_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20static size_type max_size(const allocator_type&) _NOEXCEPT {return numeric_limits::max() / sizeof(value_type);}

3 参考文献

• cppreference-allocator
• llvm-review-vstd
• Difference between “destroy” “destructor” “deallocate” in std::allocator?
• STL源码阅读小记(一)——Allocator