Information and Computer Science 45C — Week 8 整合学习笔记

目录

• 1. 周学习目标
• 2. C++ 标准库
• 3. STL 框架 — 总体概念
• 4. 容器：分类总览
• 5. 序列容器（Sequence Containers）
• 6. 关联容器（Associative Containers）
• 7. 容器适配器（Container Adapters）
• 8. 把任务匹配到容器（Klefstad 练习）
• 9. STL Iterators
• 10. Iterator 分类
• 11. STL Algorithms
• 12. Iterator Adapters
• 13. 算法中的函数对象（Function Objects）
• 14. Ranges（C++20）
• 15. I/O 流 — iostream 库
• 16. 用 istream 做输入
• 17. 用 ostream 与 ios 做输出
• 18. 容器横向对比速查表
• 19. Week 8 综合 Cheat Sheet
• 20. Week 8 最重要的五条记忆

UCI ICS 45C: Programming in C++ (35770)
本笔记整合 Week 8 阅读材料：LearnCpp 21.1（标准库）、21.2（STL 容器总览）、21.3（STL iterator 总览）、21.4（STL 算法总览）、28.1（输入输出流）、28.2（用 istream 做输入）、28.3（用 ostream 与 ios 做输出）；cppreference 上 std::vector、std::set 与 std::map 的参考页；以及 Klefstad 教授的 Topic 8 PPT —— STL 容器、iterator、算法、insert/stream/reverse iterator adapter、容器适配器、函数对象与 ranges。内容按 主题 组织，而不是按出处。
关于跨周 PPT 内容的说明：Topic 8 PPT 的第 26–27 张幻灯片讲的是 标准 C++ 异常层次结构（std::bad_alloc、std::logic_error、std::runtime_error 等）。异常处理这部分属于 Week 7 阅读列表（LearnCpp 27.x），所以这里不再重复 —— 它们已经整合在 Week 7 笔记的 9–14 节里。如果想看一行版的标准异常层次回顾，参考 Week 7 cheat sheet 的 19.5 节。

1. 周学习目标

Week 8 三个概念板块的鸟瞰

1.1 标准模板库 — STL（chapters 21.1–21.4）

• 理解：什么是 C++ 标准库，以及它为什么存在
• 掌握：STL 的三方分解 —— containers、iterators、algorithms —— 以及它们如何组合在一起
• 区分：sequence containers（vector、deque、list、array、forward_list、string）vs. associative containers（set、map、multiset、multimap、unordered 各种版本）vs. container adapters（stack、queue、priority_queue）
• 掌握：为一项任务挑选合适的容器（sequence vs. associative；有序 vs. 无序;只存元素 vs. 键/值对）
• 掌握:iterator 抽象 —— begin()、end()、*、++、==，以及半开区间 [begin, end)
• 理解：iterator categories（input、output、forward、bidirectional、random-access、contiguous），以及它们为什么存在
• 掌握：常见 algorithms —— sort、find、min_element、max_element、reverse、accumulate、transform、for_each、copy
• 掌握：iterator adapters —— back_inserter、front_inserter、inserter、istream_iterator、ostream_iterator、reverse iterator
• 理解：作为算法实参的 function objects（普通函数、函数指针、lambda）
• 了解：C++20 ranges 作为传 begin/end 这一对的更高层替代

1.2 I/O 流（chapters 28.1–28.3）

• 理解：流（stream） 就是一段可以顺序读或写的字节序列
• 掌握：类层次 —— ios、istream、ostream、iostream，以及预定义的 cin/cout/cerr/clog
• 掌握：输入用的 提取运算符（>>）、输出用的 插入运算符（<<），包括跳过空白的行为
• 掌握：输入技巧 —— setw() 限制读取长度、get() / getline()（成员和自由函数两种）、gcount()、peek()、unget()、putback()、ignore()
• 掌握：输出格式化 —— 通过 flags（setf/unsetf）和 manipulators（std::hex、std::fixed、std::setprecision、std::setw、std::setfill、std::left/std::right）
• 区分：属于 format groups 的 flag（一组之内同一时刻只能有一个生效）

1.3 串联：Iterator 把一切串起来

• STL 的最大思想：算法操作的是 iterator range，不是 container。 一旦容器提供一对 iterator，<algorithm> 里的每个算法都能在它上面工作。
• Stream iterator 把 cin/cout/ifstream/ofstream 也变成了 iterator range —— 同一套算法因此可以同时跑在文件和键盘上。

2. C++ 标准库

对应 LearnCpp 21.1

2.1 什么是标准库？

C++ 标准库 是一组模板化类的集合，提供了可复用的 container、algorithm 和 iterator。绝大多数典型程序里需要的东西 —— 循环、字符串、数组、排序、查找 —— 都可以用它的组件搭出来，不必从头实现。

为什么要用它：

• 代码已经写好、调过、效率也基本过得去
• 它是 标准化的：同一个 std::vector 在不同编译器和平台上行为完全一致
• 它消除了一整类手写非类容器版本里常见的 bug

为什么有人怕它：

• 体量大，而且全是模板，错误信息很吓人
• 最好按小块学 —— 用到什么学什么，剩下的先放一边

💡 核心洞察（LearnCpp 21.1）
标准库 不是 C++ 语言的扩展 —— 它住在 std 命名空间里。从 C++ 的视角看，你和 std::vector 是 平等的：只要遵循约定，任何人都能写出一个让算法可以操作的容器。这就是 STL 对用户可扩展 的本质原因。

2.2 STL：标准库的一个子集

STL（Standard Template Library，标准模板库）这个名字有时被当作 "标准库" 的同义词，但从历史上看，STL 特指那套 container/iterator/algorithm 框架，主要由 Alexander Stepanov 设计。标准库的其他部分 —— <iostream>、<chrono>、<filesystem>、<regex> 等 —— 严格来说不属于 STL。

在本课中,"STL" 几乎总是指 container/iterator/algorithm 这一部分。

3. STL 框架 — 总体概念

对应 Topic 8 PPT slides 1–2

3.1 三大支柱

Klefstad 的幻灯片把设计哲学讲得很简洁：

STL 是 一个用来定义可组合库组件的框架：

• containers —— 装东西（stack、list、map 等等）
• iterators —— 把每个算法连到每个容器上
• algorithms —— 做事情（min、sort 等等）

想象一张 M×N 的表格：

• M 行 = M 种算法
• N 列 = N 种容器
• 没有 iterator 的话，每个格子都要写一份实现 → 总共 M × N 份
• 有了 iterator，每个算法只用 iterator 写一次，每个容器也只暴露一次 iterator → 总共只剩 M + N 份

这就是为什么 STL 能 scale。

3.2 配套组件

还有两块拼图把这个框架补完：

• Function objects（函数对象） —— 任何可调用的东西，都可以作为参数传给算法。这包括普通函数、函数指针、像函数指针一样行为的类（带 operator() 的 struct），以及 lambda（Week 7）。它们让算法 灵活，不必为每种调用方式写上千个重载。
• Standard exceptions（标准异常） —— 用于 STL 的错误处理（Week 7 已经讲过）。它们给 STL 操作提供了一套统一的报错方式（std::out_of_range、std::bad_alloc 等）。

3.3 扩展 STL

STL 对遵守约定的用户是可扩展的：

• 写一个暴露 begin() / end() 的容器，再写一个带相应运算符的 iterator 类 → 所有 STL 算法立即对你的容器有效。
• 写一个签名符合算法预期的 function object → 它就能被传给任何接受可调用对象的算法。

你已经在 HW6 里练过这个思想（Picture 链表配一个 iterator 风格的自定义遍历）。

4. 容器：分类总览

对应 LearnCpp 21.2 + Topic 8 PPT slide 3

4.1 三大容器家族

4.2 Klefstad 的实现策略区分（PPT slide 3）

Klefstad 重点强调容器背后的两种 实现策略：

• 基于数组的（Array-based） —— 连续内存,随机访问快（HW1 Stack、HW4 String）
• 基于链式结构的（Linked-structure-based） —— 节点 + 指针，中间插入快（HW5 String、HW6 Picture）

这件事很重要：挑容器时，底层数据结构决定了每个操作的 复杂度。vector 和 list 都装一串元素，但 vector[i] 是 O(1)，而 list[i] 根本不存在（只能一个节点一个节点走 —— O(n)）。

