一、copy / fill / replace / reverse：四个"看得懂"的

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

void show(const char *t, const vector<int> &v) {
    cout << t << "：";
    for (int x : v) cout << x << " ";
    cout << endl;
}

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

    // ── ① copy：复制到目标（目标要"已经有空间"）──
    vector<int> dst(5);                          // ★ 先造出 5 个位置
    copy(src.begin(), src.end(), dst.begin());
    show("copy 到 dst ", dst);

    // ── ② fill：把一段填成同一个值 ──────────
    vector<int> f(6);
    fill(f.begin(), f.end(), 9);
    show("fill 成 9  ", f);

    fill(f.begin() + 1, f.begin() + 3, 7);       // 只填中间两个
    show("中间填 7  ", f);

    // ── ③ replace：把"某个值"换成"另一个值" ──
    vector<int> r = {1, 5, 3, 5, 5, 2};
    show("replace 前 ", r);
    replace(r.begin(), r.end(), 5, 0);           // ★ 所有 5 换成 0
    show("5 换成 0  ", r);

    // ── ④ replace_if：按条件替换 ────────────
    vector<int> r2 = {1, 5, 3, 5, 5, 2};
    replace_if(r2.begin(), r2.end(), [](int x) { return x > 3; }, -1);  // 大于 3 的换 -1
    show("大于3换-1 ", r2);

    // ── ⑤ reverse：反转 ────────────────────
    vector<int> rv = {1, 2, 3, 4, 5};
    reverse(rv.begin(), rv.end());
    show("reverse 后 ", rv);
    return 0;
}

看到什么算成功：

copy 到 dst ：1 2 3 4 5 
fill 成 9  ：9 9 9 9 9 9 
中间填 7  ：9 7 7 9 9 9 
replace 前 ：1 5 3 5 5 2 
5 换成 0  ：1 0 3 0 0 2 
大于3换-1 ：1 -1 3 -1 -1 2 
reverse 后 ：5 4 3 2 1 

copy 的第一大坑：目标必须已经有空间。vector<int> dst;（空的）然后 copy(src.begin(), src.end(), dst.begin()); → dst.begin() 就是 end()，往空容器写是未定义行为（崩溃）。 要"边复制边长"，得用插入迭代器（13.4.1）： cpp vector<int> dst; copy(src.begin(), src.end(), back_inserter(dst)); // ★ 自动 push_back 这就是 13.4.1 输出迭代器要解决的问题——先记着，下一节兑现。

二、remove：最会骗人的一个算法

先记住一句话：remove 不是"删除"，是"把不要的挪到后面"。

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

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

    cout << "原始：";
    for (int x : v) cout << x << " ";
    cout << "（size=" << v.size() << "）" << endl;

    // ── ★ 只调 remove，不调 erase ──────────
    vector<int>::iterator newEnd = remove(v.begin(), v.end(), 5);

    cout << "调完 remove 后的全部元素：";
    for (int x : v) cout << x << " ";
    cout << "（size 还是 " << v.size() << "！）" << endl;

    cout << "它返回的【新末尾】之前（也就是【有效区】）是：";
    for (vector<int>::iterator it = v.begin(); it != newEnd; ++it) cout << *it << " ";
    cout << endl;

    // ── 正确姿势：remove + erase（erase-remove 惯用法）──
    vector<int> w = {1, 5, 3, 5, 5, 2};
    w.erase(remove(w.begin(), w.end(), 5), w.end());     // ★ 一句话真删
    cout << "erase-remove 之后：";
    for (int x : w) cout << x << " ";
    cout << "（size=" << w.size() << "）" << endl;
    return 0;
}

看到什么算成功：

原始：1 5 3 5 5 2 （size=6）
调完 remove 后的全部元素：1 3 2 5 5 2 （size 还是 6！）
它返回的"新末尾"之前（也就是"有效区"）是：1 3 2 
erase-remove 之后：1 3 2 （size=3）

这张输出是本章最值得反复看的一页：

remove 之前：  [ 1 | 5 | 3 | 5 | 5 | 2 ]
                          ↓ 把不要的（5）往后挪，要的往前挤
remove 之后：  [ 1 | 3 | 2 | 5 | 5 | 2 ]
                 ↑ 有效区      ↑ 从这开始是"垃圾区"
                 begin()    newEnd()（remove 的返回值）
                           ↑ 但 size() 还是 6！容器的末尾还在最后

