第 10 章 泛型算法
泛型算法 generic algorithm
10.1 概述
大多数算法定义在头文件 algorithm 中。另外在 numeric 种定义了一组数值泛型算法。
一般来说这些算法并不直接操作容器，二十遍历由两个迭代器指定的一个元素范围来进行操作。
10.2 初识泛型算法
10.2.1 只读算法
accumulate(c.cbegin(), c.cend(), init);
操作两个序列的算法
一般操作两个序列的算法，第二个序列只接受一个迭代器时，都假定第二个序列至少和第一个一样长。
equal(vec.cbegin(), vec.cend(), vec2.cbegin());
10.2.2 写容器元素的算法
fill(c.begin(), c.end(), val);
算法不检查写操作
vector<int> vec;
fill_n(vec.begin(), 10, 0);
如上例，fill_n 并不检查是否有足够空间写入 10 个元素，应当由程序员来保证。
介绍 back_inserter
可以使用插入迭代器 insert iterator 来保证有足够空间插入元素。
fill_n(back_inserter(vec), 10, 0);
拷贝算法
auto ret = copy(vec.begin(), vec.end(), vec2.begin());
返回递增之后的迭代器。
replace(vec.begin(), vec.end(), oldVal, newVal);
replace(vec.begin(), vec.end(), back_inserter(vec2), oldVal, mewVal);
10.2.3 重排容器元素的算法
sort
unique
10.3 定制操作
谓词 predicate
一元谓词 unary predicate
二元谓词 binary predicate
10.3.2 lambda 表达式
可以向一个算法传递任何类别的可调用对象 callable object。
lambda 表达式 lambda expression
[capture list](parameter list) -> return type { function body }
10.3.3 lambda 捕获和返回
值捕获
注意捕获发生在 lambda 创建时，而传入参数是调用时。
引用捕获
引用捕获的变量必须保证 lambda 被调用时还是存在的。
[] // 空捕获列表
[names] // 逗号分隔的捕获列表，名字前使用 & 的是引用捕获
[&] // 隐式捕获列表，所有变量采用引用捕获
[=] // 隐式值捕获
[&, identifier_list] // identifier_list 中的变量使用值捕获，
// 其余使用引用捕获
[=, identifier_list] // identifier_list 中的变量使用引用捕获，且不能
// 包含 this
// 其余使用值捕获，且每个变量前必须加 &
可变 lambda
值被拷贝的变量，lambda 不会改变其值。如果我们希望能改变一个被捕获的变量的值，那么需要增加 mutable 关键字。
指定 lambda 返回类型
当 lambda 只有一个返回值时，由于返回值类型是可推断的，可以不指定。
当 lambda 不能推断返回值类型时可以指定返回值类型。
[](int i) -> int { if (i < 0) return -i; else return i; }
10.3.4 参数绑定
如果 lambda 的捕获列表为空，则通常可以用函数代替它。对于有捕获的 lambda 我们可以利用 bind
标准库 bind 函数
auto newCallable = bind(callable, arg_list);
其中 arg list 可能包含形如 _n 的占位符，n 是某个整数，代表 newCallable 的第 n 个参数，下标从 1 开始。因此 newCallable 参数顺序与 callable 无关。
将使用 arg_list 里面的参数调用 callable。
要使用这些占位符需要
using namespace std::placeholders;
绑定引用参数
bind 会拷贝它的参数，但是如果我们希望以引用方式传递则需要 ref() 。
void f(int &a);
int b;
auto ff = bind(f, ref(b));
ref 返回一个对象，包含给定的引用。此外 cref 函数，生成一个保存 const 引用的类。与 bind 一样，这些函数定义在头文件 functional 中。
注意新标准中已经弃用了限制比较大的 bind1st 和 bind2nd 函数。
10.4 再探迭代器
除了每个容器定义的迭代器外，标准库在头文件 iterator 中还定义了额外几种迭代器。
插入迭代器 insert iterator 绑定到容器，向容器插入元素
流迭代器 stream iterator 绑定到输入输出流，用来遍历关联的 IO 流
反向迭代器 reverse iterator 与一般的迭代器移动方向相反
移动迭代器 move iterator 这些迭代器不拷贝其中元素而是移动它们
10.4.1 插入迭代器
it = t; // 向 it 指定的当前位置插入值 t。
*it; ++it; it++; // 操作存在但不会对 it 做任何事。返回 it。
back_inserter; // 使用 push_back
front_inserter; // 使用 push_front
inserter; // 接受两个参数，第一个参数是容器，第二个参数是迭代器，
// 插入到给定迭代器之前
10.4.2 iostream 迭代器
istream_iterator 操作
对于 istream_iterator<T> 需要类型 T 定义 >>
#include <iostream>
#include <iterator>
using namespace std;
int main() {
istream_iterator<int> int_it(cin), int_eof;
while(int_it != int_eof) {
cout << *int_it++ <<endl;
}
return 0;
}
istream_iterator<T> in(is); // in 从输入流 is 读取 T 的值
istream_iterator<T> end; // 尾后迭代器
in1 == in2; // 读取相同类型且
// 同为尾后迭代器或绑定到相同输入
in1 != in2;
*in; // 读取流中的值
in->mem // (*in).mem
++in, in++; // 读取流中的下一个值
当然我们也可以像使用其他迭代器一样使用流迭代器
accumulate(in, eof, 0)
istream_iterator 允许使用懒惰求值
istream_iterator 绑定到流时，标准库并不保证迭代器立即从流读取数据，直到我们使用迭代器时才真正读取。标准库的实现保证的是，第一次解引用迭代器之前，从流中读取数据的操作已经完成了。
ostream_iterator 操作
对于 ostream_iterator<T> 需要类型 T 定义 <<
ostream_iterator<T> out(os);
ostream_iterator<T> out(os,d); // d 是一个 C 风格字符串
// 每次输出都会追加一个 d
out = val; // val 写入绑定的流
*out, ++out, out++; // 存在但无用，返回 out 统一迭代器行为
10.4.3 反向迭代器
反向迭代器 ++ 和 -- 的方向与普通迭代器相反
反向迭代器需要支持递减运算符，因此不能从 forward_list 和流迭代器创建反向迭代器。
反向迭代器和其他迭代器的关系
注意我们不能混用普通迭代器和反向迭代器，我们可以使用 base 函数将反向迭代器转换为普通迭代器
rcomma
v
FIRST,SECOND,THIRD
^
rcomma.base()
注意为了使反向迭代器与普通迭代器表示的范围一致，因此实际指向的位置会不同。
10.5 泛型算法结构
迭代器类别 iterator category
| 迭代器类别 | 操作 |
|---|---|
| 输入迭代器 | 只读，不写；单遍扫描，只能递增 |
| 输出迭代器 | 只写，不读；单遍扫描，只能递增 |
| 前向迭代器 | 可读写；多遍扫描，只能递增 |
| 双向迭代器 | 可读写；多遍扫描，可递增递减 |
| 随机访问迭代器 | 可读写；多遍扫描，支持全部迭代器运算 |
10.5.1 5 类迭代器
C++ 标准指明了泛型和数值算法的每个迭代器参数的最小类别。
对于每个迭代器参数，其能力至少与最小类别相当。
输入迭代器 input iterator：
用于比较两个迭代器的相等和不相等运算符 == !=
用于推进迭代器的前置和后置递增运算 ++
用于读取元素的解引用运算符 * 解引用只能出现在赋值运算符的右侧
箭头运算符 ->
输出迭代器 output iterator：
用于推进迭代器的前置和后置递增运算 ++
用于读取元素的解引用运算符 * 解引用只能出现在赋值运算符的左侧
前向迭代器 forward iterator：
支持所有输入输出迭代器操作，且可以多次读写同一元素。
双向迭代器 bidirectional iterator ：
支持所有前向迭代器的操作，支持前置和后置递减运算符 --
随机访问迭代器 random-access iterator：
支持双向迭代器所有功能，提供常数时间访问序列中任意元素的能力。
用于比较两个迭代器相对位置关系的关系算符 < <= > >=
迭代器和一个整数值的加减运算 + += - -=
两个迭代器上的 -
下标运算符 iter[n]
10.5.2 算法形参模式
大多数算法有如下 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);
dest 一般假定 assume 能够写入足够多的数据。
只有 beg2 （没有 end2）作为输入的算法假定 beg2 开始的范围与 beg end 的范围至少一样大。
10.5.3 算法命名规范
一些算法采用重载形式传递谓词来代替 < 或 ==
unique(beg, end);
unique(beg, end, comp);
有些算法本身会接受一个 val 因此使用谓词的版本会加上 _if
find(beg, end, val);
find_if(beg, end, pred);
有些算法需要区分写回原序列和写到新序列，使用 _copy
reverse(beg, end);
reverse_copy(beg, end, dest);
remove_copy_if(beg, end, dest, pred);
10.6 特定容器算法
对于 list 和 forward_list
lst.merge(lst2);
lst.merge(lst2, comp); // 要求两个链表有序
lst.remove(val);
lst.remove_if(pred);
lst.reverse();
lst.sort();
lst.sort(comp);
lst.unique();
lst.unique(pred);
splice 成员
lst.splice 和 flst.splice_after
(p, lst2) // p 是 lst 的迭代器或 flst 的首前迭代器。将 lst2 元素插入到对应位置。将元素从 lst2 中删除。
(p, lst2, p2) // 将 p2 之后的元素移动插入到 p
(p, lst2, b, e) // 将 [b, e) 中元素移动插入到 p
Next: [模板][计算几何] 平面最近点对