第10章 泛型算法

泛型算法

因为它们实现共同的操作，所以称之为“算法”；而“泛型”指的是它们可以操作在多种容器类型上。
算法通过在迭代器上进行操作来实现类型无关。
泛型算法本身不执行容器操作，只是单独依赖迭代器和迭代器操作实现。
头文件： #include <algorithm>或者 #include <numeric>(算数相关)
大多数算法是通过遍历两个迭代器标记的一段元素来实现其功能。
必要的编程假定：算法永远不会改变底层容器的大小。算法可能改变容器中保存的元素的值，也可能在容器内移动元素，但不能直接添加或者删除元素。

标准库定义了一类特殊的迭代器，称为插入器（inserter）。
当一个算法操作这样一个迭代器时，迭代器可以完成向容器添加元素的操作，但算法自身永远不会做这样的操作。

find

vector<int>::const_iterator result = find(vec.begin(), vec.end(), search_value);
输入：两个标记范围的迭代器和目标查找值。返回：如果找到，返回对应的迭代器，否则返回第二个参数，即标记结尾的迭代器。

初识泛型算法

标准库提供了超过100个算法，但这些算法有一致的结构。
理解算法的最基本的方法是了解它们是否读取元素、改变元素、重排元素顺序。

只读算法

只读取范围中的元素，不改变元素。
如 find和 accumulate（在numeric中定义，求和）。

int sum = accumulate(vec.cbegin(), vec.cend(), 0) 注意第3个参数决定了函数使用哪个加法运算符以及返回值的类型。

要求序列中的元素必须和第三个参数匹配，或者能转换成第三个参数的类型。

比如：string sum = accumulate(v.cbegin(), v.cend(), "") 是错误的，因为const char* 并没有定义+运算符，此调用将会产生编译错误。需要把"“换为string(”")。
find_first_of，输入：两对迭代器标记两段范围，在第一段中找第二段中任意元素，返回第一个匹配的元素，找不到返回第一段的end迭代器。
通常最好使用cbegin和cend。
equal：确定两个序列是否保存相同的值。

equal(roster1.cbegin(), roster1.cend(), roster2.cbegin())
其中roster2的元素数目至少和roster1一样多
由于equal使用迭代器完成操作，元素类型不必一样，只要我们能使用==比较两个元素类型是否一致即可。

练习10.4

Q：假定 v 是一个vector<double>，那么调用 accumulate(v.cbegin(),v.cend(),0) 有何错误（如果存在的话）？
A：元素将被转为int后再执行+

练习10.5

Q：在本节对名册（roster）调用equal的例子中，如果两个名册中保存的都是C风格字符串而不是string，会发生什么？

A：C风格字符串是用指向字符的指针表示的，因此会比较两个指针的值（地址），而不会比较这两个字符串的内容。

写容器元素的算法

一些算法将新值赋予序列中的元素。
算法不检查写操作。
fill： fill(vec.begin(), vec.end(), 0); 将每个元素重置为0。
fill_n： fill_n(vec.begin(), 10, 0); 假定目的位置足够大，能容纳写入的元素。

注意：算法永远不会改变底层容器的大小，不能添加或删除元素。

一个初学者非常容易犯的错误是在一个空容器上调用 fill_n（或类似的写元素操作），这条语句的结果是未定义的。

注意：泛型算法对容器要的要求并非是足够的空间，而是足够的元素。
使用reserve()只是分配空间，并未添加元素，而算法不能添加元素，所以要改为在resize()后才能添加元素。
插入迭代器back_inserter：
- 用来确保算法有足够的空间存储数据。
- #include <iterator>
- back_inserter(vec) 返回与容器绑定的插入迭代器
拷贝算法copy
- 输入：前两个参数指定输入范围，第三个指向目标序列。
- copy(ilst.begin(), ilst.end(), back_inserter(ivec));
- 必须保证目标目的序列至少要包含与输入序列一样多的元素。
- 返回的是目的位置迭代器（递增后）的值
多个算法提供”拷贝“版本，会创建一个新序列保存结果
replace(ilst.begin(), ilst.end(), 0, 42) 序列汇总0都替换为42
replace_copy(ilst.cbegin(), ilst.cend(), back_insecter(ivec), 0, 42) 第3个参数指出调整后序列的保存位置。

练习10.7

Q：下面程序是否有错误？如果有，请改正：

(a) vector<int> vec; list<int> lst; int i;
	while (cin >> i)
		lst.push_back(i);
	copy(lst.cbegin(), lst.cend(), vec.begin());
(b) vector<int> vec;
	vec.reserve(10);
	fill_n(vec.begin(), 10, 0);

