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()）仍然包含原来的元素，这些元素是未定义的（通常是重复元素的残留）。

为什么会有重复元素？

1. std::unique 只去除相邻的重复元素：

   • 如果容器中有多个相同的元素，但它们不相邻，std::unique 不会去除它们。

   • 例如，{1, 2, 2, 3, 2, 4}，std::unique 只会将相邻的 2 去除，结果是 {1, 2, 3, 2, 4}，后面的 2 仍然存在。

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;
}

输出：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

---

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;
}

输出：

3 2 1
3 1 2
2 3 1
2 1 3
1 3 2
1 2 3

---

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，支持动态大小调整，操作更灵活。

• 数组版本：使用静态数组，操作更底层，适合固定大小的场景。

• 两段代码的功能基本相同，包括查找、排序、去重、二分查找、排列生成等操作。