C++ STL 核心算法全景解析与实战指南
1. 只读与非修改序列操作
此类算法在遍历容器时，仅进行读取或条件判断，绝不会修改底层元素的值或容器的物理结构。
1.1 元素检索 (find 家族)
std::find：在区间内线性查找首个与目标值匹配的元素。std::find_if：查找首个使自定义谓词返回true的元素。std::find_end：在主干序列中查找子序列最后一次出现的起始位置。
#include <vector>
#include <algorithm>
#include <iostream>
std::vector<int> data_set = {10, 20, 30, 40, 50};
// 精确匹配查找
auto iter = std::find(data_set.begin(), data_set.end(), 30);
if (iter != data_set.end()) {
std::cout << "Located target: " << *iter << '\n';
}
// 条件谓词查找
auto cond_iter = std::find_if(data_set.begin(), data_set.end(), [](int val) {
return val > 35;
});
// cond_iter 指向 40
// 子序列查找
std::vector<int> sub_seq = {30, 40};
auto sub_iter = std::find_end(data_set.begin(), data_set.end(), sub_seq.begin(), sub_seq.end());
if (sub_iter != data_set.end()) {
std::cout << "Subsequence offset: " << std::distance(data_set.begin(), sub_iter) << '\n';
}
1.2 统计与遍历
std::count/std::count_if：统计满足特定值或谓词条件的元素数量。std::for_each：对区间内的每个元素执行指定的可调用对象。
std::vector<int> metrics = {12, 45, 12, 89, 12, 33};
int target_count = std::count(metrics.begin(), metrics.end(), 12);
int high_val_count = std::count_if(metrics.begin(), metrics.end(), [](int m) {
return m > 30;
});
std::for_each(metrics.begin(), metrics.end(), [](int& m) {
m += 10; // 通过引用修改元素值，但不改变容器结构
});
1.3 比较与断言
std::equal/std::mismatch：判断两个序列是否一致，或定位首个差异点。std::all_of/std::any_of/std::none_of：验证区间内元素是否全部、部分或完全不满足特定条件。
std::vector<int> seq_a = {100, 200, 300};
std::vector<int> seq_b = {100, 200, 999};
bool is_identical = std::equal(seq_a.begin(), seq_a.end(), seq_b.begin());
auto mismatch_pair = std::mismatch(seq_a.begin(), seq_a.end(), seq_b.begin());
// mismatch_pair.first 指向 300, mismatch_pair.second 指向 999
std::vector<int> temperatures = {22, 24, 21, 25};
bool all_above_zero = std::all_of(temperatures.begin(), temperatures.end(), [](int t) { return t > 0; });
bool has_freezing = std::any_of(temperatures.begin(), temperatures.end(), [](int t) { return t <= 0; });
bool none_extreme = std::none_of(temperatures.begin(), temperatures.end(), [](int t) { return t > 50; });
2. 序列修改与元素操作
这类算法会直接改变容器内元素的值、顺序，或改变容器的逻辑边界。
2.1 拷贝与转换
std::vector<int> source = {11, 22, 33, 44, 55};
std::vector<int> destination(source.size());
std::copy(source.begin(), source.end(), destination.begin());
std::vector<int> filtered;
std::copy_if(source.begin(), source.end(), std::back_inserter(filtered), [](int v) {
return v % 2 != 0; // 提取奇数，back_inserter 自动处理扩容
});
std::vector<int> base = {1, 2, 3};
std::vector<int> multiplier = {10, 20, 30};
std::vector<int> product(base.size());
// 双序列转换
std::transform(base.begin(), base.end(), multiplier.begin(), product.begin(), [](int a, int b) {
return a * b;
});
2.2 替换与移除
std::remove 系列算法并不会真正销毁元素，而是将保留的元素前移，并返回新的逻辑尾迭代器。必须配合 erase 才能真正收缩容器（Erase-Remove 惯用法）。
std::vector<int> values = {5, 10, 15, 10, 20};
std::replace(values.begin(), values.end(), 10, 99);
std::vector<int> cloned;
std::replace_copy(values.begin(), values.end(), std::back_inserter(cloned), 99, 0);
// Erase-Remove 惯用法
auto new_logical_end = std::remove(values.begin(), values.end(), 99);
values.erase(new_logical_end, values.end());
values = {2, 4, 6, 7, 8, 9};
values.erase(
std::remove_if(values.begin(), values.end(), [](int v) { return v % 2 == 0; }),
values.end()
);
2.3 重排操作
std::vector<int> raw_data = {1, 1, 2, 3, 3, 3, 4};
auto unique_end = std::unique(raw_data.begin(), raw_data.end());
raw_data.erase(unique_end, raw_data.end()); // 去除相邻重复项
std::reverse(raw_data.begin(), raw_data.end());
std::vector<int> ring = {10, 20, 30, 40, 50};
std::rotate(ring.begin(), ring.begin() + 3, ring.end()); // 40 成为首元素
#include <random>
std::vector<int> deck = {1, 2, 3, 4, 5, 6};
std::mt19937 rng(std::random_device{}());
std::shuffle(deck.begin(), deck.end(), rng); // 现代 C++ 随机打乱
3. 排序、检索与合并
3.1 排序算法
std::vector<int> scores = {85, 92, 78, 92, 88};
std::sort(scores.begin(), scores.end(), std::greater<int>()); // 降序排列
struct Record { int id; int score; };
std::vector<Record> records = {{1, 90}, {2, 80}, {3, 90}};
std::stable_sort(records.begin(), records.end(), [](const Record& a, const Record& b) {
return a.score > b.score; // 保证相同分数的 id 相对顺序不变
});
std::vector<int> pool = {45, 12, 89, 33, 67, 21};
std::partial_sort(pool.begin(), pool.begin() + 3, pool.end()); // 前3个是最小的且有序
// 将第 N 小的元素放置在正确位置，其左侧均小于它，右侧均大于它
std::nth_element(pool.begin(), pool.begin() + 2, pool.end());
3.2 二分查找与归并
以下算法要求输入序列必须处于已排序状态，否则会导致未定义行为或错误结果。
std::vector<int> sorted_ids = {101, 104, 104, 108, 110};
bool has_104 = std::binary_search(sorted_ids.begin(), sorted_ids.end(), 104);
auto lower = std::lower_bound(sorted_ids.begin(), sorted_ids.end(), 104); // 指向第一个 104
auto upper = std::upper_bound(sorted_ids.begin(), sorted_ids.end(), 104); // 指向 108
std::vector<int> list_a = {1, 3, 5};
std::vector<int> list_b = {2, 4, 6};
std::vector<int> combined(list_a.size() + list_b.size());
std::merge(list_a.begin(), list_a.end(), list_b.begin(), list_b.end(), combined.begin());
4. 堆结构操作
STL 提供了一套基于迭代器范围的堆操作接口，默认构建大顶堆。
std::vector<int> priority_queue = {30, 10, 50, 20, 40};
std::make_heap(priority_queue.begin(), priority_queue.end());
priority_queue.push_back(60);
std::push_heap(priority_queue.begin(), priority_queue.end()); // 维护堆性质
std::pop_heap(priority_queue.begin(), priority_queue.end()); // 最大值移至末尾
int top_val = priority_queue.back();
priority_queue.pop_back(); // 物理移除
std::sort_heap(priority_queue.begin(), priority_queue.end()); // 堆排序，转为升序序列
5. 极值探测
int x = 15, y = 25;
int minimum = std::min(x, y);
int maximum = std::max({10, 50, 30, 20}); // 支持初始化列表
std::vector<int> sensor_readings = {42, 17, 89, 23, 56};
auto min_iter = std::min_element(sensor_readings.begin(), sensor_readings.end());
auto max_iter = std::max_element(sensor_readings.begin(), sensor_readings.end());
// 一次性获取最小和最大元素的迭代器对
auto bounds = std::minmax_element(sensor_readings.begin(), sensor_readings.end());
6. 数值计算
这些算法定义在 <numeric> 头文件中，专注于数学与统计运算。
#include <numeric>
std::vector<int> cash_flows = {100, -50, 200, -30};
int net_balance = std::accumulate(cash_flows.begin(), cash_flows.end(), 0);
std::vector<int> weights = {1, 2, 3};
std::vector<int> values = {10, 20, 30};
int weighted_sum = std::inner_product(weights.begin(), weights.end(), values.begin(), 0);
std::vector<int> indices(5);
std::iota(indices.begin(), indices.end(), 100); // 填充为 100, 101, 102, 103, 104
std::vector<int> daily_sales = {10, 20, 30, 40};
std::vector<int> cumulative_sales(daily_sales.size());
std::partial_sum(daily_sales.begin(), daily_sales.end(), cumulative_sales.begin()); // 前缀和
std::vector<int> diffs(daily_sales.size());
std::adjacent_difference(daily_sales.begin(), daily_sales.end(), diffs.begin()); // 相邻差分
7. 集合与生成操作
std::vector<int> generated(5);
int seed = 10;
std::generate(generated.begin(), generated.end(), [&seed]() { return seed += 5; });
std::vector<int> base_set = {1, 2, 3, 4, 5};
std::vector<int> sub_set = {2, 4};
bool is_subset = std::includes(base_set.begin(), base_set.end(), sub_set.begin(), sub_set.end());
std::vector<int> set_a = {1, 2, 3, 4};
std::vector<int> set_b = {3, 4, 5, 6};
std::vector<int> union_set, intersect_set, diff_set, sym_diff_set;
std::set_union(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(), std::back_inserter(union_set));
std::set_intersection(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(), std::back_inserter(intersect_set));
std::set_difference(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(), std::back_inserter(diff_set));
std::set_symmetric_difference(set_a.begin(), set_a.end(), set_b.begin(), set_b.end(), std::back_inserter(sym_diff_set));
8. 核心机制与常见陷阱
8.1 排序算法的稳定性差异
std::sort 底层通常采用 Introsort（内省排序），在提供 O(n log n) 平均时间复杂度的同时，不保证相等元素的相对顺序（不稳定）。当业务逻辑要求保留原始插入顺序时（如多级排序），必须使用 std::stable_sort。后者基于归并排序变体，虽然稳定，但通常需要额外的 O(n) 内存空间。
8.2 Erase-Remove 惯用法的底层逻辑
std::remove 并不具备直接调用容器内存释放接口的能力。它的实际行为是将不需要删除的元素向前覆盖，并返回一个新的逻辑边界迭代器。容器的 size() 在此阶段并未改变。只有将该返回的迭代器与 end() 传递给容器的 erase 方法，才能真正销毁多余元素并回收内存。
8.3 有序性前置条件
大量高效算法（时间复杂度低于 O(n)）严重依赖输入序列的有序性。这包括二分查找家族（binary_search, lower_bound）、集合运算（set_union, includes）以及 merge。若传入未排序的容器，这些算法不会抛出异常，但会产生完全错误的计算结果或触发未定义行为。在调用前，务必确保数据已完成排序。