4.3 与 Python 的对比

⚠️ 陷阱
Python 的 list 对应 C++ 的 std::vector，不是 C++ 的 std::list。名字误导人 —— C++ std::list 是双向链表，没有随机访问的 []。

5. 序列容器（Sequence Containers）

对应 LearnCpp 21.2（sequence containers 部分）+ Topic 8 PPT slide 6

Sequence container 都会保留 你插入的顺序。它们之间怎么挑，看你需要哪些操作快、哪些可以慢。

5.1 std::vector

一个 动态可变大小的数组，存在连续内存里。现代 C++ 里使用最多的容器。

典型特征：

• 连续内存布局（所以 &v[0] 指向一段真正的 C 风格数组）
• 随机访问 O(1)，通过 operator[] 和 at()
• 尾部追加/弹出 O(1) 摊销：push_back()、pop_back()、back()
• 中间插入或删除是 O(n)（后面所有元素都要往前/后挪）
• 满了会自动扩容（通常容量翻倍）

LearnCpp 21.2 示例：

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> vect;
    for (int count=0; count < 6; ++count)
        vect.push_back(10 - count);   // insert at end

    for (int index=0; index < vect.size(); ++index)
        std::cout << vect[index] << ' ';
    std::cout << '\n';
}
// Output: 10 9 8 7 6 5

Klefstad PPT slide 6（明确强调 O(1)）：

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

int main() {
    vector<int> v;   // or vector<int> v2(100, 0);  with 100 elements init to zero
    for (int i = 0; i < 100; ++i)  // fill v
        v.push_back(i);            // appends to end of v
    for (int i = 0; i < v.size(); ++i)   // print v
        cout << v[i] << endl;
    for (; v.size() > 0; v.pop_back())   // drain v from the back
        cout << v.back() << endl;
}

💡 PPT 备注 —— "元素存在动态数组里 —— 像 Python list"

• push_back()、pop_back()、back() 都是 O(1)
• v[i] 也很快（随机访问）

值得记的构造函数：

std::vector<int> v1;                  // empty
std::vector<int> v2(100);             // 100 default-initialized ints (= 0)
std::vector<int> v3(100, 7);          // 100 copies of 7
std::vector<int> v4{1, 2, 3, 4};      // initializer-list: exactly these 4 elements
std::vector<int> v5(v1.begin(), v1.end()); // copy from a range

⚠️ 容易搞混 —— std::vector<int> v(100) 造的是一个 100 个 0 的 vector，而 std::vector<int> v{100} 造的是一个 只有一个元素、值为 100 的 vector。花括号 initializer-list 构造函数能匹配上时总是胜出。

5.1.1 size vs capacity（cppreference）

vector 跟踪 两个不同的量：

永远 size <= capacity。这个差距是因为增长是 摊销 O(1)：vector 容量用尽时，会分配一块更大的缓冲区（通常翻倍），把已有元素拷贝/移动过去，然后释放旧缓冲区。重分配开销大，所以 vector 会多分配一些 —— 提前留出余地，让后续 push_back 几乎是免费的。

💡 cppreference 原文（意译） —— "vector 通常会比静态数组占更多空间，因为为了应付后续增长会多分配一些内存。这样一来，vector 不需要每次插入元素都重分配，只在那块多分配的内存用完时才重分配。"

两个与性能相关的成员函数：

v.reserve(1000);     // bumps capacity to ≥ 1000 without changing size
                     // — use when you know roughly how many push_backs are coming
v.shrink_to_fit();   // requests that capacity shrink to size
                     // — non-binding; implementation may ignore it

⚠️ 最佳实践 —— 如果你知道（或能估算出）最终大小，在 push_back 的大循环前先用 reserve()。这能消掉 所有 重分配，以及连带的 iterator/指针失效。

5.1.2 复杂度小结（cppreference）

5.1.3 成员函数地图（cppreference）

💡 at() vs operator[] —— 都是用下标访问 vector。区别是：v.at(i) 在 i 非法时抛 std::out_of_range；v[i] 在 i 非法时是 未定义行为。无法保证下标合法时用 at()；性能敏感的内循环里用 []。

💡 push_back vs emplace_back —— push_back(x) 接收一个已经构造好的对象，把它 拷贝（或移动）进容器。emplace_back(args...) 把参数转发给元素的构造函数，就地构造，不产生临时对象。对于 int 这种平凡可拷贝类型没有区别。对于昂贵类型（std::string 或你自己写的类），emplace_back 能省一次移动。

5.1.4 Iterator 失效（cppreference —— 关键知识）

这是关于 std::vector 最重要的一张表，必须背下来。对 vector 的修改可能让指向它的 iterator（以及指针/引用）失效 —— 失效之后再用就是未定义行为。

⚠️ 经典 bug

for (auto it = v.begin(); it != v.end(); ++it)
    if (*it == bad)
        v.erase(it);    // ⚠️ it is invalidated after erase!

修法是用 erase-return 惯用法：it = v.erase(it);（而且在那次循环里别再 ++it）。或者直接用 C++20 的 std::erase / std::erase_if。

5.1.5 vector<bool> 特化（cppreference）

⚠️ 标准库为 bool 提供了 std::vector 的特化版本，可能针对空间效率做了优化。 这 并不是 一个真正的 vector<bool> —— 它打包成位，v[i] 返回的是一个 代理对象，不是真正的 bool&。许多在 vector<int> 上能跑的东西在 vector<bool> 上编不过（你拿不到指向元素的 bool*,某些泛型算法也用不了）。

如果你需要一段行为像普通 vector 的布尔序列，用 std::vector<char> 或 std::deque<bool>。需要 bitset 的话，std::bitset<N>（固定大小）或者 std::vector<bool>（动态）都可以 —— 只要清楚你拿到的是什么就行。

5.1.6 cppreference 示例

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = {8, 4, 5, 9};
    v.push_back(6);
    v.push_back(9);
    v[2] = -1;              // overwrite element at position 2

    for (int n : v)
        std::cout << n << ' ';
    std::cout << '\n';
}
// Output: 8 4 -1 9 6 9

5.2 std::deque（双端队列，发音 "deck"）

一种类似动态数组的容器，但 两端 都支持快速 push/pop。

典型特征：

• 前端和后端的 push/pop 都是 O(1)
• 通过 operator[] 的随机访问也是 O(1)，但比 vector 慢（它的存储通常是一串固定大小的块，不是一整段连续内存）
• 中间插入/删除是 O(n)

#include <iostream>
#include <deque>

int main()
{
    std::deque<int> deq;
    for (int count=0; count < 3; ++count)
    {
        deq.push_back(count);       // insert at back
        deq.push_front(10 - count); // insert at front
    }

    for (int index=0; index < deq.size(); ++index)
        std::cout << deq[index] << ' ';
    std::cout << '\n';
}
// Output: 8 9 10 0 1 2

5.3 std::list（双向链表）与 std::forward_list（单向链表）

std::list 是 双向链表，每个节点保存 prev、next 和元素值。std::forward_list 是 C++11 引入的单向变体（只有 next，更省内存，只能往前走）。

典型特征：

• 没有随机访问 —— 没有 operator[]、没有 at()。要访问第 i 个元素必须 walk the list（O(n)）。
• 在 任意位置 插入或删除是 O(1)，前提是手里已有一个指向那个位置的 iterator
• 其他地方插入/删除后，iterator 仍然有效（vector 的 iterator 不能这么保证）

LearnCpp 21.2: "List 只提供对头和尾的访问 —— 不提供随机访问。如果你想找中间某个值，必须从一端开始 'walk the list' 直到找到目标元素。"

list 适合那种 经常在中间插入/删除、不需要随机访问 的场景。

5.4 std::array（C++11，简单的 C 数组包装）

固定大小 的数组,大小是类型的一部分。本质上是 C 风格数组的一个更安全、与 STL 兼容的替代品。

std::array<int, 5> a{1, 2, 3, 4, 5};  // size 5 is part of the type

典型特征：

• 大小在编译期就已知，不动态分配
• 随机访问 O(1)
• 有 STL iterator（begin()、end()），所以能跟 std::sort、std::find 等配合
• 不能变大或变小

5.5 std::string 作为 sequence container

