C++ STL 标准算法库实战指南
一、非侵入式查询算法
这类函数专用于读取数据，保证不会触发布容器的内容发生改变，适用于安全检查或统计场景。
1.1 元素定位系列
std::find 用于寻找首个匹配目标值的节点，若不存在则返回尾部迭代器。std::find_if 则允许传入自定义条件。而 std::find_end 能够定位子序列在容器末尾的最后一次出现位置。
std::vector<int> dataset = {10, 30, 50, 70, 90};
// 尝试定位值为 50 的节点
auto position = std::find(dataset.begin(), dataset.end(), 50);
if (position != dataset.end()) {
std::cout << "Located value: " << *position << std::endl;
}
// 搜索首个超过 60 的数值
auto high_val = std::find_if(dataset.begin(), dataset.end(), [](int val) {
return val > 60;
});
std::cout << "First high value: " << *high_val << std::endl;
// 匹配连续子序列
std::vector<int> pattern = {30, 50};
auto pattern_pos = std::find_end(dataset.begin(), dataset.end(), pattern.begin(), pattern.end());
if (pattern_pos != dataset.end()) {
std::cout << "Pattern starts at index: " << (pattern_pos - dataset.begin()) << std::endl;
}1.2 数量统计功能
使用 std::count 可统计特定值的频次，配合谓词使用的 std::count_if 则能统计满足条件的元素总数。
std::vector<int> values = {5, 10, 5, 20, 5, 30};
size_t total_fives = std::count(values.begin(), values.end(), 5); // 结果为 3
size_t even_total = std::count_if(values.begin(), values.end(), [](int v) {
return v % 2 == 0;
}); // 偶数计数结果为 31.3 遍历执行
std::for_each 允许对区间内的每一项调用指定逻辑。
std::vector<double> scores = {1.1, 2.2, 3.3};
std::for_each(scores.begin(), scores.end(), [](double& s) {
s += 0.5; // 每个分数增加 0.5
});
// scores 变为 {1.6, 2.7, 3.8}1.4 一致性校验
比较两个区间是否完全一致使用 std::equal，若需找到第一个不一致的位置，使用 std::mismatch 返回一对迭代器。
std::vector<char> strA = {'x', 'y', 'z'};
std::vector<char> strB = {'x', 'y', 'a'};
bool match = std::equal(strA.begin(), strA.end(), strB.begin());
// false
auto diff_pair = std::mismatch(strA.begin(), strA.end(), strB.begin());
if (diff_pair.first != strA.end()) {
std::cout << "Mismatch found: " << *diff_pair.first << " vs " << *diff_pair.second << std::endl;
}1.5 范围判断
通过 std::all_of、std::any_of 和 std::none_of 快速验证区间内所有、任意或无元素是否满足条件。
std::vector<int> numbers = {10, 20, 30};
bool all_positive = std::all_of(numbers.begin(), numbers.end(), [](int n) { return n > 0; }); // true
bool any_hundred = std::any_of(numbers.begin(), numbers.end(), [](int n) { return n >= 100; }); // false二、数据修改与迁移
此类算法会直接修改容器内存中的数据分布或改变其大小。
2.1 复制与筛选复制
std::copy 进行基础搬运，目标区需预先分配足够空间。若需动态增长，推荐结合 back_inserter 适配器使用 std::copy_if。
std::vector<int> source = {1, 2, 3, 4};
std::vector<int> target(4);
std::copy(source.begin(), source.end(), target.begin());
std::vector<int> filtered;
std::copy_if(source.begin(), source.end(), std::back_inserter(filtered), [](int val) {
return val % 2 != 0;
}); // filtered: [1, 3]2.2 数据转换
std::transform 将源区数据经变换后存入目标区，支持单输入或双输入映射。
std::vector<int> inputs = {1, 2, 3};
std::vector<int> outputs(3);
std::transform(inputs.begin(), inputs.end(), outputs.begin(), [](int x) {
return x * x;
});
std::vector<int> base = {10, 20};
std::vector<int> adds = {1, 1};
std::vector<int> result(2);
std::transform(base.begin(), base.end(), adds.begin(), result.begin(),
[](int a, int b) { return a + b; });2.3 元素替换
std::replace 覆盖旧值，std::replace_if 根据条件覆盖，std::replace_copy 则在副本中替换保持原样。
std::vector<int> items = {1, 99, 2, 99};
std::replace(items.begin(), items.end(), 99, 0); // 原地改
std::vector<int> backup;
std::replace_copy(items.begin(), items.end(), std::back_inserter(backup), 0, 88); // 仅影响 backup2.4 逻辑删除与物理擦除
std::remove 仅将元素移至末尾并返回新逻辑边界，必须配合容器的 erase 方法才能真正释放内存。
std::vector<int> list = {1, 5, 3, 5, 2};
// 移动 5 到后面
auto new_end = std::remove(list.begin(), list.end(), 5);
// 真正截断
list.erase(new_end, list.end());
// 链式写法：移除所有奇数
list.erase(std::remove_if(list.begin(), list.end(), [](int n) { return n % 2 != 0; }), list.end());2.5 去重与序列操作
std::unique 移除相邻重复项（需先排序），std::reverse 翻转顺序，std::rotate 循环移位，std::shuffle 随机打乱。
#include <random>
std::vector<int> seq = {1, 1, 2, 2};
seq.erase(std::unique(seq.begin(), seq.end()), seq.end()); // [1, 2]
std::vector<int> order = {A, B, C};
std::rotate(order.begin(), order.begin() + 1, order.end()); // B, C, A
std::mt19937 rng(std::random_device{}());
std::shuffle(order.begin(), order.end(), rng);三、排序与二分查找
3.1 全排序与部分排序
std::sort 为默认不稳定快排；std::stable_sort 保持相等元素相对顺序；std::partial_sort 仅对前 N 个元素排序。
std::vector<int> unsorted = {5, 2, 9, 1};
std::sort(unsorted.begin(), unsorted.end(), std::greater<int>()); // 降序
std::vector<int> large_data = {1, 5, 2, 8, 3};
// 只需最小的 3 个有序
std::partial_sort(large_data.begin(), large_data.begin() + 3, large_data.end());3.2 第 N 大元素
std::nth_element 使指定索引处的元素处于正确排序位置，左侧均小于它，右侧均大于等于它，时间复杂度 O(N)。
std::vector<int> data = {4, 2, 9, 1, 7};
std::nth_element(data.begin(), data.begin() + 2, data.end());
// data[2] 是第 3 小的数，例如可能是 43.3 二分查找家族
前提：**容器已排序**。lower_bound 找首个不小于值，upper_bound 找首个大于值，std::binary_search 仅返回存在性。
std::vector<int> sorted = {1, 2, 4, 4, 5};
auto low = std::lower_bound(sorted.begin(), sorted.end(), 4); // 指向第一个 4
auto up = std::upper_bound(sorted.begin(), sorted.end(), 4); // 指向 53.4 合并有序序列
std::merge 将两个已排序的范围合并到一个新容器中。
std::vector<int> l1 = {1, 3}, l2 = {2, 4};
std::vector<int> merged(4);
std::merge(l1.begin(), l1.end(), l2.begin(), l2.end(), merged.begin()); // 1,2,3,4四、堆管理算法
将普通容器视为二叉堆进行操作，无需手动实现树结构。
std::vector<int> heap_vec = {3, 1, 5, 2};
std::make_heap(heap_vec.begin(), heap_vec.end()); // 调整为最大堆
heap_vec.push_back(6);
std::push_heap(heap_vec.begin(), heap_vec.end()); // 插入堆顶
std::pop_heap(heap_vec.begin(), heap_vec.end());
int max_item = heap_vec.back();
heap_vec.pop_back(); // 移除最大值五、极值检索
获取单个值比较结果用 min/max，获取容器迭代器用 min_element/max_element，同时获取两者可用 minmax_element。
std::vector<int> vals = {3, 8, 1};
auto result = std::minmax_element(vals.begin(), vals.end());
int smallest = *result.first; // 1
int largest = *result.second; // 8六、数值计算
位于 <numeric> 头文件中。
6.1 累加与内积
std::accumulate 求和或连乘，std::inner_product 向量点积。
#include <numeric>
std::vector<int> nums = {1, 2, 3};
int sum_res = std::accumulate(nums.begin(), nums.end(), 0); // 6
int prod_res = std::accumulate(nums.begin(), nums.end(), 1, std::multiplies<int>()); // 6
std::vector<int> vecA = {1, 2}, vecB = {3, 4};
int dot_prod = std::inner_product(vecA.begin(), vecA.end(), vecB.begin(), 0); // 116.2 填充与前缀和
std::iota 填充递增序列，std::partial_sum 计算累积和。
std::vector<int> arr(4);
std::iota(arr.begin(), arr.end(), 10); // 10, 11, 12, 13
std::vector<int> src = {1, 2, 3};
std::vector<int> dst(3);
std::partial_sum(src.begin(), src.end(), dst.begin()); // 1, 3, 6七、集合与生成操作
集合操作要求输入序列有序。生成器用于批量创建数据。
// 生成器示例
std::vector<int> gen_buf(3);
std::generate(gen_buf.begin(), gen_buf.end(), [](){ static int c=0; return c++; });
// 集合差集
std::vector<int> setA = {1, 2, 3}, setB = {2, 3, 4};
std::vector<int> diff;
std::set_difference(setA.begin(), setA.end(), setB.begin(), setB.end(),
std::back_inserter(diff)); // diff: {1}八、常见注意事项
- 稳定性问题：
sort不保证相等元素顺序，对结构体排序且需保序时必须选stable_sort。 - Remove Idiom：STL 的
remove只是移动元素，必须紧接着调用erase更新容器 size。 - 有序前提：涉及二分查找或集合运算（union/diff）的算法，若输入未排序，行为将不可定义或错误。
