C++ STL算法函数 —— 应用及其操作实现

一、STL算法函数分类概述

STL算法库提供了大量实用函数，按功能可分为以下五类：

1. 不修改序列的操作

定义：这些算法不会改变容器中的元素，仅对数据进行查询或统计。
典型函数：

函数	功能	示例
`find(first, last, value)`	在区间 `[first, last)` 内顺序查找值为 `value` 的元素。	`find(a.begin(), a.end(), 5)`
`count(first, last, value)`	统计区间内值为 `value` 的元素个数。	`count(a.begin(), a.end(), 3)`
`all_of(first, last, pred)`	检查区间内所有元素是否满足谓词 `pred`。	`all_of(a.begin(), a.end(), is_positive)`
`accumulate(first, last, init)`	对区间内元素进行累加，初始值为 `init`。	`accumulate(a.begin(), a.end(), 0)`

说明：

搜索操作：如 find、search。
批量操作：如 for_each（对每个元素执行操作）。
折叠操作：如 accumulate（将元素通过运算折叠为一个值）。

2. 修改序列的操作

定义：这些算法会直接修改容器中的元素或顺序。有复制操作、交换操作、生成操作、移除操作、顺序变更操作、采样操作。
典型函数：

函数	功能	示例
`copy(src_begin, src_end, dest)`	复制源区间元素到目标位置。	`copy(a.begin(), a.end(), b.begin())`
`swap(a, b)`	交换两个元素的值。	`swap(a[0], a[1])`
`remove(first, last, value)`	移除区间内所有值为 `value` 的元素（需配合 `erase` 使用）。	`a.erase(remove(a.begin(), a.end(), 5), a.end())`
`reverse(first, last)`	翻转区间内元素的顺序。	`reverse(a.begin(), a.end())`

说明：

复制操作：如 copy、copy_n。
移除操作：如 remove、remove_if。
顺序变更操作：如 reverse、rotate。

3. 排序和相关操作

定义：涉及排序、划分、堆操作等与元素顺序相关的算法。有划分操作、排序操作、二分搜索操作（在已划分范围上）、集合操作（在已排序范围上）、归并操作（在已排序范围上）、堆操作、最大/最小操作、字典序比较操作、排列操作。
典型函数：

函数	功能	示例
`sort(first, last, cmp)`	对区间进行排序（默认升序）。	`sort(a.begin(), a.end())`
`binary_search(first, last, value)`	在已排序区间内进行二分查找。	`binary_search(a.begin(), a.end(), 10)`
`nth_element(first, nth, last)`	将第 `n` 大的元素放到正确位置，左侧均小于它，右侧均大于它。	`nth_element(a.begin(), a.begin()+3, a.end())`
`make_heap(first, last)`	将区间转换为堆结构。	`make_heap(a.begin(), a.end())`

说明：

划分操作：如 partition（按条件划分元素）。
集合操作：如 set_union（求并集，需已排序）。
排列操作：如 next_permutation（生成下一个排列）。

4. 数值运算

定义：与数学计算相关的算法，需包含 <numeric> 头文件。
典型函数：

函数	功能	示例
`iota(first, last, start)`	用连续递增的值填充区间，从 `start` 开始。	`iota(a.begin(), a.end(), 1)`
`inner_product(a_begin, a_end, b_begin, init)`	计算两个序列的内积（点积）。	`inner_product(a.begin(), a.end(), b.begin(), 0)`
`partial_sum(first, last, dest)`	计算前缀和并写入目标位置。	`partial_sum(a.begin(), a.end(), b.begin())`

说明：

此类算法通常用于数学计算，如求和、乘积、差值等。

5. 在未初始化内存上的操作

定义：直接在未初始化的内存区域构造对象，需包含 <memory> 头文件。
典型函数：

函数	功能	示例
`uninitialized_copy(src_begin, src_end, dest)`	将源区间复制到未初始化的内存。	`uninitialized_copy(a.begin(), a.end(), raw_mem)`
`uninitialized_fill(first, last, value)`	在未初始化内存区间填充 `value`。	`uninitialized_fill(a.begin(), a.end(), 0)`

说明：

这些函数用于低级内存管理，常见于自定义容器实现或性能优化场景。

总结

STL算法分类清晰，覆盖了从数据查询、修改到数学运算和内存管理的广泛需求。在算法竞赛中，合理使用这些函数可以大幅简化代码并提高效率。例如：

快速查找：使用 lower_bound 和 binary_search。
高效排序：结合 sort 和 nth_element。
灵活修改：通过 copy 和 reverse 调整数据顺序。

二、算法函数

下面简要介绍一些在算法竞赛中常用的函数：

