14.3. 传统分配器

分配器(allocators)几十年来一直是 C++ 的核心组成部分，但它们以多种不同的形式和面貌存在过。本章中，我们将采用一种大致按时间顺序的方式，从早期(且更为复杂的)分配器类型开始，逐步过渡到更简单且更通用的类型。

要理解本章内容，一个关键概念是：容器类型如 std::vector<T> 实际上并不存在。真正存在的是 std::vector<T, A> 类型，其中默认情况下，A 是 std::allocator<T>，它通过 ::operator new() 进行内存分配，并通过 ::operator delete() 进行内存释放。当我们提到“传统分配器”时，指的是作为容器类型一部分的分配器类型(这并不是编写分配器的唯一方式，稍后讨论 PMR 分配器时，会看到其他方法)。

首先探讨在 C++11 之前编写一个分配器需要满足哪些要求，以及像 std::vector<T, A> 这样的容器如何使用类型为 A 的对象来抽象其内存分配任务。关于分配器表达方式的改进，将在本章后续章节中陆续介绍。

14.3.1 C++11 之前

传统分配器在 C++11 之前就已经存在，但编写它们的任务对于许多人来说显得非常艰巨，因为需要实现大量成员函数。回顾那个时代，开发者必须手动编写许多内容，而且需要注意的是，随着分配器 API 的不断演进，以下内容在今天并非仍然适用。

我们将介绍一个名为 small_allocator<T> 的分配器，并以类似 std::allocator<T> 的方式实现它，从而突出在 C++11 时代编写分配器的含义。之后，还将将其与使用较新标准编写的功能等价的分配器进行对比。实现过程中，会使用 C++17 的特性，以避免在这个本就微妙的话题上引入不必要的复杂性。

介绍完 small_allocator<T> 之后，还将展示第 12 章和第 13 章中提到的 Vector<T> 如何增强为 Vector<T, A>，并说明其中的 A 可以是 std::allocator<T>、small_allocator<T>，或者任何符合标准的分配器类型。这将展示分配器如何与容器解耦，从而提升容器的灵活性和适应性。

类型别名

一个针对类型 T 的分配器必须暴露一系列类型别名(type aliases)，包括 value_type、size_type、difference_type(即两个指针相减后所得的类型)、pointer、const_pointer、reference 和 const_reference。一种理解方式是：对于容器来说，分配器代表了底层内存，因此需要定义最能描述这些底层概念的类型。这样一来，容器就可以将自己的类型别名与分配器提供的对应类型保持一致，以实现兼容性。

在 small_allocator<T> 类型中，这将体现为：

template <class T>
struct small_allocator {
  using value_type = T;
  using pointer = T*;
  using const_pointer = const T*;

  using reference = T&;
  using const_reference = const T&;

  using size_type = std::size_t;
  using difference_type = std::ptrdiff_t;
  // ...

实际上，对于一个针对类型 T 的分配器，除非在一些极其特殊的情况下，都可以期望这些类型别名与 small_allocator<T> 中所展示的相对应：只要 value_type 正确定义，其他类型几乎总是可以推导出来。

成员函数

一个针对类型 T 的分配器必须暴露一个成员函数 max_size()，用于返回该分配器所能实际分配的最大内存块大小。

实践中，这个函数证明难以真正实现，因为在某些操作系统上，内存分配总是会成功(但若程序申请了过多内存，使用这些内存时可能会失败)。因此，这个函数通常只能基于特定平台以“尽最大努力”的方式实现。一个可能的实现如下：

// ...
constexpr size_type max_size() const {
  return std::numeric_limits<size_type>::max(); // bah
}
// ...

一个针对类型 T 的分配器还必须暴露两个函数重载，这个函数用到了作者的学生们在单个函数签名中“最喜欢”(注意这里的讽刺！)的所有关键词。它们是：pointer address(reference r)和const_pointer address(const_reference r)，用于常量对象。此处的意图是对“如何获取一个对象的地址”这一操作进行抽象。

我们可能会忍不住将这两个函数简单实现为 return &r;，但在实践中，这样做是非常危险的。因为允许用户为其类型重载一元 operator&()，所以这样的实现会调用任意用户代码，这无疑是一个令人不安的情况……除非真的有充足的理由，否则不要轻易去重载像“取对象地址”这样基础的操作，即使有正当理由，也应考虑是否有替代方案可以解决问题！

一个更好的实现方式是通过 return std::addressof(r); 来实现这些函数。其中，std::addressof() 是 <memory> 头文件中的一个“魔法”标准库函数(而且是 constexpr 的)，可以在不经过重载机制的前提下返回对象的地址，从而避免上述问题：

// ...
constexpr pointer address(reference r) const {
  return std::addressof(r);
}

constexpr
const_pointer address(const_reference r) const {
  return std::addressof(r);
}
// ...

显然，分配器需要暴露一些成员函数，来执行实际的内存分配与释放操作。这些函数的签名是：

pointer allocate(size_type n)

void deallocate(pointer p, size_type n)

其分别用于分配和释放足以存储 n 个类型为 T 的对象的内存块。对这两个函数的简单实现可能如下所示：

// ...
pointer allocate(size_type n) {
  auto p = static_cast<pointer>(
    malloc(n * sizeof(value_type))
  );

  if (!p) throw std::bad_alloc{};

  return p;
}

void deallocate(pointer p, size_type) {
  free(p);
}
// ...

allocate() 成员函数过去还有一个第二个参数，类型为 void*，名为 hint，默认初始化为 nullptr。该参数的目的是告知分配器可能用于提供存储的内存位置，以防容器已经知道这样一个位置。但在实践中，这个功能几乎(即使有)很少使用，因此它在 C++17 中弃用，并在 C++20 中移除。

这两个函数正是分配器存在的核心所在：

• allocate()：返回一块足够大的内存块，能够容纳 n 个连续的 value_type 类型对象，在分配失败时抛出 bad_alloc 异常；

• deallocate()：释放一块足够大的内存块，能够容纳 n 个连续的 value_type 类型对象。

当编写一个分配器时，通常是为了针对某一特定问题提供定制化的解决方案。

allocate() 和 deallocate() 都刻意对使用端代码撒了谎：它们处理的是原始内存，既不创建也不销毁 T 类型的对象。然而，allocate() 返回的是一个指向 T 的指针(本质上是一个 T*)，而 deallocate() 接受一个指针作为参数，即使在调用前所有 T 类型的对象都应销毁。

这些函数对类型系统“撒谎”的事实，从某种意义上来说是一件好事，这减轻了容器自身必须去“撒谎”的负担。当然，容器必须清楚这些函数的实际行为，不应假设 allocate() 返回的内存或传递给 deallocate() 的内存中，已经存在有效的对象。

最后，分配器还需要暴露一些成员函数，用于将原始内存转变为对象，反之亦然。其中：construct(pointer p, const_reference r)：用于在预先分配好的内存位置 p 处构造 r 的一个副本；destroy(pointer p)：用于销毁位于位置 p 的对象(但不会释放其底层存储)：

