《Effective STL》 Chapter 1: Containers

50 Specific Ways to Improve Your Use of the Standard Template Library.

本文作为读书的记录，后续会陆续更新。

Chapter 1: Containers

Item 1: Choose your containers with care（谨慎选择你的容器）.

您知道 C++ 提供了多种容器供您使用，但您是否意识到这些容器种类繁多？为了确保您没有忽略任何选项，下面简要回顾一下。

标准 STL 序列容器、vector、string、deque 和 list。
标准 STL 关联容器，set、multiset、map 和 multimap。
非标准序列容器 slist 和 rope。slist 是单链表，而 rope 本质上是重载string。（“rope” 是重载“string”。明白了吗？）您可以在 Item 50 中找到这些非标准（但常用）容器的简要概述。
非标准关联容器 hash_set、hash_multiset、hash_map 和 hash_multimap。我在 Item 25 中研究了这些广泛使用的基于哈希表的标准关联容器变体。
vector<char> 替代了 string。第 13 条描述了这种替代在哪些条件下是合理的。
vector 可以替代标准的关联容器。正如 Item 23 所明确指出的，有时 vector 在时间和空间上的表现都优于标准的关联容器。
几个标准的非 STL 容器，包括arrays、bitset、valarray、stack、queue,和priority_queue。由于这些都是非 STL 容器，因此本书中我很少谈论它们，不过第 16 条提到了数组优于 STL 容器的情况，第 18 条解释了为什么位集可能比 vector<bool> 更好。还值得一提的是，arrays可以与 STL 算法一起使用，因为指针可以用作array迭代器。

关于容器的选项非常丰富，选择时需要考虑的因素也非常多。遗憾的是，大多数关于 STL 的讨论都对容器世界持相当狭隘的看法，忽略了许多与选择最合适的容器相关的问题。甚至STL也参与其中，为在 vector、deque 和 list 之间进行选择提供了以下指导：

vector、list 和 deque 为程序员提供了不同的复杂性权衡，应相应地使用它们。vector 是默认应使用的序列类型。当在序列中间频繁插入和删除时，应使用 list。当大多数插入和删除发生在序列的开头或结尾时，deque 是首选的数据结构。

如果您主要关心的是算法复杂性，我想这是一个合理的建议，但还有很多值得关注的事情。

首先我需要介绍一种对 STL 容器进行分类的方法，这种方法讨论得并不多。这就是连续内存容器和基于节点的容器之间的区别。

连续内存容器（也称为基于数组的容器）将其元素存储在一个或多个（动态分配的）内存块中，每个内存块包含多个容器元素。如果插入新元素或删除现有元素，则同一内存块中的其他元素必须上移或下移，以便为新元素腾出空间或填充以前被删除元素占用的空间。这种移动会影响性能（参见第 5 和 14 条）和异常安全性（我们很快就会看到）。标准的连续内存容器是 vector、string 和 deque。非标准 rope也是连续内存容器。

基于节点的容器每块（动态分配的）内存仅存储一个元素。插入或删除容器元素只会影响指向节点的指针，而不会影响节点本身的内容，因此插入或删除某些内容时无需移动元素值。表示链接列表的容器（如 list和slist）是基于节点的，所有标准关联容器也是如此。（它们通常实现为平衡树。）非标准哈希容器使用不同的基于节点的实现，如您将在条目 25 中看到的那样。

您是否需要能够在容器中的任意位置插入新元素？如果是，则需要一个序列容器；关联容器不行。
您是否关心元素在容器中的排序方式？如果不关心，散列容器将是一个可行的选择。否则，您将希望避免使用散列容器。
容器必须是标准 C++ 的一部分吗？如果是，那就排除了散列容器、slist 和rope。
你需要哪一类迭代器？如果它们必须是随机访问迭代器，那么从技术上讲，你只能使用 vector、deque 和 string，但你也许还想考虑 rope。有关rope的信息，请参阅。）如果需要双向迭代器，你必须避免使用 slist（参见 Item 50）以及散列容器的一种常见实现（参见 Item 25）。
在进行插入或删除时，避免移动现有的容器元素是否重要？如果重要，你需要远离连续内存容器（参见条款 5）。
在插入或删除时避免移动现有容器元素是否重要？如果重要，则需要远离连续内存容器（参见条目 5）。
容器中的数据是否需要与 C 兼容布局？如果重要，则只能使用vector（参见条目 16）。
查找速度是否是关键考虑因素？如果重要，则需要查看散列容器（参见条目 25）、排序兼容布局？如果重要，则只能使用vector（参见条目（参见条目 23）和标准关联容器 — 可能按此顺序。
您是否介意底层容器使用引用计数？如果重要，则需要避开 string，因为许多字符串实现都是引用计数的（参见条目 13）。还需要避免使用 rope，因为最终的 rope 实现基于引用计数（参见条目 50）。当然，您必须以某种方式表示字符串，因此需要考虑 vector<char>。
插入和擦除是否需要事务语义？也就是说，您是否需要能够可靠地回滚插入和擦除？如果是，您将需要使用基于节点的容器。如果您需要多元素插入的事务语义（例如，范围形式 - 参见第 5 条），您将需要选择list,，因为list,是唯一提供多元素插入事务语义的标准容器。事务语义对于有兴趣编写异常安全代码的程序员来说尤其重要。（事务语义也可以通过连续内存容器实现，但会降低性能，并且代码不那么简单。要了解更多信息，请参阅 Sutter 的《Exceptional C++》第 17 条 [8]。）
您是否需要最小化迭代器、指针和引用无效？如果是这样，您将需要使用基于节点的容器，因为在此类容器上插入和擦除永远不会使迭代器、指针或引用无效（除非它们指向您要擦除的元素）。通常，在连续内存容器上插入或擦除可能会使容器中的所有迭代器、指针和引用无效。
您是否关心在容器上使用 swap是否会使迭代器、指针或引用无效？如果是这样，您需要避免使用 string，因为在 STL 中，string是唯一在交换期间使迭代器、指针和引用无效的。
如果有一个带有随机访问迭代器的序列容器，其中只要不删除任何内容并且只在容器的末尾进行插入，指针和对数据的引用就不会失效，这会很有帮助吗？这是一种非常特殊的情况，但如果这是你的情况，deque就是你梦寐以求的容器。（有趣的是，当只在容器的末尾进行插入时，deque的迭代器可能会失效。deque是唯一一个迭代器可能会失效而不会使其指针和引用失效的标准 STL 容器。）

