企业官网建设流程全解析

OI-wiki 深入解析 STL<algorithm>算法库：查找、排序、二分与排列组合实战指南

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

STL（Standard Template Library，标准模板库）为 C++ 提供了约 100 个实现算法的模板函数，绝大多数定义于<algorithm>头文件，另有部分分布在<numeric>与<functional>中。本文以 OI-wiki 的 STL 算法文档 为核心骨架，系统讲解这些算法的调用约定、复杂度特性、典型坑点，并结合仓库内docs/basic/、docs/lang/csl/等章节的配套代码与示例，给出可在竞赛与工程中直接复用的完整用法。

读完本文，你将掌握：如何用find/reverse/unique/shuffle完成基础序列操作；如何用sort/stable_sort/nth_element进行高效排序与划分；如何用binary_search/lower_bound/upper_bound/merge/inplace_merge完成有序序列的二分与归并；如何用next_permutation/prev_permutation生成全排列，以及如何用partial_sum一行求出前缀和。

概览：算法库从哪来、到哪去

C++ 标准库由 ISO 组织标准化，自 C++98 起先后发布了 C++98、C++03、C++11、C++14、C++17、C++20、C++23 等正式标准（详见 C++ 标准与 STL 简介）。STL 是标准库中模板化的通用数据结构和算法部分，NOI 与 ICPC 赛事均支持 STL 的使用，因此合理利用 STL 可以避免重复编写已验证的算法（俗称“造轮子”），并充分利用编译器对模板库的优化。

算法函数大多通过迭代器（Iterator）与容器交互，迭代器可看作行为类似指针的统一访问格式，支持自增（++）与解引用（*）。根据支持的操作，迭代器分为输入、输出、前向、双向、随机访问、连续（C++17 引入）等类别；不同容器支持的迭代器类别不同，调用算法前需确认参数要求（详见 迭代器详解）。例如sort需要随机访问迭代器，而find只需输入迭代器即可工作。

完备的函数列表参见 cppreference 的算法参考手册；排序相关的更多内容可参考 排序内容的对应页面 与 排序的用途分析。

基础序列操作：find、reverse、unique与shuffle

顺序查找find

find在区间内顺序查找第一个等于指定值的元素，返回指向该元素的迭代器；若找不到则返回区间的尾迭代器（end）。

// 在 vector 中查找值为 value 的元素 auto it = find(v.begin(), v.end(), value); if (it != v.end()) { // 找到，*it 即为该元素 } else { // 未找到 }

find适用于未排序的任意容器（包括list、forward_list等不支持随机访问的容器），时间复杂度为 $O(n)$。

翻转序列reverse

reverse将区间内的元素原地逆序，可用于翻转数组、字符串等。

// 翻转 vector 或字符串 reverse(v.begin(), v.end()); // 翻转数组下标 [begin, end) 区间 reverse(a + begin, a + end);

去除相邻重复unique

unique去除容器中相邻的重复元素，签名与语义如下：

ForwardIterator unique(ForwardIterator first, ForwardIterator last);

它返回一个指向去重后容器结尾的迭代器，但原容器的大小不变——未被删除的“尾巴”元素仍然存在，只是逻辑上已被忽略。正因为unique只消除相邻重复，若要实现完整的容器去重，必须与sort结合使用：先排序使相同元素相邻，再去重。

一个典型用法是配合sort求“去重后的元素个数”，下面这段来自 STL 算法文档 的示例演示了求数组第 $k$ 小（不重复计值）的整数：

int N = 10, a[] = {1, 3, 3, 7, 2, 5, 1, 2, 4, 6}, k = 3; sort(a, a + N); // unique 将返回去重之后数组最后一个元素之后的地址，计算出的 cnt 为去重后数组的长度 int cnt = unique(a, a + N) - a; cout << a[k - 1]; // 输出去重后第 k 小的值

注意：去重后原数组末尾仍残留重复值，计算长度时必须以unique的返回值为准，不可使用原数组长度。

随机打乱random_shuffle与shuffle

random_shuffle可随机打乱数组或容器：

random_shuffle(v.begin(), v.end()); random_shuffle(v + begin, v + end);

⚠️ 注意：random_shuffle自 C++14 起被弃用，C++17 起被移除。在新标准中应改用shuffle，其最后一个参数需要传入一个随机数生成器，通常使用以真随机数生成器std::random_device播种的梅森旋转伪随机数生成器std::mt19937：

// #include <random> std::mt19937 rng(std::random_device{}()); std::shuffle(v.begin(), v.end(), rng);

shuffle在现代竞赛代码与数据生成器（例如docs/contest/problemsetting.md中提到的对拍数据构造）中被广泛使用，用mt19937播种可以避免rand()的周期过短与可预测性问题。

排序与选择：sort、stable_sort、nth_element

sort

sort对区间[first, last)原地排序，是竞赛中最常用的排序算法：

