C++ Primer - 第 10 章 泛型算法

10.1 概述

1. 标准库的 find 算法可用于查找输入范围中是否包含某个指定元素。

   template<class InputIterator, class T>
     InputIterator find (InputIterator first, InputI
     terator last, const T& val)
   {
     while (first != last) {
       if (*first == val) return first;
       ++first;
     }
     return last;
   }

2. 标准库的 count 算法可用于查找某个指定元素在输入范围中出现的次数。

   template <class InputIterator, class T>
     typename iterator_traits<InputIterator>::difference_type
       count (InputIterator first, InputIterator last, const T& val)
   {
     typename iterator_traits<InputIterator>::difference_type ret = 0;
     while (first != last) {
       if (*first == val) ++ret;
       ++first;
     }
     return ret;
   }

10.2 初识泛型算法

1. 除了少数例外，标准库算法都对一个范围内的元素进行操作。我们将此元素范围称为“输入范围”。接受输入范围的算法总是使用前两个参数来表示此范围，两个参数分别是指向要处理的第一个元素和尾元素之后位置的迭代器。

10.2.1 只读算法

1. 另一个只读算法是 accumulate，它定义在头文件 numeric 中。accumulate 函数接受三个参数，前两个指出了需要求和的元素的范围，第三个参数是和的初值。

   // 对 vec 中的元素求和，和的初值是 0
   int sum = accumulate(vec.cbegin(), vec.cend(), 0);

   用于连接 string：

   string sum = accumulate(v.cbegin(), v.cend(), string(""));

   将空串当做一个字符串字面值传递给第三个参数是不可以的，会导致一个编译错误：

   // 错误：const char* 上没有定义 + 运算符
   string sum = accumulate(v.cbegin(), v.cend(), "");

2. 另一个只读算法是 equal，用于确定两个序列是否保存相同的值。它将第一个序列中的每个元素与第二个序列中的对应元素进行比较。如果所有对应元素都相等，则返回 true，否则返回 false。此算法接受三个迭代器：前两个（与以往一样）表示第一个序列中的元素范围，第三个表示第二个序列的首元素：

   // roster2 中的元素数目应该至少与 roster1 一样多
   equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());

   由于 equal 利用迭代器完成操作，因此我们可以通过调用 equal 来比较两个不同类型的容器中的元素。而且，元素类型也不必一样，只要我们能用 == 来比较两个元素类型即可。
   例如，在此例中，roster1 可以是 vector<string>，而 roster2 是 list<const char*>。但是，equal 基于一个非常重要的假设：它假定第二个序列至少与第一个序列一样长。此算法要处理第一个序列中的每个元素，它假定每个元素在第二个序列中都有一个与之对应的元素。

10.2.2 写容器元素的算法

1. 使用 fill 算法填充容器：

   fill(vec.begin(), vec.end(), 0); // 将每个元素重置为 0
   // 将容器的一个子序列设置为 10
   fill(vec.begin(), vec.begin() + vec.size() / 2, 10);

2. fill_n 算法也可用于填充容器，它接受的是一个迭代器、一个计数值和一个值：

   vector<int> vec; // 空 vector
   // 使用 vec，赋予它不同值
   fill_n(vec.begin(), vec.size(), 0); // 将所有元素重置为 0

   容易犯的错误是在一个空容器上调用 fill_n（或类似的写元素的算法）：

   vector<int> vec; // 空向量
   // 灾难：修改 vec 中的 10 个（不存在）元素
   fill_n(vec.begin(), 10, 0);

   WARNING： 向目的位置迭代器写入数据的算法假定目的位置足够大，能容纳要写入的元素。

3. 一种保证算法有足够元素空间来容纳输出数据的方法是使用插入迭代器（insert iterator）。当我们通过一个插入迭代器赋值时，一个与赋值号右侧值相等的元素被添加到容器中。

4. 一个典型的插入迭代器是 back_inserter，它定义在头文件 iterator 中。back_inserter 接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器。当我们通过此迭代器赋值时，赋值运算符会调用 push_back 将一个具有给定值的元素添加到容器中：

   vector<int> vec;              // 空向量
   auto it = back_inserter(vec); // 通过它赋值会将元素添加到 vec 中
   *it = 42;                     // vec 中现在有一个元素，值为42

   通常使用 back_inserter 来创建一个迭代器，作为算法的目的位置来使用。例如：

   vector<int> vec; // 空向量
   // 正确：back_inserter 创建一个插入迭代器，可用来向 vec 添加元素
   fill_n(back_inserter(vec), 10, 0); // 添加 10 个元素到 vec

