C++ STL 算法：常用操作与易错点

find_end 查找最后一次出现子序列的位置，还有 search 可查找第一次出现。

统计

std::count 和 count_if 用于计数。后者通过谓词实现条件统计，我经常用它统计满足特定条件的元素个数，比手写循环直观。

std::vector<int> vec = {1, 2, 3, 2, 4, 2};
int cnt = std::count(vec.begin(), vec.end(), 2); // 3
int even_cnt = std::count_if(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; }); // 4

遍历

虽然现在更多用范围 for，但 for_each 在需要传递 lambda 或函数对象时仍然方便，它会对范围内每个元素应用一个函数。

std::vector<int> vec = {1, 2, 3, 4, 5};
std::for_each(vec.begin(), vec.end(), [](int& x) { x *= 2; });
// vec 变成 {2, 4, 6, 8, 10}

比较

判断两个序列是否相等，或者找出第一个不匹配的位置。

std::vector<int> a = {1, 2, 3};
std::vector<int> b = {1, 2, 4};
bool is_equal = std::equal(a.begin(), a.end(), b.begin());
std::cout << "a == b? " << std::boolalpha << is_equal << std::endl; // false

auto mis = std::mismatch(a.begin(), a.end(), b.begin());
if (mis.first != a.end()) {
    std::cout << "mismatch: " << *mis.first << " vs " << *mis.second << std::endl;
}

逻辑检查

all_of、any_of、none_of 这三个算法特别适合验证数据是否满足某种约束，代码语义清晰。

std::vector<int> vec = {2, 4, 6, 8};
bool all_even = std::all_of(vec.begin(), vec.end(), [](int x) { return x % 2 == 0; }); // true
bool any_odd  = std::any_of(vec.begin(), vec.end(), [](int x) { return x % 2 != 0; }); // false
bool none_neg  = std::none_of(vec.begin(), vec.end(), [](int x) { return x < 0; }); // true

修改序列算法

这类算法会直接改动容器内容，使用时要特别注意空间管理。

复制

std::copy 将源范围的数据复制到目标，目标必须已有足够空间，或使用 back_inserter 自动扩容。copy_if 支持条件复制。

std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dest(5);
std::copy(src.begin(), src.end(), dest.begin());

std::vector<int> evens;
std::copy_if(src.begin(), src.end(), std::back_inserter(evens), [](int x) { return x % 2 == 0; });

变换

std::transform 将每个元素通过函数转换后输出到目标范围，可以接收一个或两个输入范围。

std::vector<int> nums = {1, 2, 3};
std::vector<int> squares(3);
std::transform(nums.begin(), nums.end(), squares.begin(), [](int x) { return x * x; });

std::vector<int> a = {1, 2, 3};
std::vector<int> b = {4, 5, 6};
std::vector<int> sum(3);
std::transform(a.begin(), a.end(), b.begin(), sum.begin(), [](int x, int y) { return x + y; });

替换

replace 原地替换值，replace_copy 则在复制过程中替换，保留原数据不变。

std::vector<int> nums = {1, 2, 3, 2, 5};
std::replace(nums.begin(), nums.end(), 2, 20); // {1, 20, 3, 20, 5}
std::vector<int> res;
std::replace_copy(nums.begin(), nums.end(), std::back_inserter(res), 3, 300);

移除（重要）

新手最常栽跟头的地方。remove 只是把要删除的元素移到末尾，返回新逻辑结尾的迭代器，容器大小不变。必须紧跟 erase 才能真正释放空间。

std::vector<int> nums = {1, 2, 3, 2, 4};
auto new_end = std::remove(nums.begin(), nums.end(), 2);
nums.erase(new_end, nums.end()); // 物理删除

// 结合 Lambda 删除偶数
nums = {1, 2, 3, 4, 5};
nums.erase(std::remove_if(nums.begin(), nums.end(), [](int x) { return x % 2 == 0; }), nums.end());

