一、算法的"统一调用姿势"

所有算法都是这个形状：

算法名( 起点迭代器, 终点迭代器 [, 条件/值/目标] )

举几个例子（先扫一眼，不用记）：

vector<int> v = {5, 2, 8, 1, 9, 3};

sort(v.begin(), v.end());                    // 排序（没有额外参数）
int n = count(v.begin(), v.end(), 3);        // 数"3 有几个"
auto it = find(v.begin(), v.end(), 8);       // 找"8 在哪"
for_each(v.begin(), v.end(), 打印函数);       // 对每个元素做一件事
reverse(v.begin(), v.end());                 // 反转

三件事一眼就看出来：

"左闭右开"是 STL 里最统一的约定，记它有三个好处：① 空区间表示为 first == last（一眼看出）；② 遍历写成 while (it != last) 不会多走；③ 拼接区间时 [a,b) + [b,c) 正好无缝。

二、四类算法地图

教材把算法分成四类，按"要不要改元素"和"干什么活"来分：

"非修正"和"修正"这两个名字怎么理解：

• 非修正＝"只看不改"（find 只是告诉你"它在哪"，不动容器）；
• 修正＝"会改内容"（replace 会把某些值换成别的）。

这个分类很实用：一眼看出"这个算法调用会不会改动我的数据"。 调试时突然发现数据变了，就先去找那一节里的调用。

三、"带条件"的版本：_if 后缀

很多算法有两个版本：无后缀的用"值"比较，带 _if 的用"条件函数"：

那个"条件"可以是三种东西（都能用，看你好哪口）：

// ① 普通函数
bool isEven(int x) { return x % 2 == 0; }
count_if(v.begin(), v.end(), isEven);

// ② 函数对象（仿函数）：重载了 operator() 的类
struct IsEven { bool operator()(int x) const { return x % 2 == 0; } };
count_if(v.begin(), v.end(), IsEven());

// ③ lambda 表达式（C++11，最常用）
count_if(v.begin(), v.end(), [](int x) { return x % 2 == 0; });

第三种（lambda）是现代 C++ 里最常用的：它把"一个短小的函数"就地写出来，不用另外起名字、另找地方放。 语法不复杂： [](参数) { 函数体 } ↑ ↑ 捕获列表 和普通函数一样 [] 里可以"捕获"外面的变量（比如 [n] 表示"把外面的 n 复制进来用"）。这一小节会大量用到它。

四、动手 Demo：三种"条件"写法，一个效果

任务：数一数 vector 里有多少个偶数，三种条件写法各来一遍。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// ① 普通函数
bool isEven(int x) { return x % 2 == 0; }

// ② 函数对象
struct IsEven {
    bool operator()(int x) const { return x % 2 == 0; }
};

int main() {
    vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    cout << "数据：";
    for (int x : v) cout << x << " ";
    cout << endl;

    // 用三种"条件"做同一件事
    cout << "① 用普通函数：  " << count_if(v.begin(), v.end(), isEven) << " 个偶数" << endl;
    cout << "② 用函数对象：  " << count_if(v.begin(), v.end(), IsEven()) << " 个偶数" << endl;
    cout << "③ 用 lambda：   " << count_if(v.begin(), v.end(),
                        [](int x) { return x % 2 == 0; }) << " 个偶数" << endl;

    // 顺便：无后缀版本只能比"具体的值"
    cout << "count(5)      = " << count(v.begin(), v.end(), 5) << "（这里比的是具体的值，不是条件）" << endl;

    // lambda 还能"用外面的变量"（捕获）
    int threshold = 6;
    int over = count_if(v.begin(), v.end(),
                        [threshold](int x) { return x > threshold; });   // ★ 捕获 threshold
    cout << "大于 " << threshold << " 的有 " << over << " 个（lambda 捕获了 threshold）" << endl;
    return 0;
}

看到什么算成功：

数据：1 2 3 4 5 6 7 8 9 10 
① 用普通函数：  5 个偶数
② 用函数对象：  5 个偶数
③ 用 lambda：   5 个偶数
count(5)      = 1（这里比的是具体的值，不是条件）
大于 6 的有 4 个（lambda 捕获了 threshold）

一个必须知道的老实话：教材里用"函数对象"讲（① ② 这两种），是因为它讲的是标准 C++ 的老写法；实战里现在几乎都用 ③ lambda。 三种效果完全一样，lambda 只是"写起来最省事"： - 普通函数：得另外定义，还要起名字； - 函数对象：得写一个完整的类（虽然能带状态）； - lambda：就地写、能捕获外部变量——所以它同时取代了前两者的优点。

30 秒实验

1. [] vs ()：把 IsEven() 写成 IsEven（忘了括号）→ 编译错误（传的是类型不是对象）。函数对象要"造一个对象出来"。
2. lambda 捕获：把 [threshold] 改成 [] → 报 'threshold' is not captured。[] 里不写，外面的变量就用不了。
3. 左闭右开：写 count(v.begin(), v.begin() + 3, 2) → 只数前 3 个里的 2（结果 1）。区间是 [begin, begin+3)。
4. 算法不认识容器：把上面 Demo 的 vector 换成裸数组 int a[] = {1,2,...}，然后 count_if(a, a + 10, isEven) → 完全能跑。因为"数组名 + 偏移"也是迭代器。

常见误区

1. "算法知道我在用 vector"——不知道。它只看到两个迭代器。所以 sort(arr, arr + n) 对裸数组也能用（12.1.2 的"数组作为模板参数"是同一个思路）。
2. "last 是最后一个元素"——是"最后一个的下一个位置"（左闭右开）。所以 find 找不到时返回 last（也就是容器的 end()），判断写法永远是 != v.end()。
3. "算法能自动扩容"——不能。copy 要求目标位置已经有足够的空间；往空容器里 copy 要用插入迭代器（back_inserter，13.4.1）。
4. "for_each 能改元素？"——能（如果传的是 T&）。但它的"正统"用途是"看不改"（for_each 属于非修正）。要改，用 transform（本节不展开，认得名字就行）。
5. "带了 _if 的算法只能配函数对象"——什么都能配：普通函数、函数对象、lambda、甚至 std::greater<int>() 这种标准库自带的。详见 13.3.3 的排序。
6. "算法都一样快"——差很远。sort 是 O(n log n)、find 是 O(n)、binary_search 是 O(log n)（但前提是数据已排序）。先看复杂度，再看要不要换容器。
7. "算法在容器里，所以要用 v.sort()"——正好相反：算法是自由函数（sort(v.begin(), v.end())），写在 <algorithm> 里，不属于任何容器。只有少数几个"和容器结构强相关"的操作才有成员版本（list::sort、set::find、map::erase）——这也是为什么 list 有 l.sort() 而 vector 没有。

• ☐ 下一节（13.3.1 非修正序列算法）

相关笔记

• 非修正序列算法（含实例03、04） —— 下一节：查找与计数
• 修正序列算法（含实例05、06） —— 会改数据的那些
• 排序算法（含实例07） —— 最重要的一类
• 迭代器 —— 算法只认的那个"插头"
• 序列容器 —— 上一段：盒子讲完了
• 函数模板的作用（含实例01） —— 算法就是函数模板
• 🔷 C++基础 · 索引 —— 全课路线图