为什么要这么设计：因为算法只认迭代器，不知道容器、更不知道 size。 它没法改变容器的大小——能"真删"的只有容器自己的成员函数 erase。 所以标准把它拆成两步：

v.erase(remove(v.begin(), v.end(), 5), v.end());
//      └─────── 第一步：把要留的挪到前面，返回新的"逻辑末尾" ───────┘
//└ 第二步：从那个位置删到真末尾 —— size 这才变小 ─┘

这个组合叫 erase-remove 惯用法，必须背下来。 它是"算法与容器交界处"的标志性写法。 有了它，13.1.1 那个"边遍历边 erase、还要自己管 i"的难看循环，可以写成一行： cpp // 删掉所有小于 60 的 v.erase(remove_if(v.begin(), v.end(), [](int s) { return s < 60; }), v.end()); 同时记住这个对比：list::remove（成员版）是真删（13.1.3），std::remove（算法版）是挪位置。名字一样、行为不同。

三、实例05：用 random_shuffle 把元素顺序随机打乱（教材实例）

任务：打乱一副牌 / 一棵名单的顺序。

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

int main() {
    // ── 教材写法：random_shuffle（旧标准）────
    vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    cout << "原始：";
    for (int x : v) cout << x << " ";
    cout << endl;

    random_shuffle(v.begin(), v.end());          // ★ 打乱
    cout << "打乱 1：";
    for (int x : v) cout << x << " ";
    cout << endl;

    random_shuffle(v.begin(), v.end());          // ★ 每次结果不同
    cout << "打乱 2：";
    for (int x : v) cout << x << " ";
    cout << endl;

    // ── 实用例子：洗牌 ────────────────────
    vector<string> cards;
    const char *suits[] = {"黑桃", "红桃", "梅花", "方块"};
    const char *ranks[] = {"A", "2", "3", "4", "5", "6", "7", "8", "9", "10", "J", "Q", "K"};
    for (int s = 0; s < 4; s++)
        for (int r = 0; r < 13; r++)
            cards.push_back(string(suits[s]) + ranks[r]);

    random_shuffle(cards.begin(), cards.end());
    cout << "洗好的牌（前 6 张）：";
    for (int i = 0; i < 6; i++) cout << cards[i] << " ";
    cout << endl;
    return 0;
}

看到什么算成功（打乱结果每次都不同）：

原始：1 2 3 4 5 6 7 8 9 10 
打乱 1：7 1 5 4 10 8 2 3 9 6 
打乱 2：3 9 6 2 8 10 1 5 4 7 
洗好的牌（前 6 张）：梅花9 黑桃K 方块3 红桃A 梅花4 黑桃7 

⚠️ 一个必须知道的现实问题：random_shuffle 已经不在标准里了。

原因：它内部用的是 C 的 rand()，随机质量差、不可复现、线程不安全。替代方案是 std::shuffle + 现代的随机数引擎：

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>              // ★ 新写法要这个头文件
using namespace std;

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

    random_device rd;                       // 真随机种子（拿硬件熵）
    mt19937 g(rd());                        // ★ 现代随机数引擎（梅森旋转）
    // 想要"每次结果一样"（便于调试）：mt19937 g(12345);   ← 固定种子

    shuffle(v.begin(), v.end(), g);         // ★ C++11 起的正规写法
    cout << "shuffle 之后：";
    for (int x : v) cout << x << " ";
    cout << endl;

    // 再来一次（同样的引擎对象，会给出不同的结果）
    shuffle(v.begin(), v.end(), g);
    cout << "再洗一次：    ";
    for (int x : v) cout << x << " ";
    cout << endl;
    return 0;
}

看到什么算成功：

shuffle 之后：4 8 1 10 3 6 2 9 7 5 
再洗一次：    9 2 6 1 7 10 4 5 3 8 

两版对照记： | | 旧写法（教材） | 新写法（现代 C++） | |---|---|---| | 函数 | random_shuffle(b, e) | shuffle(b, e, 引擎) | | 头文件 | <algorithm> | <algorithm> + <random> | | 随机源 | 内部用 rand() | 你显式传一个引擎（mt19937） | | 能否复现 | 靠 srand()（全局、别扭） | 固定种子就能完全复现（mt19937 g(12345)） | | 现在能用吗 | C++17 起编译不过 | ✅ |

"能不能复现"这件事在实战里很重要：调试一个"随机出的 bug"时，固定种子能让问题每次都出现。这正是旧 random_shuffle 被淘汰的主要理由之一。

四、实例06：用 partition 把容器分组（教材实例）

partition = 按一个条件，把元素分成"满足的"和"不满足的"两堆（满足的挪到前面，不满足的挪到后面）。

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

void show(const char *t, const vector<int> &v) {
    cout << t << "：";
    for (int x : v) cout << x << " ";
    cout << endl;
}

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

    // ── 按"是不是偶数"分组 ────────────────
    vector<int> a = v;
    vector<int>::iterator p = partition(a.begin(), a.end(),
                                        [](int x) { return x % 2 == 0; });   // ★ 条件
    show("partition（偶数在前）", a);
    cout << "分界点：从 " << *p << " 开始是不满足条件的（奇数）" << endl;

    cout << "分界点前（满足的偶数）：";
    for (vector<int>::iterator it = a.begin(); it != p; ++it) cout << *it << " ";
    cout << endl;
    cout << "分界点后（不满足的奇数）：";
    for (vector<int>::iterator it = p; it != a.end(); ++it) cout << *it << " ";
    cout << endl;

    // ── 实用例子：成绩分组 ────────────────
    vector<int> scores = {88, 45, 92, 58, 76, 100, 30, 65};
    show("成绩          ", scores);
    vector<int>::iterator passLine = partition(scores.begin(), scores.end(),
                                               [](int s) { return s >= 60; });
    show("及格在前      ", scores);
    cout << "及格 " << (passLine - scores.begin()) << " 人，不及格 "
         << (scores.end() - passLine) << " 人" << endl;

    // ── stable_partition：保持各自内部的相对顺序 ──
    vector<int> b = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    stable_partition(b.begin(), b.end(), [](int x) { return x % 2 == 0; });
    show("stable_partition", b);
    return 0;
}

看到什么算成功（partition 不保证组内顺序，所以你的实际输出可能不同）：

partition（偶数在前）：10 2 8 4 6 5 7 3 9 1 
分界点：5 开始是"不满足条件"的（奇数）
分界点前（满足的偶数）：10 2 8 4 6 
分界点后（不满足的奇数）：5 7 3 9 1 
成绩          ：88 45 92 58 76 100 30 65 
及格在前      ：88 92 76 100 65 58 30 45 
及格 5 人，不及格 3 人
stable_partition：2 4 6 8 10 1 3 5 7 9 

三个必须收下的点：

1. partition 的返回值是"分界点迭代器" —— 它左边是满足条件的、右边是不满足的。这就是"分组"的语义：它没有"真的分成两个容器"，只是把分界线挪到了中间。
2. partition 不保证组内顺序 —— 所以"偶数在前"那一行的偶数顺序是乱的（10 2 8 4 6）。
3. stable_partition 保持组内原顺序 —— 输出是 2 4 6 8 10 1 3 5 7 9，两组的内部顺序都和原来一致。代价：它比 partition 慢（要搬更多次）。

"要不要保持相对顺序"是这一节的一个通用主题： | 要快 | 要稳 | |---|---| | partition | stable_partition | | sort（13.3.3） | stable_sort | 所以"stable"这个词在 STL 里统一表示"相等元素的相对顺序保持不变"。

五、unique：去重（要配 sort 或 erase）

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

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

    cout << "原始：";
    for (int x : v) cout << x << " ";
    cout << endl;

    // ── ① 直接 unique：只合并"相邻"的重复 ──
    vector<int> a = v;
    vector<int>::iterator e = unique(a.begin(), a.end());
    cout << "unique 之后（有效区）：";
    for (vector<int>::iterator it = a.begin(); it != e; ++it) cout << *it << " ";
    cout << "    ← 注意后面那两个 1 没被合并（它们不相邻）" << endl;

    // ── ② 正确姿势：先 sort 再 unique 再 erase ──
    vector<int> b = v;
    sort(b.begin(), b.end());                       // ★ 排序让相等的相邻
    b.erase(unique(b.begin(), b.end()), b.end());   // ★ 再来一次 erase-remove
    cout << "sort + unique + erase 之后：";
    for (int x : b) cout << x << " ";
    cout << "（size=" << b.size() << "）" << endl;

    // ── ③ 只想去重不想排序？那得用 set 的亲戚（13.2.1 提过的 unordered_set）──
    cout << "（要保持原顺序去重，可以借 set/哈希：见 13.2.1 的生词本）" << endl;

    // ── ④ 对比：list 的成员版 unique 也是"只合并相邻" ──
    cout << "记住：unique 和 remove 一样，返回的是逻辑末尾，要 erase 才真的变短。" << endl;
    return 0;
}

