第十章 泛型算法

10.1 泛型算法

• 泛型算法本身不直接操作容器，而是遍历两个迭代器指定的一个元素范围来进行操作
• 必要的编程假定：算法（注意是标准库中的算法）永远不会改变底层容器的大小。算法可能改变容器中保存的元素的值，也可能在容器内移动元素，但不能直接添加或者删除元素。

10.2 初识泛型算法

只读算法

• 最好使用cbegin和cend。
• accumulate函数：计算一个序列的和。序列中的元素必须与第三个元素匹配，或者能转换为第三个参数的类型（accumulate函数是模板函数，类型由第三个参数推导而来，此类型决定了使用哪种加法运算符）
• find函数：接受一对迭代器范围和目标查找值，如果找到，则返回对应的迭代器，否则返回尾后迭代器
• find_if函数：接受一对迭代器范围和一个谓词，对范围内的每个元素调用给定谓词进行判断，返回第一个使谓词返回非零的元素，否则返回尾后迭代器。
• find_first_of，输入：两对迭代器标记两段范围，在第一段中找第二段中任意元素，返回第一个匹配的元素，找不到返回第一段的end迭代器。
• equal：确定两个序列是否保存相同的值。（顺序也相同）

写容器元素的算法

• 修改算法
  • fill： fill(vec.begin(), vec.end(), 0);
  • fill_n： fill_n(vec.begin(), len, 0);
  • for_each函数：接受一对迭代器和一个谓词，对范围内的每个元素调用谓词
  • transform函数：接受三个迭代器和一个谓词，前两个迭代器指定一个输入序列的范围，第三个迭代器指定目的位置，它对输入序列中的每个元素调用谓词，并将结果写入到目的位置。
• 拷贝算法
  • copy (src.begin(), src.end(), dst.begin());前两个参数指定输入范围，第三个指向目标序列的起始位置。
  • replace(src.begin(), src.end(), old, new)：将范围内old替换为new
  • replace_copy(src.begin(), src.end(), dst.begin(), old, new)：基本同replace，但是保留原范围不变，将替换后的结果保存到dst位置
  • 很多算法都提供copy版本，不会将新元素放回原序列，而是将结果保存到新序列中

• 重排容器元素的算法

• 排序算法sort：接受两个迭代器，利用元素的<运算符重排元素
• stable_sort
• 消除重复unique：之前要先调用sort，返回的迭代器指向最后一个不重复元素之后的位置（最后一个不重复元素的尾后位置）；重复的元素在原来容器的后边，并没有真正删除。

10.3 定制操作

向算法传递函数

• 谓词（predicate）：是一个可调用的表达式，返回结果是一个能用作条件的值
• 接受谓词参数的算法会对输入序列中的元素调用谓词，因此序列的元素类型必须能转换为谓词的参数类型
• 可以向算法传递四种可调用对象：函数、函数指针、重载了函数调用运算符的类、lambda表达式

lambda表达式

• 形式：[capture list](parameter list) -> return type {function body}。
  • capture list捕获列表是一个由lambda所在函数定义的局部变量的列表（通常为空）。不可忽略。捕获列表只能用于局部非static变量，lambda表达式可以直接使用局部static变量和所在函数之外声明的名字。
  • return type是返回类型。可忽略（省略返回类型时，可以由return返回表达式的类型推断而来，否则返回类型为void），必须使用尾置返回。
  • parameter是参数列表。可忽略（等价于指定空参数列表），不能有默认实参。
  • function body是函数体。不可忽略。