去重与重排

unique 移除连续重复元素，同样需要 erase 配合。reverse、rotate 和 shuffle 分别用于反转、旋转和随机打乱。

std::vector<int> vec = {1, 1, 2, 2, 3};
auto last = std::unique(vec.begin(), vec.end());
vec.erase(last, vec.end());

// 随机打乱
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(vec.begin(), vec.end(), g);

排序和查找

排序

std::sort 通常最快但不保证稳定性，stable_sort 保持相等元素的相对顺序。如果只关心前几个最小（大）元素，partial_sort 比全排序更高效。

std::vector<int> vec = {5, 3, 1, 4, 2};
std::sort(vec.begin(), vec.end()); // 升序
std::sort(vec.begin(), vec.end(), std::greater<int>()); // 降序

// 只让前三个最小且有序
std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());

快速定位第N小元素

std::nth_element 将第 N 小的元素放到第 N 位，左边都比它小，右边都比它大，复杂度优于完全排序。

std::vector<int> vec = {5, 3, 1, 4, 2, 6};
std::nth_element(vec.begin(), vec.begin() + 2, vec.end());
// vec[2] 现在是第 3 小的元素

二分查找

这些算法要求容器已经排好序。lower_bound 和 upper_bound 返回迭代器，比 binary_search 返回布尔值更实用。

std::vector<int> sorted = {1, 3, 3, 5, 7};
auto lb = std::lower_bound(sorted.begin(), sorted.end(), 3);
auto ub = std::upper_bound(sorted.begin(), sorted.end(), 3);

合并有序序列

std::merge 将两个已排序范围合并成一个。

std::vector<int> a = {1, 3, 5};
std::vector<int> b = {2, 4, 6};
std::vector<int> merged(a.size() + b.size());
std::merge(a.begin(), a.end(), b.begin(), b.end(), merged.begin());

堆操作

STL 提供了一组基于堆的函数，常用于实现优先队列，默认构建最大堆。

std::vector<int> vec = {4, 1, 3, 2, 5};
std::make_heap(vec.begin(), vec.end()); // 构建最大堆
vec.push_back(6);
std::push_heap(vec.begin(), vec.end());
std::pop_heap(vec.begin(), vec.end());
int max_val = vec.back();
vec.pop_back();
std::sort_heap(vec.begin(), vec.end()); // 堆排序

数值计算

这些算法放在 <numeric> 头文件里，非常实用。

• std::accumulate：累加，可自定义运算。
• std::inner_product：内积。
• std::iota：填充递增序列。
• std::partial_sum / std::adjacent_difference：前缀和与差分。

#include <numeric>
std::vector<int> vec = {1, 2, 3, 4, 5};
int sum = std::accumulate(vec.begin(), vec.end(), 0);
std::vector<int> dst(vec.size());
std::partial_sum(vec.begin(), vec.end(), dst.begin());

集合运算

对两个已排序的范围执行并集、交集、差集等操作。同样要求输入有序，否则结果未定义。

std::vector<int> v1 = {1, 2, 3, 4, 5};
std::vector<int> v2 = {3, 4, 5, 6, 7};
std::vector<int> result;
std::set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));
std::set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), std::back_inserter(result));

容易犯的错

• sort 与 stable_sort：多数情况下 sort 更快，但如果相等元素的相对顺序不能打乱，一定要用 stable_sort。
• remove 必须接 erase：remove 只移动元素不释放空间，单独使用容器 size 不变，这是记忆点。
• 有序性前提：二分查找、集合运算和 merge 都要求输入有序，忘了排序结果就是错的。
• 目标空间不足：使用 copy / transform 等输出到另一个容器时，要么提前分配空间，要么用 back_inserter。

掌握这些算法能有效减少手写循环带来的 bug，也让代码更清晰地表达意图。建议在实际项目中多尝试组合使用，慢慢就会形成肌肉记忆。