看到什么算成功：

原始：1 1 2 2 2 3 1 1 
unique 之后（有效区）：1 2 3 1     ← 注意后面那两个 1 没被合并（它们不相邻）
sort + unique + erase 之后：1 2 3 （size=3）
（要保持原顺序去重，可以借 set/哈希：见 13.2.1 的生词本）
记住：unique 和 remove 一样，返回"新的逻辑末尾"，要 erase 才真短。

unique 和 remove 是"同一个脾气"：返回新的逻辑末尾，不改变 size()。所以它也要配 erase（第二次遇到 erase-remove 惯用法了）。 "先 sort 再 unique"是标准动作：sort 的副作用是把相等元素聚到一起，于是"去重"这件事从"全局比对"变成了"和邻居比一比"。和 13.3.1 的 adjacent_find 是同一个思路。 如果你的数据不能排序（比如要保持原顺序），去重就得用 set / unordered_set 来记"见过没有"（13.2.1 的生词本 Demo 就是）。

30 秒实验

1. remove 不删：vector<int> v={1,5,3}; auto e = remove(v.begin(),v.end(),5); cout << v.size(); → 输出 3（没删）。加上 v.erase(e, v.end()) 后才变 2。
2. copy 到空容器会崩：vector<int> dst; copy(src.begin(), src.end(), dst.begin()); → 多半直接崩（dst.begin() 是无效位置）。改成 back_inserter(dst) 就好（13.4.1）。
3. partition 不保序、stable_partition 保序：同一个输入分别跑两个，比较"偶数"那一组的顺序。
4. random_shuffle 的现状：如果你的编译器是 C++17 以上，random_shuffle 会报"未定义/已移除"——这时改用 shuffle + mt19937（本节第三部分给了完整代码）。

常见误区

1. "remove 会把元素删掉"——不会！它只把要留的挪到前面，返回新的逻辑末尾，size() 不变。真删必须 v.erase(remove(...), v.end());
2. "list::remove 和 std::remove 一样"——不一样：成员版真删，算法版只挪位置。这是"同名不同行为"的经典陷阱。
3. "copy 会自己扩容"——不会。目标必须有空间（先 resize 或用 back_inserter）。算法改不了容器大小——这是它的设计边界。
4. "unique 能全局去重"——只合并相邻的。要先 sort（或者用 set 记录"见过"）。
5. "reverse 也能用在 list 上"——能（list 的迭代器是双向的，reverse 只要 ++ / -- 和交换）。但 list 有自己的成员 l.reverse()（13.1.3）——成员版更了解自己的结构，通常更快。
6. "random_shuffle 是标准函数，随便用"——C++14 弃用、C++17 移除。新代码用 std::shuffle + <random> 的引擎。好处：随机质量更好、还能固定种子复现。
7. "partition 分完组，两组内部还是原来的顺序"——不保证（这就是 stable_partition 存在的理由）。要保序就用 stable_partition，接受它慢一点。
8. "用了修正算法，"我的原数据肯定被改了""——分算法：copy / replace 可以只改"目标"（不改源）；但 sort / reverse / shuffle / partition / remove / unique 都是就地改的。要保留原数据，自己先复制一份。（13.3.1 的数据体检 Demo 里那个 vector<int> sorted(scores); 就是干这个。）

• ☐ 下一节（13.3.3 排序算法）

相关笔记

• 非修正序列算法（含实例03、04） —— 上一节：只看不改的那些
• 排序算法（含实例07） —— 下一节：sort 与二分查找
• 输出迭代器（含实例09） —— back_inserter 解决 copy 到空容器的问题
• 链表类模板 —— 成员版 remove / reverse / unique 是"真删"
• 向量类模板 —— 那个"边遍历边 erase"的难看循环，现在一行搞定
• 函数模板的定义 —— 算法为什么能"只认迭代器"
• 🔷 C++基础 · 索引 —— 全课路线图