这些问题远非问题的结束。例如，它们没有考虑不同容器类型所采用的不同内存分配策略。（第 10 和 14 条讨论了此类策略的某些方面。）尽管如此，它们应该足以说服您，除非您对元素排序、标准一致性、迭代器功能、与 C 的布局兼容性、查找速度、由于引用计数导致的行为异常、实现事务语义的难易程度或迭代器无效的条件不感兴趣，否则您要考虑的不仅仅是容器操作的算法复杂性。当然，这种复杂性很重要，但它远非全部。

STL 在容器方面为您提供了许多选项。如果您超越 STL 的范围，还会有更多的选择。在选择容器之前，请务必考虑所有选项。“默认容器”？我不这么认为。

Item 2: Beware the illusion of container-independent code（警惕容器无关代码的幻觉）.

STL（标准模板库）的基础是泛化。数组被泛化为容器，并通过模板参数化为存储特定类型对象的容器。函数被泛化为算法，并通过模板参数化为使用特定类型迭代器的算法。指针被泛化为迭代器，并通过模板参数化为指向特定类型对象的迭代器。

这仅仅是个开始。单个容器类型被泛化为序列容器和关联容器，而相似的容器则提供相似的功能。标准的连续内存容器（如vector、deque和string）提供随机访问迭代器，而标准的节点型容器（如list和关联容器）提供双向迭代器。序列容器支持push_front和/或push_back，但关联容器不支持。关联容器提供对数时间复杂度的lower_bound、upper_bound和equal_range成员函数，而序列容器则不提供这些函数。

在如此多的泛化之下，想要加入这种趋势是很自然的。这种想法值得赞扬，当你编写自己的容器、迭代器和算法时，你当然应该追求这种泛化。然而，许多程序员试图以另一种方式追求泛化。他们试图避免在代码中绑定到特定类型的容器，而是试图泛化“容器”的概念，以便可以用vector，也可以用deque或list，而无需修改使用它们的代码。换句话说，他们试图编写“容器无关”的代码。

这种泛化的愿望虽然出发点是好的，但几乎总是误入歧途。

即使是最热衷于容器无关代码的支持者也很快会意识到，试图编写同时适用于序列容器和关联容器的代码是没有意义的。许多成员函数仅存在于某一类容器中，例如，只有序列容器支持push_front或push_back，而只有关联容器支持count和lower_bound等。甚至像insert和erase这样基本的操作，其签名和语义也因容器类别不同而有所不同。例如，将对象插入序列容器时，它会保留在插入的位置，而插入关联容器时，容器会根据排序规则将对象移动到适当的位置。再比如，针对迭代器的erase在序列容器中会返回一个新的迭代器，而在关联容器中则什么也不返回。

假设你希望编写可同时用于最常见序列容器（vector、deque和list）的代码。显然，你必须限制自己仅使用它们的共同功能。这意味着不能使用reserve或capacity（因为deque和list不支持它们）。由于list的存在，你也不能使用operator[]，并且必须限制自己使用双向迭代器的功能。这进一步意味着你不能使用需要随机访问迭代器的算法，例如sort、stable_sort、partial_sort和nth_element。

另一方面，由于vector的存在，你不能使用push_front和pop_front，而vector和deque的存在则使你无法使用splice和成员形式的sort。结合上述限制，这意味着你无法调用任何形式的sort来对“泛化的序列容器”进行排序。

这些是显而易见的限制。如果你违反了这些限制，你的代码至少会在某些容器上无法通过编译。而能够通过编译的代码则更为棘手。

