设计模式之美32｜容器里的内存管理：分配器

32｜容器里的内存管理：分配器

你好，我是吴咏炜。

上一讲里我们讨论了 C++ 里内存管理的基本工具，分配和释放函数。今天，我们来讨论一下容器里管理内存的机制——分配器（allocator）。

一点点历史

从网上可以找到的 SGI STL 的文档 [1] 中能够看到，在 C++ 标准化之前，STL 已经引入了分配器的概念，并且还引入了多种分配器，为不同的使用场景进行优化：

• alloc：线程安全的默认分配器；默认对小于 128 字节的分配要求使用内存池，超过则使用 malloc_alloc
• pthread_alloc：每线程使用独立内存池的分配器
• single_client_alloc：线程不安全的快速分配器
• malloc_alloc：调用 malloc 和 free 来分配和释放内存的分配器

分配器的目的是分离对象的构造和内存分配。显然，这种方式把内存分配的决策交给了容器（而非对象），带来了很大的灵活性，性能上也有好处，因此较早的 C++ 标准库的实现也都沿袭了 SGI STL 里的这些分配器。

不过，随着时间的发展，大家也慢慢放弃了 SGI STL 实现里的这些不同的分配器，而只使用 C++ 标准里定义的 std::allocator 了。除了标准里定义的分配器和 SGI STL 的接口不同外，一个很重要的原因恐怕是分配器是容器类型的一部分，因此使用不同分配器的容器是不同的类型：一个要求 vector<int>& 作为形参类型的函数，是不能接受 vector<int, single_client_alloc<int> > 作为实参类型的。这个问题要到 C++17 引入多态分配器（ polymorphic_allocator）才算部分得到解决。

在 SGI STL 的实现里，分配器需要提供两个静态成员函数：

• static void* allocate(size_t n)
• static void deallocate(void* p, size_t n)

这跟我们上一讲讨论的分配和释放函数非常相似，只除了一点——这里的 deallocate 是可以看到释放的内存块的大小的。这当然对性能很有好处：有了它，我们可以很方便地根据内存块的大小来实现内存池。另外需要注意的一个细节是 allocate 和 deallocate 都是静态成员函数，因此 SGI STL 里的分配器只有全局状态，不能根据实例来区分状态。

C++98 的分配器里最重要的成员函数同样是 allocate 和 deallocate，但形式和语义都进行了修改，并且不再是静态成员函数，因而理论上它们可以拥有非全局的状态。可惜的是，“尽管不要求自定义分配器为无状态，标准库中是否及如何支持分配器是实现定义的。若实现不支持使用不相等的分配器值，则这种使用可能导致实现定义的运行时错误或未定义行为” [2]。也就是说，在 C++98 的年代里，你最好使用跟 SGI STL 分配器一样不携带状态的分配器，否则可能有兼容性问题。

C++98 的分配器里另外一个问题是有点过度设计了。分配器不仅要负责对象的内存分配和释放，还要负责构造和析构——分配器需要有成员函数 construct 和 destroy。这个功能不能说一点用都没有（比如，你可以用它来跟踪某种对象在容器中被构造了多少次），但用处真的不大，跟分配器的关系也有点远。

从 C++11 开始，在 allocator_traits 的帮助下，我们终于可以进一步抛开一些不必要的细节，在保留向后兼容性的同时，简单而快速地实现出自己需要的分配器。分配器也明确规定了 可以 有自己的状态。下面，我们就以 C++17 里的分配器要求为基础来讨论一下分配器的实现。

标准分配器

标准分配器 std::allocator 是一个非常简单的分配器。下面，我们就一起看一个标准分配器的示例实现，来了解一下分配器里的必要成员：

template <class T>
class allocator {
public:
  using size_type = size_t;
  using difference_type = ptrdiff_t;
  using value_type = T;

  using is_always_equal = true_type;
  using propagate_on_container_move_assignment =
    true_type;

  template <class U>
  struct rebind {
    using other = allocator<U>;
  };

  allocator() = default;

  template <class U>
  allocator(
    const allocator<U>&) noexcept
  {}