A: (a) 应该加一条语句 vec.resize(lst.size()) 。copy时必须保证目标目的序列至少要包含与输入序列一样多的元素。
(b) reserve分配了足够的空间，但是不会创建新元素。算法可能改变容器中保存的元素的值，也可能在容器内移动元素，永远不会直接添加和删除元素，所以此处应该改为resize(10)。

重排容器元素的算法

这些算法会重排容器中元素的顺序。
排序算法sort：
- 接受两个迭代器，表示要排序的元素范围。
消除重复unique：
- 要先调用sort。
- 返回的迭代器指向最后一个不重复元素之后的位置。
- 顺序会变，重复的元素被“删除”。
- 并没有真正删除，标准库算法是对迭代器操作而非容器，只有容器操作才能删除元素。
  1
  2
  sort(words.begin(), words.end());
  words.erase(unique(words.begin(), words.end()), words.end());

练习10.10

Q：你认为算法不改变容器大小的原因是什么？

A：

算法根本不知道容器的存在，它与容器的成员函数是分开的
算法操作的是迭代器

定制操作

向算法传递函数

谓词（predicate）：
- 是一个可调用的表达式，返回结果是一个能用作条件的值
- 一元谓词：接受一个参数
- 二元谓词：接受两个参数
例子：
- stable_sort：
  - 排序算法的稳定性：保留相等元素的原始相对位置。
  - stable_sort(words.begin(), words.end(), isShorter);

lambda表达式

有时可能希望操作可以接受更多的参数。
lambda表达式表示一个可调用的代码单元，可以理解成是一个未命名的内联函数。
目前已经学过4种可调用对象：
- 函数
- 函数指针
- 冲在了函数调用符的类
- lambda表达式
形式：[capture list](parameter list) -> return type {function body}。
- 其中capture list捕获列表是一个lambda所在函数定义的局部变量的列表（通常为空）。不可忽略。
- return type是返回类型，必须尾置。可忽略，但最好不要忽略：如果函数体非只有一条语句，就不能判断返回类型，会默认返回void。
- parameter是参数列表。可忽略。
- function body是函数体。不可忽略。
- auto f = [] {return 42;}
lambda不能有默认参数。
一个lambda只有在其捕获列表中捕获一个它所在函数中的局部变量，才能在函数体中使用该变量。
捕获列表只用于局部非static变量，lambda可以直接使用局部static变量和它所在函数之外声明的名字。
例子：
- find_if:
  - 接受一对表示范围的迭代器和一个谓词，用来查找第一个满足特定要求的元素。返回第一个使谓词返回非0值的元素。
  - auto wc = find_if(words.begin(), words.end(), [sz](const string &a){return a.size() >= sz;});
- for_each：
  - 接受一个可调用对象，并对序列中每个元素调用此对象。
  - for_each(wc, words.end(), [](const string &s){cout << s << " ";})

lambda捕获和返回

定义lambda时会生成一个新的类类型和该类型的一个对象。
默认情况下，从lambda生成的类都包含一个对应该lambda所捕获的变量的数据成员，在lambda对象创建时被初始化。
值捕获：前提是变量可以拷贝，size_t v1 = 42; auto f = [v1] {return v1;};。
引用捕获：必须保证在lambda执行时，变量是存在的，auto f2 = [&v1] {return v1;};

尽量减少捕获的数据量，尽可能避免捕获指针或引用。
隐式捕获：让编译器推断捕获列表，在捕获列表中写一个&（引用方式）或=（值方式）：auto f3 = [=] {return v1;}

lambda捕获列表：

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

可变lambda：若希望能改变一个被捕获的变量的值，则必须在参数列表后加上关键词mutable，如auto f = [v1] () mutable {return ++v1;}。

指定lambda返回类型：默认情况下，如果一个lambda体包含return以外的任何语句，则编译器假定此lambda返回void。

// 错误: 不能推断lambda的返回类型
transform(vi.begin(), vi.end(), vi.begin(),
          [] (int i) {if (i < 0) return -i; else return i;});
          
// 正确: 使用了尾置返回类型
transform(vi.begin(), vi.end(), vi.begin(),
         [] (int i) -> int {if (i < 0) return -i; else return i;});

// 正确: 只有一条return, 无需指定返回类型, 可根据条件运算符类型推断出
transform(vi.begin(), vi.end(), vi.begin(),
         [] (int i) {return i < 0 ? -1 : i;});

练习10.21

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

A：