函数	功能
unique(first, last)	去除容器中相邻的重复元素，所以一般需要先排序，然后用 `unique` 去重。返回值为指向去重后最后一个不同元素的迭代器。注意原容器大小不变，末尾的重复元素可以用 `erase()` 删除。
nth_element(a.begin(), a.begin() + mid, a.end(), cmp)	按指定范围进行分类，找出序列中第 `n` 大的元素，使其左边均为小于它的数，右边均为大于它的数。该函数一般用于求第 `k` 小的数。
binary_search(a.begin(), a.end(), value)	在已经排序的序列上做二分查找，需要先用 `sort()` 排序。`value` 为需要查找的值，如果找到，返回 `true`，否则返回 `false`。
lower_bound(a.begin(), a.end(), x)	在一个有序序列中进行二分查找，返回指向第一个大于或等于 `x` 的元素的位置。如果不存在这样的元素，则返回尾迭代器。
upper_bound(a.begin(), a.end(), x)	在一个有序序列中进行二分查找，返回指向第一个大于 `x` 的元素的位置的迭代器。如果不存在这样的元素，则返回尾迭代器。
next_permutation(a.begin(), a.end())	将当前排列更改为全排列中的下一个排列。如果当前排列已经是全排列中的最后一个排列，该函数返回 `false`，并将排列更改为全排列中的第一个排列。
prev_permutation()	将当前排列更改为全排列中的上一个排列，用法与 `next_permutation()` 相同。
max(), min()	查找最大、最小值。
swap()	交换两个元素的值。
find(a.begin(), a.end(), value)	顺序查找，`value` 为需要查找的值。如果找到，返回指向该元素的迭代器；否则返回尾迭代器。
reverse(a.begin(), a.end())	翻转数组、字符串。
sort(a.begin(), a.end(), cmp)	排序，`cmp` 为自定义的比较函数。如果没有提供 `cmp`，默认按升序排序。

详细说明：

1. `unique(first, last)`

功能：去除相邻的重复元素，通常需要先对容器进行排序。返回的迭代器指向去重后的最后一个元素，原容器的大小不变，末尾的重复元素可以通过 erase() 删除。

std::unique 函数的作用是去除相邻的重复元素，但它并不会改变容器的大小。它只是将不重复的元素移动到容器的前面，并返回一个指向去重后最后一个元素的迭代器。去重后的元素范围是从 begin() 到 unique() 返回的迭代器之间的部分，而剩下的部分（从返回的迭代器到 end()）仍然包含原来的元素，这些元素是未定义的（通常是重复元素的残留）。

为什么会有重复元素？

std::unique 只去除相邻的重复元素：
- 如果容器中有多个相同的元素，但它们不相邻，std::unique 不会去除它们。
- 例如，{1, 2, 2, 3, 2, 4}，std::unique 只会将相邻的 2 去除，结果是 {1, 2, 3, 2, 4}，后面的 2 仍然存在。
std::unique 不会改变容器的大小：
- 它只是将不重复的元素移动到容器的前面，并返回一个指向去重后最后一个元素的迭代器。
- 剩下的部分（从返回的迭代器到 end()）仍然包含原来的元素，这些元素是未定义的（通常是重复元素的残留）。

为什么需要 `erase`？

为了真正删除这些残留的重复元素，我们需要使用 erase 函数，将去重后的范围之后的元素删除。
如果不使用 erase，容器的大小不会改变，末尾的残留元素仍然存在。

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> vec = {1, 2, 2, 3, 2, 4, 4, 5};// 先排序，确保相同的元素相邻std::sort(vec.begin(), vec.end());// 使用 unique 去除相邻的重复元素auto last = std::unique(vec.begin(), vec.end());// 使用 erase 删除末尾的残留元素vec.erase(last, vec.end());// 输出去重后的结果for (int i : vec) {std::cout << i << " ";}return 0;
}

输出：1 2 3 4 5

2. `nth_element(a.begin(), a.begin() + mid, a.end(), cmp)`

功能：在序列中找到第 n 大的元素，并将其放置在正确的位置，使得左边的元素都小于它，右边的元素都大于它。常用于快速找到第 k 小的元素。

在 std::nth_element 函数中，cmp 参数是一个可选的比较函数，用于定义元素的排序规则。如果不提供 cmp 参数，std::nth_element 会使用默认的比较规则，即升序排序（从小到大）。

默认行为

如果不提供 cmp，std::nth_element 会使用 operator< 来比较元素。
这意味着它会将序列划分为：左边的元素都小于第 n 个元素，右边的元素都大于或等于第 n 个元素。

