4.2. 交换操作与标准模板库

交换操作在 C++ 标准库中广泛使用。所有标准模板库(STL)容器都提供了交换功能，并且存在一个非成员函数模板 std::swap。STL 算法中也存在对交换的使用。此外，标准库也为实现与标准功能相似的自定义特性提供了范本。

因此，我们将从考察标准库所提供的功能开始，研究交换操作。

4.2.1 交换操作与STL容器

从概念上讲，交换等同于以下操作：

template <typename T> void swap(T& x, T& y) { T tmp(x);
  x = y;
  y = tmp;
}

调用 swap() 之后，对象 x 和 y 的内容被互换，这很可能是实际实现交换最糟糕的方式。这种实现最明显、最首要的问题就是不必要地复制了两个对象(实际上执行了三次复制操作)。该操作的执行时间与类型 T 的大小成正比。对于 STL 容器而言，这里的“大小”指的是容器实际内容的大小，而不是元素类型的大小。

void swap(std::vector<int>& x, std::vector<int>& y) {
  std::vector<int> tmp(x);
  x = y;
  y = tmp;
}

这段代码可以编译，并且在大多数情况下甚至能正确完成任务，它会多次复制向量中的每个元素。第二个问题是，它会临时分配资源 —— 交换过程中，创建了第三个vector，其占用的内存与交换的任一vector相当。考虑到最终状态下数据总量与初始时完全相同(只是访问这些数据所用的名称发生了变化)，这种内存分配似乎不必要。当考虑前述内存分配可能失败时，这种简单实现的最后一个缺陷便暴露出来。

本应如交换访问vector元素的名称般简单可靠的整个交换操作，反而会因内存分配失败而失败。

但这并非唯一的失败途径 —— 复制构造函数和赋值运算符都可能抛出异常。

所有 STL 容器(包括 std::vector)都提供了一项保证：可以在常数时间内完成交换。如果考虑到 STL 容器对象本身仅包含指向数据的指针以及一些状态(例如对象大小)，那么实现这一目标的方式就相当直接了。要交换这些容器，只需交换指针(当然，还有其余状态)即可 —— 容器的元素仍然保留在原本所在的动态分配内存中，无需复制甚至无需访问。交换的实现仅需交换指针、大小以及其他状态变量(在实际的 STL 实现中，容器类(如 vector)并非直接由指针等内置类型的数据成员构成，而是拥有一到多个类数据成员，而这些成员本身由指针和其他内置类型构成)。

由于指针或其他vector数据成员均不可公开访问，因此交换操作必须作为容器的成员函数实现，或声明为友元函数。STL 采用了前一种方式 —— 所有 STL 容器都提供了一个 swap() 成员函数，用于与另一个同类型对象交换内容(参见示例 01a 和 01b)。

通过交换指针来实现这一操作，间接地解决了我们之前提到的另外两个问题。首先，由于仅交换了容器的数据成员，不会发生内存分配。其次，复制指针及其他内置类型不会抛出异常，整个交换操作是无异常抛出的(也不会以其他方式失败)。

目前，我们所描述的简单而一致的图景，只在大多数情况下成立。第一个复杂情况(也是相对简单的一个)仅适用于那些不仅以元素类型为模板参数，还以某种可调用对象为参数的容器。例如，std::map 容器接受一个用于比较元素的可选比较函数，默认情况下为 std::less。这类可调用对象必须随容器一同存储。由于频繁调用，出于性能考虑，非常希望将它们与容器对象本身存储在同一块内存分配中，事实上也确实设计为容器类的数据成员。

然而，这种优化是有代价的 —— 现在交换两个容器需要交换比较函数本身，即实际的对象，而不仅是它们的指针。这些比较对象由库的使用者实现，无法保证交换这些对象是可行的，更无法保证交换过程不会抛出异常。

因此，对于 std::map，标准规定：要使 map 可交换，其包含的可调用对象也必须是可交换的。此外，交换两个 map 不会抛出异常，除非交换比较对象的操作可能抛出异常；这种情况下，比较对象交换时抛出的异常都会从 std::map 的交换操作中传递出来。

这种考虑不适用于 std::vector 等不使用可调用对象的容器，交换这些容器仍然不会抛出异常(就如目前所知)。