// capture list 就算没有也不可省
// parameter list 可省
// return type 可省, 但是func body非只有一条return, 必须尾置指定
auto f = [&i]() -> bool {
  if (i > 0) {
    --i;
    return false;
  } else {
    return true;
  }
};

参数绑定

lambda表达式更适合在一两个地方使用的简单操作；如果需要在很多地方使用相同的操作，或者一个操作需要很多语句才能完成，还是需要定义函数（参数绑定的背景）。
函数如何包装成一元谓词？使用参数绑定。

标准库bind函数：

定义在头文件functional中，可以看做为一个通用的函数适配器。
auto newCallable = bind(callable, arg_list);
我们再调用newCallable的时候，newCallable会调用callable并传递给它arg_list中的参数。
_n代表第n个位置的参数。定义在placeholders的命名空间中。using std::placeholder::_1;
auto g = bind(f, a, b, _2, c, _1);，调用g(_1, _2)实际上调用f(a, b, _2, c, _1) （从1而非0开始）

非占位符的参数要使用引用传参，必须使用标准库ref函数或者cref函数，需要#include <functional> 。

// lambda version
for_each(words.begin(), words.end(),
        [&os, c](const string &s) { os << s << c; });

// bind version
ostream &print(ostream &os, const string &s, char c) {
    return os << s << c;
}
for_each(words.begin(), words.end(), bind(print, ref(os), _1, ' '));

bind1st和bind2nd类似bind，也是接受一个函数作为参数生成一个新的可调用对象，该对象调用给定函数，并将绑定的参数传递给它。但是分别只能绑定第一个或第二个参数，已被弃用（deprecated)。

再探迭代器

标准库在头文件iterator中还定义了额外几种迭代器。

插入迭代器（insert iterator）
流迭代器（stream iterator）
反向迭代器（reverse iterator）
移动迭代器（move iterator）

插入迭代器

插入器是一种迭代器适配器，接受一个容器，生成一个迭代器，能实现向给定容器添加元素。

三种类型：

back_inserter：创建一个使用push_back的迭代器。
front_inserter创建一个使用push_front的迭代器。
只有在容器支持 push_front 的情况下，才可以使用 front_inserter。
当使用 front_inserter 时，元素总是插入到容器第一个元素之前。

inserter创建一个使用insert的迭代器。接受第二个参数，即一个指向给定容器的迭代器，元素会被插到迭代器所指向的元素之前。

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

插入迭代器操作：

操作	解释
`it=t`	在`it`指定的当前位置插入值`t`。假定`c`是`it`绑定的容器，依赖于插入迭代器的不同种类，此赋值会分别调用`c.push_back(t)`、`c.push_front(t)`、`c.insert(t, p)`，其中`p`是传递给`inserter`的迭代器位置
`*it, ++it, it++`	这些操作虽然存在，但不会对`it`做任何事情，每个操作都返回`it`

iostream迭代器（速读）

迭代器可与输入或输出流绑定在一起，用于迭代遍历所关联的 IO 流。
通过使用流迭代器，我们可以用泛型算法从流对象中读取数据以及向其写入数据。

// note1: 
*in_iter++;  // 返回旧值，迭代器前进
// ++优先级与*同，但略高，但后置++返回的是旧值

