一、查找三兄弟

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

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

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

    // ── ① find：按"值"找，返回迭代器 ──────
    vector<int>::iterator it = find(v.begin(), v.end(), 9);
    if (it != v.end())
        cout << "找到 9，它在第 " << (it - v.begin()) << " 个位置（从 0 数）" << endl;
    else
        cout << "没找到 9" << endl;

    // ★ it - v.begin() 能给"下标" —— 因为 vector 的迭代器是随机访问的（13.4.5）

    // ── ② find_if：按"条件"找 ────────────
    vector<int>::iterator it2 = find_if(v.begin(), v.end(),
                                        [](int x) { return x % 2 == 0; });  // 找第一个偶数
    if (it2 != v.end())
        cout << "第一个偶数是 " << *it2 << "，位置 " << (it2 - v.begin()) << endl;

    // ── ③ find_first_of / find_end / search：找"一段" ──
    vector<int> sub = {9, 4};
    vector<int>::iterator it3 = search(v.begin(), v.end(), sub.begin(), sub.end());
    if (it3 != v.end())
        cout << "找到子序列 9 4，起点位置 " << (it3 - v.begin()) << endl;

    vector<int>::iterator it4 = find_end(v.begin(), v.end(), sub.begin(), sub.end());
    cout << "find_end 找同一段（从后往前数最后一个匹配）→ 位置 "
         << (it4 - v.begin()) << endl;
    return 0;
}

看到什么算成功：

数据：3 7 1 9 4 7 2 
找到 9，它在第 3 个位置（从 0 数）
第一个偶数是 4，位置 4
找到子序列 9 4，起点位置 3
find_end 找同一段（从后往前数最后一个匹配）→ 位置 3

关键点：it - v.begin() 就是下标。能这么写的前提是 vector 的迭代器支持减法（随机访问迭代器，13.4.5）——换成 list 就编译不过。这是"迭代器能力决定能干什么"的第一个实证。

二、计数：count 与 count_if

这两个算法是本节教材实例04 的主角：

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

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

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

    // ── 实例04：用 count 数相同元素的个数 ──
    cout << "7 出现了 " << count(v.begin(), v.end(), 7) << " 次" << endl;
    cout << "100 出现了 " << count(v.begin(), v.end(), 100) << " 次（没有就是 0）" << endl;

    // ── count_if：按条件数 ──────────────
    cout << "大于 5 的有 " << count_if(v.begin(), v.end(),
                                [](int x) { return x > 5; }) << " 个" << endl;

    // ── 对比一下"手写循环" ──────────────
    int manual = 0;
    for (size_t i = 0; i < v.size(); i++) if (v[i] == 7) manual++;
    cout << "手写循环数的 7：" << manual << " 次（一样，但多写了三行）" << endl;
    return 0;
}

看到什么算成功：

数据：3 7 1 9 4 7 2 7 
7 出现了 3 次
100 出现了 0 次（没有就是 0）
大于 5 的有 4 个
手写循环数的 7：3 次（一样，但多写了三行）

count 的返回值是"个数"（difference_type，可以当成 int 用），不是迭代器。这是它和 find 最大的区别：你只想知道"几个"，用 count；想知道"在哪"，用 find。 效率提醒：count 是 O(n)，无论容器是什么。 而 set::count / map::count 是 O(log n)（13.2.1）。"要数字数"时，如果数据已经在 set 里，就用成员 count，别搬出来用算法。

三、实例03：用 adjacent_find 搜索相邻的重复元素（教材实例）

任务：找出第一对"挨在一起且相等"的元素。典型用途：查重复录入（比如一批数据里有没有连续重复的编号）。

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

int main() {
    // ── 例 1：有一对相邻重复 ─────────────
    vector<int> v1 = {1, 3, 3, 5, 7, 7, 9};
    cout << "数据：";
    for (int x : v1) cout << x << " ";
    cout << endl;

    vector<int>::iterator it = adjacent_find(v1.begin(), v1.end());
    if (it != v1.end()) {
        cout << "找到相邻重复：两个 " << *it
             << "，第一个在第 " << (it - v1.begin()) << " 位"
             << "，第二个在第 " << (it - v1.begin() + 1) << " 位" << endl;
    } else {
        cout << "没有相邻重复" << endl;
    }

    // ── 例 2：没有相邻重复 ───────────────
    vector<int> v2 = {1, 2, 3, 4, 5};
    if (adjacent_find(v2.begin(), v2.end()) == v2.end())
        cout << "v2 = 1 2 3 4 5 → 没有相邻重复" << endl;

    // ── ★ 注意：不相邻的重复它不管 ────────
    vector<int> v3 = {1, 2, 1, 2, 1};
    if (adjacent_find(v3.begin(), v3.end()) == v3.end())
        cout << "v3 = 1 2 1 2 1 → 没有【相邻】重复（虽然 1 出现了 3 次）" << endl;

    // ── 带条件的版本：找"相邻且都满足条件"（C++11 的 adjacent_find 重载）──
    //    这里用"相邻且都是偶数"当例子
    vector<int> v4 = {1, 3, 4, 6, 8, 10, 11};
    vector<int>::iterator it4 = adjacent_find(v4.begin(), v4.end(),
                                              [](int a, int b) { return a % 2 == 0 && b % 2 == 0; });
    if (it4 != v4.end())
        cout << "v4 里第一对相邻的偶数：" << *it4 << " 和 " << *(it4 + 1) << endl;

    // ── 实用场景：查"重复录入" ────────────
    vector<int> ids = {1001, 1002, 1003, 1003, 1005};   // 排序后查最快
    vector<int>::iterator dup = adjacent_find(ids.begin(), ids.end());
    if (dup != ids.end())
        cout << "警告：编号 " << *dup << " 重复录入！" << endl;
    return 0;
}

