C++Primer学习笔记10.泛型算法
## 泛型算法### 概述
大多数算法定义在头文件 `algorithm` 中，部分在 `numeric` 中，这些算法不直接操作容器，而是遍历两个迭代器指定的一个元素范围来进行操作。因为没有限定具体的操作元素类型，因此称为泛型算法。
算法不会改变容器的大小。
### 初识泛型算法
标准库提供了超过 100 个算法。
标准库算法都对一个范围内的元素进行操作，此元素范围称为“输入范围”
部分算法从两个序列中读取元素，两个序列不必相同（如 vector 和 list），序列中的元素也不必相同（如 double 和 int），要求是只要能比较两种元素即可。
<b>几种假定</b>
操作两个序列的算法有的接受三个迭代器：前两个表示第一个序列的元素范围，第三个表示第二个序列的元素范围。这种情况假定第二个序列至少与第一个一样长。
向目的位置迭代器写入 n 个数据的算法假定目的位置足够大（大于等于 n）
#### 只读算法
对于只读算法，最好使用 cbegin() 和 cend()。
| 方法 | 说明 |
| ----------------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------- |
| accumulate(vec.cbegin(),vec.cend(),val) | 对输入范围内的元素在 val 的基础上求和。可以对字符串“+”。注意元素是加在 val上，如果元素是 double，val 是 int，和会被转换成 int |
| equal(vec1.cbegin(),vec1,end(),vec2.cbegin()) | 比较两个序列的元素是否全部相等（假定第二个序列至少与第一个序列一样长） |
| find_if(vec.begin(),vec.end(),'一元谓词') | 查找符合某条件的元素，返回迭代器，如果没有就返回尾迭代器 |
#### 写容器元素算法
| 方法 | 说明 |
| -------------------------------------------------- | ------------------------------------------------------------------------------------------------------ |
| fill(vec.begin(),vec.end(),val); | 将 val 赋予输入序列中的每一个元素 |
| fill(vec.begin(),vec.begin() + vec.size()/2,10); | 将一个容器的前一半的值写为10 |
| fill_n(dest,n,val); | 将 val 赋予从 dest 开始的连续 n 个元素。假定 dest 开始的序列有至少 n 个元素 |
| fill_n(vec.begin(),vec.size(),0) | 将 vec 的所有元素重置为0 |
| for_each(vec.begin(),vec.end(),'可调用对象'); | 对输入范围内的每一个元素执行可调用对象的内容。注意：可调用对象是一元谓词，参数类型是迭代器指向的类型 |
<b>插入迭代器</b>
插入迭代器是一种向容器中添加元素的迭代器。
当通过插入迭代器向容器赋值时，一个新的元素被添加到容器中。
函数 back_inserter 定义在头文件 iterator 中。
```cpp
vector<int> vec;
auto it = back_inserter(vec);//it 即为vec新加的插入迭代器
*it = 24;//给 it 赋值后，vec 现在有一个元素为 24
```
可以用 back_inserter() 函数的返回值作为算法的目的位置
```cpp
fill_n(back_inserter(vec),10,0);//添加 10 个元素到 vec
```
<b>拷贝算法</b>
```cpp
//把数组 a1 的内容拷贝给 a2，返回的是目的位置迭代器（递增后）的值
auto ret = copy(begin(a1),end(a1),begin(a2));
//把输入范围内所有值为 0 的元素改为 42
replace(ilst.begin(),ilst.end(),0,42);
//把输入范围内所有值为 0 的元素改为 42 并拷给 dest 开头的序列。
replace_copy(ilst.begin(),ilst.end(),dest,0,42);
```
#### 重排容器算法
消除重复单词，先对容器进行排序（sort 函数），然后使用 unique 函数，将相邻的重复项“消除”，并返回一个指向不重复值范围末尾的迭代器。
```cpp
//默认按字典序从小到达排列输入范围内的元素。重复的元素会相邻
sort(words.begin(),words.end());
// 将重复的元素放到末尾，并且返回第一个重复元素的迭代器。
auto end_unique = unique(words.begin(),words.end());
//删除重复的元素。erase()函数可以接受两个相等的迭代器作为参数。
words.erase(end_unique,words.end());
```
完整的案例
```cpp
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
vector<string> svec{"hello", "world", "hello", "hello", "c++"};
sort(svec.begin(), svec.end());
auto unique_result = unique(svec.begin(), svec.end());
svec.erase(unique_result, svec.end());
for (auto w: svec) cout << w << endl;
return 0;
}
```
### 定制操作
如果算法本身不满足我们的需求，我们可以将自己的需求封装成函数，然后传递给算法，让他按这个需求进行操作 <span style="color:red">==> 定制操作</span>
#### 向算法传递函数
定制操作的过程是向函数传递一个谓词，由这个谓词进行条件判断。比如符合返回 true，不符合返回 false。函数 sort 就可以实现这种定制操作，通过向 sort 传递一个谓词，由谓词进行大小比较的判断。
那什么是谓词？谓词是一个可调用的表达式，返回结果是一个可以作为条件的值，如返回一个 bool 值。
谓词的参数类型必须是元素类型可以转换到的类型。谓词的实参是输入序列的元素（是元素本身不是迭代器）
谓词分为一元谓词和二元谓词，分别接受一个参数和两个参数。不同的标准库算法会接受不同的谓词作为参数。
```cpp
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
// 比价函数，按长度排序
bool isShorter(const string &s1, const string &s2){
return s1.size() < s2.szie();
}
int main() {
vector<string> svec{"hello", "world", "hello", "hello", "c++"};
// 使用 stabl_sort. 稳定的排序。
stable_sort(svec.begin(), svec.end(), isShorter);
for (auto w: svec) cout << w << endl;
return 0;
}
```
#### lambda表达式
根据算法接受一元谓词还是二元谓词，我们传递给算法的谓词必须严格接受一个或两个参数。但是，有时我们希望进行的操作需要更多参数，超出了算法对谓词的限制。
lambda 表达式适合那种只在一两个地方使用的简单操作。
我们可以向一个算法传递任何类别的可调用对象。而一共有四种可调用对象：函数、函数指针、重载了函数调用运算符的类、lambda 表达式。
<b>lambda 的基本使用</b>
<span style="color:red">lambda 表达式组成部分：捕获列表、参数列表、返回类型、函数体。</span>
```cpp
(parameter list)->return type {function body}
```
捕获列表的内容为 lambda 所在函数中定义的<span style="color:orange">局部变量</span>（直接写局部变量的名字即可，通常为空）。捕获列表只用于局部非 static 变量。
参数列表和返回类型都可以省略。如果忽略返回类型，则根据 return 语句推断返回类型（此时函数体必须只有 return 语句）。
```cpp
auto f = [] { return 42; };
cout<< f() <<endl; // 调用 lambda
```
<b>向 lambda 传递参数</b>
```cpp
// 定义一个比较字符串长度的 lambda 表达式
[](const stirng &s1, const string &s2)
{ return s1.size()<s2.size(); }
```
空捕获列表表明此 lambda 不使用它所在函数中的任何局部变量。
自定义字符串的排序规则，字符串越长的越大。
```cpp
#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
void defineSortedRules() {
vector<string> svec = {"hello", "ni", "paidaixing"};
sort(svec.begin(), svec.end()); // 默认字典升序
for (auto const &w: svec)cout << w << endl;
// 返回 true 的为真，默认从 小-->大
// s1 < s2, s1 在前，即 size 小的在前。
auto rules = [](const string &s1, const string &s2) { return s1.size() < s2.size(); };
sort(svec.begin(), svec.end(), rules);
for (auto const &w: svec)cout << w << endl;
}
int main() {
defineSortedRules();
}
```
<b>lambda 的捕获列表</b>
lambda 可以使用那些在捕获列表中指定了的局部遍历。
```cpp
void localVariable() {
int sz = 100;
// 捕获局部遍历 sz 并使用。sz 的传递是值传递。
auto lambda = (const string &s1) {
return s1.size() > sz;
};
cout << lambda("hello") << endl;
}
```
使用捕获列表，捕获局部变量参数，查找容器中第一个长度大于 sz 的元素。注意，此处用的值捕获，在创建 lambda 的一瞬间，lambda 内就保存好了 sz 的副本值 5，即后面可以认为 sz 就是一个固定的值 5。
```cpp
void returnContainerVariable() {
int sz = 5;
auto lambda = (const string &s1) {
return s1.size() > sz;
};
vector<string> svec{"ni", "hao", "kimmis"};
// 拿到指向查找到元素的迭代器指针
auto str = find_if(svec.begin(), svec.end(), lambda);
cout << *str << endl;
}
```
<b>for_each 算法</b>
遍历容器，并使用指定的谓词对遍历的每个元素进行操作。
```cpp
void returnContainerVariable() {
int sz = 5;
auto lambda = (const string &s1) {
return s1.size() > sz;
};
vector<string> svec{"ni", "hao", "kimmis"};
auto str = find_if(svec.begin(), svec.end(), lambda);
cout << *str << endl;
for_each(svec.begin(), svec.end(), (string &str) {
if (str.size() >= sz) {
str.replace(0, 0, "long_str:");
}
cout << str << endl;
});
}
```
<span style="color:red">捕获列表只用于局部非 static 变量， lambda 可以直接使用局部 static 变量和在它所在函数之外声明的名字。为什么？因为局部变量存在静态段，不会因为函数调用完就消失吗？</span>
#### lambda捕获和返回值
lmabda 和普通函数一样，可以进行值捕获和引用捕获，但是在使用引用捕获的时候有诸多注意事项。<span style="color:orange">使用引用捕获时要确保捕获的引用在 lambda 调用时还存在。但是这种往往不好判断，因此尽量不要使用引用捕获。</span>
<b>值捕获的用法</b>
```cpp
int sz = 5;
// 没有引用符号，值捕获。
auto lambda = (const string &s1) {
return s1.size() > sz;
};
```
<b>引用捕获的用法</b>
```cpp
int sz = 5;
// 加了引用符，引用捕获。
auto lambda = [&sz](const string &s1) {
return s1.size() > sz;
};
```
如果我们采用引用方式捕获一个变量，就必须确保被引用的对象在 lambda 执行的时候是存在的。lambda 捕获的都是局部变量，这些变量在函数结束后就不复存在了。如果 lambda 可能在函数结束后执行，捕获的引用指向的局部变量已经消失。
引用捕获存在的必要性：有些数据不允许拷贝构造，此时只能使用引用捕获，如 ostream。我们不能拷贝 ostream 对象，因此捕获 os 的唯一方法就是捕获其引用。
<b>变量捕获的建议</b>
- 尽量采用简单的值捕获。
- 如果我们捕获一个指针或迭代器，或采用引用捕获方式，就必须确保在 lambda 执行时，绑定到迭代器、指针或引用的对象仍然存在。
- 应该尽量减少捕获的数据量，来避免潜在的捕获导致的问题。而且，如果可能的话，应该避免捕获指针或引用。
<b>隐式捕获</b>
除了显式列出我们希望使用的来自所在函数的变量之外，还可以让编译器根据 lambda 体中的代码来推断我们要使用哪些变量。
- [=] 表示，lambda 内部使用的局部变量使用值捕获
- [&] 表示，lambda 内部使用的局部变量使用引用捕获
也可以混合使用显示捕获和隐式捕获。
- [=, &sz]，sz 使用引用捕获，其他的使用值捕获
- [&, sz]，sz 使用值捕获，其他的使用引用捕获
<b>可变 lambda</b>
lambda 不会改变一个值拷贝的变量，如果希望可以改变它，需要在参数列表首加上关键字 mutable。
```cpp
size_t sz = 10;
auto f = () mutable { return ++sz; };
cout<< f() <<endl; // 11
```
<b>返回值</b>
如果 lambda 内部只有 return 语句可以不用指定返回类型，可以自动进行类型推断。如果有其他语句，需要我们显示指定返回类型。
```cpp
void testReturn() {
vector<int> ivec{1, 2, 3, 4, 5, 6};
auto map = [](vector<int> &i) -> vector<int> {
// ele % 2 == 1 则 ele+=1 , 即奇数变偶数
for (auto &ele: i) if (ele % 2) ele += 1;
return i;
};
map(ivec);
for (auto ele: ivec) cout << ele << endl;
}
```
#### 参数绑定
再次强调，lambda 适用于那些简单的操作。
如果 lambda 的捕获列表为空，既可以使用函数也可以使用 lambda。如果捕获列表不为空，使用函数的话需要将使用到的捕获列表的参数传递给函数，要多一个形式参数，而 lambda 则可以直接用捕获列表捕获，然后直接使用，形式参数的数量不用改变。
但是，对于捕获局部变量的 lambda，用函数来替换它就不是那么容易了。例如，我们用在 find_if 调用中的 lambda 比较一个 string 和一个给定大小。我们可以很容易地编写一个完成同样工作的函数
```cpp
// 为函数传递两个参数
bool check_size(const string &s, string::size_type sz){
return s.size() >= sz;
}
```
但是我们不能把这个函数传递给 find_if，因为它接受的是一元谓词，因此传递过去的函数必须是单一形参。如何解决这个问题呢？可以使用 C++ 提供的 bind 函数。
<b>标准库中的 bind 函数</b>
bind 函数位于 functional 头文件中。我们可以将 bind 函数看作一个通用的函数适配器，它接受一个可调用对象，生成一个新的可调用对象来“适应”原对象的参数列表。
```cpp
auto newCallable = bind(callable, arg_list);
```
arg_list 如果是 \_1 \_2 这种表示占位符。下面来看一个具体的例子来理解 arg_list
```cpp
// _1(_ 开头的)表示这是一个占位符，即它需要再传递过去一个实参。
auto check = bind(check_size, _1, 6);
```
此 bind 调用只有一个占位符，表示 check 只接受单一参数。这样就将 check_size 转换为了一个只接收单一实参的函数了。
```cpp
#include <functional>
#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;
void testBind(int sz) {
vector<string> svec{"ni", "hao", "kimmis"};
auto str = find_if(svec.begin(), svec.end(), bind(check_size, std::placeholders::_1, sz));
cout << *str << endl;
}
int main() {
testBind(3);
}
```
这样就解决形参数量的问题。
<b>placeholders 名字</b>
名字_n 都定义在一个名为 placeholders 的命名空间中，而这个命名空间本身定义在 std 命名空间。
对每个占位符名字，我们都必须提供一个单独的 using 声明，很繁琐。我们可以使用另外一种不同形式的 using 语句
```cpp
using namespace namespace_names;
using namespace std::placeholders;
```
这样 placeholders 中定义的所有名字就都可用了。
<b>用 bind 重排参数</b>
我们可以用 bind 修正参数的值。也可以用 bind 调整函数的参数顺序。例如，假定 binds 是一个可调用对象，它有 3 个参数，则下面对 bind 的调用。
```cpp
#include<iostream>
#include<vector>
#include <algorithm>
#include <functional>
using namespace std;
void binds(int a, int b, int c) {
cout << "0:" << a << endl;
cout << "1:" << b << endl;
cout << "2:" << c << endl;
}
void testBinds() {
// _2 表示第二个形式参数
// _1 表示第一个形式参数
auto bds = bind(binds,
0,
std::placeholders::_2,
std::placeholders::_1);
bds(2, 1);
// std::placeholders::_2 对应第二个参数 1
// std::placeholders::_1 对应第一个参数 2
// 最后就是
// binds(0,1,2) 输出 0:0 1:1 2:2
}
/*
0:0
1:1
2:2
*/
```
确实有点绕，，，
<b>bind 绑定引用参数</b>
bind 不能直接绑定引用参数，需要使用 ref
```cpp
ostream &print(ostream &os, const string &s, char c){
return os<< s <<c;
}
// 错误，不能拷贝 os
for_each(words.begin(), words.end(), bind(print, os, _1, ' '));
// 使用标准库 ref 函数
for_each(words.begin(), words.end(), bind(print, ref(os), _1, ' '));
```
<span style="color:orange">函数 ref 返回一个对象，包含给定的引用，此对象是可以拷贝的。标准库中还有一个 cref 函数，生成一个保存 const 引用的类。与 bind 一样，函数 ref 和 cref 也定义在头文件 functional 中。</span>
### 再探迭代器
除了为每个容器定义的迭代器之外，标准库在头文件 iterator 中还定义了额外几种迭代器。
- 插入迭代器（insert iterator）：这些迭代器被绑定到一个容器上，可用来向容器插入元素。
- 流迭代器（stream iterator）：这些迭代器被绑定到输入或输出流上，可用来遍历所关联的 IO 流。
- 反向迭代器（reverse iterator）：这些迭代器向后而不是向前移动。除了 forward_list 之外的标准库容器都有反向迭代器。
- 移动迭代器（move iterator）：这些专用的迭代器不是拷贝其中的元素，而是移动它们。
感觉还用不上，只简单过一遍。
### 泛型算法结构
不同的泛型算法要求迭代器提供功能也不一样。但是算法要求的迭代器操作可以分为 5 个迭代器类别。
| 迭代器类型 | 说明 |
| ---------------- | -------------------------------------- |
| 输入迭代器 | 只读，不写；单遍扫描，只能递增 |
| 输出迭代器 | 只写，不读；单遍扫描，只能递增 |
| 前向迭代器 | 可读写；多遍扫描，只能递增 |
| 双向迭代器 | 可读写；多遍扫描，可递增递减 |
| 随机访问迭代器 | 可读写；多遍扫描，支持全部迭代器运算 |
#### 算法形参模式
在任何其他算法分类之上，还有一组参数规范。通过理解参数的含义，我们可以将注意力集中在算法所做的操作上。大多数算法具有如下4种形式之一
```cpp
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，都是迭代器参数。顾名思义，如果用到了这些迭代器参数，它们分别承担指定目的位置和第二个范围的角色。除了这些迭代器参数，一些算法还接受额外的、非迭代器的特定参数。
#### 算法命名规范
除了参数规范，算法还遵循一套命名和重载规范。这些规范处理诸如：如何提供一个操作代替默认的 < 或 == 运算符以及算法是将输出数据写入输入序列还是一个分离的目的位置等问题。
<b>一些算法使用重载形式传递一个谓词</b>
接受谓词参数来代替 < 或 == 运算符的算法
```cpp
unique(beg, end); // 使用 == 运算符比较原始
unique(beg, end, comp); // 使用 comp 比较元素
```
<b>\_if 版本的算法</b>
接受一个元素值的算法通常有另一个不同名的（不是重载的）版本，该版本接受一个谓词代替元素值。接受谓词参数的算法都有附加的 _if 前缀
<div align="center"><img src="./mdimg/cppprimer/image-20221205175727788.png"></div>
```cpp
find(beg, end, val); // 查找 val 第一次出现位置
find_if(beg, end, pred); // 查找第一个令 pred 为真的元素
```
<b>区分拷贝元素的版本和不拷贝的版本</b>
\_copy 结尾的都是将结果存储在新的内存空间，不会修改原有数据。
<div align="center"><img src="./mdimg/cppprimer/image-20221205175955899.png"></div>
### 特定容器算法
和其他容器不一样，链表类型 list 和 forward_list 定义了几个成员函数形式的算法。它们定义了独有的 sort, merge, remove, reverse 和 unique。
通用版本的 sort 要求随机访问迭代器，而 list 和 forward_list 分别提供双向迭代器和前向迭代器，因此不能用于 list 和 forward_list。
其他链表类型定义的算法的通用版本可以用于链表，但是性能差很多，应该优先使用成员函数版本的算法。
<b>成员函数版本的算法</b>
```cpp
lst.merge(lst2); // 将 lst2 的元素合并入 lst。两者必须都是有序的，合并后 lst2 将变为空。使用 < 比较元素。
lst.merge(lst2,comp); // 上面的 merge 的重载版本，用给定的 comp 代替 <
lst.remove(val); // 调用 erase 删除掉与给定值相等的每个元素。
lst.remove_if(pred); // pred 是个一元谓词，删除掉 lst 中使 pred 为真的每个元素。
lst.reverse(); // 反转 lst 中元素的顺序。
lst.sort(); // 使用 < 给元素排序
lst.sord(comp); // 重载版本
lst.unique(); // 调用 erase 删除同一个值的连续拷贝。
lst.unique(pred); // pred 是个二元谓词，删除使 pred 为真的连续拷贝。
```
<b>splice 算法</b>
链表类型定义了 splice 算法，此算法是链表特有的，没有通用版本。
splice 算法用来在两个链表间移动元素或在一个链表中移动元素的位置。
```cpp
lst.splice(p, lst2); flst.splice_after(p, lst2); // p 是一个指向 lst 中元素的迭代器，或一个指向 flst 首前位置的迭代器。
// 函数将 lst2 中的所有元素移动到 lst 中 p 之前的位置或 flst中 p 之后的位置。
lst.splice(p, lst2, p2); flst.splice_after(p, lst2, p2); // p2 是一个指向 lst2 中位置的迭代器。
// 函数将 p2 指向的元素移动到 lst 中，或将 p2 之后的元素移动到 flst 中,lst2 可以是与 lst 或 flst 相同的链表。
lst.splice(p, lst2, b, e); flst.splice_after (p, lst2, b, e); // b 和 e 表示 lst2 中的合法范围。
// 将给定范围中的元素从 lst2 移动到 lst 中。lst2 可以是与 lst 或 flst 相同的链表，但是 p 不能指向 b 和 e 之间的元素。
```
页:
[1]