主要的问题在于不同序列容器对迭代器、指针和引用的失效规则不同。为了编写能够正确运行在vector、deque和list上的代码，你必须假设任何会使这些容器中的迭代器、指针或引用失效的操作都会使你使用的容器中的它们失效。因此，你必须假设每次调用insert都会使所有内容失效，因为deque::insert会使所有迭代器失效，而由于无法调用capacity，vector::insert必须被假定为会使所有指针和引用失效。

类似的推理表明，除非你正在删除容器中的最后一个元素，否则你也必须假设调用erase会使所有内容失效。

更糟糕的是，你不能将容器中的数据传递给C接口，因为只有vector支持这一点（详见第16条）。你不能将bool作为存储类型实例化你的容器，因为正如第18条所解释的，vector<bool>并不总是像vector，并且它实际上并不存储bool。你也不能假设list的插入和删除操作是常数时间的，因为vector和deque在执行这些操作时需要线性时间。

最终，你会发现自己创建了一个“泛化的序列容器”，它不能调用reserve、capacity、operator[]、push_front、pop_front、splice或任何需要随机访问迭代器的算法；一个每次调用insert和erase都需要线性时间并使所有内容失效的容器；一个与C接口不兼容的容器；一个不能存储bool的容器。这真的是你希望在应用程序中使用的容器类型吗？我猜不是。

如果你放弃对list的支持，你仍然会失去reserve、capacity、push_front和pop_front；你仍然必须假设所有对insert和erase的调用需要线性时间并使所有内容失效；你仍然失去了与C的内存布局兼容性；你仍然不能存储bool。

如果你转而尝试编写可以与不同关联容器一起工作的代码，情况也不会好多少。试图同时支持set和map几乎是不可能的，因为set存储单一对象，而map存储对象对。即使是同时支持set和multiset（或map和multimap）也很困难。以值为参数的insert成员函数在set/map和它们的多重版本中具有不同的返回类型，并且你必须非常小心地避免假设容器中存储的值的数量。

面对现实吧：这不值得。不同的容器有显著不同的优缺点。它们并不是为了可以互换而设计的，你也几乎无法掩盖它们之间的差异。如果你尝试这样做，你只是在诱惑命运，而命运并不喜欢被诱惑。

当然，总有一天你会发现自己选择的容器类型并不理想，需要更换为另一种类型。你现在知道，当你更换容器类型时，不仅需要修复编译器诊断出的问题，还需要检查所有使用容器的代码，以了解在新容器的性能特性和迭代器/指针/引用失效规则下需要进行哪些更改。如果你从vector切换到其他容器，你还需要确保不再依赖于vector的C兼容内存布局；如果你切换到vector，你需要确保没有使用它来存储bool。

考虑到更换容器类型的不可避免性，你可以通过封装来简化这种更改。这是传统的解决方案：封装、封装、封装。最简单的方法之一是通过广泛使用容器类型的typedef进行封装。因此，与其写成这样：

class Widget { ... };
vector<Widget> vw;
Widget bestWidget;
...
// 给bestWidget赋值
vector<Widget>::iterator i = find(vw.begin(), vw.end(), bestWidget);

不如写成这样：

class Widget { ... };
typedef vector<Widget> WidgetContainer;
WidgetContainer cw;
Widget bestWidget;
...
WidgetContainer::iterator i = find(cw.begin(), cw.end(), bestWidget);

这使得更改容器类型变得容易得多，尤其是在更改仅仅是添加自定义分配器时（这种更改不会影响迭代器/指针/引用失效规则）：

class Widget { ... };
template<typename T>
SpecialAllocator { ... }; // 第10条解释了为什么需要模板
typedef vector<Widget, SpecialAllocator<Widget>> WidgetContainer;
WidgetContainer cw;
Widget bestWidget;
...
WidgetContainer::iterator i = find(cw.begin(), cw.end(), bestWidget);

如果typedef的封装特性对你来说无关紧要，你仍然可能会欣赏它节省的工作量，尤其是对于迭代器类型。例如，如果你有一个类型为map<string, vector<Widget>::iterator, CIStringCompare>的对象，并希望使用const_iterator遍历该map，你真的愿意多次拼写出map<string, vector<Widget>::iterator, CIStringCompare>::const_iterator吗？一旦你使用STL一段时间，你就会意识到typedef是你的朋友。

typedef只是某种类型的同义词，因此它提供的封装仅限于词法层面。typedef不会阻止客户端做任何他们本来就可以做的事情（或依赖的行为）。如果你想限制客户端对你选择的容器的依赖，你需要更强大的工具：类。

为了限制在更换容器类型时可能需要修改的代码量，可以将容器隐藏在类中，并通过类接口限制暴露的容器特定信息。例如，如果你需要创建一个客户列表，不要直接使用list。相反，创建一个CustomerList类，并将list隐藏在其私有部分：

class CustomerList {
private:
    typedef list<Customer> CustomerContainer;
    typedef CustomerContainer::iterator CCIterator;
    CustomerContainer customers;
public:
    ...
    // 限制通过接口暴露的list特定信息
};