sort(v.begin(), v.end(), cmp); // 容器写法 sort(a + begin, a + end, cmp); // 数组写法

其中end是排序区间最后一个元素的后一位，cmp为自定义比较函数；不传cmp时默认按operator<从小到大排序。C++11 及后续标准要求sort的最坏时间复杂度为 $O(n\log n)$，具体实现取决于编译器（libstdc++ 与 libc++ 通常采用内省排序，详见 排序相关 STL）。

sort的第三个参数可传入函数指针、函数对象（如greater<int>()）或 lambda。需要注意：std::sort的比较函数返回值是bool（true/false 表示先后关系），与 C 语言qsort的三值比较函数（正/负/零）语义完全不同，不可混用。

stable_sort

stable_sort是稳定排序，用法与sort完全一致，但保证相等元素排序后的相对顺序与排序前相同：

stable_sort(v.begin(), v.end()); stable_sort(v.begin(), v.end(), cmp);

其时间复杂度为 $O(n\log^2 n)$，在额外内存可用时可达 $O(n\log n)$。当业务需要“按主关键字排序、次关键字保持原始顺序”时（例如先按总分降序、同分者保持输入顺序），应优先考虑stable_sort。

nth_element

nth_element按指定位置对序列进行部分划分：重排[first, last)，使得nth所指向的元素成为“排好序后该位置应出现的元素”，其左侧所有元素小于或等于它，右侧所有元素大于或等于它：

nth_element(v.begin(), v.begin() + n, v.end(), cmp); nth_element(a + begin, a + begin + n, a + end, cmp);

平均时间复杂度为 $O(n)$，适合求解“第 $k$ 大/第 $k$ 小元素”这类无需完全排序的问题。从仓库源码看，nth_element被用于构建 K-D Tree（见docs/ds/code/kdt/kdt_1.cpp等实现），因为 K-D Tree 的建树过程需要在每一维上取中位数作为划分点，nth_element正是做这件事的高效工具。此外，它也是求解第 $k$ 小的经典选择，比sort整体排序后取下标效率更高。

有序序列的二分与归并

binary_search与lower_bound/upper_bound

binary_search在有序序列中二分查找指定值是否存在：

binary_search(v.begin(), v.end(), value);

lower_bound与upper_bound则返回边界迭代器，是竞赛中最常用的“二分答案在序列中的位置”工具：

• lower_bound(v.begin(), v.end(), x)：返回指向第一个大于等于$x$ 的元素的迭代器；不存在时返回尾迭代器。
• upper_bound(v.begin(), v.end(), x)：返回指向第一个大于$x$ 的元素的迭代器；不存在时返回尾迭代器。

在有序数组 $a$ 中，二者配合可以精确划分出“小于 $x$ / 等于 $x$ / 大于 $x$”三段区间。下面示例来自 STL 算法文档：

int N = 10, a[] = {1, 1, 2, 4, 5, 5, 7, 7, 9, 9}, x = 5; int i = lower_bound(a, a + N, x) - a, j = upper_bound(a, a + N, x) - a; // a[0] ~ a[i - 1] 为小于 x 的元素，a[i] ~ a[j - 1] 为等于 x 的元素， // a[j] ~ a[N - 1] 为大于 x 的元素 cout << i << " " << j << endl; // 输出 4 6

⚠️ 复杂度陷阱：在一般数组/vector中，lower_bound/upper_bound均为 $O(\log n)$；但在set等关联式容器上，直接调用lower_bound(s.begin(), s.end(), val)的时间复杂度是 $O(n)$ 的！因为关联容器的迭代器不是随机访问迭代器，无法直接跳到中点。set/map等容器已经封装了成员函数版本（如s.lower_bound(val)），这样调用的时间复杂度才是 $O(\log n)$。此点同样记录在 关联容器文档 中。

实战：用lower_bound求最接近 $x$ 的元素

STL 算法文档 给出了一个经典的应用——查找有序数组中与 $x$ 最接近的元素：

int N = 10, a[] = {1, 1, 2, 4, 5, 5, 8, 8, 9, 9}, x = 6; // lower_bound 将返回 a 中第一个大于等于 x 的元素的地址，计算出的 i 为其下标 int i = lower_bound(a, a + N, x) - a; // 在以下两种情况下，a[i] (a 中第一个大于等于 x 的元素) 即为答案： // 1. a 中最小的元素都大于等于 x； // 2. a 中存在大于等于 x 的元素，且第一个大于等于 x 的元素 (a[i]) // 相比于第一个小于 x 的元素 (a[i - 1]) 更接近 x； // 否则，a[i - 1] (a 中第一个小于 x 的元素) 即为答案 if (i == 0 || (i < N && a[i] - x < x - a[i - 1])) cout << a[i]; else cout << a[i - 1];