5. 可以通过 copy 算法实现内置数组的拷贝：

   int al[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
   int a2[sizeof(al) / sizeof(*al)]; // a2 与 a1 大小一样
   // ret 指向拷贝到 a2 的尾元素之后的位置
   auto ret = copy(begin(al), end(al), a2); // 把 a1 的内容拷贝给 a2

6. replace 算法读入一个序列，并将其中所有等于给定值的元素都改为另一个值。此算法接受 4 个参数：前两个是迭代器，表示输入序列，后两个一个是要搜索的值，另一个是新值。它将所有等于第一个值的元素替换为第二个值：

   // 将所有值为 0 的元素改为 42
   replace(ilst.begin(), ilst.end(), 0, 42);

   此调用将序列中所有的 0 都替换为 42。如果我们希望保留原序列不变，可以调用 replace_copy。此算法接受额外第三个迭代器参数，指出调整后序列的保存位置：

   // 使用 back_inserter 按需要增长目标序列
   replace_copy(ilst.cbegin(), ilst.cend(), back_inserter(ivec), 0, 42);

   此调用后，ilst 并未改变，ivec 包含 ilst 的一份拷贝，不过原来在 ilst 中值为 0 的元素在 ivec 中都变为 42。

10.2.3 重排容器元素的算法

1. 调用 sort 会重排输入序列中的元素，使之有序，它是利用元素类型的 < 运算符来实现排序的。

2. unique 算法重排输入序列，将相邻的重复项“消除”，并返回一个指向不重复值范围末尾的迭代器。unique 并不真的删除任何元素，它只是覆盖相邻的重复元素，使得不重复元素出现在序列开始部分。unique 返回的迭代器指向最后一个不重复元素之后的位置，此位置之后的元素仍然存在，但我们不知道它们的值是什么。

10.3 定制操作

10.3.1 向算法传递函数

1. sort 默认使用 < 运算符进行排序，还可以传给它一个二元比较函数来进行排序，这个二元比较函数称为谓词（predicate），标准库算法所使用的谓词分为两类：一元谓词（unary predicate，意味着它们只接受单一参数）和二元谓词（binary predicate，意味着它们有两个参数）。

2. stable_sort 算法维持相等元素的原有顺序。

3. 标准库定义了名为 partition 的算法，它接受一个谓词，对容器内容进行划分，使得谓词为 true 的值会排在容器的前半部分，而使谓词为 false 的值会排在后半部分。算法返回一个迭代器，指向最后一个使谓词为 true 的元素之后的位置。

10.3.2 lambda 表达式

1. 标准库的 find_if 算法接受一对迭代器，表示一个范围。但与 find 不同的是，find_if 的第三个参数是一个谓词。find_if 算法对输入序列中的每个元素调用给定的这个谓词。它返回第一个使谓词返回非 0 值的元素，如果不存在这样的元素，则返回尾迭代器。

   Returns an iterator to the first element in the range [first,last) for which pred returns true. If no such element is found, the function returns last.

2. lambda 表达式（lambda expression）是一个可调用对象（callable object）。一个 lambda 表达式表示一个可调用的代码单元。我们可以将其理解为一个未命名的内联函数。与任何函数类似，一个 lambda 具有一个返回类型、一个参数列表和一个函数体。但与函数不同，lambda 可能定义在函数内部。一个 lambda 表达式具有如下形式：

   [capture list] (parameter list) -> return type { fiunction body }

   其中，capture list（捕获列表）是一个 lambda 所在函数中定义的局部变量的列表（通常为空）；return type、parameter list 和 function body 与任何普通函数一样，分别表示返回类型、参数列表和函数体。但是，与普通函数不同，lambda 必须使用尾置返回来指定返回类型。我们可以忽略参数列表和返回类型，但必须永远包含捕获列表和函数体：

   auto f = [] { return 42; };

3. 在 lambda 中忽略括号和参数列表等价于指定一个空参数列表。如果忽略返回类型，lambda 根据函数体中的代码推断出返回类型。如果函数体只是一个 return 语句，则返回类型从返回的表达式的类型推断而来。否则，返回类型为 void。

   Note： 如果 lambda 的函数体包含任何单一 return 语句之外的内容，且未指定返回类型，则返回 void。

4. 与一个普通函数调用类似，调用一个 lambda 时给定的实参被用来初始化 lambda 的形参。通常，实参和形参的类型必须匹配。但与普通函数不同，lambda 不能有默认参数。因此，一个 lambda 调用的实参数目永远与形参数目相等。一旦形参初始化完毕，就可以执行函数体了。

   [](const string &a, const string &b)
   { return a.size() < b.size(); }

   空捕获列表表明此 lambda 不使用它所在函数中的任何局部变量。

5. 虽然一个 lambda 可以出现在一个函数中，使用其局部变量，但它只能使用那些明确指明的变量。一个 lambda 通过将局部变量包含在其捕获列表中来指出将会使用这些变量。捕获列表指引 lambda 在其内部包含访问局部变量所需的信息。

   Note： 一个 lambda 只有在其捕获列表中捕获一个它所在函数中的局部变量，才能在函数体中使用该变量。

6. for_each 算法接受一个可调用对象，并对输入序列中每个元素调用此对象：

   // 打印长度大于等于给定值的单词，每个单词后面接一个空格
   for_each(wc, words.end(),
            [](const string &s)
            { cout << s << ""; });
   cout << endl;

7. Note：捕获列表只用于局部非 static 变量，lambda 可以直接使用局部 static 变量和在它所在函数之外声明的名字。

10.3.3 lambda 捕获和返回

1. 当定义一个 lambda 时，编译器生成一个与 lambda 对应的新的（未命名的）类类型。可以这样理解，当向一个函数传递一个 lambda 时，同时定义了一个新类型和该类型的一个对象：传递的参数就是此编译器生成的类类型的未命名对象。类似的，当使用 auto 定义一个用 lambda 初始化的变量时，定义了一个从 lambda 生成的类型的对象。

2. 默认情况下，从 lambda 生成的类都包含一个对应该 lambda 所捕获的变量的数据成员。类似任何普通类的数据成员，lambda 的数据成员也在 lambda 对象创建时被初始化。

3. 类似参数传递，变量的捕获方式也可以是值或引用。与传值参数类似，采用值捕获的前提是变量可以拷贝。与参数不同，被捕获的变量的值是在 lambda 创建时拷贝，而不是调用时拷贝。由于被捕获变量的值是在 lambda 创建时拷贝，因此随后对其修改不会影响到 lambda 内对应的值。

4. 一个以引用方式捕获的变量与其他任何类型的引用的行为类似。当我们在 lambda 函数体内使用此变量时，实际上使用的是引用所绑定的对象。如果我们采用引用方式捕获一个变量，就必须确保被引用的对象在 lambda 执行的时候是存在的。 lambda 捕获的都是局部变量，这些变量在函数结束后就不复存在了。如果 lambda 可能在函数结束后执行，捕获的引用指向的局部变量已经消失。

5. 我们也可以从一个函数返回 lambda。函数可以直接返回一个可调用对象，或者返回一个类对象，该类含有可调用对象的数据成员。如果函数返回一个 lambda，则与函数不能返回一个局部变量的引用类似，此 lambda 也不能包含引用捕获。

6. WARNING：当以引用方式捕获一个变量时，必须保证在 lambda 执行时变量是存在的。

7. 建议：尽量保持 lambda 的变量捕获简单化。 如果我们捕获一个指针或迭代器，或采用引用捕获方式，就必须确保在 lambda 执行时，绑定到迭代器、指针或引用的对象仍然存在。而且，需要保证对象具有预期的值。在 lambda 从创建到它执行的这段时间内，可能有代码改变绑定的对象的值。也就是说，在指针（或引用）被捕获的时刻，绑定的对象的值是我们所期望的，但在 lambda 执行时，该对象的值可能已经完全不同了。一般来说，我们应该尽量减少捕获的数据量，来避免潜在的捕获导致的问题。而且，如果可能的话，应该避免捕获指针或引用。

8. 除了显式列出我们希望使用的来自所在函数的变量之外，还可以让编译器根据 lambda 体中的代码来推断我们要使用哪些变量。为了指示编译器推断捕获列表，应在捕获列表中写一个 & 或 =。& 告诉编译器采用捕获引用方式，= 则表示采用值捕获方式。

9. 如果我们希望对一部分变量采用值捕获，对其他变量采用引用捕获，可以混合使用隐式捕获和显式捕获：

   // os 隐式捕获，引用捕获方式；c 显式捕获，值捕获方式
   for_each(words.begin(), words.end(),
            [&, c](const string &s)
            { os << s << c; });
   // os 显式捕获，引用捕获方式；c 隐式捕获，值捕获方式
   for_each(words.begin(), words.end(),
            [=, &os](const string &s)
            { os << s << c; });

10. 当我们混合使用隐式捕获和显式捕获时，捕获列表中的第一个元素必须是一个 & 或=。此符号指定了默认捕获方式为引用或值。当混合使用隐式捕获和显式捕获时，显式捕获的变量必须使用与隐式捕获不同的方式。即，如果隐式捕获是引用方式（使用了 &），则显式捕获命名变量必须采用值方式，因此不能在其名字前使用 &。类似的，如果隐式捕获采用的是值方式（使用了 =），则显式捕获命名变量必须采用引用方式，即，在名字前使用 &。

11. lambda 捕获列表：

    lambda 捕获列表
    []	空捕获列表。lambda 不能使用所在函数中的变量。一个 lambda 只有捕获变量后才能使用它们
    [names]	names 是一个逗号分隔的名字列表，这些名字都是 lambda 所在函数的局部变量。默认情况下，捕获列表中的变量都被拷贝。名字前如果使用了 &，则采用引用捕获方式
    [&]	隐式捕获列表，采用引用捕获方式。lambda 体中所使用的来自所在函数的实体都采用引用方式使用
    [=]	隐式捕获列表，采用值捕获方式。lambda 体将拷贝所使用的来自所在函数的实体的值
    [&, identifier_list]	identifier_list 是一个逗号分隔的列表，包含 0 个或多个来自所在函数的变量。这些变量采用值捕获方式，而任何隐式捕获的变量都采用引用方式捕获。identifier_list 中的名字前面不能使用 &
    [=, identifier_list]	identifier_list 中的变量都采用引用方式捕获，而任何隐式捕获的变量都采用值方式捕获。identifier_list 中的名字不能包括 this，且这些名字之前必须使用 &

12. 默认情况下，对于一个值被拷贝的变量，lambda 不会改变其值。如果我们希望能改变一个被捕获的变量的值，就必须在参数列表首加上关键字 mutable。因此，可变 lambda 能省略参数列表：

    void fcn3()
    {
        size_t v1 = 42; // 局部变量
        // f 可以改变它所捕获的变量的值
        auto f = [v1]() mutable { return ++v1; };
        v1 = 0;
        auto j = f(); // j 为 43
    }

    一个引用捕获的变量是否（如往常一样）可以修改依赖于此引用指向的是一个 const 类型还是一个非 const 类型。

13. 默认情况下，如果一个 lambda 体包含 return 之外的任何语句，则编译器假定此 lambda 返回 void。与其他返回 void 的函数类似，被推断返回 void 的 lambda 不能返回值。

14. 可以使用标准库 transform 算法和一个 lambda 来将一个序列中的每个负数替换为其绝对值：

    transform(vi.begin(), vi.end(), vi.begin(),
              [](int i)
              { return i < 0 ? -i : i; });

    函数 transform 接受三个迭代器和一个可调用对象。前两个迭代器表示输入序列，第三个迭代器表示目的位置。算法对输入序列中每个元素调用可调用对象，并将结果写到目的位置。如本例所示，目的位置迭代器与表示输入序列开始位置的迭代器可以是相同的。当输入迭代器和目的迭代器相同时，transform 将输入序列中每个元素替换为可调用对象操作该元素得到的结果。

15. 当我们需要为一个 lambda 定义返回类型时，必须使用尾置返回类型。

16. 标准库定义了一个名为 count_if 的算法。类似 find_if，此函数接受一对迭代器，表示一个输入范围，还接受一个谓词，会对输入范围中每个元素执行。count_if 返回一个计数值，表示谓词有多少次为真。

17. 练习 10.21： 编写一个 lambda，捕获一个局部 int 变量，并递减变量值，直至它变为 0。一旦变量变为 0，再调用 lambda 应该不再递减变量。lambda 应该返回一个 bool 值，指出捕获的变量是否为 0。

    auto func = [&sum]() -> bool
    {
        if (sum <= 0)
            return true;
        else
        {
            --sum;
            return false;
        }
    }

10.3.4 参数绑定

1. 对于那种只在一两个地方使用的简单操作，lambda 表达式是最有用的。如果我们需要在很多地方使用相同的操作，通常应该定义一个函数，而不是多次编写相同的 lambda 表达式。类似的，如果一个操作需要很多语句才能完成，通常使用函数更好。

2. C++11 引入一个名为 bind 的标准库函数，它定义在头文件 functional 中。可以将 bind 函数看作一个通用的函数适配器，它接受一个可调用对象，生成一个新的可调用对象来“适应”原对象的参数列表。调用 bind 的一般形式为：

   auto newCallable = bind(callable, arg_list);

   其中，newCallable 本身是一个可调用对象，arg_list 是一个逗号分隔的参数列表，对应给定的 callable 的参数。即，当我们调用 newCallable 时，newCallable 会调用 callable，并传递给它 arg_list 中的参数。arg_list 中的参数可能包含形如 _n 的名字，其中 n 是一个整数。这些参数是“占位符”，表示 newCallable 的参数，它们占据了传递给 newCallable 的参数的“位置”。数值 n 表示生成的可调用对象中参数的位置：1 为 newCallable 的第一个参数，2 为第二个参数，依此类推。例如：

   // check6 是一个可调用对象，接受一个 string 类型的参数
   // 并用此 string 和值 6 来调用 check_size
   auto check6 = bind(check_size, _1, 6);

   此 bind 调用只有一个占位符，表示 check6 只接受单一参数。占位符出现在 arg_list 的第一个位置，表示 check6 的此参数对应 check_size 的第一个参数。

3. 名字 _n 都定义在一个名为 placeholders 的命名空间中，而这个命名空间本身定义在 std 命名空间中。placeholders 命名空间也定义在 functional 头文件中。

4. 下面的典型示例说明了 bind 的用法：

   // g 是一个有两个参数的可调用对象
   auto g = bind(f, a, b, _2, c, _1);

   上述 bind 调用生成一个新的可调用对象，它有两个参数，分别用占位符 _2 和 _1 表示。这个新的可调用对象将它自己的参数作为第三个和第五个参数传递给 f。f 的第一个、第二个和第四个参数分别被绑定到给定的值 a、b 和 c 上。

   传递给 g 的参数按位置绑定到占位符。即，第一个参数绑定到 _1，第二个参数绑定到 _2。因此，当我们调用 g 时，其第一个参数将被传递给 f 作为最后一个参数，第二个参数将被传递给 f 作为第三个参数。实际上，这个 bind 调用会将

   g(_1, _2);

   映射为

   f(a, b, _2, c, _1)

   即，对 g 的调用会调用 f，用 g 的参数代替占位符，再加上绑定的参数 a、b 和 c。例如，调用 g(X, Y) 会调用

   f(a, b, Y, c, X)

5. 默认情况下，bind 的那些不是占位符的参数被拷贝到 bind 返回的可调用对象中。但是，与 lambda 类似，有时对有些绑定的参数我们希望以引用方式传递，或是要绑定参数的类型无法拷贝，例如 ostream 类型，我们不能拷贝一个 ostream。如果我们希望传递给 bind 一个对象而又不拷贝它，就必须使用标准库 ref 函数，函数 ref 返回一个对象，包含给定的引用，此对象是可以拷贝的。标准库中还有一个 cref 函数，生成一个保存 const 引用的类。与 bind 一样，函数 ref 和 cref 也定义在头文件 functional 中。

6. 练习 10.24： 给定一个 string，使用 bind 和 check_size 在一个 int 的 vector 中查找第一个大于 string 长度的值。

   注意是要查找第一个大于 string 长度的值，而 check_size 检查的是 sz 是否小于等于 string 长度，所以此处使用 find_if_not：

   bool check_size(const string &s, string::size_type sz) { return s.size() >= sz; }
   
   string str = "test";
   vector<int> vec = {2, 1, 3, 6, 9, 5, 7, 10, 0};
   auto iter = find_if_not(vec.begin(), vec.end(), bind(check_size, str, _1));
   cout << "result is " << (iter == vec.end() ? "null" : to_string(*iter)) << endl;

10.4 再探迭代器

1. 除了容器迭代器，标准库在头文件 iterator 中还定义了额外几种迭代器：
   • 插入迭代器（insert iterator）：这些迭代器被绑定到一个容器上，可用来向容器插入元素。
   • 流迭代器（stream iterator）：这些迭代器被绑定到输入或输出流上，可用来遍历所关联的 IO 流。
   • 反向迭代器（reverse iterator）：这些迭代器向后而不是向前移动。除了 forward_list 之外的标准库容器都有反向迭代器。
   • 移动迭代器（move iterator）：这些专用的迭代器不是拷贝其中的元素，而是移动它们。

10.4.1 插入迭代器

1. 插入器有三种类型，差异在于元素插入的位置：

   • back_inserter 创建一个使用 push_back 的迭代器。
   • front_inserter 创建一个使用 push_front 的迭代器。
   • inserter 创建一个使用 insert 的迭代器。此函数接受第二个参数，这个参数必须是一个指向给定容器的迭代器。元素将被插入到给定迭代器所表示的元素之前。

   只有在容器支持 push_front 的情况下，我们才可以使用 front_inserter。类似的，只有在容器支持 push_back 的情况下，我们才能使用 back_inserter。

2. 如果 it 是由 inserter 生成的迭代器，则下面这样的赋值语句：

   *it = val;

   其效果与下面代码一样：

   it = c.insert(it, val); // it 指向新加入的元素
   ++it;                   // 递增 it 使它指向原来的元素

3. front_inserter 生成的迭代器的行为与 inserter 生成的迭代器完全不一样。当我们使用 front_inserter 时，元素总是插入到容器第一个元素之前。即使我们传递给 inserter 的位置原来指向第一个元素，只要我们在此元素之前插入一个新元素，此元素就不再是容器的首元素了：

   list<int> lst = {1, 2, 3, 4};
   list<int> lst2, lst3; // 空 list
   // 拷贝完成之后，lst2 包含 4 3 2 1
   copy(lst.cbegin(), lst.cend(), front_inserter(lst2));
   // 拷贝完成之后，1st3 包含 1 2 3 4
   copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.begin()));

   当调用 front_inserter(c) 时，我们得到一个插入迭代器，接下来会调用 push_front。当每个元素被插入到容器 c 中时，它变为 c 的新的首元素。因此，front_inserter 生成的迭代器会将插入的元素序列的顺序颠倒过来，而 inserter 和 back_inserter 则不会。

