泛型算法概述

算法：一套处理逻辑完成功能。
泛型算法：广泛/宽泛类型的算法，支持多种类型的算法。
这里重点讨论c++标准库中的算法。
本章主要讨论下面3个头文件：<algorithm> 、<numeric> 、 <ranges>

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    std::vector<int> x(100);
    std::sort(std::begin(x), std::end(x)); // sort就是泛型算法
    int y[100];
    std::sort(std::begin(y), std::end(y)); // y和x类型是不同的，但是都可以使用sort

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

为什么要引入泛型算法而不采用方法的形式：
方法和算法的区别，方法借用了java在类里面定义的函数，比如list的sort方法，但是std::sort是定义在库函数中的函数，算法就是我们定义了一段程序，能够实现一定的功能。泛型算法，一般针对不同类型。

int main()
{
    std::vector<int> x(100);
    std::sort(std::begin(x), std::end(x)); // sort就是泛型算法
    x.sort(); // 这个sort就是vector里的一个方法，不是算法
}
1
2
3
4
5
6

内建数据类型不支持方法

int main()
{
    std::vector<int> x(100);
    std::sort(std::begin(x), std::end(x)); // sort就是泛型算法
    int x[100]; // 内建数据类型不支持方法，不能x.sort
}
1
2
3
4
5
6

计算逻辑存在相似性，避免重复定义

std::sort就是一个典型的模版参数，每一种方法都声明了一个模版，不同的类型实例化，编译器会生成不同的模版实例。我们只需要写一个sort逻辑即可。

如何实现支持多种类型：使用迭代器作为算法与数据的桥梁
迭代器一般是模拟数组指针的一些操作。递增，解引用等。指针的功能推而广之就是迭代器。迭代器就是容器和算法的桥梁。通常情况下，算法就是操作一个容器的。



在c++中：泛型算法通常来说都不复杂，但优化足够好
算法越不复杂，越具有广泛性。比如自动驾驶后者语音识别，这样的算法就是很受局限性。但是泛型算法，比如容器中查找元素，将容器中的元素加起来，都是简单的，具有广泛性的算法。

泛型算法c++自己实现的，优化是足够好的。速度快，bug少。所以建议多使用泛型算法，而不是自己手写。

一些泛型算法与方法同名，实现功能类似，此时建议调用方法而非算法
std::find V.S. std::map::find
泛型算法，由于支持多种类型，所以就会有一定的性能损失，为了更加的通用。而方法一般都是针对固定的容器的方法，这样效率更快。

泛型算分类

读算法：accumulate/find/count

读取其中的元素，并进行计算

accumulate：查找一个值，返回累计后的值


find：返回一个迭代器，找到这个值，在区间中的位置。位于first和last之间的一个值。
count：遍历区间，返回要查找的数值的个数

读算法不会修改迭代区间，对于输入，是只读的。

写算法：像一个迭代区间写入元素

单纯写操作：fill


单纯写操作：fill_n


读 + 写操作： transform（注意ppt写错了） / copy

transform：遍历输入区间的每一个元素，进行变换，再将结果写入输出区间。


copy

注意：写算法一定要保证目标区间足够大

排序算法：

改变输入序列中元素的顺序

sort

unique：删除连续相同的元素

泛型算法使用迭代器实现元素访问

迭代器的分类：
输入迭代器：可读，可递增 典型应用为 —— find 算法


输出迭代器：可写，可递增 典型应用为 —— copy 算法


前向迭代器：可读写，可递增 典型应用为 —— replace 算法


双向迭代器：可读写，可递增递减 典型应用为 —— reverse 算法


随机访问迭代器：可读写，可增减一个整数 典型应用为 —— sort 算法

一些算法会根据迭代器类别（PPT勘误）的不同引入相应的优化：如 distance 算法

distance接收2个迭代器，算2个迭代器之间的距离。

泛型算法使用的特殊迭代器

插入迭代器

泛型算法是需要区间的，无论是读也好，写也好，都是需要区间的。
通常我们会使用迭代器来描述这样的区间。比如我们有一个vector的容器，我们用vector.begin()和vector.end()来表示容器的区间，去读写里面的元素。

插入迭代器： back_insert_iterator / front_insert_iterator / insert_iterator




front_insert_iterator

如果要使用相应的插入迭代器，要确保底层的容器支持相应的操作。比如back_insert_iterator需要支持push_back，front_insert_iterator需要支持push_front.

insert_iterator更加一般化的插入迭代器。会调用容器的insert。

流迭代器

流迭代器： istream_iterator



y是缺省的迭代器，x != y。用来表示x的结尾。

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <iterator>
using namespace std;

int main()
{
    std::istringstream str("1 2 3 4 5");
    std::istream_iterator<int> x(str);
    std::istream_iterator<int> y{};
    int res = std::accumulate(x, y, 0);
    cout << res << endl; // 15
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

ostream_iterator：可以进行输出了

反向迭代器

移动迭代器

move_iterator


迭代器与哨兵（ Sentinel ）
哨兵一般标识区间结尾的地方。

泛型算法的并发算法（ C++17 / C++20 ）

std::execution::seq
std::execution::par
std::execution::par_unseq
std::execution::unseq