  T* allocate(size_t n)
  {
    return static_cast<T*>(
      ::operator new(n *
                     sizeof(T)));
  }

  void deallocate(T* p,
                  size_t n) noexcept
  {
    ::operator delete(p);
  }
};

头三个类型别名基本上永远这样写，不需要修改。把 is_always_equal 定义为 true_type，意味着这个分配器是没有内部状态的，所有的标准分配器都相等。类似地，我们把 propagate_on_container_move_assignment 定义为 true_type，意味着在容器移动的时候目标容器可以取得源内存的所有权，这样可以高效地进行移动（否则目标容器即使在移动赋值时仍然只能对所有元素逐个构造或赋值）。类似的特征成员还有 propagate_on_container_copy_assignment 和 propagate_on_container_swap，不过这两个我们取默认值 false_type 就行（这些特征的详细说明请参考 [2]）。

上一讲我们提到类特定的分配和释放函数的一个大问题是，当对象放到容器里的时候，对象的内存空间一般是和所需的其他数据一起分配的。以 GCC 11 标准库的 std::set 为例：当你创建 set<Obj> 的时候，结点的真正类型是 std::_Rb_tree_node<Obj>，而用户对象则存储在这个结点对象的内存里。因此，类特定的分配和释放函数对此是无效的。

分配器解决这个问题的方式是 rebind（重新绑定）成员类模板。以 set<Obj> 为例，它的默认模板参数规定了默认分配器是 allocator<Obj>，在 set 的实现里实际使用的分配器类型最终会变成 allocator<Obj>::rebind<_Rb_tree_node<Obj>>::other，用这个分配器分配出来的内存大小就是红黑树的结点大小，而不是用户对象的大小了。

标准分配器没有数据成员，所以我们使用缺省的默认构造函数就可以了。我们需要显式声明缺省的默认构造函数，是因为我们还有另外一个构造函数，一个可以接受使用其他模板参数的 std::allocator 的构造函数。它也不需要实际做任何事情。

真正需要干活的，就是 allocate 和 deallocate 函数了。跟 SGI STL 的分配器不同，标准库里的分配器是知道自己要为什么类型分配内存的，所以 allocate 的参数不是要分配内存的对象的大小，而是要分配内存的对象的数量。在这个最简单的 std::allocator 里，那就是简单地计算出所需分配的内存的大小，然后调用全局的 operator new 来分配内存了。类似地， deallocate 会得到需要释放的指针和这个指针指向的对象的数量。由于目前我们的实现只是简单地调用 operator delete 来释放内存，数量这个参数也就不使用了。

分配器特征

我上面给出的 allocator 跟目前 C++17 里的标准分配器还是有点小区别，最主要就是在 C++17 里标准分配器仍然有 construct 和 destroy 等成员，虽然它们已经是不必要的了。以这两个成员函数为例，它们的定义非常简单：

template <class T>
class allocator {
public:
  …
  template <typename U,
            typename... Args>
  void
  construct(U* p, Args&&... args) noexcept(
    std::is_nothrow_constructible<
      U, Args...>::value)
  {
    ::new((void*)p) U(
      std::forward<Args>(args)...);
  }

  template <typename U>
  void destroy(U* p) noexcept(
    std::is_nothrow_destructible<
      U>::value)
  {
    p->~U();
  }
};

相信你在学过了完美转发（ ）、type traits（ ）、可变模板（ ）和分配函数（ ）之后，理解上面的代码应该已经没什么问题了。唯一需要略加说明一下的是， noexcept 说明里的编译期布尔表达式是用来计算当前函数是否会抛出异常的。这样，如果能用 Args... 来无异常地构造 U 对象，那 construct 函数也能保证不抛异常；如果 U 的析构能够不抛异常，那 destroy 函数也能保证不抛异常。

这两个函数在 C++17 里被标为废弃，在 C++20 里被正式移除。我们的替代方案，就是在分配器没有提供某个成员的时候，可以通过分配器特征（ allocator_traits）提供默认版本。基本技巧就是我们在 讨论的 SFINAE。比如，在 GCC 的头文件 bits/alloc_traits.h 你可以找到别名模板 __has_construct，就是用来检测分配器是不是有参数形式匹配的 construct 成员函数。略去 noexcept 的处理， allocator_traits 里对 construct 的处理大致如下：