代码示例（默认）：

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> vec = {5, 3, 1, 4, 2};int mid = 2; // 找第3小的元素// 使用默认的比较规则（升序）std::nth_element(vec.begin(), vec.begin() + mid, vec.end());std::cout << "第3小的元素是: " << vec[mid] << std::endl;// 输出整个向量for (int i : vec) {std::cout << i << " ";}return 0;
}

输出：第3小的元素是: 3

代码示例（自定义比较函数）：

#include <iostream>
#include <vector>
#include <algorithm>bool cmp(int a, int b) {return a > b; // 降序排序
}int main() {std::vector<int> vec = {5, 3, 1, 4, 2};int mid = 2; // 找第3大的元素// 使用自定义的比较规则（降序）std::nth_element(vec.begin(), vec.begin() + mid, vec.end(), cmp);std::cout << "第3大的元素是: " << vec[mid] << std::endl;// 输出整个向量for (int i : vec) {std::cout << i << " ";}return 0;
}

3. `binary_search(a.begin(), a.end(), value)`

功能：在已排序的序列中进行二分查找，查找值为 value。如果找到，返回 true，否则返回 false。

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> vec = {1, 2, 3, 4, 5};bool found = std::binary_search(vec.begin(), vec.end(), 3);std::cout << (found ? "找到" : "未找到") << std::endl;return 0;
}

输出：找到

4. `lower_bound(a.begin(), a.end(), x)`

功能：在有序序列中查找第一个大于或等于 x 的元素的位置。如果不存在这样的元素，返回尾迭代器。

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> vec = {1, 2, 4, 4, 5};auto it = std::lower_bound(vec.begin(), vec.end(), 3);if (it != vec.end()) {std::cout << "第一个大于或等于3的元素是: " << *it << std::endl;} else {std::cout << "未找到" << std::endl;}return 0;
}

输出：第一个大于或等于3的元素是: 4

5. `upper_bound(a.begin(), a.end(), x)`

功能：在有序序列中查找第一个大于 x 的元素的位置。如果不存在这样的元素，返回尾迭代器。

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> vec = {1, 2, 4, 4, 5};auto it = std::upper_bound(vec.begin(), vec.end(), 3);if (it != vec.end()) {std::cout << "第一个大于3的元素是: " << *it << std::endl;} else {std::cout << "未找到" << std::endl;}return 0;
}

输出：第一个大于3的元素是: 4

6. `next_permutation(a.begin(), a.end())`

功能：将当前排列更改为全排列中的下一个排列。如果当前排列已经是最后一个排列，则返回 false，并将排列重置为第一个排列。

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> vec = {1, 2, 3};do {for (int i : vec) {std::cout << i << " ";}std::cout << std::endl;} while (std::next_permutation(vec.begin(), vec.end()));return 0;
}

输出：

7. `prev_permutation()`

功能：将当前排列更改为全排列中的上一个排列。用法与 next_permutation() 类似。

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> vec = {3, 2, 1};do {for (int i : vec) {std::cout << i << " ";}std::cout << std::endl;} while (std::prev_permutation(vec.begin(), vec.end()));return 0;
}

输出：

8. `max(), min()`

功能：用于查找序列中的最大值和最小值。

代码示例：

#include <iostream>
#include <algorithm>int main() {int a = 5, b = 3;std::cout << "最大值: " << std::max(a, b) << std::endl;std::cout << "最小值: " << std::min(a, b) << std::endl;return 0;
}

输出：

最大值: 5
最小值: 3

9. `swap()`

功能：交换两个元素的值。

代码示例：

#include <iostream>
#include <algorithm>int main() {int a = 5, b = 3;std::swap(a, b);std::cout << "a: " << a << ", b: " << b << std::endl;return 0;
}

输出：a: 3, b: 5

10. `find(a.begin(), a.end(), value)`

功能：在序列中顺序查找值为 value 的元素。如果找到，返回指向该元素的迭代器；否则返回尾迭代器。

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> vec = {1, 2, 3, 4, 5};auto it = std::find(vec.begin(), vec.end(), 3);if (it != vec.end()) {std::cout << "找到: " << *it << std::endl;} else {std::cout << "未找到" << std::endl;}return 0;
}

输出：找到: 3

11. `reverse(a.begin(), a.end())`

功能：翻转数组或字符串。

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> vec = {1, 2, 3, 4, 5};std::reverse(vec.begin(), vec.end());for (int i : vec) {std::cout << i << " ";}return 0;
}

输出：5 4 3 2 1

12. `sort(a.begin(), a.end(), cmp)`

功能：对序列进行排序，cmp 为自定义的比较函数。如果没有提供 cmp，默认按升序排序。

代码示例：