4. 除了 unique 之外，标准库还定义了名为 unique_copy 的函数，它接受第三个迭代器，表示拷贝不重复元素的目的位置。

10.4.2 iostream 迭代器

1. 虽然 iostream 类型不是容器，但标准库定义了可以用于这些 IO 类型对象的迭代器。istream_iterator 读取输入流，ostream_iterator 向一个输出流写数据。这些迭代器将它们对应的流当作一个特定类型的元素序列来处理。通过使用流迭代器，我们可以用泛型算法从流对象读取数据以及向其写入数据。

2. 当创建一个流迭代器时，必须指定迭代器将要读写的对象类型。一个 istream_iterator 使用 >> 来读取流。因此，istream_iterator 要读取的类型必须定义了输入运算符。当创建一个 istream_iterator 时，我们可以将它绑定到一个流。当然，我们还可以默认初始化迭代器，这样就创建了一个可以当作尾后值使用的迭代器。

3. 下面是一个用 istream_iterator 从标准输入读取数据，存入一个 vector 的例子：

   istream_iterator<int> in_iter(cin); // 从 cin 读取 int
   istream_iterator<int> eof;          // istream 尾后迭代器
   while (in_iter != eof)              // 当有数据可供读取时
       // 后置递增运算读取流，返回迭代器的旧值
       // 解引用迭代器，获得从流读取的前一个值
       vec.push_back(*in_iter++);

   对于一个绑定到流的迭代器，一旦其关联的流遇到文件尾或遇到 IO 错误，迭代器的值就与尾后迭代器相等。