看到什么算成功：

数据：1 3 3 5 7 7 9 
找到相邻重复：两个 3，第一个在第 1 位，第二个在第 2 位
v2 = 1 2 3 4 5 → 没有相邻重复
v3 = 1 2 1 2 1 → 没有【相邻】重复（虽然 1 出现了 3 次）
v4 里第一对相邻的偶数：4 和 6
警告：编号 1003 重复录入！

四个必须收下的点：

1. 它只认"相邻" —— v3 = {1,2,1,2,1} 里 1 出现了 3 次，但 adjacent_find 说"没有"（因为它们不挨着）。这是它的"名如其义"，也是最容易误解的一点。
2. 找到后，第二个元素是 *(it + 1) —— 但注意：it + 1 只在"随机访问迭代器"上能写（13.4.5）。要兼容 list，得写 ++it 之类。
3. 返回的迭代器指向"这一对里的第一个" —— 所以 it - v.begin() 是"第一个的位置"。
4. 它常用于"排好序后查重复" —— 排序之后，相等的一定相邻，此时 adjacent_find 就能查出任何重复（不只是原本相邻的）。这正是 13.3.3 的 unique 去重的前置动作（sort + unique）。

四、其它几个"只看不改"的算法

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

int main() {
    vector<int> v = {1, 2, 3, 4, 5};

    // ── ① for_each：对每个元素做一件事 ─────
    cout << "for_each 打印：";
    for_each(v.begin(), v.end(), [](int x) { cout << x * 10 << " "; });
    cout << endl;

    // ── ② all_of / any_of / none_of（C++11）──
    cout << "全是正数？  " << (all_of(v.begin(), v.end(), [](int x) { return x > 0; }) ? "是" : "否") << endl;
    cout << "有偶数？    " << (any_of(v.begin(), v.end(), [](int x) { return x % 2 == 0; }) ? "是" : "否") << endl;
    cout << "全不是零？  " << (none_of(v.begin(), v.end(), [](int x) { return x == 0; }) ? "是" : "否") << endl;

    // ── ③ equal：两个区间是否完全相同 ──────
    vector<int> a = {1, 2, 3};
    vector<int> b = {1, 2, 3};
    vector<int> c = {1, 2, 4};
    cout << "a == b ? " << (equal(a.begin(), a.end(), b.begin()) ? "相同" : "不同") << endl;
    cout << "a == c ? " << (equal(a.begin(), a.end(), c.begin()) ? "相同" : "不同") << endl;

    // ── ④ mismatch：第一个不同的位置 ───────
    pair<vector<int>::iterator, vector<int>::iterator> m =
        mismatch(a.begin(), a.end(), c.begin());
    if (m.first != a.end())
        cout << "a 和 c 第一次不同：a 里是 " << *m.first
             << "，c 里是 " << *m.second << endl;

    // ── ⑤ max_element / min_element：找最大最小 ──
    vector<int>::iterator mx = max_element(v.begin(), v.end());
    vector<int>::iterator mn = min_element(v.begin(), v.end());
    cout << "最大 " << *mx << "，最小 " << *mn << endl;

    // ── ⑥ 对"字符串"也能用（字符就是一个区间）──
    string s = "hello world";
    cout << "s 里有 " << count(s.begin(), s.end(), 'l') << " 个 l" << endl;
    return 0;
}

看到什么算成功：

for_each 打印：10 20 30 40 50 
全是正数？  是
有偶数？    是
全不是零？  是
a == b ? 相同
a == c ? 不同
a 和 c 第一次不同：a 里是 3，c 里是 4
最大 5，最小 1
s 里有 3 个 l

三个实用提醒：

equal 要求两个区间一样长（只传了第二段的起点）——长度不够就是"越界读"，属于未定义行为。 长度可能不同时，要用 mismatch 或者自己先比 size()。

五、动手 Demo：用"只看不改"的算法做一份数据体检报告

任务：对一批考试成绩做不改数据的体检：几个不及格、有没有相邻重复（重复录入）、最高最低、是否全部及格。

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