#include <iostream>
#include <vector>
#include <algorithm>bool cmp(int a, int b) {return a > b; // 降序排序
}int main() {std::vector<int> vec = {5, 3, 1, 4, 2};std::sort(vec.begin(), vec.end(), cmp);for (int i : vec) {std::cout << i << " ";}return 0;
}

输出：5 4 3 2 1

三、两种相关例子说明

注意：最重要的一点是迭代器是左闭右开区间，即最左边能取到，但是最右边取不到，换成数组也是一样的。

1. 使用 `vector` 定义数列的代码

#include <bits/stdc++.h>  // 包含标准库的所有头文件
using namespace std;      // 使用标准命名空间vector<int> a {23, 5, 36, 4, 8, 7, 5, 23};  // 初始化一个 vector，包含元素 23, 5, 36, 4, 8, 7, 5, 23void out() {  // 定义一个输出函数，用于打印 vector 的内容for (int i = 0; i < a.size(); i++)  // 遍历 vectorcout << a[i] << " ";  // 输出每个元素cout << endl;  // 换行
}int main() {auto it = find(a.begin(), a.end(), 5);  // 在 vector 中查找值为 5 的元素if (it != a.end()) cout << "yes" << endl;  // 如果找到，输出 "yes"else cout << "no" << endl;  // 如果没找到，输出 "no"nth_element(a.begin(), a.begin() + 4, a.end());  // 将第 5 小的元素放到正确位置out();  // 输出当前 vector 内容cout << "第 5 小:" << a[4] << endl;  // 输出第 5 小的元素sort(a.begin(), a.end());  // 对 vector 进行升序排序out();  // 输出排序后的 vectorauto last = unique(a.begin(), a.end());  // 去除相邻重复元素，返回去重后的尾迭代器out();  // 输出去重后的 vectora.erase(last, a.end());  // 删除末尾的重复元素out();  // 输出最终去重后的 vectorit = lower_bound(a.begin(), a.end(), 11);  // 查找第一个大于或等于 11 的元素if (it != a.end()) cout << *it << endl;  // 如果找到，输出该元素it = upper_bound(a.begin(), a.end(), 5);  // 查找第一个大于 5 的元素if (it != a.end()) cout << *it << endl;  // 如果找到，输出该元素return 0;  // 主函数结束
}

2. 使用数组定义数列的代码

#include <bits/stdc++.h>  // 包含标准库的所有头文件
using namespace std;      // 使用标准命名空间int a[] = {23, 5, 36, 4, 8, 7, 5, 23};  // 初始化一个数组，包含元素 23, 5, 36, 4, 8, 7, 5, 23
int n = 8;  // 数组的长度void out() {  // 定义一个输出函数，用于打印数组的内容for (int i = 0; i < n; i++)  // 遍历数组cout << a[i] << " ";  // 输出每个元素cout << endl;  // 换行
}int main() {int k = find(a, a + n, 5) - a;  // 在数组中查找值为 5 的元素，返回其索引if (k != n) cout << "yes" << endl;  // 如果找到，输出 "yes"else cout << "no" << endl;  // 如果没找到，输出 "no"nth_element(a, a + 4, a + n);  // 将第 5 小的元素放到正确位置out();  // 输出当前数组内容cout << "第 5 小:" << a[4] << endl;  // 输出第 5 小的元素sort(a, a + n);  // 对数组进行升序排序out();  // 输出排序后的数组n = unique(a, a + n) - a;  // 去除相邻重复元素，并更新数组长度out();  // 输出去重后的数组k = lower_bound(a, a + n, 11) - a;  // 查找第一个大于或等于 11 的元素if (k != n) cout << a[k] << endl;  // 如果找到，输出该元素k = upper_bound(a, a + n, 5) - a;  // 查找第一个大于 5 的元素if (k != n) cout << a[k] << endl;  // 如果找到，输出该元素if (binary_search(a, a + n, 23)) cout << "yes1" << endl;  // 在数组中二分查找值为 23 的元素else cout << "no1" << endl;  // 如果没找到，输出 "no1"reverse(a, a + n);  // 反转数组out();  // 输出反转后的数组int b[] = {2, 5, 7, 4, 5};  // 初始化另一个数组do {  // 使用 do-while 循环生成排列for (int i = 1; i < 4; i++) cout << b[i] << " ";  // 输出数组的部分元素cout << " ";  // 输出空格} while (next_permutation(b + 1, b + 4));  // 生成从第 2 个元素到第 4 个元素的全排列return 0;  // 主函数结束
}

总结

vector 版本：使用 STL 容器 vector，支持动态大小调整，操作更灵活。
数组版本：使用静态数组，操作更底层，适合固定大小的场景。
两段代码的功能基本相同，包括查找、排序、去重、二分查找、排列生成等操作。