• 定义一个lambda表达式时，编译器生成一个与lambda对应的未命名的类类型
  • 当向函数传递一个lambda时，传递的参数实际上就是这个未命名类的对象。
  • [[ch14-重载运算与类型转换#lambda是函数对象|lambda是函数对象]]

lambda捕获和返回

• 捕获：lambda表达式将局部变量包含在捕获列表中，在捕获列表中的参数可以被lambda函数体所使用，lambda 捕获列表
  • 值捕获：被值捕获的变量的值是在lambda创建时拷贝，而非调用时拷贝。因此在lambda创建后改变被捕获的变量不会影响lambda中对应的值。
  • 引用捕获：捕获的变量前加&，此时修改局部变量会影响lambda内对应的值，但是必须确保被引用的对象在 lambda 执行时是存在的。
• 隐式捕获：不显式列出捕获变量，而是编译器进行推断
  • &为引用捕获，=为值捕获
• 混合显式捕获与隐式捕获
  • 此时捕获列表第一个元素必须是&或=，指定默认捕获方式，显式捕获的变量必须使用与隐式捕获不同的方式
• 可变lambda：默认情况下，通过值捕获得到的变量（的拷贝），lambda无法修改其值，如果希望改变，可以在参数列表后加上mutable
  • 通过引用捕获的变量，取决于变量是否为const
• 如果lambda中除了return还有其他语句，此时应该指明返回类型；否则可以省略返回类型
• lambda可以作为函数的返回值，此时lambda不能包含引用捕获。

  1 2 3 4 5 6

  int a = 1, b = 2, c = 4; auto g = [=, &b] (int c) -> void {b+=c; cout<<a<<endl;}; // 隐式的值捕获(a),显式的引用捕获(b) auto f = [&, b] (int c) -> void {a+=c;}; // 隐式的引用捕获(a),显式的值捕获(b) auto gg = [=, &b] (int c) mutable -> void {b+=c; a+=c; cout<<a<<endl;}; auto ff = [&, b] (int c) mutable -> void {b+=c; cout<<b<<endl;};

参数绑定

• 例子：找到vector中第一个大于val的元素，即需要将二元谓词包装成一元谓词，可以使用bind绑定第二个参数

  1 2 3 4 5

  bool isBigger(int a, int val) {return a > val} vector<int> v{1,2,4,5}; int val = 3; vector<int>::iterator it = find_if(v.begin(), v.end(), isBigger); // 错误，find_if只能接受一元谓词，但是isBigger是二元谓词，可以使用bind进行参数绑定 vector<int>::iterator it = find_if(v.begin(), v.end(), bind(isBigger, val, std::placeholders::_1)); vector<int>::iterator iter = find_if(v.begin(), v.end(), [val] (int a) -> bool {return a<val;}; // 可以使用lambda表达式

• 标准库bind函数：auto newCallable = bind(callable, arg_list);
  • 定义在头文件functional中，接受一个可调用对象和一些实参，生成一个新的可调用对象
  • 我们在调用newCallable的时候，newCallable会调用callable并传递给它arg_list中的参数（将绑定的参数拷贝过去）。
• 参数绑定和重排：std::placeholder::_n表示将newCallable的第n个参数放在占位符_n的位置
• 绑定引用参数：
  • ref函数接受一个参数，返回一个可以拷贝的对象，该对象含有参数的引用。
  • cref返回const的引用

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void show(int a, int b, int c, int d, int e) {cout<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<e<<endl;}
void out(ostream &os, int a, int b, int c, int d, int e) {os<<a<<" "<<b<<" "<<c<<" "<<d<<" "<<e<<endl;}

int a = 1, b = 2, c = 3, d = 4, e = 5;
auto g = bind(show, a, b, placeholders::_2, d, placeholders::_1); // 将g的第一个参数放到placeholders::_1的位置
auto h = bind(show, a, b, placeholders::_1, d, placeholders::_2); // 重排参数顺序
g(e, c); // 将e放到placeholders::_1的位置，将c放到placeholders::_2的位置
h(e, c); // show(a, b, _1, d, _2), 其中_1是e，_2是c

ostream& os = cout;
auto f = bind(out, ref(os), a, b, placeholders::_2, d, placeholders::_1); // 绑定引用参数
f(e, c);    

10.4 再探迭代器

插入迭代器

• 插入器是一种迭代器适配器，接受一个容器，生成一个迭代器，能实现向给定容器添加元素，定义在头文件iterator中
  • back_inserter：创建一个调用push_back操作的迭代器。
    • back_inserter是插入器，back_insert_iterator<vector<int>>是插入迭代器类型
  • front_inserter创建一个调用push_front操作的迭代器。
  • inserter创建一个调用insert操作的迭代器。接受第二个参数，即一个指向给定容器的迭代器，元素会被插入到迭代器所指向的元素之前。
    • 随着插入过程，inserter永远指向指定的元素，而不是永远指向某个特定的位置
• 每向插入器赋值一次就相当于调用一次相关操作，*it, ++it, it++等操作虽然存在，但不会有任何作用（仍返回it）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

deque<int> v{1, 2, 3, 4, 5};
back_insert_iterator<deque<int>> biter = back_inserter(v); // 相当于永远指向尾后位置
front_insert_iterator<deque<int>> fiter = front_inserter(v);

// 每赋值一次就相当于调用一次相关操作
biter = 6; 
biter = 7;
fiter = 0;
fiter = -1;

for_each(v.begin(), v.end(), [] (int i) -> void {cout<<i<<" ";});  

流迭代器

• 流迭代器将对应的流当作一个特定类型的元素序列来处理
  • istream_iterator：读取输入流
    • 可以不绑定到流，相当于尾后迭代器
    • istream_iterator 操作：没有赋值操作，解引用操作相当于返回输入流中读取的值，需要递增操作
    • istream_iterator允许使用懒惰求值，即标准库不保证迭代器可以立即从输入流中获取数据，但是保证迭代器第一次解引用操作之前，从流中读取数据的操作已经完成。
  • ostream_iterator：向输出流中写入数据
    • ostream_iterator必须绑定到一个指定的流，不允许空的或者尾后位置
    • ostream_iterator 操作：赋值操作相当于输出流的输出操作，递增、解引用操作没有意义
    • 向ostream_iterator赋值时，可以省略解引用和递增运算（实际上解引用和递增操作不会对ostream_iterator做任何事情）。但是不推荐省略，可以保持迭代器行为的一致性，便于修改。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  istream_iterator<int> int_iter(cin); // 可以将流迭代器绑定到一个流（输入流读取操作 就相当于 从流迭代器中取出值，流迭代器累加）， istream_iterator<int> int_eof; // 默认初始化相当于尾后迭代器或eof ostream_iterator<int> out_iter(cout, " "); // 必须将ostream_iterator绑定到一个指定的流, 每个值后面跟着一个C风格字符串str // 原始方式，注意输入时Ctrl+Z表示eof // vector<int> v; // for(; int_iter != int_eof; ++int_iter){ // v.push_back(*int_iter); // } vector<int> v(int_iter, int_eof); // 等价方式，更能体现流迭代器的特点 // for(int i: v){ // *(out_iter++) = i; // 原始方式（先后置递增，返回旧值，再解引用），但是更推荐 // // out_iter = i; // 等价方式，更简略 // } copy(v.begin(), v.end(), out_iter); // 最简单的写法，将序列范围直接复制到输出迭代器中 // copy(int_iter, int_eof, out_iter); // 直接将输入进行输出

反向迭代器

• 递增会移动到前一个元素
• 调用反向迭代器的base函数可以获得其对应的正向迭代器
  • rbegin()指向的是最后一个元素，而end()指向的是尾后元素；对应的，【反向迭代器】与【其调用base函数得到的正向迭代器】的关系类似于rbegin()与end()，指向的不是相同元素。图示

    1 2 3 4 5

    vector<int> v{1, 2, 3, 4, 5}; vector<int>::reverse_iterator riter = v.rbegin(); // 5 vector<int>::iterator iter = v.end(); // 尾后位置 cout<<*riter<<" "<<*(--iter)<<endl; // 5 5 cout<<*(++riter)<<" "<<*riter.base()<<endl; // 4 5

移动迭代器

10.5 泛型算法结构

5类迭代器

• 算法所要求的迭代器操作可以分为 5 类，C++ 标准指明了泛型算法的每个迭代器参数的最小类别。
• vector<int>::iterator迭代器是随机访问迭代器，list<int>::iteraotr迭代器是双向迭代器

算法的形参模式

• alg(beg, end, other args);
• alg(beg, end, dest, other args);
• alg(beg, end, beg2, other args);
• alg(beg, end, beg2, end2, other args); 其中，alg是算法名称，beg和end表示算法所操作的输入范围。dest表示输出范围或输出流迭代器，beg2、end2表示第二个输入范围

算法命名规范

• 一些算法使用重载形式传递一个谓词，来代替<或==，比如sort
• 接受谓词参数的算法都有附加的_if后缀，没有的一般都是接受元素值
• 将执行结果写入额外目的空间的算法都有_copy后缀（即拷贝版本）

10.6 特定容器算法

• 对于list和forward_list，优先使用【成员函数版本的算法】而不是通用算法。
• list和forward_list成员函数版本的算法：

• 上面的操作都返回void
• 链表特有版本的算法操作会改变底层容器
  • list和forward_list的splice函数可以进行容器合并，使用lst.splice(args)或flst.splice_after(args)