在交换操作整体上一致且自然的行为中，另一个复杂问题源于分配器，而这个问题更难解决。考虑以下问题：两个交换的容器必须具有相同类型的分配器，但分配器对象本身不一定相同。每个容器的元素由其自身的分配器分配，并且必须由同一个分配器来释放。交换之后，第一个容器拥有了原先属于第二个容器的元素，并最终必须释放这些元素。这只能(正确地)使用第一个容器的分配器来完成，所以分配器本身也必须进行交换。

C++11 之前的 C++ 标准完全忽略了这个问题，规定两个相同类型的分配器对象都必须能够释放彼此分配的内存。如果这是成立的，则根本不需要交换分配器。如果这不成立，则已经违反了标准，进入了未定义行为的领域。C++11 允许分配器具有非简单的状态，因此这些状态也必须被交换。但分配器对象本身并不必须是可交换的。标准通过以下方式来解决这个问题：对于任意 allocator_type 分配器类，存在一个特征类(trait class)，其定义了包括 std::allocator_traits<allocator_type>::propagate_on_container_swap::value 在内的特性属性。如果该值为 true，则使用非限定调用的非成员 swap 来交换分配器；也就是说，简单地调用 swap(allocator1, allocator2)(参见下一节以了解该调用实际执行的操作)。如果该值为 false，则分配器根本不交换，且两个容器对象必须使用相同的分配器。如果也不成立，那么又回到了未定义行为。C++17 通过将 STL 容器的 swap() 成员函数声明为条件性 noexcept()，为这一机制披上了更正式的外衣，但其限制条件相同。

交换两个容器不能抛出异常的要求 —— 至少在不涉及分配器且容器不使用可调用对象或使用的是不抛出异常的可调用对象时 —— 最终对容器的实现施加了一个相当微妙的限制：阻止了局部缓冲区优化的使用。

我们将在第 10 章会详细讨论这种优化，其思想是通过在容器类内部定义一个缓冲区，避免为元素极少的容器(例如短字符串)进行动态内存分配。然而，这种优化通常与无异常抛出的交换概念不兼容，容器对象内部的元素不能再仅通过交换指针来互换，而必须在容器之间进行复制。

4.2.2 非成员函数交换

标准还提供了一个模板函数 std::swap()。C++11 之前，在 <algorithm> 头文件中声明；从 C++11 开始，移至 <utility> 头文件。该函数的声明如下：

template <typename T>
  void swap (T& a, T& b);
template <typename T, size_t N>
  void swap(T (&a)[N], T (&b)[N]); // Since C++11

C++11 中为数组增加了重载版本。C++20 中，这两个版本还额外声明为 constexpr。对于 STL 容器，std::swap() 会调用其成员函数 swap()。我们将在下一节看到，swap() 的行为，也可以为其他类型进行自定义，但如果不做特殊处理，则会使用默认实现。该默认实现使用一个临时对象来完成交换。在 C++11 之前，该临时对象通过复制构造创建，交换过程通过两次赋值完成。类型必须是可复制的(即可复制构造且可复制赋值)，否则 std::swap() 将无法编译(参见示例 02a 和 02b)。在 C++11 中，std::swap() 重新定义为使用移动构造和移动赋值(参见示例 02c)。与通常情况一样，如果类是可复制的，但根本未声明移动操作，则会使用复制构造函数和赋值操作。如果类声明了复制操作，同时将移动操作声明为已删除，则不会自动回退到复制操作 —— 该类视为不可移动类型，std::swap() 对其将无法编译(参见示例 02d)。

由于一般情况下复制对象可能会抛出异常，因此对于未提供自定义交换行为的对象，交换操作也可能抛出异常。移动操作通常不会抛出异常，在 C++11 中，如果对象具有移动构造函数和赋值操作符，且两者均不抛出异常，则 std::swap() 也提供不抛出异常的保证。这一行为在 C++17 中通过条件性 noexcept() 规范得到了正式化。

4.2.3 标准般的交换操作

从上述对标准库如何处理交换操作的回顾中，可以总结出以下指导原则：

支持交换操作的类应实现 swap() 成员函数，且该函数应以常数时间完成交换操作。
对于所有可交换的类型，都应提供一个独立的非成员 swap() 函数。
交换两个对象不应抛出异常或以其他方式失败。

最后一条指导原则相对宽松，并非总能遵循。通常来说，如果某个类型具有不抛出异常的移动操作，那么实现一个不抛出异常的 swap 有可能。另外许多异常安全保证(尤其是标准库提供的保证)都要求，移动和交换操作不能抛出异常。

返回目录