  // ...
  void construct(pointer p, const_reference r) {
    new (static_cast<void*>(p)) value_type(r);
  }

  void destroy(const_pointer p) {
    if(p) p->~value_type();
  }

  // ...

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

大多数实现本质上都会执行与上述代码相同的操作。虽然也存在其他实现方式，但在实际中很少见。

这些函数对类型系统进行了“欺骗”：construct() 函数接受一个指针(实际上是一个 T*)作为参数，但在调用该函数时，该指针指向的是原始内存，而不是一个 T 类型的对象。

分配器的另一个要求是：定义两个不同类型的分配器对象是否相等。一个可能的实现如下所示：

// ...
template <class T, class U>
constexpr bool operator==(const small_allocator<T>&,
                          const small_allocator<U>&) {
  return true;
}

template <class T, class U>
constexpr bool operator!=(const small_allocator<T>&,
const small_allocator<U>&) {
  return false;
}

两个针对不同类型的 small_allocator 特化版本所描述的策略是相同的，因此认为是相等的。“但是等等！”有读者可能会问，“你在这种比较中是如何考虑分配器状态的呢？”这里有一个关键点要揭示：在 C++11 之前，分配器本质上认为是无状态的(stateless)。

好吧，它们其实并不完全无状态，但当时对于这样一个问题并没有明确的答案：如果一个带有状态的分配器与某个容器对象相关联，并且该容器对象被复制了，那么这个分配器的状态会发生什么？你看，如果分配器是有状态的，就必须知道在复制分配器时该如何处理这个状态。这个状态是被复制了吗？还是共享了？在 C++11 之前的时代，我们并不清楚在这种情况下应该怎么做。因此，除非容器是在某些不会被复制的上下文中使用 —— 例如一个位于函数内部的 vector，并且关联的分配器使用的是栈空间作为存储 —— 大多数人都完全避免使用有状态的分配器。

在研究如何编写“分配器感知”的容器之前，先退一步，看看如何调整第 12 章和第 13 章中使用的一些“未初始化内存操作算法”，使其能够使用分配器所提供的服务。这将减少后续重构过程中的工作量。

支持分配器感知的辅助算法

由于使用分配器来弥合“原始存储”与“对象”之间的鸿沟，在编写支持分配器的实现时，将无法继续使用第 12 章和第 13 章中介绍的那些原始内存操作算法。

当然可以选择在容器的每一处调用点，手动编写这些算法的完整版本，但这样做会非常繁琐(而且容易出错)。相反，我们将编写这些底层内存管理算法的简化版本，并让这些简化版本使用一个作为参数传入的分配器。通过这种方式，可以降低将容器改为“分配器感知”所带来的实现复杂性影响。

前三个这样的算法将是支持分配器的版本，用于初始化一系列值，以及销毁这样的一段值。为了尽量减少对现有实现的影响，我们将基本上使用与非分配器感知版本相同的函数签名，只添加一个分配器的引用作为参数。对于那个将一块原始内存填充为某个值的算法：

template <class A, class IIt, class T>
void uninitialized_fill_with_allocator(
  A& alloc, IIt bd, IIt ed, T init
) {
  // bd: 目的地的起始位置
  // ed: 目的地的终止位置
  auto p = bd;

  try {
    for (; p != ed; ++p)
      alloc.construct(p, init);
  } catch (...) {
    for (auto q = bd; q != p; ++q)
      alloc.destroy(q);
    throw;
  }
}

然后，对于将一段值复制到一块原始内存中的算法：

template <class A, class IIt, class OIt>
void uninitialized_copy_with_allocator(
  A& alloc, IIt bs, IIt es, OIt bd
) {
  // bs: 源的起始位置
  // es: 源的结束位置
  // bd: 目的地的起始位置
  auto p = bd;

  try {
    for (auto q = bs; q != es; ++q) {
      alloc.construct(p, *q);
    ++p;
  }
  } catch (...) {
    for (auto q = bd; q != p; ++q)
      alloc.destroy(q);
    throw;
  }
}

最后，对于将一系列对象转换为一块原始内存的算法：

template <class A, class It>
void destroy_with_allocator(A &alloc, It b, It e) {
  for (; b != e; ++b)
    alloc.destroy(b);
}

在每种情况下，如果在发生异常时能以与构造顺序相反的顺序销毁对象，实现将更加符合标准。可以自由地实现这一细微调整；它并不难，但这会给示例引入一些干扰代码。

我们将重写的另一个标准工具是 cmp_less()，允许将有符号值与无符号值进行比较，而不会受到 C 语言整数提升规则的影响。它并不直接与内存相关，但在 Vector<T> 实现中需要，并且是 C++20 的特性，所以在使用 C++17 编译时将无法使用：

template<class T, class U>
constexpr bool cmp_less(T a, U b) noexcept {
  if constexpr (std::is_signed_v<T> ==
                std::is_signed_v<U>)
    return a < b;
  else if constexpr (std::is_signed_v<T>)
    return a < 0 || std::make_unsigned_t<T>(a) < b;
  else
    return b >= 0 && a < std::make_unsigned_t<U>(b);
}

std::is_signed<T> 类型特性以及 std::make_unsigned<T>() 函数都可以在头文件 <type_traits> 中找到。

现在，看看这些分配器和支持算法如何在容器内使用：首先是一个使用连续存储的容器(我们的 Vector<T,A> 类)，然后是一个基于节点的容器(我们的 ForwardList<T,A> 类)。

一个使用分配器的 Vector<T,A> 类

在一个使用连续内存的容器(更具体地说，我们的 Vector<T> 类)中引入分配器感知(allocator awareness)功能，会对该容器的实现产生什么影响。在这种情况下，我们将以第12章中使用的显式内存管理方法作为基准，因为想要探索分配器感知所带来的影响，而这种方法有助于更清晰地展示实现上的变化，也可以将本章中的代码改编为使用隐式内存管理的方式。

从模板本身的签名开始来看，现在将拥有一个包含两个类型参数的模板，其中 T 表示元素的类型，A 表示分配器的类型，这里为 A 提供了一个合理的默认类型，以便普通用户无需担心这些技术细节：

template <class T, class A = std::allocator<T>>
class Vector : A { // 注意：私有继承
public:
  using value_type = typename A::value_type;
  using size_type = typename A::size_type;
  using pointer = typename A::pointer;
  using const_pointer = typename A::const_pointer;
  using reference = typename A::reference;
  using const_reference = typename A::const_reference;
private:
  // 故意将私有基类中选定的成员
  // 暴露为我们自己的成员
  using A::allocate;
  using A::deallocate;
  using A::construct;
  using A::destroy;
  // ...

其中的一些技巧：

• 由于预期 A 是无状态的，因此使用了私有继承，将 A 作为 Vector 的基类，这样可以启用“空基类优化”(empty base optimization)。或者，可以在每个 Vector 对象中使用一个类型为 A 的数据成员(这可能会略微增加对象的大小)。

• 我们从分配器的类型别名推导出容器的类型别名。实际上，这与前面章节中使用的别名可能没有区别，但如果分配器 A 做了一些“花哨的技巧”(fancy tricks)，这种设计可以确保兼容性(不能太掉以轻心)。

• 类的私有部分，将基类中的一些选定成员暴露为自己的成员。这样可以在后续编写代码时更简洁，可以写成 allocate(n)，而不要写成 this→A::allocate(n)。

不出所料，我们类中那些不需要分配内存的成员函数没有发生变化。数据成员保持不变，基本的访问函数如 size()、empty()、begin()、end()、front()、operator[] 等也保持不变。甚至连默认构造函数也没有改变，因为它不分配内存，也不需要与分配器交互。

不过，我们需要新增一个构造函数，该构造函数接受一个分配器作为参数。这个构造函数在处理有状态分配器(stateful allocators)时尤其有用：

// ...
  Vector(A &alloc) : A{ alloc } {
}
// ...

当然，当涉及到需要分配内存的构造函数时，情况就变得更加有趣了。例如，考虑这样一个构造函数：它接受元素的数量和一个初始值作为参数：

// ...
Vector(size_type n, const_reference init)
: A{},elems{ allocate(n) },
  nelems{ n }, cap{ n } {
  try {
    uninitialized_fill_with_allocator(
      *static_cast<A*>(this), begin(), end(), init
    );
  } catch (...) {
    deallocate(elems, capacity());
    throw;
  }
}
// ...

这里有很多值得注意的细节：

• 用于作为容器底层存储的内存块，是通过调用基类的 allocate() 成员函数来分配的。尽管该函数返回的是一个指针(T*)，但这其实是个“谎言” —— 这块新分配的内存中还并没有构造 T 类型的对象。

• 通过自制的、支持分配器(allocator-aware)的版本 std::uninitialized_fill() 来填充这段未初始化的内存(请注意函数名后缀 _with_allocator)。