template <typename Alloc>
struct allocator_traits {
  …
  template <typename T,
            typename... Args>
  using __has_construct = …;
  template <typename T,
            typename... Args>
  static enable_if_t<
    __has_construct<T,
                    Args...>::value>
  construct(Alloc& a, T* p,
            Args&&... args)
  { // Alloc 里面有 construct 的情况
    a.construct(
      p, forward<Args>(args)...);
  }
  template <typename T,
            typename... Args>
  static enable_if_t<
    !__has_construct<T,
                     Args...>::value>
  construct(Alloc& a, T* p,
            Args&&... args)
  { // Alloc 里面没有 construct 的情况
    new(p) T(forward<Args>(args)...);
  }
};

对于其他可能缺失的成员的处理也大致如此。

多态分配器

我们前面已经提到，分配器是容器的类型的一部分，因而同种容器有不同的分配器也被视作不同的类型。如果我们在代码中使用了不同的分配器，又希望忽略分配器的不同，特别是在函数的形参之中，那多态分配器就有了用武之地。

在多态分配器里，把内存管理的功能放在一个抽象类 memory_resource（内存资源；[3]）里面。它提供下面这三个主要接口：

• void* allocate(size_t bytes, size_t alignment = alignof(max_align_t));
• void deallocate(void* p, size_t bytes, size_t alignment = alignof(max_align_t));
• bool is_equal(const memory_resource& other) const noexcept;

可以看到，这个接口又回到了 SGI STL 那种纯粹的内存分配的样子。不过，里面加上了新的对齐参数，默认值是跟平台最大的标量类型一致。另外，专门有一个接口用来多态地检查两个 memory_resource 是否相等。

这三个接口都是需要子类来“实现”的。但这三个函数本身不是虚函数——它们会调用前面加上 do_ 前缀的保护成员函数，这才是子类里需要覆盖的。一个简单能实际干活的子类可能长这个样子：

class new_delete_alloc_resource
  : public pmr::memory_resource {
protected:
  void* do_allocate(
    size_t bytes,
    size_t alignment) override
  {
    return ::operator new(
      bytes, align_val_t{alignment});
  }

  void do_deallocate(
    void* p, size_t bytes,
    size_t alignment) override
  {
    ::operator delete(
      p, align_val_t{alignment});
  }

  bool do_is_equal(
    const pmr::memory_resource&
      other) const noexcept override
  {
    return dynamic_cast<
      const new_delete_alloc_resource*>(
      &other);
  }
};

也就是说，我们调用全局的 operator new 和 operator delete 来分配和释放内存；而任何两个 new_delete_alloc_resource 都被视作相等，因此我们只需要使用 dynamic_cast 检查 other 也是个 new_delete_alloc_resource 就可以了。

另外， pmr 名空间里也提供了针对两个 memory_resource 的相等和不等运算符。相等定义为：

inline bool operator==(
  const memory_resource& a,
  const memory_resource& b) noexcept
{
  return &a == &b || a.is_equal(b);
}

即，两个 memory_resource 是同一个，或者 is_equal 函数返回真。

不等运算符从 C++20 开始能根据相等运算符自动提供，在 C++20 之前总是定义成相等运算符的否操作（ !(a == b)）。

我们定义的 new_delete_alloc_resource 是一个 memory_resource，我们需要把这个 memory_resource 注入到 polymorphic_allocator（多态分配器；[4]）里才能真正使用。 polymorphic_allocator 里面只保存一个 memory_resource 的指针，它的成员函数基本上也只是转发调用 memory_resource 的成员函数。向 polymorphic_allocator 注入的方式有两种：

对于第一种情况，我们多半需要使用函数 pmr::set_default_resource[6] 来修改默认的内存资源。默认值是 new_delete_resource()[7] 返回的 memory_resource 指针，使用 new 和 delete 来进行内存分配和释放，功能上像我上面定义的 new_delete_alloc_resource。注意这一修改是全局的，会影响所有后面的 polymorphic_allocator 的默认构造，因而存在潜在的多线程冲突问题。