虽然 LearnCpp 提到 string 一般 不被归到 sequence container 里，但 它本质上就是一种 sequence container：行为像一个 vector<char>，外加一些字符串专属的辅助函数（+、substr、find 等）。它暴露同样的 iterator 接口，所以 STL 算法在字符串上原封不动就能跑。

std::string s = "world";
std::reverse(s.begin(), s.end());  // s == "dlrow"

6. 关联容器（Associative Containers）

对应 LearnCpp 21.2（associative containers 部分）+ Topic 8 PPT slides 7–10

关联容器在插入时 自动排序（或哈希）。位置不由你决定 —— 容器决定。

默认比较：operator<。你也可以传一个自定义比较器。

6.1 std::set 与 std::multiset

set —— 一个按值排序的 唯一 元素集合。 multiset —— 同上，但允许重复。

操作及复杂度（平衡 BST 版本都是 O(log n)）：

• insert(x) —— 加入 x；set 上若已存在则什么都不做
• find(x) —— 返回指向 x 的 iterator，找不到返回 end()
• erase(x) 或 erase(iter) —— 删除
• 遍历会按 排序顺序 输出元素

Klefstad PPT slide 8 示例：

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<char> S;
    for (char c = 'A'; c <= 'Z'; ++c)   // fill S
        S.insert(c);
    for (char c = 'Z'; c >= 'A'; --c)   // fill S again
        S.insert(c);                    // duplicates are silently rejected
    for (auto E : S)
        cout << E << endl;              // each letter appears exactly once

    if (S.find('A') != S.end())
        cout << "A is in there" << endl;
}

如果把 S 换成 multiset，因为每个字母都被插了两次，你会看到 A A B B C C ... Z Z。

💡 概念提醒
std::set 不是 Python 的 set。Python 的 set 是哈希表（无序，O(1) 查找）。C++ 的 std::set 是 平衡二叉搜索树（有序，O(log n) 查找）。哈希版本叫 std::unordered_set。

6.1.1 实现与唯一性规则（cppreference）

💡 cppreference（意译） —— std::set 是 一组按类型 Key 排序的、唯一的对象。查找、删除、插入都是 对数时间。Set 通常实现为红黑树 —— 一种自平衡的二叉搜索树。

唯一性是按等价（equivalence）定义的，不是相等（equality）：

当满足下式时，两个元素 a 与 b 被认为 "相同"（set 里只留一份）：

!comp(a, b) && !comp(b, a)

通俗讲：在比较函数下，谁都不严格 小于 谁。默认 comp 是 std::less<Key>，它用的就是 operator<。

⚠️ 微妙的推论 —— std::set 永远不调用 operator==。它只调用 operator<。所以一个 < 行为怪、== 行为正常的类型，可能在 set 里出现意外的 "重复" 或 "不重复"。

⚠️ 通过 iterator 访问的元素是 const 的。 对 set<Key> 的 iterator 解引用得到的是 const Key&，不是 Key&。你 不能 原地修改元素 —— 改了可能破坏排序不变量、悄悄地把树搞坏。要 "改" 一个元素就：erase 旧的，再 insert 新的。（这就是为什么 std::map 的 value_type 是 pair<const Key, T> —— key 部分是 const，也是同一个不变量的要求。）

6.1.2 成员函数地图（cppreference）

💡 contains（C++20） 是现代版本里检查成员关系的惯用写法：

if (s.contains(x))  { /* ... */ }   // C++20
if (s.find(x) != s.end()) { /* ... */ }   // pre-C++20 equivalent

💡 set 上的 count 只会返回 0 或 1（因为 key 唯一）。在 multiset 上可能更大。无论哪种情况，用 count(x) > 0 检查成员关系都不如 contains(x) 高效 —— 后者在第一次匹配上就可以短路。

6.1.3 范围查询 —— lower_bound、upper_bound、equal_range

这三个函数在 已排序 的 set 上返回 iterator，适合做范围查询：

在 multiset [1, 2, 2, 2, 3] 中：

• lower_bound(2) → 指向第一个 2 的 iterator
• upper_bound(2) → 指向 3 的 iterator
• 在这两者之间遍历，会访问到所有的 2。

6.1.4 cppreference 示例

#include <iostream>
#include <set>
#include <string_view>

int main() {
    std::set<int> set{1, 5, 3};
    // set: { 1, 3, 5 }  — automatically sorted on construction

    set.insert(2);
    // set: { 1, 2, 3, 5 }

    set.erase(1);
    // set: { 2, 3, 5 }

    // C++20 contains
    if (set.contains(3))
        std::cout << "set contains 3\n";

    // Range-constructor from any iterable
    std::string_view word = "element";
    std::set<char> characters(word.begin(), word.end());
    // characters: { e, l, m, n, t }   — 5 unique characters
}

💡 Range 构造惯用法 —— 每个 STL 容器都接受一对 (begin, end) iterator，所以你可以用 string 造 set<char>、用 vector<int> 造 set<int>，等等。

6.2 std::map 与 std::multimap

map —— 一组 键/值对，按 key 排序，key 唯一。 multimap —— 同上，但允许同一个 key 对应多个 value。

每个元素是 std::pair<const Key, Value>，通过 .first（key）和 .second（value）访问。

Klefstad PPT slide 9 —— "元素是 pair<first, second>，可看作 pair<key, value> —— 行为像数组，但可以用任意类型当下标（像 Python 字典）。元素按 first 排序（不按 second）。"

Multimap 当作真正的字典： 现实世界中的字典是一个单词（key）对应一个或多个释义（value）—— 这恰好是 multimap，不是 map。

LearnCpp 21.3 示例：

#include <map>
#include <string>
#include <iostream>

int main() {
    std::map<int, std::string> mymap;
    mymap.insert(std::make_pair(4, "apple"));
    mymap.insert(std::make_pair(2, "orange"));
    mymap.insert(std::make_pair(1, "banana"));
    mymap.insert(std::make_pair(3, "grapes"));
    mymap.insert(std::make_pair(6, "mango"));
    mymap.insert(std::make_pair(5, "peach"));

    auto it{ mymap.cbegin() };
    while (it != mymap.cend()) {
        std::cout << it->first << '=' << it->second << ' ';
        ++it;
    }
    std::cout << '\n';
}
// Output: 1=banana 2=orange 3=grapes 4=apple 5=peach 6=mango

Klefstad PPT slide 10 —— 三种遍历方式：

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> A;
    A["Bill"]   = 33;
    A["George"] = 29;
    A["Al"]     = 27;

    // Way 1: classic for-each, E is a pair<string,int>
    for (auto E : A)
        cout << E.first << " is " << E.second << " ";

    // Way 2: C++17 "destructuring for loop" — by const reference (no copy)
    for (const auto& [name, age] : A)
        cout << name << " is " << age << " ";

    // Both print: Al is 27 Bill is 33 George is 29
}

💡 核心洞察 —— map 按 first 字段排序，所以遍历时 key 按升序输出：Al、Bill、George。

map 的中括号运算符：

A["Bill"] = 33;   // insert or overwrite key "Bill" with value 33
int x = A["Al"];  // read the value at key "Al"

⚠️ 陷阱 —— 在不存在的 key 上 A["NewKey"] 会 插入 一个 默认构造值（int 是 0，string 是 ""）的新条目，并返回它的引用。要 只判断是否存在、不插入，用 A.find(key) != A.end() 或（C++20）A.contains(key)。

6.2.1 实现与排序顺序（cppreference）

💡 cppreference（意译） —— std::map 是 一个有序的关联容器，存放唯一 key 的 key-value 对。查找、删除、插入都是 对数时间。Map 通常实现为红黑树。

Iterator 会按 key 升序 访问元素（用比较函数 —— 默认是 std::less<Key>）。

唯一性规则跟 set 一样基于 等价：key a 与 b 在 !comp(a, b) && !comp(b, a) 时被认为相同。

6.2.2 value_type = std::pair<const Key, T>（cppreference）

一个微妙但关键的细节：map<Key, T> 的每个元素是

std::pair<const Key, T>

—— 注意 Key 上的 const。你不能在元素插入之后原地改 key（改了会破坏排序顺序）。要 "改" key,只能 erase 旧条目再 insert 新的。

你会见到的三个类型别名：

6.2.3 元素访问：at() vs operator[]

⚠️ 三个含义：

