算法概览与分类：非修改式、修改式与排序算法

说实话，STL 算法库是我在 C++ 里用得最爽的部分之一。你想想看，不用自己手写循环，不用操心边界检查，一行代码就能搞定一个复杂操作。我刚开始用的时候，总觉得这玩意儿有点「黑魔法」的味道，后来读了几遍源码才明白——其实底层就是模板加迭代器，设计得特别精巧。

今天咱们就把 STL 算法分成三大类来聊：非修改式、修改式和排序相关。这三类基本覆盖了日常开发中 90% 的场景。

STL 算法三大分类 STL 算法 非修改式算法 find / find_if count / count_if for_each equal / mismatch 修改式算法 copy / copy_if transform replace / replace_if fill / generate 排序相关算法 sort / stable_sort partial_sort nth_element binary_search 注：箭头表示算法大类下的典型代表，实际 STL 包含更多变体

一、非修改式算法：只看不动手

这类算法的特点很直白——它们遍历容器，查找或统计某些元素，但绝不改变容器内容。我个人的经验是，调试阶段先用非修改式算法验证数据状态，确认无误后再上修改式操作，能省不少排查时间。

1. find 与 find_if

find 用来查找第一个等于某个值的元素。它返回一个迭代器，指向找到的位置。如果没找到，就返回 end()。

#include <algorithm>
#include <vector>
#include <iostream>

std::vector<int> vec = {3, 1, 4, 1, 5, 9, 2, 6};
auto it = std::find(vec.begin(), vec.end(), 5);
if (it != vec.end()) {
    std::cout << "找到了: " << *it << std::endl;
} else {
    std::cout << "没找到" << std::endl;
}

find_if 则更灵活——它接受一个谓词（函数或 lambda），只要条件满足就算找到。我在项目中经常用它来查找第一个满足复杂条件的元素。

// 查找第一个大于 5 的元素
auto it = std::find_if(vec.begin(), vec.end(), 
                       [](int x) { return x > 5; });
if (it != vec.end()) {
    std::cout << "第一个大于5的元素是: " << *it << std::endl;
}
小技巧：如果你需要查找所有匹配的位置，可以配合循环使用 find。每次找到后，把起始迭代器更新为 it + 1 继续查找。

2. count 与 count_if

count 统计某个值出现的次数。count_if 统计满足条件的元素个数。这两个函数的时间复杂度都是 O(n)，但胜在代码简洁。

std::vector<int> scores = {85, 92, 78, 92, 88, 92, 70};
int count_92 = std::count(scores.begin(), scores.end(), 92);
// count_92 == 3

int count_above_90 = std::count_if(scores.begin(), scores.end(),
                                   [](int s) { return s > 90; });
// count_above_90 == 3
注意：count 对自定义类型需要 operator== 支持。如果你用 count_if，记得谓词要返回 bool 值。我曾经见过有人返回 int，结果非零值全被当成 true，统计结果完全不对。

3. for_each：遍历的瑞士军刀

for_each 对每个元素执行一个可调用对象。它比范围 for 循环更灵活，因为你可以传入函数对象，甚至保存状态。

std::vector<std::string> names = {"Alice", "Bob", "Charlie"};
std::for_each(names.begin(), names.end(), 
              [](const std::string& name) {
                  std::cout << "Hello, " << name << "!" << std::endl;
              });

我个人习惯用 for_each 来做日志输出或调试打印。它比手写循环少一行代码，而且意图更明确——「我要对每个元素做点事」。

二、修改式算法：动手改数据

这类算法会改变容器中的元素。使用时一定要小心——确保目标容器有足够的空间，或者使用 back_inserter 这类插入迭代器。

1. copy 与 copy_if

copy 把一个区间的元素复制到另一个区间。它不会自动扩容，所以目标容器要提前准备好空间。

std::vector<int> src = {1, 2, 3, 4, 5};
std::vector<int> dst(5);  // 必须预留空间

std::copy(src.begin(), src.end(), dst.begin());
// dst == {1, 2, 3, 4, 5}

如果你不想手动算大小，可以用 back_inserter：

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

copy_if 是带条件复制的版本。我曾经用它来过滤日志文件中的错误行，一行代码搞定，比手写循环清爽多了。

std::vector<int> numbers = {1, 2, 3, 4, 5, 6};
std::vector<int> evens;
std::copy_if(numbers.begin(), numbers.end(),
             std::back_inserter(evens),
             [](int n) { return n % 2 == 0; });
// evens == {2, 4, 6}

2. transform：一换一

transform 对每个元素应用一个函数，把结果写入目标区间。它有两种形式：一元版本（一个输入区间）和二元版本（两个输入区间）。

std::vector<int> input = {1, 2, 3, 4};
std::vector<int> output(4);

// 一元版本：每个元素乘以 2
std::transform(input.begin(), input.end(), output.begin(),
               [](int x) { return x * 2; });
// output == {2, 4, 6, 8}

// 二元版本：两个向量对应元素相加
std::vector<int> a = {1, 2, 3};
std::vector<int> b = {10, 20, 30};
std::vector<int> sum(3);
std::transform(a.begin(), a.end(), b.begin(), sum.begin(),
               [](int x, int y) { return x + y; });
// sum == {11, 22, 33}
核心区别：copy 是原样复制，transform 是「加工后复制」。如果你需要做类型转换、数学运算或字符串拼接，transform 是首选。

3. replace 与 replace_if

replace 把某个特定值替换成新值。replace_if 则根据条件替换。这两个函数是原地修改，不会改变容器大小。

std::vector<int> data = {1, 0, 3, 0, 5, 0, 7};
// 把所有 0 替换成 -1
std::replace(data.begin(), data.end(), 0, -1);
// data == {1, -1, 3, -1, 5, -1, 7}

// 把所有负数替换成 0
std::vector<int> values = {-5, 3, -2, 8, -1};
std::replace_if(values.begin(), values.end(),
                [](int v) { return v < 0; }, 0);
// values == {0, 3, 0, 8, 0}

三、排序相关算法：让数据有序

排序是算法库的重头戏。STL 提供了多种排序策略，各有各的适用场景。

1. sort 与 stable_sort

sort 是最常用的排序函数。它平均时间复杂度 O(n log n)，底层通常是快速排序加插入排序的混合体。

std::vector<int> nums = {9, 3, 7, 1, 5, 8, 2, 6, 4};
std::sort(nums.begin(), nums.end());
// nums == {1, 2, 3, 4, 5, 6, 7, 8, 9}

// 降序排序
std::sort(nums.begin(), nums.end(), std::greater<int>());
// nums == {9, 8, 7, 6, 5, 4, 3, 2, 1}

stable_sort 保证相等元素的相对顺序不变。代价是稍微慢一点，需要额外内存。如果你排序的是有多个字段的结构体，并且希望保持原始顺序，就用它。

避坑指南：sort 要求随机访问迭代器，所以它只能用于 vector、deque、array 和 C 数组。list 不能用 sort，得用 list 自己的成员函数 list::sort。

2. partial_sort：只排一部分

有时候你不需要全排完，只要前 N 个最小的元素有序就行。partial_sort 就是干这个的。

std::vector<int> scores = {88, 72, 95, 60, 83, 91, 77};
// 只让前 3 个元素有序（最小的 3 个）
std::partial_sort(scores.begin(), scores.begin() + 3, scores.end());
// scores 前 3 个是 {60, 72, 77}，后面顺序不确定

我在做排行榜功能时用过这个——只关心前三名，后面的顺序无所谓。性能比全排序好不少。

3. nth_element：找到第 N 大的元素

nth_element 是个被低估的算法。它把第 N 个元素放到正确的位置上，左边都比它小，右边都比它大。但它不保证左右两边内部有序。

std::vector<int> data = {7, 2, 9, 1, 8, 3, 6, 4, 5};
// 找到中位数（第 5 个元素）
std::nth_element(data.begin(), data.begin() + 4, data.end());
// data[4] 现在是 5，左边都 ≤5，右边都 ≥5
std::cout << "中位数: " << data[4] << std::endl;

这个算法的时间复杂度是 O(n)，比排序快得多。找中位数、找百分位数、做分桶统计时特别好用。

4. binary_search：二分查找

binary_search 要求容器已经有序。它返回 bool 值，告诉你目标值是否存在。

std::vector<int> sorted = {1, 3, 5, 7, 9, 11, 13};
bool found = std::binary_search(sorted.begin(), sorted.end(), 7);
// found == true

bool not_found = std::binary_search(sorted.begin(), sorted.end(), 8);
// not_found == false
注意：binary_search 只告诉你「有没有」，不告诉你「在哪里」。如果你需要位置，用 lower_bound 或 equal_range。

总结一下

这三类算法各有各的用武之地。非修改式算法适合数据探查和验证，修改式算法适合数据清洗和转换，排序相关算法则是有序数据的基础。我个人建议你把这些算法记在脑子里——写代码时能少写很多循环，代码的可读性也会上一个台阶。

嗯，今天就聊到这儿。这些算法你用得越多，就越能体会到 STL 设计的精妙之处。

← 上一章 📖 返回目录 下一章 →