无论是上面哪种情况，程序员都需要确保内存资源对象在多态分配器的存续期间也一直存在，否则即会导致未定义行为。因此，内存资源对象常常会被实现为一个单件，如标准库中 new_delete_resource 和 null_memory_resource[8] 函数返回的内存资源对象就是如此。

不过，我们如果小心管理内存的话，生命期更短的对象也是可以的。标准库提供的内存池内存资源 [9]、[10] 和单调缓冲区内存资源 [11]，就展示了一些更大的灵活性。下面是使用单线程无保护内存池 [10] 的一个例子：

pmr::unsynchronized_pool_resource
  res;
pmr::polymorphic_allocator<int>
  a{&res};

{
  set<int, less<int>,
      pmr::polymorphic_allocator<int>>
    s(a);
  // 使用 s，会自动使用内存池
} // s 的生命周期不可长于 res

到这里，你应该已经看到多态内存池的强大功能了。不过，有一个使用多态内存池的后果不知道你留意到了没有：跟把 propagate_on_container_move_assignment 设为 false_type 一样，移动的行为可能会发生变化。使用默认分配器时，如果你把一个 vector 移动赋值到另外一个 vector，编译器不会产生元素对象移动的代码，因为只需要调整一下 vector 本身的指针就可以了。而现在只有在分配器相等的情况下才能这样做了；在不相等时，就只能两个 vector 各自使用分配器分配内存，然后把源 vector 里面的元素逐个移动过去……

此外，使用分配器的标准容器在 pmr 名空间下都存在别名模板：我们可以使用 std::pmr::set<int>，而不是又臭又长的 std::set<int, std::less<int>, std::pmr::polymorphic_allocator<int>>。这让我们在容器中使用多态分配器会方便很多。

最后再补充一句，使用多态分配器是一个系统工程，毕竟 std::vector<int> 和 std::pmr::vector<int> 仍然是两个不同的类型。这也是目前多态分配器仍没有被广泛使用的主要原因之一吧。

内容小结

本讲我们详细讲解了分配器这一概念，包括标准前的 SGI STL 分配器、标准的分配器、分配器特征和多态分配器。这些功能一起为内存管理提供了极大的灵活性。

课后思考

请阅读一下你使用的 C++ 标准库里的分配器相关源码，并考虑一下洋葱原则在相关设计里的体现。有任何问题或想吐槽的地方，欢迎留言和我分享。

参考资料

[1] SGI, “Standard Template Library programmer’s guide”. 原本属于 SGI 网站的一部分，后属于惠普分拆出来的 HPE；HPE 在 2018 年初宣布将其下线，目前只能通过 Internet Archive 访问——在国内直接访问可能有问题

[2] cppreference.com, “C++ named requirements: Allocator”.

[2a] cppreference.com, “C++ 具名要求：分配器 (Allocator)”.

[3] cppreference.com, “std::pmr::memory_resource”.

[3a] cppreference.com, “std::pmr::memory_resource”.

[4] cppreference.com, “std::pmr::polymorphic_allocator”.

[4a] cppreference.com, “std::pmr::polymorphic_allocator”.

[5] cppreference.com, “std::pmr::get_default_resource”.

[5a] cppreference.com, “std::pmr::set_default_resource”.

[6] cppreference.com, “std::pmr::set_default_resource”.

[6a] cppreference.com, “std::pmr::set_default_resource”.

[7] cppreference.com, “std::pmr::new_delete_resource”.

[7a] cppreference.com, “std::pmr::new_delete_resource”.

[8] cppreference.com, “std::pmr::null_memory_resource”.

[8a] cppreference.com, “std::pmr::null_memory_resource”.

[9] cppreference.com, “std::pmr::synchronized_pool_resource”.

[9a] cppreference.com, “std::pmr::synchronized_pool_resource”.

[10] cppreference.com, “std::pmr::unsynchronized_pool_resource”.

[10a] cppreference.com, “std::pmr::unsynchronized_pool_resource”.

[11] cppreference.com, “std::pmr::monotonic_buffer_resource”.

[11a] cppreference.com, “std::pmr::monotonic_buffer_resource”.