• 你 不能 在 const map 上用 operator[] —— 它可能会插入！
• 你 不能 在 T 没有默认构造函数时用 operator[]。
• m[k] 即使你写成 int x = m[k]; 也是一次 写 —— 它会创建一条新条目。要做只读访问，用 m.find(k)、m.contains(k)（C++20）或 m.at(k)。

6.2.4 成员函数地图（cppreference）

值得记的三种 insert 变体（C++17）：

💡 为什么需要 try_emplace？ 假设 T 构造起来很贵（比如要靠函数调用造一个大 std::string）。insert({k, expensive_construct()}) 总是会构造 value，即使 k 已存在、然后又把它丢掉。try_emplace(k, args_for_construct...) 只在需要时才构造。

emplace_hint(hint, args...) —— 跳过 O(log n) 的搜索：

insert 和 emplace 通常会做一次 O(log n) 的树搜索来定位新元素该放哪里。emplace_hint 让你传一个 iterator 来告诉它 "从这里开始找"：

std::map<int, std::string> m;
auto it = m.end();
for (int i = 0; i < 1000; ++i)
    it = m.emplace_hint(it, i, "v");   // 摊还 O(1) 一次，而不是 O(log n)

• 如果 hint 指向 紧挨着 新元素应该放的位置，插入会是 摊还 O(1) 而不是 O(log n)。
• 如果 hint 给错了，实现会退回到普通的 O(log n) 搜索 —— 所以乱给的 hint 没额外代价，但也帮不上忙。
• 经典用法：批量插入已经排好序的数据（上面的写法，或者键单调递增时反复传 m.end()）。set / multiset / multimap 上也有同样的技巧。

6.2.5 cppreference 示例

#include <iostream>
#include <map>
#include <string>

void print_map(std::string_view label, const std::map<std::string, int>& m) {
    std::cout << label;
    for (const auto& [key, value] : m)        // C++17 structured binding
        std::cout << '[' << key << "] = " << value << "; ";
    std::cout << '\n';
}

int main() {
    // List-initialization with brace-pair entries
    std::map<std::string, int> m{{"CPU", 10}, {"GPU", 15}, {"RAM", 20}};
    print_map("1) Initial:  ", m);
    // 1) Initial:  [CPU] = 10; [GPU] = 15; [RAM] = 20;

    m["CPU"] = 25;   // update existing
    m["SSD"] = 30;   // insert new
    print_map("2) Updated:  ", m);
    // 2) Updated:  [CPU] = 25; [GPU] = 15; [RAM] = 20; [SSD] = 30;

    // ⚠️ operator[] on a NON-EXISTENT key inserts default value (0 for int)
    std::cout << "3) m[UPS] = " << m["UPS"] << '\n';
    // 3) m[UPS] = 0
    // m now contains UPS=0 even though we only "read" it!

    m.erase("GPU");
    print_map("4) After erase: ", m);

    // C++20: erase_if free function
    std::erase_if(m, [](const auto& pair){ return pair.second > 25; });
    print_map("5) After erase_if (>25): ", m);

    std::cout << "size = " << m.size() << '\n';
    m.clear();
    std::cout << std::boolalpha << "empty? " << m.empty() << '\n';
}

💡 List-initialization 语法 —— {{"CPU", 10}, {"GPU", 15}} 是两个 brace-init-list，每个构造一个 pair<string, int>，最外层再包成一个 initializer_list<pair> 传给 map 的构造函数。你会一直看到这个写法。

6.2.6 迭代器失效（set / multiset / map / multimap）

有序关联容器底层是树，所以失效规则比 vector 友好得多 —— 这是它们在实践中最大的优势之一。

💡 和 vector 对比 —— vector::insert 可能让插入点之后的 所有 iterator 失效（reallocation 时则全部失效）。set/map 这边即使在 iteration 过程中插入，已经持有的 iterator 也还是安全的。

iteration 中安全 erase 的写法（因为 erase 只会让 被删的 iterator 失效，你必须接住返回值）：

for (auto it = m.begin(); it != m.end(); ) {
    if (should_remove(*it))
        it = m.erase(it);     // erase 返回指向 **下一个** 元素的 iterator
    else
        ++it;
}

或者 C++20 直接用：std::erase_if(m, predicate) 帮你做（参见 §6.2.5 的示例）。

6.3 std::unordered_set 与 std::unordered_map

C++11 加入的 哈希表 版本。

• 平均 O(1) 的 insert、find、erase（有序版本是 O(log n)）
• 元素 没有 任何有意义的顺序
• 不需要排序遍历、追求速度时用这一组

6.4 速查对比表

7. 容器适配器（Container Adapters）

对应 LearnCpp 21.2（container adapters 部分）+ Topic 8 PPT slide 23

容器适配器是 包在已有 sequence container 外面的壳；它对外暴露一套 受限 的接口，对应到某个特定的抽象数据类型。底层用哪个容器你可以自己选（也有合理的默认值）。

7.1 std::stack —— LIFO

栈 是 后进先出（Last-In, First-Out）的容器。

#include <stack>
std::stack<int> s;
s.push(1);
s.push(2);
s.push(3);
int top = s.top();   // 3
s.pop();             // removes 3

Klefstad PPT slide 23 —— 对底层容器的要求：

可以用任何支持 empty、size、back、push_back、pop_back 的容器。
兼容的底层：vector、deque、list。默认：deque。

💡 PPT 备注 —— "默认是 deque（看上去有点奇怪，毕竟 vector 似乎更自然）。" 这是历史/效率上的选择 —— deque 避开了 vector::push_back 在容量超出时周期性重分配的开销。

7.2 std::queue —— FIFO

队列 是先进先出（First-In, First-Out）：尾部插入,头部删除。

#include <queue>
std::queue<int> q;
q.push(1);
q.push(2);
int front = q.front();   // 1
q.pop();                 // removes 1

对底层容器的要求：支持 empty、size、front、back、push_back、pop_front。 兼容的底层：deque、list。默认：deque。

⚠️ queue 为什么不用 vector？ 因为 vector 没有 pop_front —— 从前面删元素得 O(n)。

7.3 std::priority_queue —— 有序队列

队列里的元素被维护成有序的（默认按 operator<）。pop 始终返回 优先级最高 的那一个。

#include <queue>
std::priority_queue<int> pq;
pq.push(3); pq.push(1); pq.push(7); pq.push(4);
int big = pq.top();   // 7
pq.pop();

兼容的底层：vector、deque。默认：vector。

它内部用 二叉堆（binary heap） 实现，所以：

• push —— O(log n)
• pop —— O(log n)
• top —— O(1)

8. 把任务匹配到容器（Klefstad 练习）

对应 Topic 8 PPT slide 5（练习）

Klefstad 的幻灯片提了一个小练习：给每项任务挑出合适的 STL 容器家族（Set、Map、Vector）。下面是一种合理的匹配方案 + 理由 —— 这就是这门课希望你能快速做出的取舍：

⚠️ 通用经验法则

• 主要做 遍历、追加 或 按位置索引 —— 用 Vector
• 按 key 查找 并要关联一个 value —— 用 Map
• 只关心 成员关系（或要排序的唯一元素）—— 用 Set
• 不需要排序遍历的话,用 Unordered_ 版本

9. STL Iterators

对应 LearnCpp 21.3 + Topic 8 PPT slides 11–13

9.1 什么是 Iterator？

Iterator 是一个不暴露容器实现细节、就能在容器上遍历的对象。可以把它想成 智能指针，它知道在自己所在的数据结构里 "如何走到下一个元素"。

为什么 iterator 重要 —— 引 LearnCpp 21.3、加上课程相关的强调：

在很多类（特别是 list 和 associative class）里，iterator 是访问元素的 主要方式。

你不能在 std::list 上写 myList[5]。但你可以在指向 list 的 iterator 上写 *it。同样的表达式对 vector iterator、set iterator、map iterator 也都成立。

💡 核心洞察
Iterator 最好被想象成 指向容器里某个元素的指针，它重载了若干运算符，看上去像指针算术，实际上做的是 对那个容器来说合适的遍历。

9.2 Iterator 的运算（五大件）

来自 Topic 8 PPT slide 12 + LearnCpp 21.3：

⚠️ 微妙但关键 —— == 比较两个 iterator 时检查的是 它们是否指向同一个位置，不是元素值是否相等。要比较值，先解引用：*it1 == *it2。

9.3 begin()、end()、cbegin()、cend()

每个容器都暴露四个基本的成员函数用来拿 iterator：