  注意我们是如何将分配器作为参数传递给这个算法的：虽然 Vector 与 A 之间的继承关系是私有的，但派生类了解这一关系，并可以通过 static_cast 使用这一信息。

• 如果在初始化这段内存块的过程中，某个构造函数抛出了异常，该算法会像往常一样销毁它已经构造的对象(毕竟也没有其他代码能完成这个任务)，然后在捕获异常后释放之前分配的内存块，并在重新抛出异常前完成这些清理工作 —— 这是为了保证异常中立性(exception neutrality)。

类似的操作也出现在其他需要分配内存的构造函数中，只是用于初始化内存块的算法会有所不同。而移动构造函数和 swap() 成员函数并不涉及内存分配，因此保持不变；赋值操作符也是如此 —— 通过调用其他成员函数来实现的，本身不需要进行内存的分配或释放。

你可能已经猜到了，我们容器的析构函数，会使用分配器来销毁对象并释放底层内存：

// ...
~Vector() {
  destroy_with_allocator(
    *static_cast<A*>(this), begin(), end()
  );
  deallocate(elems, capacity());
}
// ...

push_back() 和 emplace_back() 成员函数本身并不直接进行内存分配，而是将任务委托给私有的 grow() 成员函数，而 grow() 又进一步将内存分配的工作委托给 reserve()。不过，它们确实需要在容器的末尾构造一个新的对象：

// ...
void push_back(const_reference val) {
  if (full()) grow();
  construct(end(), val);
  ++nelems;
}

void push_back(T&& val) {
  if (full()) grow();
  construct(end(), std::move(val));
  ++nelems;
}

template <class ... Args>
reference emplace_back(Args &&...args) {
  if (full()) grow();
  construct(end(), std::forward<Args>(args)...);
  ++nelems;
  return back();
}
// ...

我们类中用于内存分配的主要工具可能是 reserve() 和 resize()。在其他情况下，算法逻辑保持不变，但底层的内存管理任务则交由分配器来完成。对于 reserve() 函数，可以写出如下的代码：

// ...
void reserve(size_type new_cap) {
  if (new_cap <= capacity()) return;
  auto p = allocate(new_cap);

  if constexpr (std::is_nothrow_move_assignable_v<T>) {
    uninitialized_move_with_allocator(
      *static_cast<A*>(this), begin(), end(), p
    );
  } else {
    auto src_p = begin();
    auto b = p, e = p + size();

    try {
      uninitialized_copy_with_allocator(
        *static_cast<A*>(this), begin(), end(), p
      );
    } catch (...) {
      deallocate(p, new_cap);
      throw;
    }
  }

  deallocate(elems, capacity());
  elems = p;
  cap = new_cap;
}
// ...

而对于 resize() 函数，现在则有了以下实现：

// ...
void resize(size_type new_cap) {

  if (new_cap <= capacity()) return;

  auto p = allocate(new_cap);

  if constexpr (std::is_nothrow_move_assignable_v<T>) {
    uninitialized_move_with_allocator(
      *static_cast<A*>(this), begin(), end(), p
    );
  } else {
    uninitialized_copy_with_allocator(
      *static_cast<A*>(this), begin(), end(), p
    );
  }

  try {
    uninitialized_fill_with_allocator(
      *static_cast<A*>(this),
      p + size(), p + new_cap, value_type{}
    );

    destroy_with_allocator(
      static_cast<A*>(this), begin(), end()
    );

    deallocate(elems, capacity());
    elems = p;
    nelems = cap = new_cap;
  } catch(...) {
    destroy_with_allocator(
      *static_cast<A*>(this), p, p + size()
    );

    deallocate(p, new_cap);
    throw;
  }
}
// ...

在之前实现的 Vector<T> 类中，只为 insert() 和 erase() 各实现了一个版本，如果实现这两个函数的所有可能版本，会使本书变得异常庞大。由于这两个函数都会涉及对已初始化和未初始化内存的操作，因此需要进行调整，以使用分配器提供的服务，而不是自行管理内存。

对于 insert() 函数来说，需要调整的关键部分是那些将对象复制或移动到原始内存中的操作：

