引言在算法竞赛中我们经常需要实现各种经典算法——二分查找、排序、求排列、去重、前缀和……如果每次都要从头手写不仅浪费时间还容易在细节上出错比如二分边界写错、排序比较函数写反。事实上C 标准库已经为我们提供了一套功能强大、高度优化的算法库——STL 算法algorithm头文件。STL 算法是 C 标准库的“瑞士军刀”它涵盖了排序、查找、排列、集合操作、堆操作、数值运算等几乎所有基础算法而且所有算法都经过精心设计和优化时间和空间效率极高。如果说手写算法是“自己炼铁打刀”那么 STL 算法就是“直接拿起现成的神兵利器”——你不需要知道刀是怎么锻造的但你能用它轻松斩断问题。当然知道锻造原理能让你更好地选择时机使用哪一把刀。前置知识在使用 STL 算法之前你需要掌握以下基础迭代器STL 算法的“接口层”。理解begin()、end()、iterator、const_iterator的概念和用法。容器基础至少会使用vector、array、string等序列容器。函数对象与 Lambda很多算法需要传入自定义的比较或操作函数掌握 Lambda 表达式能让你事半功倍。引用与 const理解何时用值传递、何时用引用避免不必要的拷贝。第一章STL算法的分类STL 算法数量众多大约 100 多个但可以按照功能清晰地分为几大类类别核心功能典型算法非修改操作只读不改变容器内容find,count,search,equal,mismatch修改操作改变容器内容但不改变大小copy,move,swap,replace,fill,generate排序与划分对元素进行排序或分组sort,partial_sort,nth_element,partition二分查找在有序区间中快速查找lower_bound,upper_bound,binary_search排列与集合排列组合、集合运算next_permutation,set_union,set_intersection堆操作在数组上维护堆结构make_heap,push_heap,pop_heap数值算法数值计算numericaccumulate,inner_product,partial_sum绝大多数 STL 算法都定义在algorithm头文件中少数数值类算法在numeric中。第二章非修改操作 —— 数据的“侦察兵”2.1find与find_if在容器中查找第一个符合条件的元素。cpp#include algorithm #include vector std::vectorint v {1, 3, 5, 7, 9, 2, 4, 6, 8}; // 查找值 5 auto it std::find(v.begin(), v.end(), 5); if (it ! v.end()) { // 找到了it 指向 5 } // 查找第一个偶数 auto it2 std::find_if(v.begin(), v.end(), [](int x) { return x % 2 0; });复杂度O(n)O(n)。竞赛用途当需要判断一个元素是否存在于无序容器中但容器又不支持哈希时用find比手写循环更清晰。2.2count与count_if统计符合条件的元素个数。cppint cnt std::count(v.begin(), v.end(), 5); int even_cnt std::count_if(v.begin(), v.end(), [](int x) { return x % 2 0; });2.3search—— 查找子序列在序列 A 中查找序列 B 第一次出现的位置类似于字符串的find的泛化版本。cppstd::vectorint text {1, 2, 3, 4, 5, 1, 2, 3}; std::vectorint pattern {4, 5}; auto it std::search(text.begin(), text.end(), pattern.begin(), pattern.end()); // it 指向第一个 4 的位置2.4equal—— 比较两个序列是否相等cppstd::vectorint a {1, 2, 3}; std::vectorint b {1, 2, 3}; bool same std::equal(a.begin(), a.end(), b.begin()); // true注意equal在 C14 前要求第二个序列至少和第一个一样长C14 后可用四参数版本指定终点。第三章修改操作 —— 数据的“加工厂”3.1copy与copy_if将元素从一个容器复制到另一个容器。cppstd::vectorint src {1, 2, 3, 4, 5}; std::vectorint dst(5); std::copy(src.begin(), src.end(), dst.begin()); // 只复制偶数 std::vectorint even; std::copy_if(src.begin(), src.end(), std::back_inserter(even), [](int x) { return x % 2 0; });重要copy不会自动扩容目标容器使用std::back_inserter作为迭代器可以自动push_back。3.2fill与generate批量赋值。cppstd::vectorint v(10); std::fill(v.begin(), v.end(), 42); // 全部填 42 int i 0; std::generate(v.begin(), v.end(), [i]() { return i; }); // 0, 1, 2, ...3.3replace与replace_if替换符合条件的元素。cppstd::vectorint v {1, 2, 3, 2, 5}; std::replace(v.begin(), v.end(), 2, 99); // 所有 2 变成 99 // v {1, 99, 3, 99, 5} std::replace_if(v.begin(), v.end(), [](int x) { return x % 2 0; }, 0); // 所有偶数变成 03.4swap—— 交换两个变量的“万能工具”cppint a 5, b 10; std::swap(a, b); // a10, b5 std::vectorint v1(100), v2(100); std::swap(v1, v2); // O(1) 交换只交换内部指针3.5unique—— 相邻去重cppstd::vectorint v {1, 1, 2, 2, 3, 3, 1, 1}; auto last std::unique(v.begin(), v.end()); // 去重后{1, 2, 3, 1, ...}last 指向第一个 1 后面的位置 v.erase(last, v.end()); // 真正删除注意unique只去掉相邻重复元素使用前通常要先sort。第四章排序与划分 —— 数据的“组织者”4.1sort—— 最常用的排序cppstd::vectorint v {5, 2, 8, 1, 9}; std::sort(v.begin(), v.end()); // 升序1, 2, 5, 8, 9 std::sort(v.begin(), v.end(), std::greaterint()); // 降序9, 8, 5, 2, 1 // 自定义比较按绝对值排序 std::sort(v.begin(), v.end(), [](int a, int b) { return abs(a) abs(b); });复杂度平均 O(Nlog⁡N)O(NlogN)最坏 O(Nlog⁡N)O(NlogN)C11 后的sort是 Introsort避免了快排的最坏情况。竞赛技巧sort是竞赛中使用频率最高的 STL 算法务必牢记。4.2partial_sort—— 只关心前 K 个当你只需要前 K 小或前 K 大的元素时partial_sort比全排序更高效。cppstd::vectorint v {9, 1, 8, 2, 7, 3, 6, 4, 5}; std::partial_sort(v.begin(), v.begin() 3, v.end()); // 前3个是最小的1, 2, 3其余元素顺序未指定复杂度O(Nlog⁡K)O(NlogK)。4.3nth_element—— 找到第 K 小的元素nth_element将第 K 个元素放到正确位置左边所有元素 ≤ 它右边所有元素 ≥ 它。它不保证左右有序但比partial_sort更快。cppstd::vectorint v {9, 1, 8, 2, 7, 3, 6, 4, 5}; std::nth_element(v.begin(), v.begin() 4, v.end()); // v[4] 是第5小的元素下标从0开始左边 ≤ v[4]右边 ≥ v[4]复杂度平均 O(N)O(N)。应用快速找中位数、找第 K 大/小。4.4partition—— 按条件分组cppstd::vectorint v {1, 2, 3, 4, 5, 6}; auto it std::partition(v.begin(), v.end(), [](int x) { return x % 2 0; }); // 偶数全部在前奇数全部在后it 指向第一个奇数第五章二分查找 —— 在有序数据中“精准定位”二分查找算法要求容器已经按升序排序或按自定义比较规则有序。5.1lower_bound—— 第一个 ≥ 目标的位置cppstd::vectorint v {1, 3, 5, 7, 9}; auto it std::lower_bound(v.begin(), v.end(), 5); // it 指向第一个 5位置2 auto it2 std::lower_bound(v.begin(), v.end(), 6); // it2 指向 7位置3因为 6 不存在返回第一个 ≥ 6 的位置5.2upper_bound—— 第一个 目标的位置cppauto it std::upper_bound(v.begin(), v.end(), 5); // it 指向第一个 5 的元素即 75.3binary_search—— 判断是否存在cppbool exists std::binary_search(v.begin(), v.end(), 5); // true bool exists2 std::binary_search(v.begin(), v.end(), 6); // false5.4 完整统计目标值的出现次数cppauto range std::equal_range(v.begin(), v.end(), 5); // range.first lower_bound, range.second upper_bound int count range.second - range.first;复杂度所有二分查找算法均为 O(log⁡N)O(logN)。第六章排列与集合操作 —— 组合数学的“工具包”6.1next_permutation—— 生成下一个排列cppstd::vectorint v {1, 2, 3}; do { // 处理当前排列 } while (std::next_permutation(v.begin(), v.end())); // 会遍历123, 132, 213, 231, 312, 321注意next_permutation会按字典序生成下一个排列如果当前已是最后一个排列返回false。6.2prev_permutation—— 生成上一个排列与next_permutation相反生成前一个字典序排列。6.3 集合运算要求有序序列cppstd::vectorint A {1, 2, 3, 4}; std::vectorint B {3, 4, 5, 6}; std::vectorint result; // 并集 std::set_union(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(result)); // result {1, 2, 3, 4, 5, 6} // 交集 std::set_intersection(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(result)); // result {3, 4} // 差集A 中有但 B 中没有 std::set_difference(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(result)); // result {1, 2}注意所有集合运算都要求输入序列已排序复杂度为 O(NM)O(NM)。第七章堆操作 —— 优先队列的“手动版”虽然std::priority_queue更方便但如果需要灵活操作堆比如取出堆顶后还能修改堆中的元素可以用algorithm中的堆函数。7.1make_heap—— 建堆cppstd::vectorint v {3, 1, 4, 1, 5, 9, 2}; std::make_heap(v.begin(), v.end()); // 默认大根堆 std::make_heap(v.begin(), v.end(), std::greaterint()); // 小根堆7.2push_heap—— 插入堆cppv.push_back(6); std::push_heap(v.begin(), v.end()); // 将最后一个元素上滤7.3pop_heap—— 弹出堆顶cppstd::pop_heap(v.begin(), v.end()); // 将堆顶移到末尾 int top v.back(); v.pop_back(); // 删除末尾元素复杂度建堆 O(N)O(N)插入/删除 O(log⁡N)O(logN)。第八章数值算法numeric8.1accumulate—— 累加或自定义归约cpp#include numeric std::vectorint v {1, 2, 3, 4, 5}; int sum std::accumulate(v.begin(), v.end(), 0); // 15 // 自定义操作求乘积 int product std::accumulate(v.begin(), v.end(), 1, std::multipliesint()); // 1208.2inner_product—— 内积cppstd::vectorint a {1, 2, 3}; std::vectorint b {4, 5, 6}; int dot std::inner_product(a.begin(), a.end(), b.begin(), 0); // 1*4 2*5 3*6 328.3partial_sum—— 前缀和cppstd::vectorint v {1, 2, 3, 4, 5}; std::vectorint prefix(5); std::partial_sum(v.begin(), v.end(), prefix.begin()); // prefix {1, 3, 6, 10, 15}8.4iota—— 填充连续递增序列cppstd::vectorint v(10); std::iota(v.begin(), v.end(), 0); // v {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}第九章迭代器适配器与技巧9.1back_inserter—— 自动扩容的插入迭代器cppstd::vectorint v; std::copy(src.begin(), src.end(), std::back_inserter(v)); // 等价于不断 v.push_back()9.2inserter—— 在指定位置插入cppstd::setint s; std::copy(src.begin(), src.end(), std::inserter(s, s.begin())); // 插入到 set 中会自动排序9.3reverse_iterator—— 反向遍历cpp// 逆序排序 std::sort(v.rbegin(), v.rend()); // 降序 // 逆序遍历 for (auto it v.rbegin(); it ! v.rend(); it) { }第十章复杂度与适用场景速查算法时间复杂度适用场景注意findO(n)O(n)无序容器查找比手写循环干净binary_searchO(log⁡n)O(logn)有序容器必须已排序sortO(nlog⁡n)O(nlogn)通用排序最常用partial_sortO(nlog⁡k)O(nlogk)只关心前 k 个比全排序快nth_elementO(n)O(n) 平均找第 k 小不排序全部uniqueO(n)O(n)去重先排序next_permutationO(n)O(n) 均摊全排列枚举字典序set_unionO(nm)O(nm)集合运算输入必须有序make_heapO(n)O(n)手控堆比 priority_queue 灵活accumulateO(n)O(n)累加/归约numeric例题与解析例题1按绝对值排序去重题目给定一个整数数组要求去掉绝对值相等的元素保留第一个出现的并按绝对值升序输出。解法cppvectorint v {-3, 5, 2, -2, 3, 4, -5, 1, 3}; // 按绝对值排序保持相对顺序sort 不保证稳定 sort(v.begin(), v.end(), [](int a, int b) { return abs(a) abs(b); }); // 去重只去相邻重复已经按绝对值排序绝对值相等的相邻 auto last unique(v.begin(), v.end(), [](int a, int b) { return abs(a) abs(b); }); v.erase(last, v.end());例题2求中位数题目给定一个长度为 N 的数组求中位数N 为奇数时取中间偶数时取下中位数。解法cppnth_element(v.begin(), v.begin() N/2, v.end()); int median v[N/2];一行代码搞定例题3统计区间内不同元素个数题目给定有序数组统计[L, R]区间内不同元素的个数。解法cppauto left lower_bound(v.begin(), v.end(), L); auto right upper_bound(v.begin(), v.end(), R); int diff 0; for (auto it left; it ! right; ) { diff; it upper_bound(it, right, *it); // 跳过所有相同的值 }总结STL 算法是算法竞赛选手的“秘密武器”。它让原本需要几十行手写代码的功能压缩成一行调用让原本可能写错的二分边界变成可靠的lower_bound让原本需要自己实现的堆变成make_heappush_heappop_heap的组合。学习 STL 算法的三个关键点知道有什么熟悉sort、lower_bound、next_permutation、unique、nth_element、set_union、accumulate这些最常用的工具。知道怎么用理解迭代器的概念会配合begin()、end()、back_inserter使用。知道复杂度知道什么时候用sortO(nlog⁡n)O(nlogn)什么时候用nth_element平均 O(n)O(n)避免选错算法导致 TLE。