起初，这可能显得有些多余。毕竟，客户列表就是一个列表，对吧？也许吧。后来你可能会发现，你并不需要像预期的那样频繁地在列表中间插入或删除客户，但你确实需要快速识别出前20%的客户——这是一个非常适合使用nth_element算法的任务（见第31条）。但nth_element需要随机访问迭代器，它无法与list一起使用。在这种情况下，你的客户“列表”可能更适合用vector或deque实现。

当你考虑这种更改时，你仍然必须检查CustomerList的每个成员函数和每个友元，以了解它们将如何受到影响（例如性能和迭代器/指针/引用失效规则等方面），但如果你在封装CustomerList的实现细节方面做得很好，对CustomerList客户端的影响应该很小。你无法编写容器无关的代码，但他们可能可以。

Item 3: Make copying cheap and correct for objects in containers（确保容器中对象的拷贝操作既高效又正确）.

STL 容器存储对象，但并不是你直接放进去的那些对象。当你将一个对象添加到容器中（例如通过 insert 或 push_back 等操作），实际存储在容器中的，是你指定对象的拷贝。

一旦对象进入容器，它可能会被进一步拷贝。例如，如果你向 vector、string 或 deque 中插入或移除元素，现有的容器元素通常会被移动（也就是被拷贝）。如果你使用排序算法（如 sort，参见第31小节）；或者使用 next_permutation、remove、unique 等算法（参见第32小节），对象也会被移动（拷贝）。是的，拷贝对象是 STL 的常见操作。

了解这些拷贝操作的实现方式很重要。实际上，拷贝是通过调用对象的拷贝构造函数和拷贝赋值运算符来完成的。例如，对于一个用户自定义的类 Widget，这些函数通常声明如下：

class Widget {
public:
    Widget(const Widget&);            // 拷贝构造函数
    Widget& operator=(const Widget&); // 拷贝赋值运算符
};

如果你没有显式声明这些函数，编译器会自动为你生成默认版本。此外，对于内置类型（如 int、指针等），拷贝操作只是简单地复制底层的比特位。

由于 STL 容器频繁地进行拷贝操作，因此本节的重点很明确：如果容器中存储的对象拷贝开销较大，那么仅仅将对象放入容器中就可能成为性能瓶颈。容器中的对象被频繁移动时，这种性能问题会更加严重。此外，如果对象的“拷贝”操作具有非传统的定义（例如，拷贝操作改变了对象的某些状态），将这些对象存入容器中通常会导致问题。

在继承的场景下，拷贝操作还会引发切片问题（slicing problem）。如果你创建一个存储基类对象的容器，然后尝试将派生类对象插入其中，派生类对象的特性会在拷贝过程中丢失。例如：

vector<Widget> vw;
class SpecialWidget : public Widget { ... }; // SpecialWidget 继承自 Widget
SpecialWidget sw;
vw.push_back(sw); // sw 被拷贝为基类对象，派生类的特性被丢弃

切片问题表明，将派生类对象插入基类对象的容器中几乎总是错误的。如果你希望对象保留派生类的行为（例如调用派生类的虚函数等），那么这种操作肯定是错误的。

一种避免切片问题，同时使拷贝操作高效和正确的简单方法是：创建指针容器，而不是直接存储对象的容器。也就是说，与其创建 vector<Widget>，不如创建 vector<Widget*>。拷贝指针的开销很低，它总是按预期工作（即复制指针的比特位），并且不会发生切片问题。然而，指针容器有其自身的 STL 相关问题（参见第7小节和第33小节）。为了避免这些问题，同时解决效率、正确性和切片问题，你可能会发现智能指针容器是一个有吸引力的选择。有关智能指针容器的更多信息，请参见第7小节。

如果你觉得 STL 对拷贝操作过于频繁，那就再想想。是的，STL 确实会进行许多拷贝操作，但它通常会尽量避免不必要的拷贝操作。例如，与 C 和 C++ 的内置容器（数组）相比，STL 容器在避免不必要的对象创建方面做得更好：

Widget w[maxNumWidgets]; 
// 创建一个包含 maxNumWidgets 个 Widget 的数组，默认构造每个对象

上面的代码会构造 maxNumWidgets 个 Widget 对象，即使你可能只会使用其中的一部分，或者你打算立即用其他值覆盖这些默认构造的对象。而使用 STL 容器，我们可以这样做：

vector<Widget> vw;
// 创建一个初始大小为 0 的 vector，它会根据需要扩展

或者，我们可以创建一个空的 vector，但预留足够的空间来存储最多 maxNumWidgets 个对象，而无需构造任何对象：

vector<Widget> vw;
vw.reserve(maxNumWidgets); // 参见第14小节了解 reserve 的细节

与数组相比，STL 容器更加智能。它们只会在需要时创建对象，并且只会在你要求时使用默认构造函数。是的，STL 容器会进行拷贝操作，但它们仍然比数组更高效、更灵活。

Item 4: Call `empty` instead of checking `size()` against zero（调用`empty`而不是检查`size()`是否为零）.

对于任何容器 c，写下：

if (c.size() == 0) ...

基本上等同于写：

if (c.empty()) ...

既然如此，你可能会好奇，为什么要优先选择使用empty的方式，特别是考虑到empty通常实现为一个内联函数，仅仅返回size是否为0。

你应该优先选择使用empty，原因很简单：对于所有标准容器来说，empty是一个常量时间（constant-time）操作，而对于某些list（链表）实现来说，size可能需要线性时间（linear-time）。

但是什么原因导致list表现得如此“棘手”？为什么它不能像其他容器一样提供常量时间的size？答案与list的范围形式（range form）的unique和splice函数密切相关。考虑以下代码：

list<int> list1;
list<int> list2;
...

list1.splice(
    list1.end(), 
    list2, 
    find(list2.begin(), list2.end(), 5), 
    find(list2.rbegin(), list2.rend(), 10).base()
);

这段代码的作用是将list2中从第一个值为5的位置到最后一个值为10的位置的所有节点移动到list1的末尾（假设list2中确实存在这样的值）。但关键问题是：在splice操作完成后，list1中有多少个元素？

显然，在splice操作后，list1的元素数量等于原有数量加上从list2中移动过来的元素数量。但是，如何知道从list2中移动了多少个元素呢？唯一的方法是遍历这个范围并逐一计数。

假设你正在实现一个list类，你希望它的性能尽可能高效。你知道，许多用户会频繁调用size来获取列表的大小，因此你希望size是一个常量时间操作。然而，你也知道list是唯一一个支持高效splice操作的标准容器，用户选择list的一个重要原因就是它的splice操作具有常量时间的性能。

这就带来了两难的局面。如果size是一个常量时间操作，那么每次splice都必须更新列表的大小。然而，对于范围形式的splice，更新大小需要遍历范围并计数，这将破坏splice的常量时间性能。如果你希望splice保持常量时间性能，那么size就不得不成为一个线性时间操作，因为它需要遍历整个列表来计算元素数量。

不同的list实现对此冲突采取了不同的解决方案，这取决于实现者更重视size的效率还是splice的效率。如果你使用的list实现优先保证splice的常量时间性能，那么调用empty会比检查size() == 0更高效，因为empty始终是一个常量时间操作。即使你当前使用的实现中size是常量时间操作，也可能在未来切换到另一个实现时遇到问题。

无论你使用哪种实现，调用empty而不是检查size()是否为零总是不会出错。因此，每当你需要判断容器是否为空时，请优先调用empty。

Item 5: Prefer range member functions to their single-element counterparts（优先使用范围成员函数而非单元素成员函数）.

快速回答！给定两个向量 v1 和 v2，如何让 v1 的内容与 v2 的后半部分相同？不要纠结当 v2 有奇数个元素时“后半部分”如何定义，只需做一些合理的事情。

时间到！如果你的答案是：

v1.assign(v2.begin() + v2.size() / 2, v2.end());

或者类似的内容，那么你得到了满分并且可以获得一颗金星。如果你的答案涉及多个语句，但没有使用任何形式的循环，那么你几乎得到了满分，但没有金星。如果你的答案涉及一个循环，那么你还有进步的空间；如果涉及多个循环，那么……我们只能说你真的需要这本书了。

顺便说一句，如果你对答案的反应是“哈？”，请认真看下去，因为你将学到一些非常有用的内容。

这个小测试旨在达到两个目的。首先，它让我有机会提醒你 assign 成员函数的存在，这是一个非常方便的工具，但很多程序员都忽略了它。assign 可用于所有标准序列容器（如 vector、string、deque 和 list）。每当你需要完全替换容器的内容时，都应该考虑使用 assign。如果你只是将一个容器复制到另一个相同类型的容器中，operator= 是首选的赋值函数，但正如本例所示，当 operator= 无法满足需求时，assign 是一个很好的选择。

这个测试的第二个目的是展示为什么范围成员函数优于它们的单元素替代方案。范围成员函数是一种成员函数，它像 STL 算法一样，使用两个迭代器参数来指定需要操作的一段范围。如果不使用范围成员函数来解决本条开头的问题，你不得不写一个显式的循环，可能类似这样：

vector<Widget> v1, v2;
// 假设 v1 和 v2 是 Widget 类型的向量
...
v1.clear();
for (vector<Widget>::const_iterator ci = v2.begin() + v2.size() / 2;
     ci != v2.end();
     ++ci)
{
    v1.push_back(*ci);
}

第43条详细探讨了为什么应该尽量避免编写显式循环，但你不需要阅读那条也能看出，写这段代码比直接调用 assign 需要更多的工作。稍后我们会看到，这段循环还带来了性能上的额外开销，但我们稍后再讨论。

避免显式循环的一种方法是遵循第43条的建议，使用算法代替：

v1.clear();
copy(v2.begin() + v2.size() / 2, v2.end(), back_inserter(v1));