💡 核心洞察 —— 半开区间 [begin, end)
end() 不 指向最后一个元素;它指向最后一个元素之后一个位置。这是故意的：

for (auto it = c.begin(); it != c.end(); ++it) { ... }

当终止条件是 it != end() 时,循环写起来最干净。如果 end() 指最后一个元素，你就得用 <=（iterator 通常不支持），还要为空容器做特判。

9.4 不同容器上的遍历

LearnCpp 21.3 的四个示例展示了 iterator 接口的 统一性：

Vector：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vect;
    for (int count = 0; count < 6; ++count)
        vect.push_back(count);

    std::vector<int>::const_iterator it;
    it = vect.cbegin();
    while (it != vect.cend()) {
        std::cout << *it << ' ';
        ++it;
    }
    std::cout << '\n';
}
// 0 1 2 3 4 5

List —— 循环写法一模一样，只是容器换了：

#include <list>
std::list<int> li;
for (int count = 0; count < 6; ++count)
    li.push_back(count);

std::list<int>::const_iterator it;
it = li.cbegin();
while (it != li.cend()) {
    std::cout << *it << ' ';
    ++it;
}
// 0 1 2 3 4 5

💡 这就是 iterator 的全部意义 —— "注意代码跟 vector 那个几乎完全一样,虽然 vector 和 list 的内部实现几乎完全不同！"（LearnCpp 21.3）

Set —— 还是同样的循环，但 输出是有序的，因为 set 在插入时就排好序：

#include <set>
std::set<int> myset;
myset.insert(7); myset.insert(2); myset.insert(-6);
myset.insert(8); myset.insert(1); myset.insert(-4);

auto it = myset.cbegin();
while (it != myset.cend()) {
    std::cout << *it << ' ';
    ++it;
}
// -6 -4 1 2 7 8   (sorted!)

Map —— 一个小拐弯：每个 *it 是一个 std::pair，所以用 it->first 和 it->second：

std::map<int, std::string> mymap;
mymap.insert(std::make_pair(4, "apple"));
// ...etc

auto it{ mymap.cbegin() };
while (it != mymap.cend()) {
    std::cout << it->first << '=' << it->second << ' ';
    ++it;
}
// 1=banana 2=orange 3=grapes 4=apple 5=peach 6=mango

9.5 范围 for 循环（现代惯用法）

上面四个循环都可以用范围 for 重写,它本质上 底层就是 iterator 驱动 的：

for (auto e : V)           // copy each element
    std::cout << e;

for (const auto& E : V)    // reference (no copy) to each element
    std::cout << E;

Topic 8 PPT slide 12：

• auto e : V —— e 是每个元素的 拷贝
• auto const& E : V —— E 是 const 引用（无拷贝，不能改）
• auto& E : V —— 非 const 引用（可以改）

⚠️ 最佳实践 —— 元素类型不平凡时（string、struct 等），优先用 const auto&，避免不知不觉地把整个容器的每个元素都拷一遍。

9.6 自定义 Iterator：链表 iterator（PPT slide 13）

Klefstad 走了一遍链表上 iterator 的样子。这是写自己的 iterator 时的 概念蓝图（如果 HW7+ 涉及让自己的容器可遍历，会用到）。

PPT 的设定：

struct Node { char data; Node * next; };

struct List {
    Node *head;
    struct iterator { /* see below */ };
    iterator begin();
    iterator end();
    // ...
};

三种等价的遍历写法：

List L;

// 1. Manual pointer walk (no STL)
for (Node *p = L.head; p != nullptr; p = p->next)
    std::cout << p->data;

// 2. STL iterator style
for (List::iterator it = L.begin(); it != L.end(); ++it)
    std::cout << (*it).data;

// 3. Range-based for (requires begin/end + iterator operators)
for (auto e : L)
    std::cout << e;

iterator 类本身 持有一个 node 指针，并重载相应的运算符：

struct List::iterator {
    Node * ptr;
    auto operator*()  -> char&  { return ptr->data; }
    auto operator->() -> Node*  { return ptr; }
    auto operator++() -> iterator& { ptr = ptr->next; return *this; }
    bool operator==(const iterator& other) const { return ptr == other.ptr; }
    bool operator!=(const iterator& other) const { return ptr != other.ptr; }
};

List::begin() 返回 iterator{head}；List::end() 返回 iterator{nullptr}。

💡 核心洞察
Iterator 是 每个类自己写的 —— 每个容器都得写自己的 iterator，因为 iterator 必须懂这个数据结构怎么遍历。STL 的精妙之处在于 algorithm 不必懂这件事；algorithm 只看到 iterator 接口。

10. Iterator 分类

对应 Topic 8 PPT slide 21

STL iterator 是一组 按能力分级的层次。每一类支持的操作严格包含前一类。algorithm 声明自己需要的 最低 iterator 等级，这就决定了它能在哪些容器上用。

💡 PPT 备注（slide 21） —— "在现代架构的 cache 上表现很好。" Contiguous iterator 正是 vector 在实践中常常比 list 快得多的根本原因，哪怕复杂度分析说它们应该一样：cache 预取让连续遍历几乎是零开销的。

⚠️ 实战含义

• std::sort 要求 random-access iterator → 能跑在 vector、deque、array、string 上,但 不能 跑在 list 或 set 上。std::list 自带一个成员 .sort()。
• std::binary_search 要求 forward iterator（且范围已排序）
• 只需要 walk 一遍的算法（std::find、std::accumulate、std::copy）用 input iterator 就够 —— 所以它们也能跑在流上

11. STL Algorithms

对应 LearnCpp 21.4 + Topic 8 PPT slides 14–15

11.1 总览

💡 大思路（LearnCpp 21.4）
Algorithm 实现为 基于 iterator 工作的函数。每个 algorithm 只写一次,就对所有提供匹配 iterator 的容器都有效 —— 包括你自己写的容器。这就是 STL 可组合的关键。

要用任何 STL algorithm，#include <algorithm>。数值算法（std::accumulate、std::iota）住在 <numeric> 里。

⚠️ 警告（LearnCpp 21.4） —— 某些 algorithm 与 container 的组合可能根本不工作、可能死循环、或者效率极差。最典型的几个：

• 对 std::list 调 std::sort 是 编译错误（list 的 iterator 不是 random-access）
• 但 list.sort()（成员函数）存在且高效
• 别传非法 iterator 对（end 在 begin 前面）—— 未定义行为

11.2 查找与 Min/Max

min_element / max_element / iota（PPT slide 15 + LearnCpp 21.4）：

#include <algorithm>   // min_element, max_element
#include <iostream>
#include <list>
#include <numeric>     // iota

int main() {
    std::list<int> li(6);
    std::iota(li.begin(), li.end(), 0);   // fills with 0,1,2,3,4,5

    std::cout << *std::min_element(li.begin(), li.end()) << ' '
              << *std::max_element(li.begin(), li.end()) << '\n';
    return 0;
}
// Output: 0 5

💡 iota 做什么
iota(begin, end, start) 把一个范围填成从 start 开始的连续值：start, start+1, start+2, ...。名字来自希腊字母 ι（APL 里用同一个符号做同样的操作）。

find（LearnCpp 21.4 + PPT slide 15）：

std::list<int> li(6);
std::iota(li.begin(), li.end(), 0);
auto it = std::find(li.begin(), li.end(), 3);   // returns iterator to 3
li.insert(it, 8);                               // insert 8 just before 3
for (int i : li) std::cout << i << ' ';
// Output: 0 1 2 8 3 4 5

⚠️ 关键惯用法 —— 检查 find 的返回值：
找不到时,find 返回 end iterator。解引用之前一定要先判：

if (it == li.end()) { std::cout << "not found\n"; }
else                { /* safe to use *it or it */ }

11.3 排序与反转

#include <vector>
#include <algorithm>

int main() {
    std::vector<int> vect{ 7, -3, 6, 2, -5, 0, 4 };

    std::sort(vect.begin(), vect.end());
    // vect: -5 -3 0 2 4 6 7

    std::reverse(vect.begin(), vect.end());
    // vect: 7 6 4 2 0 -3 -5
}

用比较器做反序排序：

#include <functional>
std::sort(vect.begin(), vect.end(), std::greater<int>{});
// Or with a lambda:
std::sort(vect.begin(), vect.end(), [](int a, int b){ return a > b; });

⚠️ Klefstad 的警告 —— std::sort 在 std::list 上 不能用。list iterator 是 bidirectional,不是 random-access。用 myList.sort()（成员函数）来代替 —— 它在渐进意义上对 list 也更快，因为它可以重排链接而不必移动元素。

11.4 中间反转、accumulate、transform（PPT slide 15）

Topic 8 PPT slide 15 展示了一个比 LearnCpp 21.4 更丰富的 algorithm demo。值得记下来：

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

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

    auto pos = min_element(V.begin(), V.end());
    cout << "Min = " << *pos << endl;        // returns iterator to V[3] (= 1)

    sort(V.begin(), V.end());                // V is {1, 2, 3, 4, 5, 6}

    pos = find(V.begin(), V.end(), 3);       // iterator to V[2]
    reverse(pos, V.end());                   // V is {1, 2, 6, 5, 4, 3}

    cout << "Total = " << accumulate(V.begin(), V.end(), 0) << endl;
    // prints Total = 21

    transform(V.begin(), V.end(), V.begin(),
              [](int i){ return i + 1; });
    // V is now {2, 3, 7, 6, 5, 4}
}

这里出场了三个新算法：

• accumulate(first, last, init) —— 把范围里的元素以 init 起始累加（在 <numeric> 里）。初值的类型决定了结果类型：accumulate(v.begin(), v.end(), 0) 返回 int；想要 double 就传 0.0。
• reverse(first, last) —— 原地反转范围；传中间的 iterator 即可只反转 子范围。
• transform(in_begin, in_end, out_begin, fn) —— 把 fn 应用到输入范围的每个元素上,结果写到 out_begin 开始的位置。当 out_begin == in_begin 时变成原地变换。

11.5 其他常见算法（参考）

11.6 谓词算法 — all_of / any_of / none_of（C++11）

这三个返回 bool —— 用谓词扫一遍范围,回答 "全部?有一个吗?都没有?":

#include <algorithm>
#include <vector>

std::vector<int> v{2, 4, 6, 8};

bool all_even  = std::all_of (v.begin(), v.end(), [](int x){ return x % 2 == 0; });   // true
bool any_neg   = std::any_of (v.begin(), v.end(), [](int x){ return x  <  0; });      // false
bool none_zero = std::none_of(v.begin(), v.end(), [](int x){ return x ==  0; });      // true

💡 短路求值 —— 都在第一个反例（all_of / none_of）或第一个命中（any_of）时停止,不会扫完范围。

11.7 Erase-Remove 惯用法

§11.5 提了 remove(b, e, val) 不真删 —— 它只是把不等于 val 的元素往前移,然后返回一个 iterator 指向 "新的逻辑末尾"。容器大小不变,后面那段是 "残留":

std::vector<int> v{1, 2, 3, 2, 4, 2, 5};
auto new_end = std::remove(v.begin(), v.end(), 2);
// v 现在是 {1, 3, 4, 5, ?, ?, ?}      ← 后三个是 unspecified
// new_end 指向第 5 个位置（? 开始那里）
// v.size() 还是 7 — 没删!

Erase-remove 惯用法 —— 用 erase(new_end, v.end()) 把残留段切掉:

v.erase(std::remove(v.begin(), v.end(), 2), v.end());
// 现在 v 是 {1, 3, 4, 5},size() == 4

带谓词的版本 —— remove_if:

v.erase(std::remove_if(v.begin(), v.end(),
                       [](int x){ return x % 2 == 0; }),
        v.end());
// 移除所有偶数

C++20 的现代写法 —— std::erase / std::erase_if 是上面这套的内置版本,一行搞定:

std::erase(v, 2);                                  // ≡ erase-remove(v, 2)
std::erase_if(v, [](int x){ return x % 2 == 0; }); // ≡ erase-remove_if

⚠️ std::list 不要用这套 —— list 有自己的成员函数 myList.remove(val) 和 myList.remove_if(pred),真删而且 O(n) —— 别套 erase-remove（对链表没必要,链表删除是 O(1) 节点重连）。

11.8 容器比较 —— equal / mismatch / lexicographical_compare

std::vector<int> a{1, 2, 3, 4};
std::vector<int> b{1, 2, 3, 4};
std::vector<int> c{1, 2, 9, 4};

bool eq = std::equal(a.begin(), a.end(), b.begin());   // true（元素逐个 ==）

auto [ita, itb] = std::mismatch(a.begin(), a.end(), c.begin());
// ita -> a[2] (= 3), itb -> c[2] (= 9) — 第一处不同

💡 直接用容器的 == —— 对相同类型的两个标准容器,a == b 已经做了 size 检查 + 逐元素比较,通常更简洁。std::equal 用在类型不同但内容应该等价的场景（比如 vector<int> 和 int[],或者比 vector<int> 的子区段）。

11.9 排序范围上的集合算法

⚠️ 前提:两个输入范围都必须是已排序的! 跟 binary_search、lower_bound 一样。这些算法不是给 std::set 用的,而是给任意排序范围（包括 vector、MapArray::keys()、std::set）用的。

#include <algorithm>
#include <vector>
#include <iterator>

std::vector<int> a{1, 2, 3, 4, 5};
std::vector<int> b{3, 4, 5, 6, 7};

std::vector<int> out;
std::set_union       (a.begin(), a.end(), b.begin(), b.end(),
                      std::back_inserter(out));   // {1,2,3,4,5,6,7}

out.clear();
std::set_intersection(a.begin(), a.end(), b.begin(), b.end(),
                      std::back_inserter(out));   // {3,4,5}

out.clear();
std::set_difference  (a.begin(), a.end(), b.begin(), b.end(),
                      std::back_inserter(out));   // {1,2}   （在 a 但不在 b）

💡 跨周链接:HW9 的 MapArray —— 它内部是排序的 vector<pair<K,V>>,所以这些算法直接能用 —— 只要你的比较器只看 pair::first 就行。Week 9 §14 见。

11.10 堆算法 —— <algorithm>

<algorithm> 直接提供操作任意 random-access 范围的堆操作 —— 这正是 std::priority_queue（§7.3）内部用的东西,但你也可以拿来在自己的 vector 上手动维护堆:

#include <algorithm>
#include <vector>

std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6};

std::make_heap(v.begin(), v.end());          // 重排成 max-heap, v.front() 是最大
// v: 9 6 4 3 5 1 2 1   （具体顺序由实现决定,但根永远是最大）

std::cout << v.front() << '\n';              // 9 — 堆顶

v.push_back(10);                             // 先 push_back
std::push_heap(v.begin(), v.end());          // 然后让新元素 sift-up

std::pop_heap(v.begin(), v.end());           // 把堆顶搬到末尾,然后修复堆
int top = v.back();
v.pop_back();                                // 真删

std::sort_heap(v.begin(), v.end());          // 把堆变成有序范围（O(n log n)）

默认是 max-heap（用 <）,想 min-heap 传 std::greater<>{}:

std::make_heap(v.begin(), v.end(), std::greater<>{});

💡 vs. priority_queue —— 适配器 priority_queue（§7.3）就是用 make_heap/push_heap/pop_heap 实现的,只是把 vector + 这些函数封装起来。直接用这些函数的好处:你能同时访问范围内所有元素（适配器只能看 top()）,还能用 sort_heap 一键把堆转成排好序的范围。

11.11 <numeric> 数值算法全家桶

§11.2 已经见过 iota,§11.4 见过 accumulate。<numeric> 里还有几个常用的:

#include <numeric>
#include <vector>
#include <functional>

std::vector<int> v{1, 2, 3, 4, 5};

// 1. iota — 填充连续递增值（§11.2）
std::iota(v.begin(), v.end(), 0);                                   // {0, 1, 2, 3, 4}

// 2. accumulate — 累加（§11.4）,也能用自定义二元运算
int sum  = std::accumulate(v.begin(), v.end(), 0);                  // 0+0+1+2+3+4 = 10
int prod = std::accumulate(v.begin(), v.end(), 1, std::multiplies<>{}); // 1*0*1*2*3*4 = 0

// 3. inner_product — 两个范围的点积
std::vector<int> a{1, 2, 3}, b{4, 5, 6};
int dot = std::inner_product(a.begin(), a.end(), b.begin(), 0);     // 1*4+2*5+3*6 = 32

// 4. partial_sum — 前缀和
std::vector<int> ps(v.size());
std::partial_sum(v.begin(), v.end(), ps.begin());                   // {0, 1, 3, 6, 10}

// 5. adjacent_difference — 相邻差（partial_sum 的反向）
std::vector<int> diff(v.size());
std::adjacent_difference(v.begin(), v.end(), diff.begin());         // {0, 1, 1, 1, 1}

C++17 并行友好版（只是认识一下）:

⚠️ accumulate 初值类型决定结果类型 —— accumulate(v.begin(), v.end(), 0) 即使 v 是 vector<double> 也会全部截断成 int。要 double 结果就传 0.0。

12. Iterator Adapters

对应 Topic 8 PPT slides 16–18、22

Iterator adapter 是一种 iterator，它把别的东西（一种容器插入操作、一个流，或一个前向 iterator）包起来，对外暴露 iterator 接口 —— 这样被包的东西就能用在任何期望 iterator 的地方。

12.1 Insert Iterators —— back_inserter、front_inserter、inserter

普通 iterator 会覆盖元素。Insert iterator 在每次赋值时调用容器的 push_back、push_front 或 insert,从而 把容器撑大。

没有 insert iterator 的话，copy 会写到空目标 后面（未定义行为）。有了它，目标会自动扩大。

PPT slide 16 —— 完整示例：

int main() {
    list<int> L;
    for (int i = 1; i <= 10; ++i)
        L.push_back(i);

    // back_inserter: each assignment calls V.push_back(...)
    vector<int> V;
    copy(L.begin(), L.end(),     // source
         back_inserter(V));       // destination

    // front_inserter: each assignment calls D.push_front(...)
    deque<int> D;
    copy(L.begin(), L.end(),
         front_inserter(D));

    // inserter: each assignment calls S.insert(hint, ...)
    // inserter works on associative containers too
    set<int> S;
    copy(begin(L), end(L),
         inserter(S, std::next(begin(S))));
}

⚠️ 陷阱 —— set 或 map 没有 back_inserter，因为关联容器自己决定位置。用 inserter(s, s.end())，或者干脆 s.insert(x)。

12.2 Stream Iterators —— istream_iterator 与 ostream_iterator

Stream iterator 把 cin、cout、ifstream、ofstream 变成一个 STL iterator range。这就是让你能直接从文件 copy 到容器，或者从输入 transform 到输出的关键。

PPT slide 17 —— 从 cin 读所有单词到 vector,排序,打印去重后的单词：

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

int main() {
    vector<string> V;
    copy(istream_iterator<string>(cin),   // start of source
         istream_iterator<string>(),       // end of source: default-ctor = EOF
         back_inserter(V));                // destination

    sort(begin(V), end(V));

    unique_copy(begin(V), end(V),
                ostream_iterator<string>(cout, "\n"));   // delimiter "\n" between writes
}

关键惯用法：

• istream_iterator<T>(stream) —— 通过 >> 从 stream 读 T 类型的值
• istream_iterator<T>()（默认构造）—— 代表 流尾（EOF）
• ostream_iterator<T>(stream, "delim") —— 通过 << 输出，然后在每个值后再写一次 "delim"

PPT slide 18 —— 同样思路,但读写文件：

#include <iostream>
#include <fstream>
#include <iterator>

int main() {
    ifstream in {"input.data"};
    ofstream out{"output.data"};

    vector<string> V;
    copy(istream_iterator<string>(in),
         istream_iterator<string>(),
         back_inserter(V));

    sort(V.begin(), V.end());

    unique_copy(V.begin(), V.end(),
                ostream_iterator<string>(out, "\n"));
}

💡 Klefstad 的教学点
同一组算法（copy、sort、unique_copy）根本不在乎它们的 iterator 来自 cin/cout、ifstream/ofstream 还是 vector。这就是 STL 设计的全部回报。

PPT slides 19–20 的小活动：

把整数从 cin 填到一个 vector 里：

int main() {
    vector<int> V;
    copy(istream_iterator<int>(cin), istream_iterator<int>(),
         back_inserter(V));
}

把 vector 里的整数一行一个写到 "out.txt"：

int main() {
    vector<int> V = {0, 2, 4, 6, 8, 10};
    ofstream out{"out.txt"};
    copy(V.begin(), V.end(),
         ostream_iterator<int>(out, "\n"));
}

12.3 Reverse Iterators（PPT slide 22）

Reverse iterator 把 ++ 和 -- 的含义互换了：自增其实是 沿容器往后走。每个容器都提供 rbegin() 和 rend()。

int main() {
    vector<int> V;
    for (int i = 1; i <= 10; ++i)
        V.push_back(i);

    // Print 10 9 8 ... 1
    copy(V.rbegin(), V.rend(),
         ostream_iterator<int>(cout, " "));
}

⚠️ 概念陷阱 —— rbegin() 指 最后一个 元素（反向遍历的起点），并不是 end() - 1。它是 另一种 iterator。要拿到底层的正向 iterator,调 .base()。

13. 算法中的函数对象（Function Objects）

对应 Topic 8 PPT slide 24

任何需要"可调用对象"的 STL algorithm —— for_each、transform、sort、find_if 等等 —— 都能接受 任意 一种：

• 自由函数（传名字时会退化为函数指针）
• 显式传一个函数指针
• 带 operator() 的类（functor）
• lambda（Week 7）

algorithm 不在乎是哪一种，它只是调 fn(x) 或 fn(a, b)。这就是 function object 抽象。

PPT slide 24 —— 两个例子：

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

void print(int i) {
    cout << i << ' ';
}

int main() {
    list<int> L;
    for (int i = 1; i <= 5; ++i)
        L.push_back(i);

    // print all ints in the list
    for_each(begin(L), end(L), print);   // 'print' is passed as a function pointer
}

int square(int i) {
    return i * i;
}

int main() {
    list<int> L1, L2;
    for (int i = 1; i <= 9; ++i)
        L1.push_back(i);

    // put squares of L1 into L2
    transform(begin(L1), end(L1),
              back_inserter(L2), square);
}

同样的例子换成 lambda（现代 C++ 里更地道）：

for_each(begin(L), end(L), [](int i){ cout << i << ' '; });

transform(begin(L1), end(L1), back_inserter(L2),
          [](int i){ return i * i; });

💡 function object 为什么重要
没有可调用参数的话,algorithm 就得有海量重载。sort(v.begin(), v.end()) 用 <；sort(v.begin(), v.end(), greater<int>{}) 用 >；sort(v.begin(), v.end(), [](X a, X b){ return a.name < b.name; }) 用任意自定义规则。同一个 algorithm,不同 策略 —— 由调用方挑。

14. Ranges（C++20）

对应 Topic 8 PPT slide 25

到目前为止的所有例子里，我们都在传一对 iterator：sort(v.begin(), v.end())。这写起来啰嗦，而且容易出错 —— 传错 begin/end 就是 UB。

C++20 ranges 让你直接传一个 range（通常就是容器本身）：

// Range-based for loop (works since C++11)
for (auto e : v)
    cout << e;

// Algorithm calls (the new C++20 way)
sort(v.begin(), v.end());   // old: still works
sort(v);                    // C++20 ranges: uses v's range = v.begin()..v.end()

C++20 的 <ranges> 库定义了 std::ranges::sort、std::ranges::find 等等，它们都接受 range。除了方便,ranges 还启用了 views —— 惰性、可组合的变换：

auto evens_squared = v
                   | std::views::filter([](int x){ return x % 2 == 0; })
                   | std::views::transform([](int x){ return x * x; });

💡 PPT 指路
更多内容看 https://en.cppreference.com/w/cpp/ranges。在 ICS 45C 里，你基本上只要知道 ranges 存在、它们能直接接受容器即可；经典的两 iterator 写法仍然到处都是、也完全正确。

15. I/O 流 — iostream 库

对应 LearnCpp 28.1

15.1 为什么 I/O 在库里（而不是语言里）

I/O 功能 不是 C++ 核心语言的一部分。它由标准库提供,住在 std 命名空间里。这也是为什么每个程序都要 #include <iostream> 才能用 cin/cout。

#include <iostream> 之后，你会得到一组 I/O 的 类层次。值得注意的是，这套层次用了 多继承（Week 7 / Week 6 提过不建议）—— 但库本身被精心设计和测试过，回避了多继承的典型坑，所以你用起来不用担心。