int main() {
    vector<int> scores = {88, 95, 72, 88, 60, 95, 88, 100, 55};

    cout << "原始成绩（" << scores.size() << " 人）：";
    for (int s : scores) cout << s << " ";
    cout << endl;

    // ① 不及格人数（count_if）
    int fail = count_if(scores.begin(), scores.end(), [](int s) { return s < 60; });
    cout << "① 不及格 " << fail << " 人" << endl;

    // ② 找"重复录入"（先把副本排序，再用 adjacent_find）
    vector<int> sorted(scores);                     // ★ 复制一份，不动原数据
    sort(sorted.begin(), sorted.end());             // 排序后相等的必然相邻
    cout << "② 重复出现的分数：";
    for (vector<int>::iterator it = sorted.begin(); it != sorted.end(); ) {
        vector<int>::iterator dup = adjacent_find(it, sorted.end());
        if (dup == sorted.end()) break;
        cout << *dup << " ";
        it = dup + 1;                               // ★ 从重复处继续找
    }
    cout << endl;

    // ③ 最高最低（max_element / min_element）
    cout << "③ 最高 " << *max_element(scores.begin(), scores.end())
         << "，最低 " << *min_element(scores.begin(), scores.end()) << endl;

    // ④ 是否全部及格（all_of）
    cout << "④ 全部及格？ "
         << (all_of(scores.begin(), scores.end(), [](int s) { return s >= 60; }) ? "是" : "否")
         << endl;

    // ⑤ 原数据动过吗？（因为上面都是"非修正"算法）
    cout << "⑤ 原成绩还是那些：" << (equal(scores.begin(), scores.begin() + 5,
                                          vector<int>{88, 95, 72, 88, 60}.begin())
                                    ? "前 5 个没变（非修正算法不碰数据）" : "变了") << endl;
    return 0;
}

看到什么算成功：

原始成绩（9 人）：88 95 72 88 60 95 88 100 55 
① 不及格 1 人
② 重复出现的分数：88 95 
③ 最高 100，最低 55
④ 全部及格？ 否
⑤ 原成绩还是那些：前 5 个没变（非修正算法不碰数据）

② 那段"找所有重复值"的写法值得看一眼：我们先复制一份再排序（排序是"修正算法"，会改数据——所以必须动副本），然后用 adjacent_find 一段段往后找。 这就是"排序 + 相邻查找"这套组合拳：排序之后，'重复'这件事从"分散的谜题"变成了"挨着的邻居"。 这是算法世界里最常见的一类技巧。

30 秒实验

1. adjacent_find 的邻近性：vector<int> v = {1,2,1,2}; → adjacent_find 返回 end()（没有相邻的）。换成 {1,2,2,1} 就能找到。
2. count vs set::count：把 {3,7,1,9,4,7,2,7} 分别放进 vector 和 set，都用 count(7) 数 → 结果一样，但 set 是 O(log n)（元素少看不出来，几百万个就明显了）。
3. find 返回 end() 的写法：if (find(v.begin(), v.end(), 999) == v.end()) cout << "没有"; → 这是所有"找不到"判断的标准写法。
4. for_each 的返回值：auto f = for_each(...); → 它返回那个函数对象。如果在函数对象里累加了一个计数器，就能拿到结果（这是"用 for_each 做统计"的老套路，现在用 lambda + 捕获更简单）。

常见误区

1. "adjacent_find 能找出所有重复"——只找"相邻"的重复。{1,2,1,2} 里一对重复它都找不到。要查所有重复：先 sort 再 adjacent_find（或先 sort 再 unique，13.3.2）。
2. "find 返回下标"——返回迭代器。要下标得 it - v.begin()（且仅限随机访问迭代器，13.4.5）。
3. "count 和 find 能省一个"——看你要什么：要"个数"用 count，要"位置/迭代器"用 find。但"只要知道在不在"时，find 更明确（而且能立刻 erase(it)）。
4. "这些算法不改数据，所以随便用"——对（这是它们叫"非修正"的原因）。但要留意你传进去的"条件"或"函数对象"有没有副作用（比如 lambda 里改了外面的变量——那是"你自己的事"，不是算法的）。
5. "equal 和 == 一样"——equal 比较的是两个"区间"（第二段只给起点，长度由第一段决定）。两段长度不同就是越界读——要用 mismatch 或先比长度。
6. "max_element 返回最大值"——返回指向它的迭代器（*mx 才是值）。好处是顺带知道了位置。
7. "算法能用在 list 上没问题"——部分是：find、count、for_each、adjacent_find（只需"能 ++"）都能用；但 sort、random_shuffle、binary_search 这些要随机访问的，在 list 上编译不过（13.4.5 讲原因）。

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

相关笔记

• 算法 —— 上一节：四类算法地图与统一姿势
• 修正序列算法（含实例05、06） —— 下一节：会改数据的那些
• 排序算法（含实例07） —— sort + binary_search
• set类模板（含实例02） —— set::find 为什么是 O(log n)
• 随机访问迭代器 —— it - begin() 为什么只在某些容器上能写
• 🔷 C++基础 · 索引 —— 全课路线图