istream_iterator<int> in_iter(cin);  // 从cin读取int
istream_iterator<int> eof;  // 默认初始化迭代器，可作为尾后值迭代器
vector<int> vec(in_iter, eof);  // 从迭代器范围构造vec

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++`	使用元素类型所定义的`>>`运算符从流中读取下一个值。前置版本返回一个指向递增后迭代器的引用，后置版本返回旧值。

ostream_iterator的操作：

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

练习10.30

Q: 使用流迭代器、sort 和 copy 从标准输入读取一个整数序列，将其排序，并将结果写到标准输出。

int main() {
	vector<int> v;
	istream_iterator<int> int_it(cin), int_eof;

	copy(int_it, int_eof, back_inserter(v));  // 尾后插入迭代器
	sort(v.begin(), v.end());

	copy(v.begin(), v.end(), ostream_iterator<int>(cout," "));
	cout << endl;
	return 0;
}

反向迭代器

反向迭代器就是在容器中从尾元素向首元素反向移动的迭代器。
对于反向迭代器，递增和递减的操作含义会颠倒。
实现向后遍历，配合rbegin和rend。
可以通过向 sort 传递一对反向迭代器来将 vector 整理为递减顺序。
当从一个普通迭代器初始化一个反向迭代器，或给一个反向迭代器复制时，结果迭代器和原迭代器指向的并非相同元素。

泛型算法结构

任何算法最基本的特征是它要求其迭代器提供哪些操作。

5类迭代器

除了输出迭代器外，一个高层类别的迭代器支持低层类别迭代器的所有操作。

C++标准指明了泛型和数值算法的每个迭代器参数的最小类别。比如replace需要一对迭代器，至少是前向迭代器（需要能对序列执行多遍扫描）。

迭代器类别	解释	支持的操作
输入迭代器	只读，不写；单遍扫描，只能递增	`==`,`!=`,`++`,`*`,`->`
输出迭代器	只写，不读；单遍扫描，只能递增	`++`,`*`
前向迭代器	可读写；多遍扫描，只能递增	`==`,`!=`,`++`,`*`,`->`
双向迭代器	可读写；多遍扫描，可递增递减	`==`,`!=`,`++`,`--`,`*`,`->`
随机访问迭代器	可读写，多遍扫描，支持全部迭代器运算	`==`,`!=`,`<`,`<=`,`>`,`>=`,`++`,`--`,`+`,`+=`,`-`,`-=`,``,`->`,`iter[n]`==`(iter[n])`

练习10.40

Q: 你认为 copy 要求哪类迭代器？reverse 和 unique 呢？

copy 需要两个输入迭代器，一个输出迭代器
reverse 需要双向迭代器
unique需要随机访问迭代器

算法的形参模式

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都是迭代器参数，是否使用要依赖于执行的操作。

算法命名规范

一些算法使用重载形式传递一个谓词。
比如unique(beg, end); 和 unique(beg, end, comp);
接受一个元素值的算法通常有一个不同名的版本：加_if，接受一个谓词代替元素值。
比如unique(beg, end)和unique(beg, end, comp);
区分拷贝元素的版本和不拷贝的版本：拷贝版本通常加_copy。
比如reverse_copy(beg, end, dest);
一些算法同时提供了_copy和_if版本，这些版本接受一个目标位置迭代器和一个谓词。

特定容器算法

对于list和forward_list，优先使用成员函数版本的算法而不是通用算法。
- 对于通用版本的sort，由于要求随机访问迭代器，因此不能使用。
- 其他算法的通用版本可以用，但是代价太高：需要交换序列中的元素。
  链表可以通过改变元素间的链接而非真的交换它们的值来快速”快速“交换元素。

list 和 forward_list 成员函数版本的算法：

通用算法不能改变底层容器
链表特有版本与通用版本相似，但一个至关重要的区别是其会改变底层的容器。

操作	解释
`lst.merge(lst2)`	将来自`lst2`的元素合并入`lst`，二者都必须是有序的，元素将从`lst2`中删除。使用<运算符。
`lst.merge(lst2, comp)`	同上，给定比较操作。
`lst.remove(val)`	调用`erase`删除掉与给定值相等(==)的每个元素
`lst.remove_if(pred)`	调用`erase`删除掉令一元谓词为真的每个元素
`lst.reverse()`	反转`lst`中元素的顺序
`lst.sort()`	使用`<`排序元素
`lst.sort(comp)`	使用给定比较操作排序元素
`lst.unique()`	调用`erase`删除同一个值的连续拷贝。使用`==`。
`lst.unique(pred)`	调用`erase`删除同一个值的连续拷贝。使用给定的二元谓词。

上面的操作都返回void

list和forward_list的splice成员函数版本的参数：

参数	解释
`(p, lst2)`	`p`是一个指向`lst`中元素的迭代器，或者一个指向`flst`首前位置的迭代器。函数将`lst2`中的所有元素移动到`lst`中`p`之前的位置或是`flst`中`p`之后的位置。将元素从`lst2`中删除。`lst2`的类型必须和`lst`相同，而且不能是同一个链表。
`(p, lst2, p2)`	同上，`p2`是一个指向`lst2`中位置的有效的迭代器，将`p2`指向的元素移动到`lst`中，或将`p2`之后的元素移动到`flst`中。`lst2`可以是于`lst`或`flst`相同的链表。
`(p, lst2, b, e)`	`b`和`e`表示`lst2`中的合法范围。将给定范围中的元素从`lst2`移动到`lst`或`first`中。`lst2`与`lst`可以使相同的链表，但`p`不能指向给定范围中的元素。

使用lst.splice(args)或flst.splice_after(args)

练习10.42

Q: 使用 list 代替 vector 重新实现10.2.3节中的去除重复单词的程序。

void elimDups(list<string> &words) {
	words.sort();
	words.unique();
}

int main() {
	list<string> l = { "aa", "aa", "aa", "aa", "aasss", "aa" };
	elimDups(l);
	for (const auto& e : l)
		std::cout << e << " ";
	std::cout << std::endl;
}