  // ...
  template <class It>
  iterator insert(const_iterator pos, It first, It last) {
    iterator pos_ = const_cast<iterator>(pos);
    const auto remaining = capacity() - size();
    const auto n = std::distance(first, last);

    // if (std::cmp_less(remaining, n)) { // 需要 C++20
    if(cmp_less(remaining, n)) {
      auto index = std::distance(begin(), pos_);
      reserve(capacity() + n - remaining);
      pos_ = std::next(begin(), index);
    }

    const auto nb_to_uninit_displace =
      std::min<std::ptrdiff_t>(n, end() - pos_);

    auto where_to_uninit_displace =
      end() + n - nb_to_uninit_displace;

    if constexpr (
      std::is_nothrow_move_constructible_v<T>
    )
      uninitialized_move_with_allocator(
        *static_cast<A*>(this),
        end() - nb_to_uninit_displace, end(),
        where_to_uninit_displace
      );
    else
      uninitialized_copy_with_allocator(
        *static_cast<A*>(this),
        end() - nb_to_uninit_displace, end(),
        where_to_uninit_displace
      );

    // 注意 : 可能是0
    const auto nb_to_uninit_insert =
      std::max<std::ptrdiff_t>(
        0, n - nb_to_uninit_displace
      );

    auto where_to_uninit_insert = end();

    uninitialized_copy_with_allocator(
      *static_cast<A*>(this),
      last - nb_to_uninit_insert, last,
      where_to_uninit_insert
    );

    // 注意 : 可能是0
    const auto nb_to_backward_displace =
      std::max<std::ptrdiff_t>(
        0, end() - pos_ - nb_to_uninit_displace
      );

    auto where_to_backward_displace = end();
    if constexpr (std::is_nothrow_move_assignable_v<T>)
      std::move_backward(
        pos_, pos_ + nb_to_backward_displace,
        where_to_backward_displace
      );
    else
      std::copy_backward(
        pos_, pos_ + nb_to_backward_displace,
        where_to_backward_displace
      );
    std::copy(
      first, first + n - nb_to_uninit_insert, pos_
    );

    nelems += n;
    return pos_;
  }
  // ...

对于 erase() 函数，我们的做法是将删除元素之后的所有对象向左移动一个位置；在完成这一复制操作后，序列末尾的那个对象需要销毁，为此需要使用分配器提供的服务。下面是一个示例：

  // ...
  iterator erase(const_iterator pos) {
  iterator pos_ = const_cast<iterator>(pos);
  if (pos_ == end()) return pos_;
    std::copy(std::next(pos_), end(), pos_);
    destroy(std::prev(end()));
    --nelems;
    return pos_;
  }
}

可以通过多种方式对这些函数进行优化或简化，例如：

• reserve() 和 resize() 之间存在一些共用的核心功能，resize() 在很大程度上可以看作是先调用 reserve()，然后进行一次未初始化的填充(uninitialized fill)，并据此来实现。

• 在 erase() 的实现中，可以在编译时检查 std::is_nothrow_move_assignable_v 类型特征的值，如果该条件成立，就可以将对 std::copy() 的调用替换为对 std::move() 的调用。

• 可以让 insert() 和 erase() 具有更好的异常安全性，尽管这会使代码变得较长，不太适合本书的篇幅。

至此，我们已经实现了一个支持分配器感知(allocator-aware)的、管理连续内存的容器。接下来很有趣的一点是，将看到分配器感知特性对基于节点(node-based)的容器会产生什么影响。将通过实现一个支持分配器感知的 ForwardList<T> 类来探讨这个问题。

一个支持分配器感知的 ForwardList<T,A> 类

编写支持分配器感知的基于节点的容器时，会出现一些有趣的现象。请留意我们 ForwardList<T,A> 类的开头部分：

template <class T, class A = std::allocator<T>>
class ForwardList {
public:
  using value_type = typename A::value_type;
  // 同样适用于其他类型别名
private:
  struct Node {
    value_type value;
    Node *next = nullptr;

    Node(const_reference value) : value { value } {
    }

    Node(value_type &&value)
    : value { std::move(value) } {
    }
  };

  Node *head {};
  size_type nelems {};
  // ...

有没有注意到类型 A 有什么有趣的地方？仔细看一下……

A 是错误的类型！像 ForwardList<T,A> 这样的基于节点的容器从不直接分配类型为 T 的对象：分配的是节点(nodes)，这些节点很可能包含 T 类型的对象，以及其他内容。比如在这个例子中，是一个指向序列中下一个节点的指针。

了解这一点之后，如果使用了一个由用户提供的分配器 A，而它实现的是一种与对象大小相关的分配策略(比如在第10章中为 Orc 对象设计的 arena 分配器)，那么让这个分配器感知到 T 类型(也就是 sizeof(T))，就会导致一个管理着错误大小对象的 arena。这显然不行！

于是我们遇到了一个有趣的难题：用户代码提供给我们一个分配器，是希望容器能够有效地使用某种特定的内存分配策略。这个分配策略作为容器的一个模板参数传入，因此它与容器元素的类型相关联 —— 但此时我们还不知道容器内部会使用什么样的节点结构。只有在我们真正定义了容器所使用的节点结构之后，才知道到底应该分配什么类型的对象。但此时，分配器 A 已经存在，并且它是与 T 相关联的，而不是我们真正需要的类型 ForwardList<T,A>::Node。

请注意，我们已经实例化了类型 A，但还没有构造任何该类型的对象。所以，这其实是一种浪费(根本不会使用它！)。我们需要的是一个与 A 类型相似的分配器，但它能够分配我们定义的 Node 类型对象，而不是 T 类型对象。我们需要一种方式来“克隆”由 A 所描述的分配策略，并将其应用到另一个类型上。

这正是 rebind 的用途所在。还记得我们之前在编写 small_allocator<T> 时提到过这个模板类型吗？当时我说我们会在更有意义的时候再回来讨论它，现在就是那个时候了。简单回顾一下，在分配器的上下文中，rebind 的形式如下所示：

template <class T>
class small_allocator { // 例如
  // ...
  template <class U>
  struct rebind {
    using other = small_allocator<U>;
  };
  // ...
}

可以把 rebind 看作是一种奇特的“代码诗”：它是分配器表达自己的一种方式，相当于在说“如果想获得和我一样的分配器类型，只不过要用于类型 U 而不是 T，这就是那个类型。”

回到 ForwardList<T,A> 类，现在已经明白了 rebind 的用途，就可以创建自己的内部分配器类型 Alloc。它将是“与分配器类型 A 相同，但作用于 Node 类型，而非 T”。然后创建该类型的对象(在实现中将其命名为 alloc)，并在容器中使用它来执行内存管理任务：

// ...
using Alloc = typename A::rebind<Node>::other;
Alloc alloc;
// ...

这真是个巧妙的技巧，不是吗？我们克隆的是分配策略和类型，而不是一个实际的对象。如果某个假想的 A 类型对象拥有某些状态(stateful)，这些状态并不一定会包含在我们的新类型 Alloc 中(至少在不做复杂处理的情况下不会)。这再次提醒我们，在最初设计的传统分配器模型中，复制和移动分配器的状态是一个相当复杂的问题。

与之前从 Vector<T> 到 Vector<T,A> 的转变类似，在原来的 List<T> 实现中，有相当一部分代码并不涉及内存分配，因此在转变为 List<T,A> 时无需修改。这些内容包括 size()、empty()、begin()、end()、front()、swap()、operator==() 等成员函数，以及 List<T,A>::Iterator<U> 类的大部分定义。由于我们在实现 ForwardList<T,A> 时偶尔需要访问其迭代器的私有数据成员 cur，并为 ForwardList 在 Iterator<U> 中赋予了友元(friend)权限：

// ...
template <class U> class Iterator {
  // ...
private:
  Node *cur {};
  friend class ForwardList<T,A>;
  // ...
};
// ...

ForwardList<T,A> 中也有一些使用内存分配机制的成员函数，其中之一是 clear()，作用是销毁容器中的所有节点。对 Node 对象的销毁和内存释放必须通过分配器来完成，因此需要将原本对 operator delete() 的调用替换为一组函数调用：

// ...
void clear() noexcept {
  for(auto p = head; p; ) {
    auto q = p->next;
    alloc.destroy(p);
    alloc.deallocate(p, 1);
    p = q;
  }
  nelems = 0;
}
// ...

在 ForwardList<T> 中，将所有涉及内存分配的构造函数统一到一个接受一对迭代器(类型为 It)作为参数的构造函数中。这使得 ForwardList<T,A> 中对构造函数的修改可以集中在这一个函数中，从而简化我们的任务。

在 ForwardList<T> 中，曾通过 std::forward_iterator 概念对模板参数 It 进行了约束，但概念(concepts)是 C++20 的特性，而我们目前是在 C++17 下编译这段实现，因此(令人遗憾地)暂时放弃了这一约束。

必须将内存分配和对象构造分为两个独立的步骤来进行，这使我们的实现稍微复杂了一些，但我相信各位读者不会认为这是很难的问题：

