1. 背景为什么还要专门研究算法库1.1 STL 六大部分算法是灵魂STLStandard Template Library由六大组件构成容器Container、迭代器Iterator、算法Algorithm、仿函数Function Object、适配器Adapter、空间配置器Allocator。容器负责数据组织而真正对数据做「排序、查找、变换、统计、复制」等通用逻辑的就是算法库集中在两个头文件algorithm排序、查找、变换、分区、堆、排列、集合操作等 100 个算法numeric累加、内积、部分和、扫描等数值算法C17 起新增并行版本。1.2 算法库解决了什么痛点手写 for 循环做「查找 删除 移动」极易出错且不可复用// 手写循环易错、冗长、难以复用 std::vectorint v{1, 2, 3, 4, 5, 2}; for (auto it v.begin(); it ! v.end();) { if (*it 2) it v.erase(it); // 迭代器失效陷阱 else it; }// 算法库一行搞定语义清晰、复杂度有保证、无迭代器失效 v.erase(std::remove(v.begin(), v.end(), 2), v.end());算法库的核心设计理念是与容器解耦算法只与迭代器打交道任何满足迭代器要求的容器vector/list/deque/set/unordered_map…甚至裸数组都能用同一套算法。这是「算法与数据结构分离」的经典范式也是泛型编程思想的直接体现。2. 核心概念理解算法库的三个基石2.1 迭代器类别五档分类算法要求特定的迭代器类别用错类别会导致编译错误或性能退化类别能力支持的主要算法输入迭代器单次单向读取 *it itfind、count、accumulate输出迭代器单次单向写入copy、fill、transform目标端前向迭代器可多次读取/写入remove、unique、partition双向迭代器可 --it 倒退reverse、next_permutation、stable_partition随机访问迭代器支持 it n、it[n]、it1 it2sort、binary_search、nth_element、partial_sort关键坑std::sort 要求随机访问迭代器std::list 只有双向迭代器必须用成员函数 list.sort()内部归并排序std::forward_list 连成员 sort 也是特殊实现。2.2 半开区间 [first, last)所有算法都作用于半开区间first 指向第一个元素last 指向最后一个元素之后的位置。last - first 即元素个数。空区间表示为 first last。这个约定贯穿全部算法也是绝大多数 off-by-one bug 的根源。2.3 谓词Predicate与严格弱序Strict Weak Ordering一元谓词bool pred(const T)如 find_if、count_if、remove_if二元谓词bool comp(const T a, const T b)用于 sort、lower_bound、max_element 等。排序类算法要求比较器满足严格弱序不可反身comp(a,a) 为 false、反对称comp(a,b) 与 comp(b,a) 不能同时为 true、传递性若 comp(a,b) 且 comp(b,c) 则 comp(a,c)。违反会直接导致未定义行为UB——可能崩溃、死循环或结果错误且难以排查。3. API 说明按功能分类速查3.1 排序与有序区操作API复杂度说明sort(first, last, comp)O(N log N)不稳定排序introsort 混合快排堆排插排stable_sort(first, last, comp)O(N log² N)稳定排序相等元素保持相对顺序内存不足退化为归并partial_sort(first, mid, last, comp)O(N log M)把最小的 M 个元素有序放到 [first, mid)nth_element(first, nth, last, comp)平均 O(N)第 n 大元素归位左侧都不大于它右侧都不小于它is_sorted(first, last, comp) / is_sorted_untilO(N)检查是否有序 / 返回首个乱序位置sort_heap(first, last, comp)O(N log N)把堆转为有序区间heap 见 3.63.2 查找API说明find / find_if / find_if_not线性查找返回迭代器或 lastfind_if 用一元谓词find_first_of在区间内查找第一个命中目标集合中任一元素的位置adjacent_find找第一对相邻相等/满足条件的元素search / search_n子序列查找可带谓词search_n 找连续 n 个相同值binary_search(first, last, value, comp)已排序区间二分只返回 boollower_bound(first, last, value, comp)二分找第一个 value 的位置不要求存在upper_bound(first, last, value, comp)二分找第一个 value 的位置equal_range(first, last, value, comp)同时返回 [lower_bound, upper_bound)即相等值区间find_end找最后一次出现子序列的位置3.3 计数、比较与最值API说明count / count_if统计相等/满足谓词的元素个数equal(first1, last1, first2, pred)逐元素比较两个区间是否相等lexicographical_compare字典序比较 或自定义谓词mismatch找两个区间第一处不同的位置返回 pairit1, it2max / min / minmax返回最大/最小/两者的引用initializer_list 或两参数max_element / min_element / minmax_element区间内最大/最小元素迭代器clamp(value, lo, hi)C17 起把值夹在 [lo, hi]comp(hi, lo) 时行为未定义3.4 变换、填充与生成API说明transform(first, last, result, unary_op)一元变换result[i] op(src[i])transform(first1, last1, first2, result, binary_op)二元变换result[i] op(src1[i], src2[i])fill / fill_n填充定值generate / generate_n用函数生成器填充可写有状态 lambdaiota(first, last, value)递增填充 value, value1, value2, ...C113.5 复制、移动与删除API说明copy / copy_if / copy_n / copy_backward复制区间copy_backward 从尾部往前复制防重叠move / move_backward移动语义复制把元素 move 到目标源元素处于有效但未指定状态swap_ranges两个区间逐元素交换remove / remove_if不真正删除把「不满足删除条件」的元素搬到前面返回新的逻辑末尾见坑点 2unique / unique_copy去重相邻重复元素同样只移动不删除可自定义相等谓词erase(first, last) / erase_ifC20 容器直接支持容器成员配合 remove 完成真正删除3.6 分区、堆与排列API说明partition(first, last, pred)不稳定分区谓词 true 的放前面返回分区点stable_partition(first, last, pred)稳定分区保持相对顺序partition_point(first, last, pred)已分区区间找分区点二分is_partitioned检查是否已分区make_heap / push_heap / pop_heap / sort_heap / is_heap堆操作族默认最大堆注意 pop_heap 后要 pop_back、push_heap 前要 push_backnext_permutation / prev_permutation字典序下一个/上一个排列返回是否还有下一个与 sort 配合可枚举全排列3.7 数值算法API说明accumulate(first, last, init, op)顺序累加默认 不要求结合律op 可自定义inner_product内积sum(init a[i]*b[i])partial_sum前缀和out[i] sum(a[0..i])adjacent_difference相邻差out[i] a[i] - a[i-1]reduce / transform_reduceC17可并行版本的 accumulate无序归约要求 op 满足结合律exclusive_scan / inclusive_scanC17可并行前缀和exclusive 不包含当前元素gcd / lcmC17最大公约数/最小公倍数3.8 集合操作有序区间API说明set_union并集去重set_intersection交集set_difference差集第一区间独有set_symmetric_difference对称差includes判断第一区间是否包含第二区间的所有元素注意这些「集合操作」要求两个输入区间都已排序否则结果是错的。4. 详细使用说明可编译实战4.1 排序、稳定排序与自定义比较器#include algorithm #include iostream #include string #include vector struct Record { int id; std::string name; double value; }; int main() { std::vectorint v{5, 2, 8, 1, 9, 3, 7, 4, 6}; // 默认升序 std::sort(v.begin(), v.end()); // 降序传入 std::greaterint()注意在 functional 中 std::sort(v.begin(), v.end(), std::greaterint()); // 自定义 lambda 比较器 std::sort(v.begin(), v.end(), [](int a, int b) { return a b; }); // 稳定排序保持相等元素的相对顺序例如先按 id 排再按 name 排 std::vectorRecord records{{2, b, 1.5}, {1, a, 2.5}, {2, c, 0.5}}; std::stable_sort(records.begin(), records.end(), [](const Record a, const Record b) { return a.id b.id; }); // 结果{1,a} 在前{2,b}、{2,c} 保持原有相对顺序 // partial_sort只要最小的 3 个且有序 std::vectorint big{9, 3, 7, 1, 8, 2, 6}; std::partial_sort(big.begin(), big.begin() 3, big.end()); // big 前 3 个为 {1,2,3}其余无序 // nth_element找第 k 小k4 → 第 5 小元素归位 std::vectorint arr{7, 2, 9, 1, 8, 3, 6, 5, 4}; std::nth_element(arr.begin(), arr.begin() 4, arr.end()); std::cout 第5小 arr[4] \n; // 5左侧都 5右侧都 5 return 0; }4.2 erase-remove 惯用法真正删除元素#include algorithm #include iostream #include vector int main() { std::vectorint v{1, 2, 3, 4, 2, 5, 2}; // remove 把非 2 的元素前移返回新的逻辑末尾erase 真正收缩容量 auto new_end std::remove(v.begin(), v.end(), 2); v.erase(new_end, v.end()); // 惯用法v.erase(std::remove(...), v.end()); // C20 容器直接支持 erase/erase_if一行搞定 std::vectorint v2{1, 2, 3, 4, 2, 5, 2}; std::erase(v2, 2); std::erase_if(v2, [](int x) { return x % 2 0; }); // remove_if erase按条件删除通常配合 find_if 等 std::vectorint v3{1, 2, 3, 4, 5}; v3.erase(std::remove_if(v3.begin(), v3.end(), [](int x) { return x 3; }), v3.end()); // v3 {1, 2, 3} return 0; }4.3 查找线性 vs 二分复杂度选择是关键#include algorithm #include iostream #include vector int main() { std::vectorint sorted{1, 3, 5, 7, 9, 11, 13}; // 已排序区间必须用二分系列不要用 findO(N) bool exists std::binary_search(sorted.begin(), sorted.end(), 7); auto it std::lower_bound(sorted.begin(), sorted.end(), 8); // it 指向第一个 8 的位置即 9 if (it ! sorted.end()) std::cout lower_bound(8) *it \n; auto [lo, hi] std::equal_range(sorted.begin(), sorted.end(), 7); // [lo, hi) 就是所有等于 7 的元素区间 // 无序区间只能用线性查找 std::vectorint unsorted{9, 1, 7, 3, 5}; auto f std::find(unsorted.begin(), unsorted.end(), 7); if (f ! unsorted.end()) std::cout found at index f - unsorted.begin() \n; // find_if按条件找第一个元素 auto f2 std::find_if(unsorted.begin(), unsorted.end(), [](int x) { return x % 2 0; }); return 0; }4.4 transform lambda批量变换与组合#include algorithm #include iostream #include numeric #include string #include vector int main() { std::vectordouble raw{1.0, 2.0, 3.0, 4.0}; std::vectordouble normalized(raw.size()); // 一元变换min-max 归一化到 [0, 1] auto [min_it, max_it] std::minmax_element(raw.begin(), raw.end()); double mn *min_it, mx *max_it; std::transform(raw.begin(), raw.end(), normalized.begin(), [mn, mx](double x) { return (x - mn) / (mx - mn); }); // 二元变换逐元素相加 std::vectordouble other{10.0, 20.0, 30.0, 40.0}; std::vectordouble sum(raw.size()); std::transform(raw.begin(), raw.end(), other.begin(), sum.begin(), [](double a, double b) { return a b; }); // iota 生成序号 transform 拼字符串 std::vectorint idx(raw.size()); std::iota(idx.begin(), idx.end(), 0); std::vectorstd::string labels(raw.size()); std::transform(idx.begin(), idx.end(), labels.begin(), [](int i) { return ch std::to_string(i); }); // accumulate 与 reduceC17 并行 double total std::accumulate(raw.begin(), raw.end(), 0.0); double total_par std::reduce(std::execution::par, raw.begin(), raw.end(), 0.0); return 0; }4.5 分区与堆快速分类与 TopK#include algorithm #include iostream #include vector int main() { std::vectorint v{5, 1, 4, 2, 3}; // partition把偶数放前面返回分区点 auto p std::partition(v.begin(), v.end(), [](int x) { return x % 2 0; }); // [begin, p) 全为偶数[p, end) 全为奇数 // partition_point在已分区区间定位分区点二分O(log N) auto pp std::partition_point(v.begin(), v.end(), [](int x) { return x % 2 0; }); // 堆维护 TopK 场景例海量数据中最大的 5 个 std::vectorint top5{3, 1, 4, 1, 5}; // 先填 5 个 std::make_heap(top5.begin(), top5.end()); // 最大堆堆顶最大 for (int x : {9, 2, 6, 8}) { if (x top5.front()) { // 新元素比当前堆顶最大小才有机会 std::pop_heap(top5.begin(), top5.end()); top5.back() x; // 把堆顶换掉 std::push_heap(top5.begin(), top5.end()); } } // 用最小堆语义greater 比较器即可维护「最大 5 个」这里做示意 return 0; }4.6 全排列与集合操作#include algorithm #include iostream #include vector int main() { std::vectorint p{1, 2, 3}; std::sort(p.begin(), p.end()); // next_permutation 要求初始有序才能枚举全排列 do { for (int x : p) std::cout x; std::cout ; } while (std::next_permutation(p.begin(), p.end())); // 输出123 132 213 231 312 321 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, 5} return 0; }4.7 C20 ranges 算法管道式现代写法#include algorithm #include iostream #include ranges #include vector int main() { std::vectorint v{5, 2, 8, 1, 9, 3, 7}; // ranges::sort直接对容器操作不需要 begin/end std::ranges::sort(v); // 视图管道过滤偶数 → 平方 → 求和惰性求值 auto sum std::ranges::fold_left( v | std::views::filter([](int x) { return x % 2 0; }) | std::views::transform([](int x) { return x * x; }), 0, std::plus{}); std::cout sum \n; // 投影projection按结构体字段排序 struct Record { int id; std::string name; }; std::vectorRecord rs{{3, c}, {1, a}, {2, b}}; std::ranges::sort(rs, std::less{}, Record::id); // 第三个参数是投影 return 0; }C20 起算法增加 ranges 版本前缀 ranges::可直接接受容器或 view、支持投影、约束更友好编译期错误信息更好。但传统 algorithm 版本在现有代码库中仍是绝对主力。5. 常错点/坑18 条高频问题坑说明与正确做法1已排序区间却用 find/find_if复杂度 O(N) vs 二分 O(log N)已排序务必用 binary_search/lower_bound/equal_range2以为 remove/remove_if 真的删除了元素remove 只是把保留元素搬到前面并返回新逻辑末尾必须 v.erase(new_end, v.end()) 才能收缩C20 用 std::erase/erase_if 一行解决3需要稳定排序却用 sortsort 不稳定相等元素顺序不确定需要保持相对顺序用 stable_sort代价是可能 O(N log² N)4比较器不满足严格弱序例如 [](double a, double b){ return a b; } 遇到 NaN、或比较器依赖可变外部状态 → 未定义行为可能死循环/崩溃5用 binary_search 想拿位置binary_search 只返回 bool要迭代器用 lower_bound第一个 v或 equal_range6对 std::list 调 std::sortlist 是双向迭代器不满足 sort 要求编译报错用 list.sort() 成员函数7partial_sort 与 nth_element 混淆partial_sort(first, mid, last) 把前 M 个有序nth_element 只保证第 n 个归位、左右分区不保证有序但平均 O(N)8transform 目标区间与输入重叠且从前往后复制输出迭代器与输入重叠时应改用 copy_backward 或保证目标空间足够先 resize否则越界/未定义行为9accumulate 用 int 累加浮点/大数溢出accumulate(v.begin(), v.end(), 0) 对 double 向量会截断为 int初始值必须给对类型 0.0大数用 long long/double10max/min 返回引用传临时对象悬挂const auto m std::max(a, b); 若 a/b 是临时值则悬垂按值接收或对容器元素操作11迭代器区间边界写错off-by-one半开区间 [first, last)sort(v.begin(), v.end()) 是全部元素v.end() 不可解引用last - first 才是个数12谓词是「有状态」函数对象被复制算法可能复制谓词尤其 remove_if、partition依赖内部状态计数的 lambda 结果不可靠优先用外部变量捕获而非成员状态13忘记包含头文件algorithm 缺了编译报 sort 未声明数值算法在 numericstd::greater 在 functionalstd::execution 在 execution且需链接 tbb 等并行后端14pop_heap 后忘了 pop_back堆操作 pop_heap 只把堆顶移到末尾需配合 v.pop_back() 真正移除push_heap 前需先 push_back 把新元素放末尾15对 const 容器/std::set 的 const 迭代器调排序类算法排序、remove、reverse 等需要可写迭代器const 容器只能做只读算法find/count/accumulate16set_union/set_intersection 输入未排序集合操作要求两个输入区间有序否则结果无意义文档虽没强制但结果是未定义行为级别的错误17iota 想生成带步长序列iota 只支持 递增value, value1, ...要步长用 generate_n 有状态 lambda18并行版 reduce/transform_reduce 的 op 不满足结合律/交换律并行归约以任意顺序合并op 必须是结合律交换律如 、min、max浮点 顺序不同结果会有微小差异需要确定性时用 accumulate6. 总结6.1 核心要点速记容器管存储算法管操作算法只依赖迭代器与具体容器解耦这是 STL 最伟大的设计先判断迭代器类别再选算法随机访问迭代器才能 sort/binary_search/nth_element双向迭代器只能 reverse/permutation有序区间的红利一旦数据有序lower_bound/equal_range/set_intersection 把 O(N) 降到 O(log N)remove 不删除erase-remove 惯用法是删除元素的唯一正确姿势C20 后 std::erase_if 更省心比较器永远要满足严格弱序这是排序/二分/堆全部有序算法的共同前提违反即 UBC17 起有并行版本std::execution::par reduce/sort/for_each但要注意 op 结合律与浮点确定性C20 起有 ranges 版本ranges::sort、投影、视图管道新代码推荐使用旧代码库渐进迁移。6.2 适用场景速查场景首选算法全量排序sort不稳定/ stable_sort稳定只要 TopKnth_elementK 个无序或 partial_sortK 个有序找是否存在/位置有序binary_search/lower_bound无序find/find_if删除符合条件的元素erase_ifC20/ remove_if erase批量映射/过滤transform / copy_if去重unique erase先 sort统计/求和/均值accumulate顺序确定/ reduce并行找出最大值及位置max_element枚举全排列next_permutation初始需有序两个有序集合运算set_intersection 等7. FAQ 速查表Q1sort 和 stable_sort 什么时候选哪个A不关心相等元素相对顺序选 sort更快、内存 O(log N)需要保持相对顺序如先按主键再按次键的多级排序选 stable_sort。Q2lower_bound 和 binary_search 有什么区别Abinary_search 只返回「是否存在」的 boollower_bound 返回第一个 value 的迭代器可能指向不存在的插入位置。查位置用 lower_bound查存在性两者皆可lower_bound 后需再判断 ! end *it value。Q3为什么 remove 不真的删除A算法只通过迭代器操作无法知道容器的容量管理接口erase 是容器成员。remove 把保留元素前移覆盖被删元素返回新逻辑末尾由调用者调用 erase 收缩——这就是 erase-remove 惯用法。Q4自定义比较器怎么写才安全A满足严格弱序三性质不可反身、反对称、传递。用 a b 系运算组合如 a.id b.id || (a.id b.id a.name b.name)最安全不要用 不满足不可反身不要依赖可变全局状态。Q5std::accumulate 和 std::reduce 结果会不一样吗A对浮点数会——reduce 并行时合并顺序不定浮点加法不满足结合律结果可能有微小差异需要完全确定的结果用 accumulate需要并行加速且能接受微小误差用 reduce。Q6对 std::unordered_map 能用 std::sort 吗A不能其迭代器不是随机访问迭代器且元素本无序。要排序可把元素拷到 std::vectorstd::pair... 再排序或直接用 std::map红黑树自动有序。Q7C20 的 std::erase_if 和旧式 erase-remove 什么关系Astd::erase_if 是 C20 新增的容器自由函数内部等价于 erase-remove 惯用法但更简洁、避免写错直接 std::erase_if(v, pred)。Q8怎么枚举一个序列的全部排列A先 sort然后 do { ... } while (std::next_permutation(...))。注意必须在排序后的状态开始否则会漏掉前面的排列。