C++ ＜algorithm＞ 算法库：排序、查找、变换与性能优化实战

1. 为什么说algorithm是 C 标准库最容易忽略的宝藏这几年我面试过不少人也帮团队 review 过不少代码发现一个挺普遍的现象很多人 C 容器用得飞起vector、map 一套一套的但一提到algorithm这个头文件能熟练使用的却没几个。遇到遍历一遍找点什么把一段数据改个形式按条件筛一批元素这种需求第一反应还是写手写 for 循环循环本身没错但写多了边界就出问题而且同样的逻辑在项目里重复出现好几遍后面想统一改策略都无从下手。algorithm解决的就是这类问题。它是 C 标准库里的算法仓库装着上百个针对区间操作的泛型算法靠迭代器把所有容器串起来vector、list、deque、array甚至 C 风格数组都能喂给同一套sort、find、count。你不用为每一种容器写不同的遍历代码算法只关心从哪里开始、到哪里结束这两个迭代器。这套东西的核心价值有三点把重复性的数据处理逻辑抽成可复用的函数、避免手写循环带来的边界错误、提供各编译器厂商反复优化过的实现。它到底能做什么简单归纳查找、统计、排序、复制、变换、删除、旋转、打乱、合并、二分查找、集合运算、堆操作……基本把业务开发里能遇到的数据结构常规操作全覆盖了。这篇文章适合两类人一类是刚熟悉 STL 容器、想往泛型算法迈进的新手跟着文章把高频算法的用法和坑过一遍基本能上手另一类是写了几年 C 但习惯手写循环、想提升代码质量的开发者。我会先给一张算法认知地图再按家族拆解核心用法穿插实际踩过的坑最后用两个完整场景演示组合使用的思路。2. 认知地图algorithm的算法家族与选型思路打开 cppreference 看algorithm的目录第一感觉是条目多得吓人光函数签名就能拉好几屏。但其实按功能分族之后记忆负担会小很多。我习惯把算法分成四个大族去看。2.1 非修改序列操作只读不改安全第一这一族算法的共同特征是不会修改容器内容适合做查找、统计、判断。最常用的有find / find_if / find_if_not按值或按条件找第一个匹配元素返回迭代器找不到返回end()。count / count_if统计匹配元素的数量。all_of / any_of / none_of判断区间里的元素是否全部、存在、全部不满足某个条件。for_each对每个元素执行一遍操作。search / find_end / adjacent_find子序列搜索与相邻重复查找。equal / mismatch / lexicographical_compare区间内容比较。is_sorted / is_partitioned / is_heap判断区间是否满足有序、划分、堆性质。这类算法基本都是 O(n) 的线性扫描性能没有悬念也不需要额外内存。我的选型原则很简单只要是读一下区间做判断优先扫一眼这族有没有现成的哪怕逻辑不能完全匹配也往往能用一个小 lambda 补上比自己写循环稳得多。2.2 修改序列操作原地变换的干活小队修改序列操作分两种一种是原地改直接在原容器上动手比如reverse、rotate、fill、replace、remove、swap_ranges另一种是拷出去改把结果写到另一个目标区间比如copy、copy_if、transform、replace_copy、remove_copy。这类算法的共性是需要明确目标输出区间在哪里如果目标区间容量不够就会越界写这是新手最容易踩的坑后面实战部分我会专门展开。这里要特别提醒的是remove。它名义上叫移除实际语义却是把要保留的元素往前挪覆盖掉要删除的位置然后返回一个新的逻辑终点迭代器。它并不会真的缩小容器的大小。这个反直觉的设计坑了无数人后面我会在专门的章节详细讲怎么配合erase使用。2.3 排序、划分与堆操作让无序变有序排序家族包括sort、stable_sort、partial_sort、partial_sort_copy、nth_element以及配套的状态检查is_sorted。划分家族是partition、stable_partition、partition_point。堆操作是make_heap、push_heap、pop_heap、sort_heap。这几个家族内部的关系很有意思partial_sort只保证前 k 个元素有序nth_element更激进只保证第 n 个元素放在如果全排序它该在的位置不管前后顺序。所以nth_element的平均复杂度是 O(n)比sort的 O(n log n) 低一个级别。选型时如果只需要前 k 小/大别一上来就sort先想想partial_sort或nth_element能不能满足需求。2.4 有序区间专供二分查找与集合运算这一族算法要求输入区间已经有序包括lower_bound、upper_bound、equal_range、binary_search、merge、inplace_merge以及includes、set_union、set_intersection、set_difference、set_symmetric_difference。它们能在有序区间上拿到 O(log n) 或 O(n) 的复杂度性能非常漂亮。但前提是区间有序这个契约不能破坏否则行为未定义。我在实际工作中见过好几次把binary_search用在没排序的 vector 上的案例结果时对时错排查了大半天才发现是数据没排好序浪费了大量时间。3. 排序家族实战sort、stable_sort、partial_sort 与 nth_element排序应该是algorithm里被用得最多的功能但很多人只停留在sort最表层的用法其实这家族里的算法各有分工。3.1 sort 的默认行为与自定义比较器先看最简单的用法#include algorithm #include vector std::vectorint v {5, 2, 8, 1, 9}; std::sort(v.begin(), v.end()); // v : 1 2 5 8 9默认版本用operator升序排列这没啥好说的。重点在于自定义比较器。比如按绝对值排序std::sort(v.begin(), v.end(), [](int a, int b) { return std::abs(a) std::abs(b); });这里有几个要点。第一比较器必须满足严格弱排序comp(a, a)必须为 false如果comp(a, b)为 true则comp(b, a)必须为 false传递性要成立。简单说别写a b这种带等于的比较也别在比较器里塞随机数之类的副作用。我帮某团队排查过一次线上偶发排序结果异常的案例最后定位到是某位开发者在比较器里用了rand()想让排序带点随机性直接把严格弱排序破坏了sort行为直接未定义而且这种 bug 极难复现。第二比较器的捕获方式要想清楚。如果按引用捕获一个临时变量并且这个临时变量在排序过程中被销毁了同样会翻车。实际项目中我习惯用值捕获的 lambda简单安全代价可以忽略不计。3.2 稳定排序的取舍sort不保证相等元素的相对顺序。需要稳定性时用stable_sort。典型场景是先按主键排再按次键排比如学生列表先按班级排班级内再按成绩排。如果第一次用稳定排序排成绩第二次用稳定排序排班级班级内的成绩顺序就能保留下来如果用不稳定排序第一次排序的结果可能被第二次完全打乱。stable_sort的时间和空间开销都比sort大它本质是归并排序需要额外内存如果内存不足会退回 O(n log² n) 的原地算法。数据量小的时候差别不明显但几十万量级以上能明显感受到差距。我的经验是先确认稳定性是不是业务真正需要的约束如果只是排个序看不出差别默认用sort就好别为了一个用不上的特性付出额外成本。3.3 Top Kpartial_sort 与 nth_element 怎么选从一个很大的数组里取出前 10 个最大的数是高频需求。三种写法对比一下// 写法一全排序取前 10 个 std::sort(v.begin(), v.end(), std::greaterint()); // 复杂度 O(n log n) // 写法二partial_sort只排前 10 个 std::partial_sort(v.begin(), v.begin() 10, v.end(), std::greaterint()); // 复杂度 O(n log k)k 10 // 写法三nth_element只保证第 10 个在正确位置 std::nth_element(v.begin(), v.begin() 10, v.end(), std::greaterint()); // 平均复杂度 O(n)但前 10 个内部无序数据量小几百上千时三种写法性能差异几乎可以忽略直接sort最省心。但如果是上万、上百万的数据取 Top Knth_element的优势非常明显。我之前做过一次百万量级的对比nth_element耗时大概是全排序的三分之一到四分之一。前提是你不关心 Top K 内部的先后顺序。顺带强调一点partial_sort输出的前 K 个元素是有序的适合排行榜要展示排序结果的场景nth_element输出的前 K 个内部乱序适合只要这 K 个是啥不关心顺序的场景。按需选择别被名字误导。4. 查找、统计与条件判断find、count、all_of 的使用细节手写循环出现最多的场景就是找元素、计数、做条件判断。这三个需求在algorithm里都有专门的算法家族用起来不只是省代码更重要的是避免边界错误。4.1 find 家族的匹配逻辑std::vectorstd::string names {alice, bob, carol}; // 按值查找 auto it std::find(names.begin(), names.end(), bob); // 按条件查找第一个以 c 开头的名字 auto it2 std::find_if(names.begin(), names.end(), [](const std::string s) { return !s.empty() s[0] c; }); if (it2 ! names.end()) { // 找到了 }find返回迭代器找不到返回end()。有个习惯问题值得说很多人拿返回的迭代器和end()比较一下就完事了但有时候你真正想要的是这个元素在容器里的下标。计算方式是用std::distance(names.begin(), it)它内部针对随机访问迭代器走的是常数时间的减法这个操作本身没有性能负担。另一个细节要特别注意std::find走的是线性扫描 O(n)。如果你在一个std::set或std::map上反复查找千万别用std::find去扫直接用关联容器自己的find成员函数那是 O(log n)。std::find是通用的不知道容器内部结构只能逐个比较这属于工具没挑对的典型场景。4.2 count 与条件统计int cnt std::count(v.begin(), v.end(), 42); int even_cnt std::count_if(v.begin(), v.end(), [](int x) { return x % 2 0; });count返回difference_type也就是迭代器差值类型在 vector 上通常是ptrdiff_t打印或赋值时最好转成合适类型。我见过有人直接把返回值赋给int在元素数量超过 int 范围时溢出虽然这种场景现实中很少见但养成用auto接收的习惯总没错。count_if能替代遍历 if 累加的手写循环。一个容易忽略的点如果你对同一个区间既想计数又想顺便干点别的连续调用两个算法就相当于遍历了两遍。这种情况下可以考虑一次for_each或者在 lambda 里用一个聚合结构同时记录多个统计值。到底哪种方式快要看数据量和缓存友好性我实际测下来数据量小的时候差别不大数据量大时单遍遍历往往更稳。4.3 all_of / any_of / none_of批量做条件判断这三个函数是 C11 加入的专门解决检查整个区间是否满足某个条件这种问题std::vectorint scores {80, 92, 75, 88}; bool all_pass std::all_of(scores.begin(), scores.end(), [](int s) { return s 60; }); bool any_top std::any_of(scores.begin(), scores.end(), [](int s) { return s 90; }); bool none_zero std::none_of(scores.begin(), scores.end(), [](int s) { return s 0; });这三个函数的内部实现其实和手写循环没有本质区别性能也几乎一样但语义清晰得多看代码的人一眼就知道这是在检查全员是否通过而不是去逐行读你的循环逻辑再推断意图。代码可读性带来的维护收益往往比那点微小的性能差异重要得多。我自己的习惯是凡是用到遍历 bool 标记的地方第一反应就换成这三个函数之一。5. 修改序列与有序区间transform、remove 与二分查找的正确姿势这部分是真正干活的算法也是出错率最高的地方。我把高频的几个单独拎出来讲透。5.1 transform批量转换的利器transform用来对区间里的每个元素做映射把结果写到另一个区间。最典型的用法是把所有字符串转成大写#include cctype std::string s hello world; std::transform(s.begin(), s.end(), s.begin(), [](unsigned char c) { return std::toupper(c); });注意目标迭代器传的是s.begin()等于原地变换。transform允许输入输出是同一个区间只要目标位置不越界就行。如果要输出到另一个容器得提前把目标容器resize或用back_inserterstd::vectorint src {1, 2, 3, 4, 5}; std::vectorint dst; dst.reserve(src.size()); std::transform(src.begin(), src.end(), std::back_inserter(dst), [](int x) { return x * x; });用std::back_inserter需要包含iterator头文件虽然很多编译器会通过其他头文件间接包含进来但显式包含是好习惯别依赖这种碰巧能用。transform还有个双区间重载能把两个区间的对应元素做二元操作比如求两个向量对应位置的和。算内积有专门的std::inner_product在numeric里但transform的二元版本在自定义场景下更灵活。我在项目里经常用transform处理配置解析结果原始字符串列表一行transform解析成结构体数组再一行sort排序比手写循环加临时变量清爽得多。这种流水线式的代码风格是algorithm最大的价值体现。5.2 remove 与 erase经典组合拳这是algorithm里最反直觉的一个算法几乎每个新手都会栽一次。std::vectorint v {1, 2, 3, 2, 4, 2}; // 想删除所有值为 2 的元素 std::remove(v.begin(), v.end(), 2); // 你以为 v 变成 {1, 3, 4}实际上并没有remove的语义是把要保留的元素往前挪覆盖掉要删除的位置然后返回一个新的逻辑终点迭代器。它不会真的缩小容器容器末尾还会残留旧元素。必须配合erase才能物理删除auto new_end std::remove(v.begin(), v.end(), 2); v.erase(new_end, v.end()); // 惯用一行写法 v.erase(std::remove(v.begin(), v.end(), 2), v.end());这个remove-erase 惯用法是 C 里最经典的组合拳之一。remove_if配合条件 lambda 可以做批量条件删除原理一样。网上很多代码片段只演示remove省略了erase我估计不少人照抄之后调试了半天才发现容器大小没变。凡是看到remove或unique出现在代码里第一反应就该问后面跟erase了吗5.3 lower_bound / upper_bound二分查找的正确姿势二分查找家族要求区间有序。lower_bound返回第一个不小于给定值的位置upper_bound返回第一个大于给定值的位置equal_range一次拿到两者构成的范围。最常见的应用场景是查值在不在不在的话该插到哪std::vectorint v {1, 3, 5, 7, 9}; int target 6; auto it std::lower_bound(v.begin(), v.end(), target); if (it ! v.end() *it target) { // 找到了 } else { // 没找到it 就是插入位置 v.insert(it, target); }注意别用std::binary_search。虽然它的名字最直观但它只返回 bool 告诉你在不在却不告诉你在哪。binary_search内部其实就是lower_bound套一层判断真要找位置还得用lower_bound。有些团队的编码规范直接要求禁用binary_search逼着大家用lower_bound/equal_range其实是合理的。复杂度要啰嗦一句lower_bound的比较次数是 O(log n)但如果容器不是随机访问的比如std::list每次跳到中间都要 O(n) 地移动迭代器整体退化到 O(n log n) 甚至更差。所以二分查找家族老老实实配 vector、deque、array 用别往 list 上套。5.4 集合运算set_intersection 与 set_difference 的妙用集合运算也要求输入有序但注意这里的集合不是指std::set容器而是有序的区间vector 排完序就能用。比如两个列表求交集std::vectorint a {1, 2, 3, 4, 5}; std::vectorint b {3, 4, 5, 6, 7}; std::vectorint inter; std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(inter)); // inter : 3 4 5set_difference求在 a 中但不在 b 中set_union求并集includes判断 a 是否为 b 的子集。这些算法都是线性复杂度处理两个有序区间时比嵌套循环高效得多关键是不会把边界写错。我在权限系统里经常用set_difference算新增权限和撤销权限两个权限列表排好序一次调用就出结果代码量少还不会错。6. 实战场景完整拆解从需求到代码光看单个算法不够我挑两个真实项目里反复出现的场景把组合用法完整过一遍。6.1 场景一海量数据取 Top K背景某系统每天产生千万级日志需要从里面提取出耗时最长的前 20 条做性能分析。日志已经用std::vectorLogEntry存好了每条含duration字段。最朴素的实现是全排序取前 20但千万级量每次全排一遍既浪费又不必要。改用nth_elementstd::vectorLogEntry logs; // 已填充数据 const size_t k 20; if (logs.size() k) { // 只取前 20 大不关心内部顺序 std::nth_element(logs.begin(), logs.begin() k, logs.end(), [](const LogEntry a, const LogEntry b) { return a.duration b.duration; }); logs.resize(k); } else { // 不足 k 条时按耗时排序一下 std::sort(logs.begin(), logs.end(), [](const LogEntry a, const LogEntry b) { return a.duration b.duration; }); }如果排行榜界面要求 Top 20 按耗时有序列出来就把nth_element换成partial_sort成本略高一点但仍然是 O(n log k)。这个场景最忌讳的就是不看数据量直接sort数据量越大nth_element的优势越明显。我实测千万级数据取 Top 20nth_element比全排序快了将近一个数量级。6.2 场景二文本过滤流水线背景一个配置解析模块从文件读入一批字符串需要做三件事过滤掉空串和以#开头的注释行、排序、去重输出。组合写法std::vectorstd::string lines; // 原始输入 std::vectorstd::string result; result.reserve(lines.size()); // 1. 过滤保留非空且不以 # 开头的行 std::copy_if(lines.begin(), lines.end(), std::back_inserter(result), [](const std::string s) { return !s.empty() s.front() ! #; }); // 2. 排序 std::sort(result.begin(), result.end()); // 3. 去重同样要用 erase 配合 result.erase(std::unique(result.begin(), result.end()), result.end());std::unique把相邻重复元素折叠只保留每组第一个返回新的逻辑终点。所以必须先排序再unique才能去掉所有重复项没排序就unique重复但不相邻的元素会漏掉。这套流水线用三个标准库调用就完成了全程没有手写循环。如果对性能有更高要求第 1 步可以改成remove_if原地过滤省掉copy_if的拷贝开销但可读性会差一点怎么取舍看业务实际。改完之后数据从原始读取到干净输出的每一步都能单独测试哪一步出问题一目了然。7. 踩坑实录常见错误与性能陷阱速查这部分算是我这几年帮别人排查代码的病例本。很多问题不是不会用而是对语义理解差一点。7.1 常见错误的典型现场错误一remove之后不erase。这个前面说过是最经典的坑。凡是看到remove或unique出现在代码里先问一句后面跟erase了吗错误二对未排序区间用lower_bound/binary_search。这个错误最阴险因为它不报错只是结果随机。小数据碰运气可能一直是对的数据量一多就间歇性出错。排查办法很简单调用二分算法之前确认区间必然有序必要时先sort或者调试阶段用is_sorted加个断言。错误三比较器不满足严格弱排序。典型表现是用了或或者比较器里依赖外部可变状态。症状是排序结果随机、甚至死循环。这类 bug 极难复现只能靠 code review 拦。我在团队里的要求很简单比较器必须是纯函数且只用语义实现。错误四在关联容器set/map上用std::find而不是成员find。这不会出错但性能白白退化一个数量级。容器几万个元素时std::find线性扫和成员find对数查找差距肉眼可见。7.2 性能陷阱与复杂度误区先记一张常用算法的复杂度晴雨表算法平均复杂度额外内存备注sortO(n log n)O(log n) 栈不稳定stable_sortO(n log n)可能 O(n)稳定partial_sortO(n log k)O(log k)前 k 个有序nth_elementO(n)O(1)只保证第 n 位正确lower_boundO(log n) 比较O(1)需要随机访问迭代器find / countO(n)O(1)线性扫描remove / uniqueO(n)O(1)必须配合 eraseset_intersectionO(n m)O(1)两个有序区间误区一迷信算法越快越好。nth_element平均 O(n) 确实快但当 k 接近 n 时partial_sort的成本会退化到接近sort数据量在几百以内时微优化意义不大写清楚最重要。误区二忽略迭代器类型对复杂度的影响。lower_bound挂在 list 上是O(log n) 次比较 O(n) 次迭代器前进和线性扫描没什么区别别被名字骗了。误区三并行策略想当然。C17 起sort、transform这些算法支持传入执行策略#include execution std::sort(std::execution::par, v.begin(), v.end());但并行版本要求迭代器随机访问而且比较器必须线程安全。数据量小的时候并行调度开销反而更大我实测几百个元素的数组开并行比串行慢一个数量级。并行策略适合百万级以上的重型操作用之前先做基准测试别为了显得高级硬开。7.3 常见场景速查表我把平时 review 时最常说的几条整理成一张表给团队新人也发过想做什么别怎么写推荐写法顺序查找一个值手写 for ifstd::find查找满足条件的第一个元素手写 for flagstd::find_if统计出现次数手写循环计数std::count判断全体满足条件循环里 bool 累加std::all_of删除满足条件的元素遍历中 eraseerase remove_if取 Top K全排序截断nth_element/partial_sort有序数组查值binary_search猜位置lower_bound 判等批量映射手写 for 赋值std::transform去重两层循环sort unique erase合并两个有序区间手写归并std::merge这张表不是什么金科玉律只是优先考虑某个算法的起点。真遇到特殊需求标准库不一定有点对点的匹配需要组合甚至自定义但先想标准库这个习惯能帮你省掉大量重复劳动。8. 我个人的使用体会最后聊点实践心得不一定适用所有人但都是摸爬滚打出来的。第一个体会是先写语义再考虑优化。我刚工作那阵子写代码特别喜欢炫技总想用最少的代码搞定问题结果可读性一塌糊涂。后来被团队前辈按着用find_if替代手写循环用transform替代 for 赋值代码里的意图变得一目了然。algorithm最大的价值不是省那几行代码而是把我到底想对这个区间做什么直接写出来后面的人维护时不用猜。第二个体会是组合比单个更重要。remove单独用是半吊子配erase才是完整功能unique单独用只能去相邻重复配sort才能全局去重。这些算法就像积木单独看平平无奇组合起来才能搭出复杂的业务逻辑。建议新人在项目里刻意练习先画数据流的草图再选算法拼装这个思路而不是看到一个需求就闷头写循环。第三个体会是工具链要配上。开发时手边常开着一个标准库参考页面不确定复杂度或重载形式就翻一下。现在 C20 的 ranges 库也成熟了写法更简洁#include ranges namespace rv std::ranges::views; auto result v | rv::filter(pred) | rv::transform(fn);但 ranges 库的底层还是algorithm那套算法的语义先把经典算法理解扎实再上 ranges 会更顺。别一上来就追新基础不牢反而更容易踩坑。如果你刚开始用algorithm我的建议是别试图一口气记下所有算法。先把排序、查找、计数、变换、删除这几类高频的在项目里实际用起来用熟了再逐步扩展到集合运算、排列、堆操作。算法是背不熟的用熟了自然就记住了。