尽管这段代码没有显式循环，但它内部确实存在一个循环（在 copy 算法中实现）。因此，性能上的问题仍然存在。我们稍后再讨论性能问题，现在先简要指出：几乎所有使用 copy 的场景中，如果目标范围是通过插入迭代器（如 inserter、back_inserter 或 front_inserter）指定的，那么它们都可以（也应该）被范围成员函数替代。例如，这里可以用 insert 的范围版本替换 copy：

v1.insert(v1.end(), v2.begin() + v2.size() / 2, v2.end());

这段代码比调用 copy 需要稍少的输入，但它也更直接地表达了发生的事情：数据被插入到 v1 中。调用 copy 也表达了这一点，但不够直接。它把重点放在了复制操作上，而这并不是这里的重点。这里的重点是 v1 正在增加新数据。insert 成员函数清楚地表达了这一点，而 copy 则掩盖了这一点。在 STL 中，复制操作是如此基础，以至于本书的第3条就是关于它的！

太多的 STL 程序员过度使用了 copy，所以我刚才的建议值得重复：几乎所有使用 copy 的场景中，如果目标范围是通过插入迭代器指定的，都应该被范围成员函数替代。

回到我们的 assign 示例，我们已经找到了两个优先使用范围成员函数而非单元素替代方案的理由：

编写代码时通常更省力。
范围成员函数往往会导致代码更加清晰和直接。

简而言之，范围成员函数生成的代码更容易编写，也更容易理解。还有什么理由不喜欢呢？

然而，有些人会将这些理由视为编程风格问题，而开发者总是喜欢就风格问题争论不休，就像他们喜欢争论哪个编辑器是“唯一正确的编辑器”一样。（好像还有什么疑问似的，当然是 Emacs！）如果我们能找到一个更为广泛认同的标准来证明范围成员函数优于单元素成员函数，那就更好了。对于标准序列容器，我们确实有这样的标准：效率。当处理标准序列容器时，使用单元素成员函数通常会对内存分配器施加更多的需求，复制对象的频率更高，或者执行冗余操作，而这些在使用范围成员函数时可以避免。

例如，假设你想将一个整型数组的内容复制到一个向量的开头。（数据可能最初存储在数组中，因为它来自某个遗留的 C API。关于将 STL 容器与 C API 混合使用时出现的问题，请参见第16条。）使用向量的范围 insert 函数，这样做非常简单：

int data[numValues];
// 假设 numValues 已在其他地方定义
vector<int> v;
...
v.insert(v.begin(), data, data + numValues);
// 将 data 中的整型插入到 v 的开头

如果使用显式循环调用单元素 insert，代码可能看起来像这样：

vector<int>::iterator insertLoc(v.begin());
for (int i = 0; i < numValues; ++i) {
    insertLoc = v.insert(insertLoc, data[i]);
    ++insertLoc;
}

注意，我们必须小心保存 insert 的返回值以供下一次循环迭代使用，然后递增返回的迭代器。如果我们不在每次插入后更新 insertLoc，我们会遇到两个问题。首先，第一次插入后，所有后续的循环迭代都会导致未定义行为，因为每次调用 insert 都会使 insertLoc 失效。其次，即使 insertLoc 保持有效，我们也会始终在向量的开头插入（即 v.begin()），结果是复制到 v 的整数会以相反的顺序排列。

如果我们遵循第43条的建议，用对 copy 的调用替换循环，我们会得到类似这样的代码：

copy(data, data + numValues, inserter(v, v.begin()));

当 copy 模板被实例化时，基于 copy 的代码和显式循环的代码几乎是相同的，因此为了分析效率，我们将专注于显式循环，同时记住，这种分析同样适用于使用 copy 的代码。关注显式循环只是为了更容易理解效率损失的来源。是的，这里的“损失”是复数形式，因为使用单元素版本的 insert 的代码会给你带来多达三种不同的性能“税”，而如果使用范围版本的 insert，这些开销都可以避免。

第一个“税”是不必要的函数调用。将 numValues 个元素逐一插入到 v 中，自然需要调用 insert 函数 numValues 次。而使用范围形式的 insert，只需要进行一次函数调用，从而节省了 numValues-1 次调用。当然，内联优化可能会帮助你避免这一开销，但也可能不会。唯一可以确定的是，使用范围形式的 insert，你绝对不会支付这笔“税”。

内联优化无法帮你避开第二种“税”，即低效地将 v 中已有元素移动到插入后的最终位置的成本。每次调用 insert 向 v 中添加一个新值时，插入点之后的每个元素都必须向上移动一个位置，以为新元素腾出空间。因此，位置为 p 的元素必须移动到位置 p+1，以此类推。在我们的示例中，我们将 numValues 个元素插入到 v 的开头，这意味着在插入之前，v 中的每个元素都需要向上移动总计 numValues 个位置。然而，每次调用 insert 时，它们只会向上移动一个位置，因此每个元素总共会被移动 numValues 次。如果在插入之前 v 中有 n 个元素，那么总共会发生 n*numValues 次移动操作。

