STL 算法分类：
| 类别 | 常见算法 | 作用 |
|---|---|---|
| 排序 | sort、stable_sort、partial_sort、nth_element等 |
排序 |
| 搜索 | find、find_if、count、count_if、binary_search等 |
查找元素 |
| 修改 | copy、replace、replace_if、swap、fill等 |
修改容器内容 |
| 删除 | remove、remove_if、unique等 |
删除元素 |
| 归约 | for_each、accumulate等 |
处理数据 |
| 合并 | merge、set_union、set_intersection等 |
处理有序序列 |
| 排列组合 | next_permutation、prev_permutation等 |
生成排列 |
| 堆操作 | push_heap、pop_heap、make_heap、sort_heap等 |
处理堆 |
STL 归约算法
STL 中的归约算法（Reduction Algorithms）主要用于从一个容器或范围中计算一个单一的结果，例如对所有元素进行累加、求最小值、求最大值等。
归约算法常见的包括 accumulate、inner_product、partial_sum 等，它们通常涉及到对容器中元素的聚合、计算或比较。
| 算法名称 | 功能描述 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|---|
accumulate |
累加容器中的元素，支持自定义操作 | O(n) | O(1) | 对容器进行累加或其他二元操作 |
reduce |
并行化版本的accumulate（C++17） |
O(n) | O(1) | 与 accumulate 类似 |
for_each |
对范围内每个元素执行一个函数 | O(n) | O(1) | 对容器中的每个元素执行某种操作 |
max_element |
返回容器中最大元素的迭代器 | O(n) | O(1) | 查找容器中的最大元素 |
min_element |
返回容器中最小元素的迭代器 | O(n) | O(1) | 查找容器中的最小元素 |
inner_product |
计算两个容器元素的内积或加权和 | O(n) | O(1) | 计算两个向量的点积或加权和 |
partial_sum |
计算部分和，将容器中的每个元素累加到结果容器中 | O(n) | O(n) | 计算前缀和或部分和 |
adjacent_difference |
计算相邻元素的差值，并将结果存储到新容器中 | O(n) | O(n) | 计算相邻元素的差值 |
（1）accumulate
- 功能：从容器的起始位置开始，对容器中的每个元素进行累加，得到最终的结果。它还支持自定义的二元操作（比如乘法、最大值等）。
- 时间复杂度：O(n)，其中
n是容器的元素数量。 - 空间复杂度：O(1)，原地操作。
示例：
#include <iostream>
using namespace std;
#include <vector>
#include <numeric> // accumulate
int main() {
vector<int> vec = { 1, 2, 3, 4, 5 };
// 累加所有元素的和
int sum = accumulate(vec.begin(), vec.end(), 0); // 初始值为0
cout << "Sum: " << sum << endl; // 输出：Sum: 15
// 使用自定义操作（乘法）
int product = accumulate(vec.begin(), vec.end(), 1, multiplies<int>());
cout << "Product: " << product << endl; // 输出：Product: 120
system("pause");
return 0;
}
注意：
accumulate适用于，当需要对容器中的元素进行累加或执行其他二元操作时。
（2）reduce（C++17）
- 作用：与
accumulate类似，但允许并行计算（并行化需与<execution>配合）。 - 时间复杂度：O(n)，其中
n是容器的元素数量。 - 空间复杂度：O(1)，原地操作。
示例：
#include <iostream>
using namespace std;
#include <vector>
#include <numeric> // reduce
int main() {
vector<int> v = { 1, 2, 3, 4 };
int sum = reduce(v.begin(), v.end()); // 累加和
cout << "Sum with reduce: " << sum << endl;
system("pause");
return 0;
}
注意：
reduce在普通使用下与accumulate类似。
（3）for_each
- 作用：对每个元素执行某个操作。
- 时间复杂度：O(n)，其中
n是容器的元素数量。 - 空间复杂度：O(1)，原地操作。
示例：
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm> // for_each
int main() {
vector<int> v = { 1, 2, 3 };
for_each(v.begin(), v.end(), [](int& x) { x *= 2;});
for (int val : v)
{
cout << val << " "; // Output: 2 4 6
}
cout << endl;
system("pause");
return 0;
}
注意：
[](int& x) { x *= 2; }是一个lambda表达式，它接受一个引用参数x，并将x的值乘以2。
（4）max_element
- 功能：返回容器中最大元素的迭代器。
- 时间复杂度：O(n)，其中
n是容器的元素数量。 - 空间复杂度：O(1)，原地操作。
示例：
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm> // max_element
int main() {
vector<int> vec = { 1, 3, 2, 4, 5 };
auto max_iter = max_element(vec.begin(), vec.end());
cout << "最大的元素: " << *max_iter << endl; // 输出：5
system("pause");
return 0;
}
注意：
max_element适用于，当需要找到容器中的最大元素时。
（5）min_element
- 功能：返回容器中最小元素的迭代器。
- 时间复杂度：O(n)，其中
n是容器的元素数量。 - 空间复杂度：O(1)，原地操作。
示例：
#include <iostream>
using namespace std;
#include <vector>
#include <algorithm> // min_element
int main() {
vector<int> vec = { 1, 3, 2, 4, 5 };
auto min_iter = min_element(vec.begin(), vec.end());
cout << "最小的元素: " << *min_iter << endl; // 输出：1
system("pause");
return 0;
}
注意：
min_element适用于，当需要找到容器中的最小元素时。
（6）inner_product
- 功能：计算两个容器中元素的内积，也可以计算加权和。它接受两个范围作为输入，并执行加法和乘法。
- 时间复杂度：O(n)，其中
n是容器的元素数量。 - 空间复杂度：O(1)，原地操作。
示例：
#include <iostream>
using namespace std;
#include <vector>
#include <numeric> // inner_product
int main() {
vector<int> vec1 = { 1, 2, 3 };
vector<int> vec2 = { 4, 5, 6 };
// 计算内积：1*4 + 2*5 + 3*6
int result = inner_product(vec1.begin(), vec1.end(), vec2.begin(), 0);
cout << "内积: " << result << endl; // 输出：32
system("pause");
return 0;
}
注意：
inner_product常用于计算两个向量的点积或加权和。
（7）partial_sum
- 功能：计算一个容器的部分和，即将容器中的每个元素累加起来，返回一个包含部分和的容器。可以选择自定义操作（例如累乘）。
- 时间复杂度：O(n)，其中
n是容器的元素数量。 - 空间复杂度：O(n)，需要存储部分和的结果。
示例：
#include <iostream>
using namespace std;
#include <vector>
#include <numeric> // partial_sum
int main() {
vector<int> vec = { 1, 2, 3, 4, 5 };
vector<int> result(vec.size());
// 计算部分和
partial_sum(vec.begin(), vec.end(), result.begin());
for (int x : result)
{
cout << x << " "; // 输出：1 3 6 10 15
}
cout << endl;
system("pause");
return 0;
}
注意：
partial_sum用于计算前缀和或部分和。
（8）adjacent_difference
- 功能：计算容器中相邻元素的差值，返回一个新的容器，其中每个元素是相邻元素的差值。
- 时间复杂度：O(n)，其中
n是容器的元素数量。 - 空间复杂度：O(n)，需要存储差值结果。
示例：
#include <iostream>
using namespace std;
#include <vector>
#include <numeric> // adjacent_difference
int main() {
vector<int> vec = { 1, 3, 6, 10, 15 };
vector<int> result(vec.size());
// 计算相邻元素的差值
adjacent_difference(vec.begin(), vec.end(), result.begin());
for (int x : result)
{
cout << x << " "; // 输出：1 2 3 4 5
}
cout << endl;
system("pause");
return 0;
}
注意：
adjacent_difference用于计算相邻元素的差值，常用于处理一系列增量或差异。