  // ...
  template <class It> // <std::forward_iterator It>
  ForwardList(It b, It e) {
    if(b == e) return;
    try {
      head = alloc.allocate(1);
      alloc.construct(head, *b);

      auto q = head;
      ++nelems;

      for(++b; b != e; ++b) {
        auto ptr = alloc.allocate(1);
        alloc.construct(ptr, *b);
        q->next = ptr;
        q = q->next;
        ++nelems;
      }

    } catch (...) {
      clear();
      throw;
    }
  }
  // ...

我们之前也为 ForwardList<T> 编写了插入操作的成员函数，因此这些函数在 ForwardList<T,A> 中也需要进行相应的调整，以支持使用分配器。我们为 push_front() 提供了两个重载版本：

  // ...
  void push_front(const_reference val) {
    auto p = alloc.allocate(1);
    alloc.construct(p, val);
    p->next = head;
    head = p;
    ++nelems;
  }

  void push_front(T&& val) {
    auto p = alloc.allocate(1);
    alloc.construct(p, std::move(val));
    p->next = head;
    head = p;
    ++nelems;
  }
  // ...

我们也为 insert_after() 提供了两个重载版本:一个用于插入单个值，另一个用于插入一个半开区间(half-open range)内的所有元素。在后一种情况下，由于我们是在为 C++17 进行编译，因此再次放弃对类型 It 使用 std::forward_iterator 的约束:

  // ...
  iterator
  insert_after(iterator pos, const_reference value) {
    auto p = alloc.allocate(1);
    alloc.construct(p, value);
    p->next = pos.cur->next;
    pos.cur->next = p;
    ++nelems;
    return { p };
  }

  template <class It> // <std::input_iterator It>
  iterator insert_after(iterator pos, It b, It e) {
    for(; b != e; ++b)
      pos = insert_after(pos, *b);
    return pos;
  }
  // ...

我们对 erase_after() 成员函数也进行了类似的调整：

  // ...
  iterator erase_after(iterator pos) {
    if (pos == end() || std::next(pos) == end())
      return end();

    auto p = pos.cur->next->next;
    alloc.destroy(pos.cur->next);
    alloc.deallocate(pos.cur->next, 1);

    --nelems;

    pos.cur->next = p;
    return { p->next };
  }
}

这便是我们将 ForwardList<T> 转变为支持分配器的 ForwardList<T,A> 类的全部过程。我希望这个过程并不像一些人所担心的那样困难：鉴于我们对本书中介绍的原则和基础技术的理解，在容器中集成分配器感知对于大多数人来说应该有一定意义了。

现在，我们已经了解了如何编写一个“传统”的迭代器，以及如何使容器支持分配器感知的例子，有读者可能会好奇使用分配器有哪些好处。我们知道，分配器让我们对容器如何管理内存有了控制权，但是从这种控制中我们能获得什么呢？

示例用法 —— 顺序缓冲区分配器

分配器使用的经典示例之一是管理预先分配的一块内存，而不是从自由存储(free store)中分配内存。这块内存不必来自线程的执行栈，但在实践中常常如此处理，因此我们的示例代码也将这样做。

在阅读下面的示例之前，需要了解以下几点：

• 这种类型的分配器是为特定用户设计的专门工具。我们期望用户清楚自己在做什么。

• 我们的示例中，将由分配器管理的预分配缓冲区必须为要存储的对象正确对齐。如果想调整这个示例以适应任何自然对齐对象的内存分配，需要付出努力(可能希望分配器返回的地址与 std::max_align_t 边界对齐，这是我们示例中的分配器未做到的)。

• 如果使用端代码尝试“过度分配”，即请求的内存量超过了受管缓冲区所能提供的量，就需要特别注意。在这个示例中，我们将如常抛出 std::bad_alloc 异常，但也有其他替代方案。

我们的顺序缓冲区分配器将如下所示：

#include <cstdint>

template <class T>
struct seq_buf_allocator {
  using value_type = T;
  // 指针、引用及其他类型别名的定义方式
  // 与常规情况相同，max_size() 函数也是如此。

private:
  char *buf;
  pointer cur;
  size_type cap;

public:
  seq_buf_allocator(char *buf, size_type cap) noexcept
  : buf{ buf }, cap{ cap } {
    cur = reinterpret_cast<pointer>(buf);
  }
  // ...

这个分配器的状态与我们在第10章中为基于大小的 内存池 所设计的类似：我们知道要管理的缓冲区从哪里开始(buf)，它的容量有多大(cap)，以及在顺序分配过程中当前的位置(cur)。

我们将 cur 设为一个指针类型的对象，是为了在后续的 allocate() 成员函数中简化计算，这只是为了方便，并非必须。某种意义上说，allocate() 成员函数非常简单：执行一个常数时间的计算，从底层存储中返回连续分配的对象，甚至不需要在内存释放后重新使用它。在 allocate() 中执行的一部分工作是防止“过度分配”，为此需要比较指针。但有时可能需要将一个指向已分配内存块内部的指针，与一个不在该内存块中的指针进行比较(这取决于参数的值)。这种比较会导致未定义行为(undefined behavior)，这是我们必须要避免的。因此，将指针转换为 std::intptr_t 类型的对象，然后比较它们的整数值。

最终，得到了如下的 allocate() 实现，以及相应的 deallocate() 成员函数。在这个特定的分配器中，deallocate() 实际上是一个空操作(no-op)，因为我们不尝试回收内存：

  // ...
  // rebind、address()、construct() 和 destroy()
  // 的定义方式均与常规情况相同
  pointer allocate(size_type n) {
    auto
      request = reinterpret_cast<
        std::intptr_t
      >(cur + n),
      limit = reinterpret_cast<
        std::intptr_t
      >(buf + cap);

    if(request >= limit)
      throw std::bad_alloc{};

    auto q = cur;
    cur += n;
    return q;
  }