在这个示例中，v 存储的是 int，因此每次移动可能会归结为调用一次 memmove。但是，如果 v 存储的是用户定义的类型（例如 Widget），每次移动都会导致调用该类型的赋值运算符或拷贝构造函数。（大多数情况下会调用赋值运算符，但每次移动 vector 的最后一个元素时，这次移动将通过调用该元素的拷贝构造函数完成。）因此，在一般情况下，将 numValues 个新对象逐一插入到一个包含 n 个元素的 vector<Widget> 的开头，会产生 n*numValues 次函数调用的开销：(n-1)*numValues 次调用 Widget 的赋值运算符，以及 numValues 次调用 Widget 的拷贝构造函数。即使这些调用被内联优化，你仍然需要执行 numValues 次移动 v 中元素的操作。

相比之下，标准要求范围插入函数将已有的容器元素直接移动到它们的最终位置，也就是说，每个元素只需要移动一次。总的开销是 n 次移动操作，其中 numValues 次调用容器中对象类型的拷贝构造函数，其余的调用该类型的赋值运算符。与单元素插入策略相比，范围插入减少了 n*(numValues-1) 次移动操作。仔细想一想这点。如果 numValues 是 100，那么范围形式的 insert 将比反复调用单元素形式的 insert 少执行 99% 的移动操作！

在继续讨论单元素成员函数相较于它们的范围版本所带来的第三种效率成本之前，我需要做一个小的补充说明。我在上一段中所写的内容是完全真实的，但并不完全全面。范围插入函数仅在能够在不失去当前位置的情况下确定两个迭代器之间的距离时，才能通过一次移动将元素放置到它的最终位置。这种情况几乎总是成立，因为所有前向迭代器（forward iterators）都提供这种功能，而前向迭代器几乎无处不在。标准容器的所有迭代器都提供前向迭代器功能，非标准的哈希容器（参见第25条）的迭代器也是如此。作为数组的迭代器的指针同样支持这种功能。实际上，唯一不支持前向迭代器功能的标准迭代器是输入迭代器（input iterators）和输出迭代器（output iterators）。因此，除非传递给范围形式 insert 的迭代器是输入迭代器（例如 istream_iterators，参见第6条），否则我上面所写的内容都是正确的。在这种情况下，范围插入函数才可能被允许逐个位置地将元素移动到它们的最终位置。如果它确实以这种方式实现，那么在元素移动次数方面的优势将不复存在。（对于输出迭代器，这个问题并不存在，因为输出迭代器不能用于指定 insert 的范围。）

对于那些愚蠢地选择使用重复的单元素插入操作而不是单次范围插入操作的人来说，最终的性能“税”与内存分配有关，尽管它也带来了讨厌的拷贝成本。正如第14条所解释的，当你试图向一个内存已满的 vector 中插入一个元素时，vector 会分配具有更大容量的新内存，将旧内存中的元素复制到新内存中，销毁旧内存中的元素，并释放旧内存。然后，它会添加正在插入的元素。第14条还解释了，vector 的实现通常通过某种乘法因子增加其容量，因此插入 numValues 个新元素通常会导致按 numValues 的对数比例多次分配新内存。例如，如果以增长率为1.5的方式向一个 vector 中逐个插入1000个元素，则可能导致多达18次新内存分配（包括每次分配时对元素的复制）。相比之下（现在这已经显而易见了），范围插入可以在开始插入之前（假设提供了前向迭代器）计算出所需的新内存量，因此它最多只需要重新分配一次底层内存。可以想象，这种方式节省的开销是相当可观的。

我刚刚进行的分析是针对 vector 的，但同样的推理也适用于 string。对于 deque，推理类似，但由于 deque 的内存管理方式不同于 vector 和 string，关于重复内存分配的论点并不适用。然而，关于不必要地多次移动元素的论点通常仍然适用（尽管细节有所不同），以及关于函数调用次数的观察也是如此。

在标准序列容器中，仅剩下 list，但即使在这里，使用范围形式的 insert 而不是单元素形式的 insert 也有性能优势。当然，关于重复函数调用的论点仍然成立，但由于链表的工作方式，拷贝和内存分配的问题并不存在。取而代之的是一个新问题：对链表中某些节点的 next 和 prev 指针进行重复的多余赋值。

每次向链表中添加一个元素时，存储该元素的链表节点必须设置其 next 和 prev 指针。当然，新节点之前的节点（我们称之为 B，代表“before”）必须设置其 next 指针，而新节点之后的节点（我们称之为 A，代表“after”）必须设置其 prev 指针：

当通过调用 list 的单元素插入函数逐个添加一系列新节点时，除了最后一个新节点以外，所有其他新节点的 next 指针都会被设置两次：第一次指向 A，第二次指向插入在它之后的元素。而 A 的 prev 指针在每次有新节点插入到它前面时，都会被设置为指向该新节点。如果在 A 前插入了 numValues 个节点，那么插入的节点的 next 指针将会有 numValues-1 次多余的赋值操作，而 A 的 prev 指针也会有 numValues-1 次多余的赋值操作。总计下来，这就是 2*(numValues-1) 次不必要的指针赋值。当然，指针赋值的开销很低，但如果可以避免，为什么还要支付这些成本呢？

