C++ STL算法库全面解析与实战
STL算法库是C++标准模板库的核心组件，提供了大量高效、通用的算法操作。本文系统梳理各类常用算法的功能特性与典型用法。
一、非修改性序列操作
这类算法仅读取数据，不会改动容器内元素的值。
1.1 查找相关
std::find 系列用于定位满足条件的元素：
std::vector<int> data = {4, 7, 2, 9, 5};
// 定位首个值为7的元素
auto pos = std::find(data.begin(), data.end(), 7);
// 定位首个大于5的元素
auto pred = std::find_if(data.begin(), data.end(),
[](int v) { return v > 5; });
// 查找子串最后一次出现的位置
std::vector<int> pattern = {2, 9};
auto last = std::find_end(data.begin(), data.end(),
pattern.begin(), pattern.end());
1.2 统计与遍历
std::vector<int> scores = {85, 92, 78, 92, 66, 92};
// 统计特定值出现次数
int nines = std::count(scores.begin(), scores.end(), 92); // 结果为3
// 统计满足条件的元素
int passed = std::count_if(scores.begin(), scores.end(),
[](int s) { return s >= 60; });
// 遍历并处理每个元素
std::for_each(scores.begin(), scores.end(), [](int& s) {
s += 5; // 每人加5分
});
1.3 范围比较与判定
std::vector<int> seqA = {10, 20, 30, 40};
std::vector<int> seqB = {10, 20, 35, 40};
// 判断两个范围是否相等
bool identical = std::equal(seqA.begin(), seqA.end(), seqB.begin());
// 查找首个不匹配位置
auto diff = std::mismatch(seqA.begin(), seqA.end(), seqB.begin());
// diff.first 指向30, diff.second 指向35
// 条件判定
std::vector<int> temps = {25, 28, 30, 27};
bool all_hot = std::all_of(temps.begin(), temps.end(),
[](int t) { return t > 20; });
bool any_extreme = std::any_of(temps.begin(), temps.end(),
[](int t) { return t > 35; });
bool none_negative = std::none_of(temps.begin(), temps.end(),
[](int t) { return t < 0; });
二、修改性序列操作
此类算法会改变容器中的元素值或位置。
2.1 复制与转换
std::vector<int> origin = {1, 2, 3, 4, 5, 6};
std::vector<int> buffer(origin.size());
// 完整复制
std::copy(origin.begin(), origin.end(), buffer.begin());
// 条件复制
std::vector<int> odds;
std::copy_if(origin.begin(), origin.end(), std::back_inserter(odds),
[](int v) { return v % 2 == 1; });
// 元素变换
std::vector<int> squared(origin.size());
std::transform(origin.begin(), origin.end(), squared.begin(),
[](int v) { return v * v; });
// 双序列运算
std::vector<int> addend = {10, 20, 30, 40, 50, 60};
std::vector<int> combined(origin.size());
std::transform(origin.begin(), origin.end(), addend.begin(),
combined.begin(), std::plus<int>());
2.2 替换与删除
std::vector<int> values = {5, 3, 5, 7, 5, 9};
// 直接替换
std::replace(values.begin(), values.end(), 5, 99);
// 条件替换
std::replace_if(values.begin(), values.end(),
[](int v) { return v > 50; }, 0);
// 复制时替换（原容器不变）
std::vector<int> modified;
std::replace_copy(values.begin(), values.end(),
std::back_inserter(modified), 99, 5);
// 删除操作（erase-remove惯用法）
std::vector<int> nums = {1, 2, 3, 4, 5, 6};
nums.erase(
std::remove_if(nums.begin(), nums.end(),
[](int v) { return v % 2 == 0; }),
nums.end()
);
2.3 重排操作
std::vector<int> arr = {1, 1, 2, 2, 2, 3, 4, 4, 5};
// 去重（需先排序）
auto unique_end = std::unique(arr.begin(), arr.end());
arr.erase(unique_end, arr.end());
// 反转
std::reverse(arr.begin(), arr.end());
// 旋转：使中间元素成为首元素
std::rotate(arr.begin(), arr.begin() + 3, arr.end());
// 随机打乱
std::random_device rd;
std::mt19937 engine(rd());
std::shuffle(arr.begin(), arr.end(), engine);
三、排序与有序范围操作
3.1 排序算法
std::vector<int> items = {64, 25, 12, 22, 11};
// 快速排序（不稳定）
std::sort(items.begin(), items.end());
// 稳定排序
std::stable_sort(items.begin(), items.end());
// 自定义比较
std::sort(items.begin(), items.end(), std::greater<int>());
// 部分排序：仅保证前k个有序
std::partial_sort(items.begin(), items.begin() + 3, items.end());
// 快速选择：定位第n小元素
std::nth_element(items.begin(), items.begin() + 2, items.end());
3.2 二分查找与边界
std::vector<int> sorted = {10, 20, 30, 30, 30, 40, 50};
bool found = std::binary_search(sorted.begin(), sorted.end(), 30);
auto lb = std::lower_bound(sorted.begin(), sorted.end(), 30);
auto ub = std::upper_bound(sorted.begin(), sorted.end(), 30);
// lb指向首个30, ub指向40的位置
// 合并有序序列
std::vector<int> a = {1, 3, 5}, b = {2, 4, 6};
std::vector<int> merged(a.size() + b.size());
std::merge(a.begin(), a.end(), b.begin(), b.end(), merged.begin());
四、堆数据结构操作
std::vector<int> heap = {3, 1, 4, 1, 5, 9, 2, 6};
// 构建最大堆
std::make_heap(heap.begin(), heap.end());
// 入堆
heap.push_back(7);
std::push_heap(heap.begin(), heap.end());
// 出堆（最大元素移至末尾）
std::pop_heap(heap.begin(), heap.end());
int max_val = heap.back();
heap.pop_back();
// 堆排序
std::sort_heap(heap.begin(), heap.end());
五、极值查询
int x = 15, y = 42;
int smaller = std::min(x, y);
int larger = std::max({10, 20, 30, 5, 25}); // 初始化列表
std::vector<int> data = {8, 3, 15, 6, 12};
auto min_pos = std::min_element(data.begin(), data.end());
auto max_pos = std::max_element(data.begin(), data.end());
// 同时获取最小最大
auto extremes = std::minmax_element(data.begin(), data.end());
// extremes.first 最小值位置, extremes.second 最大值位置
六、数值运算（<numeric>）
#include <numeric>
std::vector<int> values = {1, 2, 3, 4, 5};
// 累加求和
int total = std::accumulate(values.begin(), values.end(), 0);
// 累乘
int factorial = std::accumulate(values.begin(), values.end(), 1,
std::multiplies<int>());
// 向量点积
std::vector<int> weights = {2, 3, 4, 5, 6};
int dot = std::inner_product(values.begin(), values.end(),
weights.begin(), 0);
// 填充连续序列
std::vector<int> sequence(5);
std::iota(sequence.begin(), sequence.end(), 100); // 100,101,102,103,104
// 前缀和
std::vector<int> prefix(values.size());
std::partial_sum(values.begin(), values.end(), prefix.begin());
// 结果: 1, 3, 6, 10, 15
// 相邻差分
std::vector<int> diff(values.size());
std::adjacent_difference(values.begin(), values.end(), diff.begin());
// 结果: 1, 1, 1, 1, 1
七、生成与集合运算
// 按规则生成序列
std::vector<int> generated(5);
int seed = 0;
std::generate(generated.begin(), generated.end(),
[&seed]() { return seed++ * 2; });
// 集合关系判定
std::vector<int> universe = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::vector<int> subset = {2, 5, 7};
bool contained = std::includes(universe.begin(), universe.end(),
subset.begin(), subset.end());
// 集合运算
std::vector<int> setA = {1, 3, 5, 7}, setB = {3, 5, 7, 9};
std::vector<int> output;
std::set_union(setA.begin(), setA.end(), setB.begin(), setB.end(),
std::back_inserter(output));
output.clear();
std::set_intersection(setA.begin(), setA.end(), setB.begin(), setB.end(),
std::back_inserter(output));
output.clear();
std::set_difference(setA.begin(), setA.end(), setB.begin(), setB.end(),
std::back_inserter(output));
output.clear();
std::set_symmetric_difference(setA.begin(), setA.end(),
setB.begin(), setB.end(), std::back_inserter(output));
八、关键概念辨析
| 算法特性 | 说明 |
|---|---|
| 稳定性 | stable_sort保持相等元素原始相对顺序，sort不保证 |
| erase-remove | remove仅移动元素返回逻辑终点，需配合erase完成物理删除 |
| 有序性前提 | 二分查找、集合运算、merge等要求输入范围已排序 |
| 复杂度保证 | 排序平均O(n log n)，堆操作O(log n)，二分查找O(log n) |