该技巧正是 UVa10487 Closest Sums 一类题目的核心：先排序，再对每个询问二分定位最接近的元素。二分查找的完整理论（时间复杂度、边界处理、最大值最小化等）参见 二分查找，其中还讨论了lower_bound/upper_bound与 C 库bsearch的区别。

merge与inplace_merge

merge将两个已排序的序列有序合并到第三个序列的插入迭代器上：

merge(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(v3));

back_inserter来自<iterator>，它返回一个插入迭代器，每次赋值都会在目标容器末尾push_back，因此v3无需预先扩容。这正是 归并排序 中“合并两个有序子序列”这一核心步骤的现成实现。

inplace_merge则将同一序列内两个相邻的、已按小于运算符排序的子区间[first, middle)与[middle, last)原地合并为一个有序序列：

inplace_merge(v.begin(), v.begin() + middle, v.end());

它常用于需要保持稳定性的归并类算法中，例如 CDQ 分治（参见 CDQ 分治 及其代码docs/misc/code/cdq-divide/cdq-divide_4.cpp）在合并处理跨区间贡献时会用到这类原地归并能力。

排列与数值算法：next_permutation、prev_permutation、partial_sum

全排列生成：next_permutation/prev_permutation

next_permutation将当前排列更改为全排列中的下一个排列：

• 如果当前排列不是最后一个排列（即尚未完全从大到小），函数返回true并将排列改为字典序的下一个；
• 如果当前排列已经是全排列中的最后一个排列（元素完全从大到小排列），函数返回false，并把排列更改为全排列中的第一个排列（元素完全从小到大排列）。

next_permutation(v.begin(), v.end()); next_permutation(v + begin, v + end);

prev_permutation对称地生成上一个排列，用法相同。

经典应用：从 $1$ 到 $9$ 的全排列生成。下面示例来自 STL 算法文档，对应例题为 Luogu P1706 全排列问题：

int N = 9, a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; do { for (int i = 0; i < N; i++) cout << a[i] << " "; cout << endl; } while (next_permutation(a, a + N));

要点：起始排列必须有序（从小到大），do-while才能保证从初始排列开始输出全部 $n!$ 个排列；若初始无序，则只会从当前排列开始输出其后缀部分。排列相关的更多数学背景可参考 排列与组合。

前缀和：partial_sum

partial_sum定义于<numeric>头文件（<algorithm>之外），用于求前缀和：设源容器为 $x$、目标容器为 $y$，则 $y[i] = x[0] + x[1] + \dots + x[i]$：

partial_sum(src.begin(), src.end(), back_inserter(dst));

示例（来自 STL 算法文档）：

vector<int> src = {1, 2, 3, 4, 5}, dst; // 求解 src 中元素的前缀和，dst[i] = src[0] + ... + src[i] // back_inserter 函数作用在 dst 容器上，提供一个插入迭代器 partial_sum(src.begin(), src.end(), back_inserter(dst)); for (unsigned int i = 0; i < dst.size(); i++) cout << dst[i] << " "; // 输出：1 3 6 10 15

partial_sum是手写前缀和的直接替代品。仓库中的 前缀和示例代码 注释里也明确写明了等价写法：

// std::partial_sum(a.begin(), a.end(), ps.begin());

由于它需要随机访问迭代器以高效计算，配合back_inserter即可在不预先指定目标长度的前提下得到结果。前缀和原理与二维扩展参见 前缀和。

常见坑点与性能建议

综合算法文档、排序相关 STL 与 关联容器 的说明，使用 STL 算法时需特别注意以下几点：

1. 比较函数语义：sort系函数的比较器是bool二元谓词，必须满足严格弱序（strict weak ordering）；用<=定义“小于”属于典型错误，会导致未定义行为或无法正确排序。内置类型的降序可直接用greater<int>()。
2. 迭代器类别匹配：sort、nth_element、partial_sum等需要随机访问迭代器；set/map的迭代器不支持随机访问，对其使用<algorithm>中的lower_bound等函数是 $O(n)$ 的，务必改用成员函数版本。
3. unique不改容器大小：去重后必须用返回值确定新的有效长度，否则残留元素会造成逻辑错误。
4. random_shuffle已移除：C++17 起不可用，统一改用shuffle+mt19937。
5. nth_element只做部分排序：它不保证两侧元素的顺序，只保证分界点元素处于正确位置；适合第 $k$ 大/小与 K-D Tree 建树，不适合需要整体有序的场景。
6. 区间一律半开：STL 算法统一使用[first, last)半开区间，end指向最后一个元素的后一位，写循环与传参时务必保持一致，否则会多处理一个元素或漏处理一个元素。

参考资料

• 算法完整函数列表：cppreference 算法库
• 排序专题：排序相关 STL、排序的使用、快速排序、归并排序
• 二分专题：二分查找
• 容器与迭代器：STL 容器、迭代器详解、关联容器
• 仓库配套示例：前缀和示例代码、K-D Tree 代码

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki