C++ STL 算法库核心功能详解
引言
C++ 标准模板库（STL）提供了一组通用的算法，位于<algorithm>头文件中。这些算法设计为与容器解耦，通过迭代器操作数据序列。根据是否改变底层数据结构，主要分为非修改性算法和修改性算法。
一、非修改性序列操作
此类函数仅读取数据，不会更改容器内的元素状态或顺序。
1.1 查找类算法
包括基础的数值匹配和条件判断。
find()：返回首次匹配特定值的迭代器。find_if()：返回首个满足自定义条件的元素位置。search_n()：查找连续重复元素序列。
#include <algorithm>
#include <vector>
#include <iostream>
int main() {
std::vector<int> dataSet = {10, 20, 30, 40, 50};
// 查找数值 30 的索引
auto it = std::find(dataSet.begin(), dataSet.end(), 30);
if (it != dataSet.end()) {
std::cout << "Found value at index: " << (it - dataSet.begin()) << std::endl;
}
// 寻找第一个大于 25 的数字
auto conditionIt = std::find_if(dataSet.begin(), dataSet.end(), [](int val) {
return val > 25;
});
return 0;
}1.2 统计与遍历
count()/count_if()：统计符合指定值的数量。for_each()：对每个元素执行 Lambda 表达式或函数对象。
#include <numeric>
// 统计偶数个数
int evenCount = std::count_if(dataSet.begin(), dataSet.end(), [](int n){ return n % 2 == 0; });
// 应用操作
std::for_each(dataSet.begin(), dataSet.end(), [](int& item){
item += 10; // 原地累加
});1.3 范围比较与性质检查
equal()：检测两个区间内容是否完全一致。mismatch()：返回第一个不匹配元素的迭代器对。all_of() / any_of() / none_of()：判断范围内是否存在全部或部分满足条件的元素。
std::vector<int> vecA = {5, 6, 7};
std::vector<int> vecB = {5, 6, 8};
// 检查是否所有元素均为正数
bool allPositive = std::all_of(vecA.begin(), vecA.end(), [](int x){ return x > 0; });
// 结果：true二、修改性序列操作
这类算法会直接变动容器中的内容、结构或容量。
2.1 复制与变换
copy()/copy_if()：将源数据写入目标地址，支持谓词过滤。transform()：应用一元或二元操作，生成新数据序列。
std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> target(5);
// 平方运算转换
std::transform(source.begin(), source.end(), target.begin(), [](int x){
return x * x;
});
// target 现为 {1, 4, 9, 16, 25}
// 双源相加
std::vector<int> src2 = {5, 5, 5, 5, 5};
std::vector<int> sumVec(5);
std::transform(source.begin(), source.end(), src2.begin(), sumVec.begin(),
[](int a, int b){ return a + b; });2.2 替换与删除（重要模式）
replace()：原地修改值。remove()：注意此函数并未真正减小容器大小，而是将有效元素前移，并返回新的尾迭代器。需结合erase()实现物理删除。unique()：移除相邻重复项（需预排序）。
std::vector<int> numList = {1, 5, 5, 3, 2, 2, 1};
// 逻辑删除值为 5 的元素
auto newEnd = std::remove(numList.begin(), numList.end(), 5);
// 此时容器末尾是无效数据
// 物理删除：调整实际大小
numList.erase(newEnd, numList.end());
// 删除重复相邻元素
std::vector<int> dupList = {1, 1, 2, 3, 3};
auto last = std::unique(dupList.begin(), dupList.end());
dupList.erase(last, dupList.end()); // 变为 {1, 2, 3}2.3 重排与随机化
reverse()：逆序区间。rotate()：循环位移。shuffle()：随机打乱（C++11 及以后）。
#include <random>
std::vector<int> cards = {1, 2, 3, 4, 5};
// 反转
std::reverse(cards.begin(), cards.end());
// 旋转：使中间元素成为起点
std::rotate(cards.begin(), cards.begin() + 1, cards.end());
// 洗牌
std::random_device rd;
std::mt19937 gen(rd());
std::shuffle(cards.begin(), cards.end(), gen);三、排序及相关操作
有序数据能显著提升查找和合并效率。
3.1 基础排序
sort()：通常基于 Introsort，不稳定，复杂度 O(N log N)。stable_sort()：保持稳定顺序，适用于多关键字排序场景。partial_sort()：仅保证前半部分有序。
struct Item { int id; double price; };
std::vector<Item> list = {{1, 10.5}, {2, 5.2}, {3, 10.5}};
// 按价格降序稳定排序
std::stable_sort(list.begin(), list.end(), [](const Item& a, const Item& b){
return a.price > b.price;
});3.2 选择与二分查找
nth_element()：快速找到第 N 小的元素，类似快速选择算法。binary_search() / lower_bound() / upper_bound()：要求容器已排序。
// 假设 sortedData 已升序排列
std::vector<int> sortedData = {10, 20, 30, 40, 50};
// 查找第一个 >= 35 的位置
auto lb = std::lower_bound(sortedData.begin(), sortedData.end(), 35);
// 如果 lb 指向 40，则 35 不存在3.3 归并
merge()：将两个有序区间合并为一个新有序区间。
std::vector<int> left = {1, 3, 5};
std::vector<int> right = {2, 4, 6};
std::vector<int> result(left.size() + right.size());
std::merge(left.begin(), left.end(),
right.begin(), right.end(),
result.begin());
// result: {1, 2, 3, 4, 5, 6}四、堆与极值操作
4.1 堆维护
利用 STL 向量模拟优先队列功能。
std::vector<int> heapData = {3, 1, 4, 1, 5};
// 构建最大堆
std::make_heap(heapData.begin(), heapData.end());
// 插入新元素
heapData.push_back(9);
std::push_heap(heapData.begin(), heapData.end());
// 弹出堆顶
std::pop_heap(heapData.begin(), heapData.end());
heapData.pop_back();4.2 最小/最大值
获取迭代器引用而非单纯数值。
std::vector<int> vals = {9, 1, 7};
auto minRes = std::minmax_element(vals.begin(), vals.end());
// minRes.first 指向最小值 1
// minRes.second 指向最大值 9五、数值计算工具（numeric）
位于 <numeric> 中，处理数学归纳逻辑。
accumulate()：累加求和或乘积。iota()：填充递增序列。inner_product()：计算点积。
#include <numeric>
std::vector<int> nums = {1, 2, 3, 4, 5};
// 求和
int total = std::accumulate(nums.begin(), nums.end(), 0);
// 填充 100 到 104
std::vector<int> seq(5);
std::iota(seq.begin(), seq.end(), 100);六、集合操作与实用工具
6.1 集合运算
涉及并集、交集等，输入必须有序。
std::vector<int> setA = {1, 2, 3, 4};
std::vector<int> setB = {3, 4, 5, 6};
std::vector<int> diff;
// 差集 (A - B)
std::set_difference(setA.begin(), setA.end(),
setB.begin(), setB.end(),
std::back_inserter(diff));
// diff 为 {1, 2}6.2 常见问题解析
Q: remove 为什么没有改变容器大小？
A: 这是为了保持迭代器有效性。它只是覆盖无效数据并返回新结束位置，必须由 erase 完成内存释放。
Q: binary_search 为何需要先排序？
A: 二分查找依赖数据的有序性来排除一半搜索空间，无序导致算法失效。
Q: stable_sort 何时使用？
A: 当相等元素的原始相对顺序对业务逻辑有意义时（如多级排序），应优先使用稳定排序，尽管它会消耗额外空间。
