C++标准库算法全景解析
一、非变异序列操作
这类算法仅读取数据，不会修改容器内的元素值。
1.1 元素查找
search、find 及其变体用于定位特定元素：
#include <vector>
#include <algorithm>
std::vector<int> data = {10, 25, 30, 45, 50, 65};
// 查找首个匹配值
auto pos = std::find(data.begin(), data.end(), 30);
if (pos != data.end()) {
std::cout << "位置: " << std::distance(data.begin(), pos); // 输出2
}
// 条件查找首个偶数
auto even_pos = std::find_if(data.begin(), data.end(),
[](int val) { return val % 2 == 0; });
// 查找子序列末次出现位置
std::vector<int> pattern = {25, 30};
auto last_occurrence = std::find_end(data.begin(), data.end(),
pattern.begin(), pattern.end());
1.2 统计与遍历
std::vector<int> scores = {85, 92, 78, 92, 88, 92};
// 统计特定值出现次数
int excellent = std::count(scores.begin(), scores.end(), 92); // 3
// 统计满足条件的元素
int passed = std::count_if(scores.begin(), scores.end(),
[](int s) { return s >= 60; }); // 6
// 遍历修改（注意：for_each可修改元素）
std::for_each(scores.begin(), scores.end(), [](int& s) { s += 5; });
1.3 范围比较
std::vector<int> seq1 = {1, 2, 3, 4};
std::vector<int> seq2 = {1, 2, 5, 4};
// 判断两范围是否相等
bool identical = std::equal(seq1.begin(), seq1.end(), seq2.begin()); // false
// 定位首个差异点
auto diff = std::mismatch(seq1.begin(), seq1.end(), seq2.begin());
// diff.first 指向3, diff.second 指向5
1.4 逻辑判定
std::vector<int> temps = {15, 22, 18, 30, 25};
bool all_positive = std::all_of(temps.begin(), temps.end(),
[](int t) { return t > 0; }); // true
bool any_hot = std::any_of(temps.begin(), temps.end(),
[](int t) { return t > 28; }); // true
bool none_freezing = std::none_of(temps.begin(), temps.end(),
[](int t) { return t < 0; }); // true
二、变异序列操作
这类算法会修改容器内容或产生新的数据序列。
2.1 复制与转换
std::vector<int> source = {2, 3, 4, 5, 6};
std::vector<int> destination;
// 条件复制（仅复制奇数）
std::copy_if(source.begin(), source.end(),
std::back_inserter(destination),
[](int n) { return n % 2 == 1; }); // {3, 5}
// 元素变换
std::vector<int> squares(source.size());
std::transform(source.begin(), source.end(), squares.begin(),
[](int n) { return n * n; }); // {4, 9, 16, 25, 36}
// 双序列运算
std::vector<int> a = {10, 20, 30};
std::vector<int> b = {1, 2, 3};
std::vector<int> diff(a.size());
std::transform(a.begin(), a.end(), b.begin(), diff.begin(),
std::minus<int>()); // {9, 18, 27}
2.2 替换与删除
std::vector<int> values = {5, 10, 5, 20, 5};
// 直接替换
std::replace(values.begin(), values.end(), 5, 99);
// {99, 10, 99, 20, 99}
// 条件替换
std::replace_if(values.begin(), values.end(),
[](int v) { return v > 50; }, 0);
// 删除-擦除惯用法（erase-remove idiom）
std::vector<int> nums = {1, 2, 3, 2, 4, 2, 5};
nums.erase(
std::remove(nums.begin(), nums.end(), 2),
nums.end()
); // {1, 3, 4, 5}
// 去重（仅移除相邻重复）
std::vector<int> dup = {1, 1, 2, 2, 2, 3, 3};
auto new_end = std::unique(dup.begin(), dup.end());
dup.erase(new_end, dup.end()); // {1, 2, 3}
2.3 重排操作
std::vector<int> arr = {10, 20, 30, 40, 50};
// 反转
std::reverse(arr.begin(), arr.end()); // {50, 40, 30, 20, 10}
// 旋转（使中间元素成为首元素）
std::rotate(arr.begin(), arr.begin() + 2, arr.end());
// {30, 20, 10, 50, 40}
// 随机打乱
#include <random>
std::random_device rd;
std::mt19937 gen(rd());
std::shuffle(arr.begin(), arr.end(), gen);
三、排序与有序范围操作
3.1 排序算法
std::vector<int> items = {64, 34, 25, 12, 22, 11, 90};
// 快速排序（不稳定）
std::sort(items.begin(), items.end());
// 自定义比较：降序
std::sort(items.begin(), items.end(), std::greater<int>());
// 稳定排序
std::vector<std::pair<int, char>> pairs = {{2, 'B'}, {1, 'A'}, {2, 'C'}};
std::stable_sort(pairs.begin(), pairs.end(),
[](auto& x, auto& y) { return x.first < y.first; });
// 结果: {(1,'A'), (2,'B'), (2,'C')} — 相对顺序保持
// 部分排序（前k个最小元素有序）
std::partial_sort(items.begin(), items.begin() + 3, items.end());
// 前3个为最小且有序，其余无序
3.2 选择算法
// 快速选择：使第n个位置元素处于正确位置
std::vector<int> data = {9, 3, 7, 1, 5, 8, 2};
std::nth_element(data.begin(), data.begin() + 3, data.end());
// data[3] = 5，左侧都≤5，右侧都≥5
3.3 二分查找
前提：序列必须有序
std::vector<int> sorted = {10, 20, 30, 30, 40, 50};
// 存在性测试
bool has_30 = std::binary_search(sorted.begin(), sorted.end(), 30); // true
// 下界：首个不小于目标的位置
auto lb = std::lower_bound(sorted.begin(), sorted.end(), 30);
// 指向第一个30，索引2
// 上界：首个大于目标的位置
auto ub = std::upper_bound(sorted.begin(), sorted.end(), 30);
// 指向40，索引4
// 等值范围
auto range = std::equal_range(sorted.begin(), sorted.end(), 30);
// range.first=lb, range.second=ub，跨度为2个元素
3.4 归并操作
std::vector<int> left = {1, 3, 5, 7};
std::vector<int> right = {2, 4, 6, 8};
std::vector<int> merged(left.size() + right.size());
std::merge(left.begin(), left.end(), right.begin(), right.end(),
merged.begin()); // {1, 2, 3, 4, 5, 6, 7, 8}
四、堆操作
STL堆默认为大根堆（父节点≥子节点）。
std::vector<int> heap = {3, 1, 4, 1, 5, 9, 2, 6};
// 建堆
std::make_heap(heap.begin(), heap.end()); // {9, 6, 4, 3, 5, 1, 2, 1}
// 入堆
heap.push_back(7);
std::push_heap(heap.begin(), heap.end()); // 7上浮至正确位置
// 出堆（将堆顶移至末尾）
std::pop_heap(heap.begin(), heap.end());
int top = heap.back(); // 9
heap.pop_back();
// 堆排序
std::sort_heap(heap.begin(), heap.end()); // 升序排列
五、极值查询
// 两值比较
int x = 42, y = 17;
int smaller = std::min(x, y); // 17
int larger = std::max(x, y); // 42
int clamped = std::clamp(100, 0, 50); // C++17，限制在[0,50]，结果50
// initializer_list版本
int list_min = std::min({5, 2, 8, 1, 9}); // 1
// 范围极值
std::vector<int> data = {33, 11, 44, 22, 55};
auto min_it = std::min_element(data.begin(), data.end()); // 指向11
auto max_it = std::max_element(data.begin(), data.end()); // 指向55
// 同时获取最小最大值（C++11）
auto minmax = std::minmax_element(data.begin(), data.end());
// minmax.first 指向11, minmax.second 指向55
六、数值运算（<numeric>）
6.1 累积与内积
#include <numeric>
std::vector<int> nums = {1, 2, 3, 4, 5};
// 求和
int total = std::accumulate(nums.begin(), nums.end(), 0); // 15
// 求积
int product = std::accumulate(nums.begin(), nums.end(), 1,
std::multiplies<int>()); // 120
// 内积（点积）
std::vector<int> weights = {2, 3, 4, 5, 6};
int weighted_sum = std::inner_product(nums.begin(), nums.end(),
weights.begin(), 0); // 1*2 + 2*3 + 3*4 + 4*5 + 5*6 = 70
6.2 序列生成
// 填充连续递增序列
std::vector<int> seq(5);
std::iota(seq.begin(), seq.end(), 100); // {100, 101, 102, 103, 104}
// 前缀和
std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> prefix(src.size());
std::partial_sum(src.begin(), src.end(), prefix.begin());
// {1, 3, 6, 10, 15}
// 相邻差分
std::vector<int> diff(src.size());
std::adjacent_difference(src.begin(), src.end(), diff.begin());
// {1, 1, 1, 1, 1}
七、集合与生成操作
7.1 集合运算
要求输入序列已排序：
std::vector<int> set_a = {1, 2, 3, 4, 5};
std::vector<int> set_b = {4, 5, 6, 7, 8};
std::vector<int> output;
// 并集
std::set_union(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(),
std::back_inserter(output)); // {1,2,3,4,5,6,7,8}
// 交集
output.clear();
std::set_intersection(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(),
std::back_inserter(output)); // {4,5}
// 差集（A-B）
output.clear();
std::set_difference(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(),
std::back_inserter(output)); // {1,2,3}
// 对称差集
output.clear();
std::set_symmetric_difference(set_a.begin(), set_a.end(),
set_b.begin(), set_b.end(), std::back_inserter(output)); // {1,2,3,6,7,8}
// 包含判定
bool is_subset = std::includes(set_a.begin(), set_a.end(),
set_b.begin(), set_b.end()); // false
7.2 自定义生成
// 用生成器填充
std::vector<int> generated(5);
int counter = 0;
std::generate(generated.begin(), generated.end(), [&]() {
return counter++ * 10; // 生成器：0, 10, 20, 30, 40
});
// 填充前n个
std::vector<int> partial(5, -1);
std::generate_n(partial.begin(), 3, [&]() {
static int seed = 1;
return seed *= 2; // 2, 4, 8, -1, -1
});
八、关键概念辨析
| 对比项 | sort | stable_sort |
|---|---|---|
| 稳定性 | 不稳定 | 稳定 |
| 算法 | Introsort（快速排序+堆排序+插入排序） | 归并排序 |
| 空间复杂度 | O(log n) | O(n) |
| 适用场景 | 一般排序，无稳定性要求 | 多关键字排序，需保持原始相对顺序 |
erase-remove 惯用法原理：
remove 算法通过覆盖移动元素，返回新的逻辑终点，但不会改变容器大小。必须与 erase 配合才能实际删除元素：
container.erase(std::remove(container.begin(), container.end(), value),
container.end());
依赖有序性的算法：
- 二分查找族：binary_search, lower_bound, upper_bound, equal_range
- 归并操作：merge, inplace_merge
- 集合运算：set_union, set_intersection, set_difference, includes