  void deallocate(pointer, size_type) {
  }
};
// ...

由于这个分配器是有状态的(stateful)，我们需要认真考虑分配器之间的相等性(allocator equality)问题。在本例中，将采取以下做法：

template <class T, class U>
constexpr bool operator==(const seq_buf_allocator<T> &a,
                          const seq_buf_allocator<U> &b){
  return a.cur == b.cur; // maybe?
}

template <class T, class U>
constexpr bool operator!=(const seq_buf_allocator<T> &a,
                          const seq_buf_allocator<U> &b){
  return !(a == b);
}

这些相等操作符仅在特定的时间点才有意义，但这种分配器类型在实践中并不打算复制；如果计划使用这样的缓冲区并共享其内部状态，则需要仔细考虑原始对象和副本之间如何共享其内部状态，并保持彼此之间的一致性 —— 我们并不需要这么做。

我们在分配时测试是否溢出，如果某个分配请求会导致缓冲区溢出，则抛出 std::bad_alloc。但这只是多种可选方案中的一种，本章前面我们已经讨论过这一点。

#include <chrono>
#include <utility>

template <class F, class ... Args>
auto test(F f, Args &&... args) {
  using namespace std;
  using namespace std::chrono;
  auto pre = high_resolution_clock::now();
  auto res = f(std::forward<Args>(args)...);
  auto post = high_resolution_clock::now();
  return pair{ res, post - pre };
}

#include <iostream>
#include <vector>

struct Data { int n; };

int main() {
  using namespace std::chrono;
  enum { N = 500'000 };
  {
    std::vector<Data> v;
    auto [r, dt] = test([](auto & v) {
      v.reserve(N);

      for(int i = 0; i != N; ++i)
        v.push_back({ i + 1 });
      return v.back();
    }, v);

    std::cout << "vector<Data>:\n\t"
              << v.size()
              << " insertions in "
              << duration_cast<microseconds>(dt).count()
              << " us\n";
  } {
    alignas(Data) char buf[N * sizeof(Data)];
    seq_buf_allocator<Data> alloc{ buf, sizeof buf };

    std::vector<Data, seq_buf_allocator<Data>> v(alloc);

    auto [r, dt] = test([](auto & v) {
      v.reserve(N);
      for(int i = 0; i != N; ++i)
        v.push_back({ i + 1 });
      return v.back();
    }, v);

    std::cout
      << "vector<Data, seq_buf_allocator<Data>>:\n\t"
      << v.size()
      << " insertions in "
      << duration_cast<microseconds>(dt).count()
      << " us\n";
  }
  // do the same replacing std::vector with Vector
}

以下是一些你在此时可能需要注意的点：

• 测试代码与所选的分配器无关，始终相同。

• 使用有状态分配器时，需要使用一个带分配器参数的构造函数。

• 关于由 seq_buf_allocator 所使用的缓冲区的大小和对齐要求，这些责任落在用户代码的肩上。再次提醒，这是一个专用工具，因此用户应该清楚自己在做什么。

• 如果在符合标准的编译器上运行此测试，可能会注意到顺序缓冲区分配器在性能方面的一些有趣表现，并且可能会发现 Vector 的性能优于 std::vector，但 Vector 并不像标准版本那样完整和严谨。在实际应用中，应优先使用标准库提供的设施。

• 提供给顺序缓冲区分配器的缓冲区大小是有限的，因为栈空间是一种有限的资源(通常总共只有一到两兆字节，因此可用的空间更少)。尽管如此，这种技术在低延迟系统中确实被实际使用。

• 如果将此类分配器应用于基于节点的容器(如 std::forward_list)，请记住每个节点都会有一定的空间开销，因此要相应地规划所提供的缓冲区大小。

当然，以上是一个符合 C++17 标准的实现。那么从那以后，关于分配器又发生了哪些变化呢？

14.3.2 符合现代标准的传统分配器

截至撰写本书时，将分配器类型嵌入关联容器类型的这种传统方法仍然存在。但分配器本身的表达方式随着时间的推移发生了变化，前面小节中提到的分配器，无论是 small_allocator<T> 还是 seq_buf_allocator<T>，在 C++20 编译器上都无法像原来那样直接编译通过。

在为此感到难过之前，请先注意：我们仍然可以编写这些分配器，只是现在必须以一种更简单的方式来编写。呼！

简化和基于 traits 的实现方式

对分配器进行简化的第一步是认识到，在大多数情况下，分配器代码中很大一部分是“样板代码”(boilerplate code) —— 这些代码在类与类之间几乎相同，可以归类为“噪声”。为此，C++11 引入了 std::allocator_traits<A>。

其核心思想是：只要给定某个类型 A::value_type，就可以为大多数分配器服务(包括像 pointer 或 size_type 这样的类型别名)生成合理且高效的默认实现，前提是用户提供了 allocate() 和 deallocate() 的实现。

以 small_allocator<T> 为例，现在可以用如下方式简洁地表达整个分配器类型：

template <class T>
struct small_allocator {
  using value_type = T;

  T* allocate(std::size_t n) {
    auto p = static_cast<T*>(
      malloc(n * sizeof(value_type))
    );

    if (!p) throw std::bad_alloc{};
    return p;
  }

  void deallocate(T *p, std::size_t) {
    free(p);
  };

  // ... 在此处插入相等性操作符

这确实是一个相当大的简化！通过这种方式，像 Vector<T,A> 这样的容器现在可以通过 std::allocator_traits<A> 间接引用分配器 A 的成员，而不是直接使用 A。这种特质（traits）作为极薄的一层抽象，几乎不会带来运行时开销，它们对成员 M 的处理本质上是：“如果 A 暴露了成员 M，就使用 A::M；否则，就采用某个合理的默认实现”。当然，实际上这里不会有分支判断，所有决策都在编译期完成。

基于之前定义的 small_allocator<T> 类型，已知 small_allocator<T>::allocate() 返回 T*，那么可以确定 std::allocator_traits<small_allocator<T>>::pointer 将等同于 T*。像 Vector<T,A> 这样的容器会使其指针类型别名对应于 std::allocator_traits<A>::pointer 所表达的类型。

再举一个例子，现在 seq_buf_allocator<T> 可以这样表达：

template <class T>
struct seq_buf_allocator {
  using value_type = T;
  using pointer = T*;
  using size_type = std::size_t;

  char* buf;
  pointer cur;
  size_type cap;

  seq_buf_allocator(char* buf, size_type cap) noexcept
    : buf{ buf }, cap{ cap } {
    cur = reinterpret_cast<pointer>(buf);
  }

  pointer allocate(size_type n) {
    auto request =
      reinterpret_cast<std::intptr_t>(cur + n),
         limit =
     reinterpret_cast<std::intptr_t>(buf + cap);

    if (request > limit) {
      throw std::bad_alloc{};
    }

    auto q = cur;
    cur += n;
    return q;
  }

  void deallocate(pointer, size_type) {
  }
};
// ... 在此处插入相等性操作符

在这种情况下，即使并非必需，类型 seq_buf_allocator<T> 仍然暴露了 pointer 和 size_type 的别名。所以对于该类型，std::allocator_traits 将使用分配器提供的版本，而不是尝试合成一个替代方案，现代基于 traits 的分配器方法非常方便。

那么，std::allocator_traits<A> 究竟提供了哪些服务呢？该类型暴露了常见的类型别名，包括 value_type(本身是 A::value_type 的别名)、pointer、const_pointer、size_type 和 difference_type。为了方便起见，它还暴露了以下别名：allocator_type(等价于 A)，void_pointer 和 const_void_pointer(大多数情况下分别等价于 void* 和 const void*)。请记住，traits 是可以特化，这些看似简单的类型别名偶尔也可能映射到更复杂的结构。

std::allocator_traits<A> 类型还以静态成员函数的形式暴露了分配器的传统服务，这些函数将分配器作为第一个参数，包括：construct()、destroy()、allocate()、deallocate() 和 max_size()。C++23 又向这一组添加了另一个静态成员函数：allocate_at_least()。该函数返回一个 std::allocation_result 对象，该对象由已分配的指针和分配块的实际大小组成，大小以对象数量表示(尽管像往常一样，在分配完成后，该内存块中实际上并没有对象)。

分配器的“重新绑定(rebind)”机制通过 std::rebind_alloc<A> 和 std::rebind_traits<T> 类型来表达。当克隆一个分配策略(主要用于节点容器)时，使用这些设施来实现类似于 typename A::rebind<T>::other 的表达式，虽然语法会稍显冗长一些：

// ...
  typename std::allocator_traits<
    A
  >::template rebind_alloc<Node>;
// ...

为了语法上的消歧，这里出现了 template 关键字。我知道你现在在想什么：这门语言真是太复杂了！但在实践中，我们很少需要使用这个关键字，只有在那些奇怪的情况下才需要用到 —— 也就是编译器看到接下来的代码时，无法判断它是模板签名的一部分，还是小于(<)操作符的时候。

此外，std::allocator_traits<A> 还带来了一些新的工具，用于处理分配器的生命周期管理，这是我们多年来逐渐学会去做的事情：

• 三个类型别名，用于告诉容器在其生命周期中的关键时刻应该如何处理分配器。这些类型包括：

  propagate_on_container_copy_assignment(也称为 POCCA)，

  propagate_on_container_move_assignment(也称为 POCMA)，

  propagate_on_container_swap(也称为 POCS)。

  这三个类型都可以实例化，并且行为类似于返回 true 或 false 的 constexpr 函数(默认情况下它们等价于 std::false_type，因为默认情况下分配器并不打算被复制或移动)。例如，一个分配器暴露了等价于 std::true_type 的 POCMA 类型别名，那么拥有该分配器的容器应该在移动分配时一并移动分配器。在这三种情况下，如果该 trait 等价于 std::true_type，则分配器的复制、移动或交换操作(分别)为 noexcept。

• 类型别名 is_always_equal；表示该类型的分配器无论分配什么类型的对象都会比较相等(这消除了对 operator==() 和 operator!=() 的需求，这两个操作符用于比较相同模板但不同 value_type 别名的两个分配器)。不过，不要在这个特性上花太多时间；它已在 C++23 中弃用，并很可能在 C++26 中移除。

• select_on_container_copy_construction() 成员函数。这是一个静态成员函数，接受一个分配器作为参数，在分配器的 traits 表明此时复制分配器是合适行为时进行复制，否则返回原始分配器。

这个分配器生命周期管理机制是新的，可能令人感到意外。那么我们该如何使用这些信息呢？

14.3.3 管理传统分配器的生命周期

一个容器在进行移动或复制操作时，应该如何处理分配器(allocator)呢？以下是详细说明：

在容器的复制构造函数中，最佳做法很可能是使用 select_on_container_copy_construction() 函数。毕竟，这就是该函数的用途。请不要在其他地方使用这个函数：确实是专为容器的复制构造函数设计的。当新构造的容器获得了自己的分配器，就可以使用该分配器来完成后续的内存分配任务。

在容器的移动构造函数中，应该做的是对分配器进行移动构造，并从源容器中“窃取”资源。

在容器的复制赋值操作符中，如果类型别名 propagate_on_container_copy_assignment 等价于 std::true_type，并且两个分配器不相等，那么目标容器首先必须释放所有内存(这一步可能在后续流程中无法完成)。完成之后，如果 propagate_on_container_copy_assignment 等价于 std::true_type，则应该对分配器进行复制赋值。只有在这所有步骤完成后，才应该复制元素。

容器的移动赋值操作符则更为复杂(移动操作是一种优化手段，我们希望它能带来性能提升！)。我们面临的选择如下：

• 类型别名 propagate_on_container_move_assignment 等价于 std::true_type。应执行的步骤是：(a) 确保目标容器释放其负责的所有内存(之后可能无法再执行此操作)，(b) 对分配器进行移动赋值，然后 (c) 将内存所有权从源容器转移到目标容器。

• 类型别名 propagate_on_container_move_assignment 等价于 std::false_type，并且两个分配器相等。在这种情况下，可以执行与前一种情况相同的步骤，但不移动分配器。

• 类型别名 propagate_on_container_move_assignment 等价于 std::false_type，并且两个分配器不相等。在这种情况下，实际上无法转移所有权，所以最好的做法是从源容器将对象本身移动到目标容器。

幸运的是，所有这些分配器的属性都可以在编译时测试，决策过程不会带来运行时开销。

分配器感知的容器中使用基于特征的分配器

在基于特征的方法中，传统分配器的剩余问题是：容器如何使用？

需要做的第一件事是，调整对标准未初始化内存算法的分配器感知(allocator-aware)实现。例如，自定义的 std::uninitialized_copy() 变成了以下形式：

template <class A, class IIt, class OIt>
void uninitialized_copy_with_allocator
  (A &a, IIt bs, IIt es, OIt bd) {
  auto p = bd;
  try {
    for (auto q = bs; q != es; ++q) {
      std::allocator_traits<A>::construct(a, p, *q);
    ++p;
    }
  } catch (...) {
    for (auto q = bd; q != p; ++q)
      std::allocator_traits<A>::destroy(a, q);
    throw;
  }
}

现在使用的是 std::allocator_traits<A>，而不是直接使用 A，这样可以提供定制的可能性，并且由于 std::allocator_traits<A> 的所有成员函数都是静态的，需要将分配器作为第一个参数传入。同样的调整也适用于我们编写过的其他支持分配器的算法版本，它们的调用方式一致，也都将分配器作为第一个参数传入。

接下来，来看 Vector<T, A> 类型。我们该如何调整其实现，以使用现代的基于特性的分配器？第一步是调整容器中类型别名的来源：

template <class T, class A = std::allocator<T>>
class Vector : A { // 注意：私有继承
public:
  using value_type =
    typename std::allocator_traits<A>::value_type;

  using size_type =
    typename std::allocator_traits<A>::size_type;

  using pointer =
    typename std::allocator_traits<A>::pointer;

  using const_pointer =
    typename std::allocator_traits<A>::const_pointer;

  using reference = value_type&;

  using const_reference = const value_type&;
  // ...

各位读者可能会感到惊讶，为什么类型别名 reference 和 const_reference 并不是取自 std::allocator_traits<A>，这是有原因的。在 C++ 中，正如本文所述，可以设计一些行为类似于“智能指针”的类型(本书中甚至已经展示过这样的例子；参见第 6 章)，因此，如果分配器提供的指针不是原始指针，这种抽象是有用的。但目前尚无已知的方法来实现“智能引用”(这需要能够重载 operator.() 的能力，而相关提案至今尚未接受)。

唯一行为类似于 T 的引用的类型是 T&。正因如此，这些类型别名在 C++17 中弃用，并在 C++20 中移除。我们仍然可以提供它们，来使类型的成员函数签名更清晰，但标准已不再要求了。

至于 Vector<T, A> 的成员函数，其总体思路是：将原本对 A 成员函数的所有调用，替换为对 std::allocator_traits<A> 的静态成员函数的调用，这些静态函数会以 A 对象的引用作为参数(我们的 Vector<T, A> 实现中，A 是容器的一个私有基类)。以下是一个示例：

Vector(size_type n, const_reference init)
: A{},
elems{ std::allocator_traits<A>::allocate(
  static_cast<A&>(*this), n)
},
nelems{ n }, cap{ n } {
  try {
    uninitialized_fill_with_allocator(
      static_cast<A&>(*this), begin(), end(), init
    );
  } catch (...) {
    std::allocator_traits<A>::deallocate(
      static_cast<A&>(*this), elems, capacity()
    );
    throw;
  }
}

如果对在数据成员初始化器中使用 *this 感到不安，可以放心，在这里仅使用的是 *this 中的 A 部分，而此时该基类子对象已经完全初始化。此时使用 *this 的这部分很安全。

同样的调整必须在整个容器中应用(可能有几十处)，这显然会让源码更加冗长。但好消息是，我们由此获得了一个在运行时零成本的抽象层，同时帮助了所有实际编写分配器的人。

对于像 ForwardList<T, A> 这样的基于节点的容器，情况类似但略有不同。首先，类型别名的处理比较棘手：其中一些是供用户代码使用的，应该根据容器的 value_type 来定义；而另一些则应基于分配器通过其特性(traits)所表达的类型来定义：

template <class T, class A = std::allocator<T>>
class ForwardList {
public:
  // 注意：这些是面向用户的类型，其定义方式
  // 基于 T 作为 value_type 的情况
  using value_type = T;

  using size_type =
    typename std::allocator_traits<A>::size_type;

  using pointer = value_type*;

  using const_pointer = const value_type*;

  using reference = value_type&;

  using const_reference = const value_type&;
  // ...

在容器内部，需要将 A 重新绑定到内部节点类型 Node 的分配器：

  // ...
private:
  struct Node {
    value_type value;
    Node *next = nullptr;
    Node(const_reference value) : value { value } {
    }
    Node(value_type &&value) : value{ std::move(value) }{
    }
  };
  using Alloc = typename std::allocator_traits<
    A
  >::template rebind_alloc<Node>;
  Alloc alloc;
  // ...

完成这一步之后，要执行内存管理任务时，就会使用 std::allocator_traits<Alloc> 中的静态成员函数，并将 alloc 数据成员作为参数传入：

  // ...
  void clear() noexcept {
    for(auto p = head; p; ) {
      auto q = p->next;
      std::allocator_traits<Alloc>::destroy(alloc, p);
      std::allocator_traits<Alloc>::deallocate(
        alloc, p, 1
      );
      p = q;
    }
    nelems = 0;
  }

  template <std::forward_iterator It>
  ForwardList(It b, It e) {
    if(b == e) return;
    try {
      head = std::allocator_traits<
        Alloc
      >::allocate(alloc, 1);
      std::allocator_traits<Alloc>::construct(
        alloc, head, *b
      );

      auto q = head;
      ++nelems;
      for(++b; b != e; ++b) {
        auto ptr = std::allocator_traits<
          Alloc
        >::allocate(alloc, 1);

        std::allocator_traits<
          Alloc
        >::construct(alloc, ptr, *b);

        q->next = ptr;
        q = q->next;
        ++nelems;
      }
    } catch (...) {
      clear();
      throw;
    }
  }
  // ...

当然，整个容器中都需要应用相同的技术，但复杂度保持不变。

现在，已经了解了传统的分配器 —— 它们嵌套在容器的类型中 —— 是如何从最初较为复杂的契约演变为如今基于特性的、更简化的实现方式的(虽然容器的代码因此变得更为冗长)。此时，我们可能会认为已经达到了某种最优状态。这种想法既有一定的道理，也存在误区。

14.3.4 传统分配器的一些烦人之处

传统的分配器方法在运行时最优，从这个意义上来说，调用此类分配器的服务没有任何开销；如果分配器是无状态的，那么在容器中引入分配器也不会带来空间上的成本。这已经很不错了！

当然，运行时零成本并不等于完全没有成本：

• 容器的实现可能会因为(编译时)抽象层次而变得较为复杂，编写、理解和维护源码都需要开销。这种专业知识并非人人具备；亲爱的读者，你当然具备这样的认知时，但其他人未必拥有。

• 两个在几乎所有方面都完全相同、只是内存管理方式不同的容器(即使用了不同分配器的两个容器)在实际中会被视为不同的类型，这可能会拖慢那些使用了多种容器-分配器组合的程序的编译速度。

• 一些本来应该是简单操作的事情会变得更加复杂。例如，想要比较两个容器 v0 和 v1 是否相等，而 v0 是 Vector 类型，v1 是 Vector 类型，就需要编写一个处理两个不同类型的 operator==() 函数……尽管从语义上来说，分配器可能并不是容器的一个显著属性，在比较两个容器的大小和值时，本不应该成为考虑因素。

许多其他与容器相关的操作都可以应用这一观点：在传统方法中，分配器是容器类型的一部分，但很多操作是与值类型相关的，与分配器无关。我们在运行时达到了最优，但在代码生成复杂度方面(可能导致更大的二进制文件，从而影响运行速度)和维护工作量(包括理解源码)方面都带来了额外的成本。

甚至连让分配器感知类型这样的看似简单的操作(毕竟传统的分配器是针对某种类型 T 的分配器)，有时也会引起争议。毕竟，像 std::malloc() 或 ::operator new() 这样的底层内存分配函数处理的是原始字节(raw bytes)，这是否说明传统的分配器模型仍有改进空间？