15.2 什么是流（Stream）？

💡 核心洞察（LearnCpp 28.1）
流 就是一段可以顺序访问的字节序列。随着时间推移，一个流可能生产或消费任意多的数据。

两种口味：

• 输入流 来自生产者（键盘、文件、网络）。你按下一个键，那个字节就进入输入流，停在那里等程序去取。
• 输出流 通向消费者（显示器、文件、打印机）。你写入时,数据先在输出流里,等消费者准备好再消费。

有些设备（文件、网络）同时是生产者和消费者。

💡 回报 —— 你一旦学会流操作，同一套操作就对键盘、文件、网络套接字、字符串缓冲区都成立。差异被操作系统藏起来了。

15.3 类层次

你应该能叫得出名字的几个关键类：

一张简化图：

            ios
           /   \
     istream   ostream
           \   /
          iostream

（没错，这是多继承 —— 那个让人头大的菱形。但还是那句话，库本身处理得很好。）

15.4 标准流

C++ 自带四个预连接的 标准流对象，可以直接拿来用：

💡 cerr vs. clog —— 两个都走标准错误，但 cerr 无缓冲（适合那种程序崩溃前必须看到的消息），clog 有缓冲（适合那种以批量效率为重的诊断日志）。实践中 clog 很少见。

💡 缓冲是什么
有缓冲的输出会先把字节攒在内存里，攒一批再一次性写（更快）。无缓冲的输出每个字节都立刻写（更慢，但你能立刻看到结果 —— 而且程序在缓冲区写完前崩溃时也不会丢东西）。

16. 用 istream 做输入

对应 LearnCpp 28.2

16.1 提取运算符 >>

提取运算符（>>）从输入流读一个值。C++ 对所有基本类型内置了 >>。你也可以为自己的类重载 >>。

int n;
std::cin >> n;            // read an int

double d;
std::cin >> d;            // read a double

char c;
std::cin >> c;            // read a single non-whitespace char

std::string s;
std::cin >> s;            // read a non-whitespace word

16.2 用 C 风格字符串时的缓冲区溢出

char buf[10] {};
std::cin >> buf;          // ⚠ user could enter 18 characters → buffer overflow → UB

⚠️ 最佳实践（LearnCpp 28.2）
一般来说，对用户会输入多少个字符做 任何 假设都是糟糕的。

修法：setw() 在 <iomanip> 里,可以限制读入字符数：

#include <iomanip>
char buf[10] {};
std::cin >> std::setw(10) >> buf;   // reads at most 9 chars (room for '\0' terminator)

16.3 提取会跳过空白

提醒（LearnCpp 28.2） —— 提取运算符 跳过空白（空格、tab、换行）。

int main() {
    char ch{};
    while (std::cin >> ch)
        std::cout << ch;
}
// Input:  Hello my name is Alex
// Output: HellomynameisAlex      ← all spaces and newlines eaten

要保留空白，用 get()。

16.4 get()

std::cin.get(ch) 读 一个字符，包括空白。

char ch{};
while (std::cin.get(ch))
    std::cout << ch;
// Input:  Hello my name is Alex
// Output: Hello my name is Alex   ← spaces preserved

还有一个字符串缓冲区重载：cin.get(buf, n) 最多读 n-1 个字符到 buf，再加上终止符。

char strBuf[11] {};
std::cin.get(strBuf, 11);     // reads up to 10 chars
std::cout << strBuf << '\n';
// Input:  Hello my name is Alex
// Output: Hello my n             ← only the first 10 chars

⚠️ get() 不会吃掉分隔符 —— 通常就是换行符。
所以第二次调 get() 立刻碰到留下的 \n，什么都没读就停下。

char strBuf[11]{};
std::cin.get(strBuf, 11);   // reads "Hello!"
std::cout << strBuf << '\n';

std::cin.get(strBuf, 11);   // sees leftover '\n', stops immediately!
std::cout << strBuf << '\n';
// Output:
// Hello!
//                          ← (empty)

16.5 getline() —— 读取并丢掉分隔符

std::cin.getline(buf, n) 行为像 get，但 会吃掉并丢弃 尾部的换行。读整行的时候,这通常才是你想要的。

char strBuf[11]{};
std::cin.getline(strBuf, 11);
std::cout << strBuf << '\n';

std::cin.getline(strBuf, 11);   // works correctly this time
std::cout << strBuf << '\n';

16.6 gcount() —— 读了多少个

一次 getline()（或带缓冲区的 get()）之后,cin.gcount() 返回提取的字符数（包括被丢弃的分隔符）。

char strBuf[100]{};
std::cin.getline(strBuf, 100);
std::cout << strBuf << '\n';
std::cout << std::cin.gcount() << " characters were read\n";

16.7 给 std::string 用的 std::getline（自由函数）

<string> 里有一个非成员 getline，把一整行读到 std::string 里。现代 C++ 用这个 —— 能避开 char[] 缓冲区就尽量避开。

#include <string>
#include <iostream>

int main() {
    std::string strBuf;
    std::getline(std::cin, strBuf);
    std::cout << strBuf << '\n';
}

⚠️ 经典混用 bug

int n;
std::cin >> n;                    // reads number, leaves '\n' in buffer
std::string line;
std::getline(std::cin, line);     // reads empty line — eats the leftover '\n'

修法：在两者之间调 std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');。

16.8 其他有用的 istream 函数

来自 LearnCpp 28.2：

写手工 parser（用 peek() 做前瞻、用 putback() 做错误恢复）时这些很有用。

其余内容参考 https://en.cppreference.com/w/cpp/io/basic_istream。

16.9 流状态 —— 为什么 while (std::cin >> x) 会终止

每个流都带着一组 状态位（state bits），记录这个流目前是不是还能用。每次操作（>>、getline()、read()）之后这些位都会更新。从 std::cin 读到坏输入时它不会抛异常 —— 它会默默地把某个状态位设上，然后继续往下走。你必须自己检查。

四个状态位

怎么检查

读取循环为什么能工作

int x;
while (std::cin >> x) {           // 测的是流的 bool 转换 → !fail()
    std::cout << x << '\n';
}
// 当 extraction 失败（坏输入）或者到流末尾时，循环退出。

std::cin >> x 返回 std::cin（按引用）。把它转 bool 实际就是调 !fail()。所以只要上次 extraction 成功，循环就继续。当你输入 done 而不是数字时，failbit 被设上，循环结束。

从失败的 extraction 中恢复

读失败之后，流就 "卡住" 了 —— failbit 被设上，之后每次读都会立刻失败，而且坏输入还留在缓冲区里。需要两步：

int n;
while (!(std::cin >> n)) {
    std::cin.clear();                                                       // 1. 把状态位复位回 goodbit
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');     // 2. 把坏输入扔掉
    std::cout << "Please enter a number: ";
}

• clear() 把所有错误位清零（也有可选参数允许设置特定的位）。
• ignore(...) 把违规字符丢掉，这样下次读才能读到新输入。

口诀： 先 clear 再 ignore —— 先清状态，再清缓冲。漏掉一步输入循环就会无限转。

17. 用 ostream 与 ios 做输出

对应 LearnCpp 28.3

17.1 插入运算符 <<

插入运算符把数据放进输出流。所有内置类型都已预定义；你也可以为自己的类重载它。

std::cout << "Hello, " << name << ", age " << age << '\n';

Week 8 这部分有意思的内容是 格式化：控制数据 怎么 写出来（进制、精度、宽度等等）。

17.2 两种格式化方式：Flags vs. Manipulators

istream 与 ostream 都从 std::ios 派生,ios 持有格式化状态。改这个状态有两种方式：

• Flags —— 布尔状态变量，用 setf() 打开,unsetf() 关闭
• Manipulators —— 你流式发送给输出的对象（如 std::hex、std::setw(10)）；它们替你操作相应的 flag

17.3 用 setf / unsetf 操作 flag

std::cout.setf(std::ios::showpos);   // turn on the "show + before positive nums" flag
std::cout << 27 << '\n';             // prints +27
std::cout.unsetf(std::ios::showpos); // turn it off
std::cout << 28 << '\n';             // prints 28

用按位或 | 一次打开多个 flag：

std::cout.setf(std::ios::showpos | std::ios::uppercase);
std::cout << 1234567.89f << '\n';    // prints +1.23457E+06