OI-wiki 深入解析 STLalgorithm算法库查找、排序、二分与排列组合实战指南【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wikiSTLStandard 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 组织标准化自 C98 起先后发布了 C98、C03、C11、C14、C17、C20、C23 等正式标准详见 C 标准与 STL 简介。STL 是标准库中模板化的通用数据结构和算法部分NOI 与 ICPC 赛事均支持 STL 的使用因此合理利用 STL 可以避免重复编写已验证的算法俗称“造轮子”并充分利用编译器对模板库的优化。算法函数大多通过迭代器Iterator与容器交互迭代器可看作行为类似指针的统一访问格式支持自增与解引用*。根据支持的操作迭代器分为输入、输出、前向、双向、随机访问、连续C17 引入等类别不同容器支持的迭代器类别不同调用算法前需确认参数要求详见 迭代器详解。例如sort需要随机访问迭代器而find只需输入迭代器即可工作。完备的函数列表参见 cppreference 的算法参考手册排序相关的更多内容可参考 排序内容的对应页面 与 排序的用途分析。基础序列操作find、reverse、unique与shuffle顺序查找findfind在区间内顺序查找第一个等于指定值的元素返回指向该元素的迭代器若找不到则返回区间的尾迭代器end。// 在 vector 中查找值为 value 的元素 auto it find(v.begin(), v.end(), value); if (it ! v.end()) { // 找到*it 即为该元素 } else { // 未找到 }find适用于未排序的任意容器包括list、forward_list等不支持随机访问的容器时间复杂度为 $O(n)$。翻转序列reversereverse将区间内的元素原地逆序可用于翻转数组、字符串等。// 翻转 vector 或字符串 reverse(v.begin(), v.end()); // 翻转数组下标 [begin, end) 区间 reverse(a begin, a end);去除相邻重复uniqueunique去除容器中相邻的重复元素签名与语义如下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与shufflerandom_shuffle可随机打乱数组或容器random_shuffle(v.begin(), v.end()); random_shuffle(v begin, v end);⚠️ 注意random_shuffle自 C14 起被弃用C17 起被移除。在新标准中应改用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_elementsortsort对区间[first, last)原地排序是竞赛中最常用的排序算法sort(v.begin(), v.end(), cmp); // 容器写法 sort(a begin, a end, cmp); // 数组写法其中end是排序区间最后一个元素的后一位cmp为自定义比较函数不传cmp时默认按operator从小到大排序。C11 及后续标准要求sort的最坏时间复杂度为 $O(n\log n)$具体实现取决于编译器libstdc 与 libc 通常采用内省排序详见 排序相关 STL。sort的第三个参数可传入函数指针、函数对象如greaterint()或 lambda。需要注意std::sort的比较函数返回值是booltrue/false 表示先后关系与 C 语言qsort的三值比较函数正/负/零语义完全不同不可混用。stable_sortstable_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_elementnth_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_boundbinary_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_mergemerge将两个已排序的序列有序合并到第三个序列的插入迭代器上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_permutationnext_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_sumpartial_sum定义于numeric头文件algorithm之外用于求前缀和设源容器为 $x$、目标容器为 $y$则 $y[i] x[0] x[1] \dots x[i]$partial_sum(src.begin(), src.end(), back_inserter(dst));示例来自 STL 算法文档vectorint 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 15partial_sum是手写前缀和的直接替代品。仓库中的 前缀和示例代码 注释里也明确写明了等价写法// std::partial_sum(a.begin(), a.end(), ps.begin());由于它需要随机访问迭代器以高效计算配合back_inserter即可在不预先指定目标长度的前提下得到结果。前缀和原理与二维扩展参见 前缀和。常见坑点与性能建议综合算法文档、排序相关 STL 与 关联容器 的说明使用 STL 算法时需特别注意以下几点比较函数语义sort系函数的比较器是bool二元谓词必须满足严格弱序strict weak ordering用定义“小于”属于典型错误会导致未定义行为或无法正确排序。内置类型的降序可直接用greaterint()。迭代器类别匹配sort、nth_element、partial_sum等需要随机访问迭代器set/map的迭代器不支持随机访问对其使用algorithm中的lower_bound等函数是 $O(n)$ 的务必改用成员函数版本。unique不改容器大小去重后必须用返回值确定新的有效长度否则残留元素会造成逻辑错误。random_shuffle已移除C17 起不可用统一改用shufflemt19937。nth_element只做部分排序它不保证两侧元素的顺序只保证分界点元素处于正确位置适合第 $k$ 大/小与 K-D Tree 建树不适合需要整体有序的场景。区间一律半开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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
OI-wiki 深入解析 STL `＜algorithm＞` 算法库：查找、排序、二分与排列组合实战指南
OI-wiki 深入解析 STLalgorithm算法库查找、排序、二分与排列组合实战指南【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wikiSTLStandard 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 组织标准化自 C98 起先后发布了 C98、C03、C11、C14、C17、C20、C23 等正式标准详见 C 标准与 STL 简介。STL 是标准库中模板化的通用数据结构和算法部分NOI 与 ICPC 赛事均支持 STL 的使用因此合理利用 STL 可以避免重复编写已验证的算法俗称“造轮子”并充分利用编译器对模板库的优化。算法函数大多通过迭代器Iterator与容器交互迭代器可看作行为类似指针的统一访问格式支持自增与解引用*。根据支持的操作迭代器分为输入、输出、前向、双向、随机访问、连续C17 引入等类别不同容器支持的迭代器类别不同调用算法前需确认参数要求详见 迭代器详解。例如sort需要随机访问迭代器而find只需输入迭代器即可工作。完备的函数列表参见 cppreference 的算法参考手册排序相关的更多内容可参考 排序内容的对应页面 与 排序的用途分析。基础序列操作find、reverse、unique与shuffle顺序查找findfind在区间内顺序查找第一个等于指定值的元素返回指向该元素的迭代器若找不到则返回区间的尾迭代器end。// 在 vector 中查找值为 value 的元素 auto it find(v.begin(), v.end(), value); if (it ! v.end()) { // 找到*it 即为该元素 } else { // 未找到 }find适用于未排序的任意容器包括list、forward_list等不支持随机访问的容器时间复杂度为 $O(n)$。翻转序列reversereverse将区间内的元素原地逆序可用于翻转数组、字符串等。// 翻转 vector 或字符串 reverse(v.begin(), v.end()); // 翻转数组下标 [begin, end) 区间 reverse(a begin, a end);去除相邻重复uniqueunique去除容器中相邻的重复元素签名与语义如下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与shufflerandom_shuffle可随机打乱数组或容器random_shuffle(v.begin(), v.end()); random_shuffle(v begin, v end);⚠️ 注意random_shuffle自 C14 起被弃用C17 起被移除。在新标准中应改用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_elementsortsort对区间[first, last)原地排序是竞赛中最常用的排序算法sort(v.begin(), v.end(), cmp); // 容器写法 sort(a begin, a end, cmp); // 数组写法其中end是排序区间最后一个元素的后一位cmp为自定义比较函数不传cmp时默认按operator从小到大排序。C11 及后续标准要求sort的最坏时间复杂度为 $O(n\log n)$具体实现取决于编译器libstdc 与 libc 通常采用内省排序详见 排序相关 STL。sort的第三个参数可传入函数指针、函数对象如greaterint()或 lambda。需要注意std::sort的比较函数返回值是booltrue/false 表示先后关系与 C 语言qsort的三值比较函数正/负/零语义完全不同不可混用。stable_sortstable_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_elementnth_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_boundbinary_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_mergemerge将两个已排序的序列有序合并到第三个序列的插入迭代器上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_permutationnext_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_sumpartial_sum定义于numeric头文件algorithm之外用于求前缀和设源容器为 $x$、目标容器为 $y$则 $y[i] x[0] x[1] \dots x[i]$partial_sum(src.begin(), src.end(), back_inserter(dst));示例来自 STL 算法文档vectorint 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 15partial_sum是手写前缀和的直接替代品。仓库中的 前缀和示例代码 注释里也明确写明了等价写法// std::partial_sum(a.begin(), a.end(), ps.begin());由于它需要随机访问迭代器以高效计算配合back_inserter即可在不预先指定目标长度的前提下得到结果。前缀和原理与二维扩展参见 前缀和。常见坑点与性能建议综合算法文档、排序相关 STL 与 关联容器 的说明使用 STL 算法时需特别注意以下几点比较函数语义sort系函数的比较器是bool二元谓词必须满足严格弱序strict weak ordering用定义“小于”属于典型错误会导致未定义行为或无法正确排序。内置类型的降序可直接用greaterint()。迭代器类别匹配sort、nth_element、partial_sum等需要随机访问迭代器set/map的迭代器不支持随机访问对其使用algorithm中的lower_bound等函数是 $O(n)$ 的务必改用成员函数版本。unique不改容器大小去重后必须用返回值确定新的有效长度否则残留元素会造成逻辑错误。random_shuffle已移除C17 起不可用统一改用shufflemt19937。nth_element只做部分排序它不保证两侧元素的顺序只保证分界点元素处于正确位置适合第 $k$ 大/小与 K-D Tree 建树不适合需要整体有序的场景。区间一律半开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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