到现在应该已经很清楚了，你完全可以避免这些成本，而关键就在于使用 list 的范围形式的 insert。由于该函数知道最终会插入多少个节点，它可以避免多余的指针赋值操作，仅通过对每个指针进行一次赋值来设置其正确的插入后值。

因此，对于标准序列容器，在选择单元素插入和范围插入时，影响的不仅仅是编程风格。对于关联容器（associative containers），效率上的理由则更难以提出，尽管重复调用单元素插入所带来的额外函数调用开销问题仍然适用。此外，某些特殊类型的范围插入可能会为关联容器带来优化的可能性，但据我所知，这种优化目前仅存在于理论中。当然，当你读到这段内容时，理论可能已经变成了实践，因此在关联容器中使用范围插入可能确实比重复的单元素插入更高效。当然，它们绝不会比单元素插入更低效，所以选择范围插入并没有任何损失。

即使抛开效率问题不谈，使用范围成员函数的事实仍然意味着在编写代码时需要更少的输入，同时还能生成更容易理解的代码，从而增强软件的长期可维护性。这两个特性本身就足以说服你优先选择范围成员函数，而效率上的优势只是一个额外的奖励。

既然已经花了这么多篇幅讨论范围成员函数的优点，那么总结一下这些函数显然是合适的。了解哪些成员函数支持范围操作可以让你更容易识别使用它们的机会。在以下函数签名中，参数类型 iterator 字面上表示容器的迭代器类型，即 container::iterator。而参数类型 InputIterator 则表示任何输入迭代器都是可以接受的。

范围构造（Range Construction）。所有标准容器都提供如下形式的构造函数：

container::container(InputIterator begin, // beginning of range
                     InputIterator end); // end of range

当传递给此构造函数的迭代器是 istream_iterator 或 istreambuf_iterator（参见第29条）时，你可能会遇到 C++ 中最令人惊讶的解析行为之一——这种行为会导致编译器将该构造视为函数声明，而不是定义一个新的容器对象。第6条详细解释了关于这种解析行为的一切，包括如何避免它。

范围插入（Range Insertion）。所有标准序列容器都提供如下形式的插入操作：

void container::insert(iterator position,   // where to insert the range
                       InputIterator begin, // start of range to insert 
                       InputIterator end);  // end of range to insert

关联容器（Associative containers）使用其比较函数来确定元素的位置，因此它们提供了省略位置参数的函数签名：

void container::insert(InputIterator begin, InputIterator end);

在寻找将单元素插入替换为范围插入的方法时，不要忘记，有些单元素插入操作可能会通过采用不同的函数名称来伪装自己。例如，push_front 和 push_back 都是向容器中插入单个元素的操作，尽管它们并不叫 insert。如果你看到一个循环在调用 push_front 或 push_back，或者看到像 copy 这样的算法被传递了 front_inserter 或 back_inserter 作为参数，那么你就发现了一个可能可以用范围形式的 insert 来替代的地方，这通常是更优的策略。

范围删除（Range Erasure）。每个标准容器都提供范围形式的 erase 操作，但序列容器和关联容器的返回类型有所不同。序列容器提供如下形式：

iterator container::erase(iterator begin, iterator end);

而关联容器则提供如下形式：

void container::erase(iterator begin, iterator end);

为什么会有这种差异？据称，让关联容器版本的 erase 返回一个迭代器（指向被删除元素之后的那个元素）会导致不可接受的性能损失。我和许多人一样认为这种说法站不住脚，但标准就是标准，标准规定了序列容器和关联容器的 erase 返回类型是不同的。

本条关于 insert 的大部分效率分析同样适用于 erase。对于单元素 erase 的重复调用，其函数调用次数仍然比单次调用范围形式的 erase 多。使用单元素 erase 时，元素值仍需一个接一个地向它们的最终位置移动，而范围形式的 erase 则可以通过一次移动将它们直接移到最终位置。

关于 vector 和 string 的 insert 的一个论点在 erase 上不适用，这涉及到重复分配的问题。（对于 erase，当然是涉及重复释放的问题。）这是因为 vector 和 string 的内存会自动扩展以容纳新元素，但当元素数量减少时，内存不会自动缩减。（第17条描述了如何减少 vector 或 string 持有的不必要内存。）

范围形式的 erase 的一个特别重要的应用是“erase-remove 惯用法”。关于它的详细信息可以在第32条中找到。

关于 vector 和 string 的 insert 的一个论点在 erase 上不适用，这涉及到重复分配的问题。（对于 erase，当然是涉及重复释放的问题。）

范围赋值（Range Assignment）。正如我在本条开头提到的，所有标准序列容器都提供范围形式的 assign 操作：

void container::assign(InputIterator begin, InputIterator end);

综上所述，有三个充分的理由支持优先选择范围成员函数而非它们的单元素版本。范围成员函数更易于编写，能够更清晰地表达你的意图，并且表现出更高的性能。这是一个难以超越的“三驾马车”。