4. 通过 istream_iterator 从 cin 中读取数据，并直接构造 vector：

   istream_iterator<int> in_iter(cin), eof; // 从 cin 读取 int
   vector<int> vec(in_iter, eof);           // 从迭代器范围构造 vec

5. istream_iterator 支持的操作：

   istream_iterator 操作
   istream_iterator<T> in(is);	in 从输入流 is 读取类型为 T 的值
   istream_iterator<T> end;	读取类型为 T 的值的 istream_iterator 迭代器，表示尾后位置
   in1 == in2	in1 和 in2 必须读取相同类型。如果它们都是尾后迭代器，或绑定到相同的输入，则两者相等
   in1 != in2
   *in	返回从流中读取的值
   in->mem	与 (*in).mem 的含义相同
   ++in，in++	使用元素类型所定义的 >> 运算符从输入流中读取下一个值。与以往一样，前置版本返回一个指向递增后迭代器的引用，后置版本返回旧值

6. 可以用一对 istream_iterator 来调用 accumulate：

   istream_iterator<int> in(cin), eof;
   cout << accumulate(in, eof, 0) << endl;

7. 当我们将一个 istream_iterator 绑定到一个流时，标准库并不保证迭代器立即从流读取数据。具体实现可以推迟从流中读取数据，直到我们使用迭代器时才真正读取。标准库中的实现所保证的是，在我们第一次解引用迭代器之前，从流中读取数据的操作已经完成了。对于大多数程序来说，立即读取还是推迟读取没什么差别。但是，如果我们创建了一个 istream_iterator，没有使用就销毁了，或者我们正在从两个不同的对象同步读取同一个流，那么何时读取可能就很重要了。

8. 我们可以对任何具有输出运算符（<< 运算符）的类型定义 ostream_iterator。当创建一个 ostream_iterator 时，我们可以提供（可选的）第二参数，它是一个字符串，在输出每个元素后都会打印此字符串。此字符串必须是一个 C 风格字符串（即，一个字符串字面常量或者一个指向以空字符结尾的字符数组的指针）。必须将 ostream_iterator 绑定到一个指定的流，不允许空的或表示尾后位置的 ostream_iterator。

9. ostream_iterator 支持的操作：

   ostream_iterator 操作
   ostream_iterator out(os);	out 将类型为 T 的值写到输出流 os 中
   ostream_iterator out(os, d);	out 将类型为 T 的值写到输出流 os 中，每个值后面都输出一个 d。d 指向一个空字符结尾的字符数组
   out = val	用 << 运算符将 val 写入到 out 所绑定的 ostream 中。val 的类型必须与 out 可写的类型兼容
   *out, ++out, out++	这些运算符是存在的，但不对 out 做任何事情。每个运算符都返回 out

10. 我们可以用 ostream_iterator 来输出值的序列：

    ostream_iterator<int> out_iter(cout, "");
    for (auto e : vec)
        *out_iter++ = e; // 赋值语句实际上将元素写到 cout
    cout << endl;

    此程序将 vec 中的每个元素写到 cout，每个元素后加一个空格。每次向 out_iter 赋值时，写操作就会被提交。值得注意的是，当我们向 out_iter 赋值时，可以忽略解引用和递增运算。即，循环可以重写成下面的样子：

    for (auto e : vec)
        out_iter = e; // 赋值语句将元素写到 cout
    cout << endl;

    运算符 * 和 ++ 实际上对 ostream_iterator 对象不做任何事情，因此忽略它们对我们的程序没有任何影响。但是，推荐第一种形式。在这种写法中，流迭代器的使用与其他迭代器的使用保持一致。如果想将此循环改为操作其他迭代器类型，修改起来非常容易。而且，对于读者来说，此循环的行为也更为清晰。

11. 可以通过调用 copy 来打印 vec 中的元素，这比编写循环更为简单：

    copy(vec.begin(), vec.end(), out_iter);
    cout << endl;

12. 我们可以为任何定义了输入运算符（>>）的类型创建 istream_iterator 对象。类似的，只要类型有输出运算符（<<），我们就可以为其定义 ostream_iterator。

10.4.3 反向迭代器

1. 反向迭代器就是在容器中从尾元素向首元素反向移动的迭代器。对于反向迭代器，递增（以及递减）操作的含义会颠倒过来。递增一个反向迭代器（++it）会移动到前一个元素；递减一个迭代器（--it）会移动到下一个元素。

2. 除了 forward_list 之外，其他容器都支持反向迭代器。我们可以通过调用 rbegin、rend、crbegin 和 crend 成员函数来获得反向迭代器。这些成员函数返回指向容器尾元素和首元素之前一个位置的迭代器。与普通迭代器一样，反向迭代器也有 const 和非 const 版本。

3. 可以通过向 sort 传递一对反向迭代器来将 vector 整理为递减序。

4. 除了 forward_list 之外，标准容器上的其他迭代器都既支持递增运算又支持递减运算。但是，流迭代器不支持递减运算，因为不可能在一个流中反向移动。因此，不可能从一个 forward_list 或一个流迭代器创建反向迭代器。

5. 通过调用 reverse_iterator 的 base 成员函数可以返回其对应的普通迭代器。下图展示了反向迭代器和普通迭代器间的关系：

   

   rcomma 和 rcomma.base() 指向不同的元素，line.crbegin 和 line.cend() 也是如此。这些不同保证了元素范围无论是正向处理还是反向处理都是相同的。

6. Note： 反向迭代器的目的是表示元素范围，而这些范围是不对称的，这导致一个重要的结果：当我们从一个普通迭代器初始化一个反向迭代器，或是给一个反向迭代器赋值时，结果迭代器与原迭代器指向的并不是相同的元素。

10.5 泛型算法结构

10.5.1 5 类迭代器

1. WARNING： 对于向一个算法传递错误类别的迭代器的问题，很多编译器不会给出任何警告或提示。

2. 迭代器有 5 类：

   • 输入迭代器（input iterator）。算法 find 和 accumulate 要求输入迭代器；而 istream_iterator 是一种输入迭代器。
   • 输出迭代器（output iterator）。copy 函数的第三个参数就是输出迭代器。ostream_iterator 类型也是输出迭代器。
   • 前向迭代器（forward iterator）。算法 replace 要求前向迭代器，forward_list 上的迭代器是前向迭代器。
   • 双向迭代器（bidirectional iterator）。算法 reverse 要求双向迭代器，除了 forward_list 之外，其他标准库都提供符合双向迭代器要求的迭代器。
   • 随机访问迭代器（random-access iterator）。算法 sort 要求随机访问迭代器。array、deque、string 和 vector 的迭代器都是随机访问迭代器，用于访问内置数组元素的指针也是。

10.5.2 算法形参模式

1. 大多数算法具有如下 4 种形式之一：

   alg(beg, end, other args);
   alg(beg, end, dest, other args);
   alg(beg, end, beg2, other args);
   alg(beg, end, beg2, end2, other args);

   WARNING： 向输出迭代器写入数据的算法都假定目标空间足够容纳写入的数据。

   如果 dest 是一个直接指向容器的迭代器，那么算法将输出数据写到容器中已存在的元素内。更常见的情况是，dest 被绑定到一个插入迭代器或是一个 ostream_iterator。插入迭代器会将新元素添加到容器中，因而保证空间是足够的。ostream_iterator 会将数据写入到一个输出流，同样不管要写入多少个元素都没有问题。

   WARNING： 接受单独 beg2 的算法假定从 beg2 开始的序列与 beg 和 end 所表示的范围至少一样大。

