C++ 标准库算法进阶

更新时间：2026-08-27。本文是 languages/cpp/ 主题高手层第 19 篇。入门篇介绍了 sort/find/binary_search 的基本用法，这篇进阶：为什么有的排序是 sort、有的是 stable_sort、还有 partial_sort 和 nth_element？lower_bound 的一大家子怎么选？C++17 的"并行算法"怎么用？以及——算法库和手写循环，谁更快？

本文要回答的问题

• 排序家族 sort / stable_sort / partial_sort / nth_element 各适用什么场景？
• 二分查找家族 lower_bound / upper_bound / equal_range 怎么选？
• C++17 并行算法（执行策略）怎么用？什么时候能加速？
• 手写循环和算法库哪个快？为什么"不用算法库"常常是错的？

排序家族：按需选型

算法	复杂度	稳定性	用途
sort	O(n log n)	不稳定	通用排序（默认）
stable_sort	O(n log² n) 最坏	稳定	等值元素保持原序
partial_sort	O(n log k)	不稳定	只排前 k 个
nth_element	平均 O(n)	不稳定	找第 k 小/中位数，不排序

#include <algorithm>
#include <vector>

std::vector<int> v{5, 3, 9, 1, 7, 2, 8, 4, 6};

std::sort(v.begin(), v.end());          // 全排序

// 只要前 3 小：partial_sort 比全排序快
std::vector<int> v2{5, 3, 9, 1, 7};
std::partial_sort(v2.begin(), v2.begin() + 3, v2.end());
// v2 前 3 个是 1,2,3，后面乱序

// 只要中位数/第 k 小：nth_element 最快
std::vector<int> v3{5, 3, 9, 1, 7, 2, 8, 4, 6};
std::nth_element(v3.begin(), v3.begin() + 4, v3.end());
// v3[4] 就是第 5 小（中位数），两侧乱序

工程经验：只找中位数或 top-k 时，别 sort 再取前几个——nth_element 和 partial_sort 快一个量级。

二分查找家族

前提：数据已排序。四个兄弟：

算法	返回值
binary_search	bool：是否存在
lower_bound	第一个 ≥ 目标的位置
upper_bound	第一个 > 目标的位置
equal_range	lower_bound + upper_bound 的对

#include <algorithm>

std::vector<int> v{1, 2, 2, 2, 3, 5};

bool found = std::binary_search(v.begin(), v.end(), 2);   // true

auto lo = std::lower_bound(v.begin(), v.end(), 2);   // 指向第一个 2
auto hi = std::upper_bound(v.begin(), v.end(), 2);   // 指向 3
int count = hi - lo;    // 3（2 的个数）

auto [l, h] = std::equal_range(v.begin(), v.end(), 2);   // C++17

记忆：lower_bound 找"插入点"——要插入一个新值并保持有序，插在它指向的位置。 这就是 insert 前找位置的标准做法。

数值与变换算法

算法	作用
accumulate	求和/累加（可指定初值和二元操作）
iota	填充递增序列
transform	逐元素变换（一/两个输入序列）
generate	用函数填充序列
count_if	统计满足条件的个数
adjacent_difference / partial_sum	差分 / 前缀和

#include <numeric>

std::vector<int> v(10);
std::iota(v.begin(), v.end(), 1);   // 1,2,3,...,10

int sum = std::accumulate(v.begin(), v.end(), 0);   // 55

std::vector<int> doubled;
doubled.reserve(v.size());
std::transform(v.begin(), v.end(), std::back_inserter(doubled),
               [](int x) { return x * 2; });

back_inserter 是输出迭代器适配器——让算法能往容器尾部追加，是 transform/copy 的常用搭档。

并行算法（C++17 执行策略）

C++17 给大多数算法加上了执行策略参数，让算法自动并行：

#include <execution>

std::vector<int> v(10000000, 1);

// 串行
std::sort(v.begin(), v.end());

// 并行（多核加速）
std::sort(std::execution::par, v.begin(), v.end());

// 并行 + 向量化
std::sort(std::execution::par_unseq, v.begin(), v.end());

执行策略	含义
std::execution::seq	串行（默认）
std::execution::par	多线程并行
std::execution::par_unseq	并行 + SIMD 向量化
std::execution::unseq	仅向量化（C++20）

注意：并行算法要求迭代器是随机访问、操作不能有数据竞争（不能改共享状态）、且不抛异常（抛了未定义）。数据量小时并行反而慢（线程创建开销），数据规模够大（百万级）才用 par。

// 数据量小时，串行反而快
std::vector<int> small(100);
std::sort(std::execution::seq, small.begin(), small.end());  // 不必并行

手写循环 vs 算法库

对比项	手写循环	标准库算法
可读性	一般（循环+临时变量）	好（意图即名字）
正确性	易越界/漏边界	迭代器区间保证
性能	未必快	编译器/库深度优化
并行化	要自己写线程	par 一行搞定
现代替代	——	范围 for + 算法组合

经验：能用算法库表达的操作，用算法库。 标准库实现（GCC libstdc++、LLVM libc++）经过深度优化（如 sort 是 introsort 混合快排+堆排），手写通常追不上。性能敏感场景的误区是"自己写循环更快"——先测再说，perf 会告诉你答案。

与本站性能主线衔接

• 排序性能：sort 的 introsort 在近似有序数据上会退化，可用 perf 实测不同数据形态。
• 并行计算：execution::par 与 多核并发 一脉相承，受缓存带宽限制。
• 容器配合：算法 + 容器选型 是 STL 的两条腿。
• 编译器优化：算法的内联展开依赖 编译选项（-O2/-O3 才够）。

一句话总结

算法库按需选型：全排序用 sort/stable_sort，只要前 k 个用 partial_sort，只要第 k 个用 nth_element（O(n)），二分用 lower_bound 系列找插入点；C++17 用 execution::par 并行大数组，能用算法库表达就别手写循环。

---

上一篇：流式 IO 深挖　下一篇：内存池与性能