10.5.3 算法命名规范

1. 接受一个元素值的算法通常有另一个不同名的（不是重载的）版本，该版本接受一个谓词代替元素值。接受谓词参数的算法都有附加的 if 前缀：

   find(beg, end, val);     // 查找输入范围中 val 第一次出现的位置
   find_if(beg, end, pred); // 查找第一个令 pred 为真的元素

   这两个算法都在输入范围中查找特定元素第一次出现的位置。算法 find 查找一个指定值；算法 find_if 查找使得 pred 返回非零值的元素。

2. 默认情况下，重排元素的算法将重排后的元素写回给定的输入序列中。这些算法还提供另一个版本，将元素写到一个指定的输出目的位置。如我们所见，写到额外目的空间的算法都在名字后面附加一个 _copy：

   reverse(beg, end);            // 反转输入范围中元素的顺序
   reverse_copy(beg, end, dest); // 将元素按逆序拷贝到 dest

   一些算法同时提供 _copy 和 _if 版本。这些版本接受一个目的位置迭代器和一个谓词：

   // 从 v1 中删除奇数元素
   remove_if(v1.begin(), v1.end(),
             [](int i)
             { return i % 2; });
   // 将偶数元素从 v1 拷贝到 v2；v1 不变
   remove_copy_if(v1.begin(), v1.end(), back_inserter(v2),
                  [](int i)
                  { return i % 2; });

   两个算法都调用了 lambda 来确定元素是否为奇数。在第一个调用中，我们从输入序列中将奇数元素删除。在第二个调用中，我们将非奇数（亦即偶数）元素从输入范围拷贝到 v2 中。

10.6 特定容器算法

1. list 和 forward_list 定义了独有的 sort、merge、remove、reverse 和 unique。链表类型定义的其他算法的通用版本可以用于链表，但代价太高。这些算法需要交换输入序列中的元素。一个链表可以通过改变元素间的链接而不是真的交换它们的值来快速“交换”元素。因此，这些链表版本的算法的性能比对应的通用版本好得多。

   最佳实践：对于 list 和 forward_list，应该优先使用成员函数版本的算法而不是通用算法。

2. list 和 forward_list 成员函数版本的算法如下表所示，这些操作都返回 void：

   list 和 forward_list 成员函数版本的算法
   lst.merge(lst2)	将来自 lst2 的元素合并入 lst。lst 和 lst2 都必须是有序的。元素将从 lst2 中删除。在合并之后，lst2 变为空。第一个版本使用 < 运算符；第二个版本使用给定的比较操作
   lst.merge(lst2, comp)
   lst.remove(val)	调用 erase 删除掉与给定值相等（==）或令一元谓词为真的每个元素
   lst.remove_if(pred)
   lst.reverse()	反转 lst 中元素的顺序
   lst.sort()	使用 < 或给定比较操作排序元素
   lst.sort(comp)
   lst.unique()	调用 erase 删除同一个值的连续拷贝。第一个版本使用 ==；第二个版本使用给定的二元谓词
   lst.unique(pred)

3. 链表类型还定义了 splice 算法，此算法是链表数据结构所特有的：

   list 和 forward_list 的 splice 成员函数的参数
   lst.splice(args) 或 flst.splice_after(args)
   (p, lst2)	p 是一个指向 lst 中元素的迭代器，或一个指向 flst 首前位置的迭代器。函数将 lst2 的所有元素移动到 lst 中 p 之前的位置或是 flst 中 p 之后的位置。将元素从 lst2 中删除。lst2 的类型必须与 lst 或 flst 相同，且不能是同一个链表
   (p, lst2, p2)	p2 是一个指向 lst2 中位置的有效的迭代器。将 p2 指向的元素移动到 lst 中，或将 p2 之后的元素移动到 flst 中。lst2 可以是与 lst 或 flst 相同的链表
   (p, lst2, b, e)	b 和 e 必须表示 lst2 中的合法范围。将给定范围中的元素从 lst2 移动到 lst 或 flst。lst2 与 lst（或 flst）可以是相同的链表，但 p 不能指向给定范围中元素

4. 链表特有版本与通用版本间的一个至关重要的区别是链表版本会改变底层的容器。例如，remove 的链表版本会删除指定的元素。unique 的链表版本会删除第二个和后继的重复元素。

   类似的，merge 和 splice 会销毁其参数。例如，通用版本的 merge 将合并的序列写到一个给定的目的迭代器；两个输入序列是不变的。而链表版本的 merge 函数会销毁给定的链表———元素从参数指定的链表中删除，被合并到调用 merge 的链表对象中。在 merge 之后，来自两个链表中的元素仍然存在，但它们都已在同一个链表中。

小结

术语表

---