cs106l-lecture-4-iterators-deep-dive-algorithm
Course: 斯坦福大学: C++标准库编程 | C++ Standard Library Programming
🎮 CS106L Lecture 4 — Iterators Deep Dive & Algorithms
🏛 课程：Stanford CS106L — Standard C++ Programming Language
📍 主题：迭代器与算法
🎯 目标：理解 STL 迭代器的类型体系与 <algorithm> 通用函数库的设计思想。
🧭 课程定位
迭代器（Iterator）是 STL 的第二大支柱。
它让容器与算法实现完全解耦。
“容器保存数据，算法处理数据，
迭代器让两者握手。”
🏷 关键词速记
Iterator｜迭代器
begin() / end()｜遍历入口
Input / Output / RandomAccess｜迭代器类别
Range-based for｜范围循环
Lambda｜匿名函数
std::for_each / std::sort｜算法库函数
Iterator Invalidation｜迭代器失效
🎮 30 秒课程摘要
“迭代器是容器的‘遥控器’，算法是它的‘指令’。
一旦你掌握它们，STL 就变成了积木世界。”
📚 核心内容讲解
🧩 1️⃣ 迭代器的本质
迭代器 ≈ “能像指针一样前进、解引用、比较的对象”。
它让算法不必关心容器内部结构。
📦 示例 1：迭代器访问 vector
std::vector<int> v = {1, 2, 3};
for (auto it = v.begin(); it != v.end(); ++it)
std::cout << *it << " ";🧩 讲解：
v.begin()返回指向第一个元素的迭代器v.end()返回“最后一个元素之后”的位置it解引用得到实际元素📤 输出：
1 2 3
🧩 2️⃣ 迭代器的分类
| 类别 | 示例容器 | 能力 |
|---|---|---|
| Input Iterator | istream_iterator | 只能读取一次（单向输入） |
| Output Iterator | ostream_iterator | 只能写入一次 |
| Forward Iterator | forward_list | 可重复读写，单向 |
| Bidirectional Iterator | list, map, set | 可前后移动 |
| Random Access Iterator | vector, deque | 支持 it + n, it[i] |
📦 示例 2：随机访问迭代器
std::vector<int> v = {10, 20, 30, 40};
auto it = v.begin();
std::cout << *(it + 2);📤 输出： 30
🧩 讲解：
vector 的迭代器底层是普通指针，因此可随机偏移。
而 list 的迭代器是链表节点指针，不支持加减操作。
🧩 3️⃣ begin() / end() / cbegin() / rend()
| 函数 | 含义 |
|---|---|
begin() | 返回第一个元素迭代器 |
end() | 返回“最后一个元素之后”的迭代器 |
cbegin() / cend() | 常量版本，不能修改元素 |
rbegin() / rend() | 反向迭代器 |
📦 示例 3：反向遍历
std::vector<int> v = {1, 2, 3};
for (auto it = v.rbegin(); it != v.rend(); ++it)
std::cout << *it << " ";📤 输出： 3 2 1
🧩 讲解：
rbegin() 从尾部开始，rend() 停在第一个元素之前。
🧩 4️⃣ 算法库 <algorithm>
STL 提供了 100+ 种算法，均通过迭代器操作。
| 函数 | 用途 |
|---|---|
std::sort(begin, end) | 排序 |
std::find(begin, end, val) | 查找 |
std::count(begin, end, val) | 计数 |
std::for_each(begin, end, fn) | 对每个元素执行操作 |
std::transform() | 批量转换 |
std::accumulate() | 累加求和（在 <numeric>） |
📦 示例 4：算法示范
std::vector<int> v = {3, 1, 4, 1, 5};
std::sort(v.begin(), v.end());
auto cnt = std::count(v.begin(), v.end(), 1);
std::cout << cnt;📤 输出： 2
🧩 讲解：
sort() 对 vector 排序，count() 统计值出现次数。
🧩 5️⃣ Lambda 表达式与算法结合
lambda 是 C++11 引入的匿名函数。
搭配算法能写出优雅的逻辑。
📦 示例 5：使用 lambda 与 for_each
std::vector<int> v = {1, 2, 3, 4};
std::for_each(v.begin(), v.end(), [](int& x){ x *= 2; });
for (int n : v) std::cout << n << " ";📤 输出： 2 4 6 8
🧩 讲解：
[] 表示捕获列表，可使用外部变量；
() {} 定义匿名函数；
lambda 让算法更灵活。
🧩 6️⃣ Range-based for
C++11 引入更简洁的语法：
for (auto& elem : v) {
std::cout << elem << " ";
}相当于：
for (auto it = v.begin(); it != v.end(); ++it)
std::cout << *it << " ";🧩 优势：
- 语法更简洁
- 自动推断类型
- 不易越界
- 可配合
const &避免拷贝
📦 示例 6：常量遍历
for (const auto& x : v) std::cout << x << " ";🧩 7️⃣ 迭代器失效（Iterator Invalidation）
迭代器失效意味着：容器修改后，旧迭代器不再有效。
| 容器 | 失效情况 |
|---|---|
vector | 扩容或插入删除后，所有迭代器失效 |
deque | 插入删除可能失效 |
list | 插入删除不失效 |
map / set | 插入安全，删除失效 |
📦 示例 7：vector 失效
std::vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4); // 重分配内存
std::cout << *it; // ⚠️ 未定义行为！
🧩 讲解：
当 vector 重新分配内存后，旧迭代器指向的地址不再有效。
解决方案：重新获取迭代器。
🧩 8️⃣ 泛型思想总结
STL 算法依赖的不是容器，而是 迭代器接口。
任何支持以下操作的类型都能被算法使用：
++it; // 前进
*it; // 解引用
it != end; // 比较
📦 示例 8：自定义容器 + 算法
std::list<int> L = {5, 2, 9};
std::sort(L.begin(), L.end()); // ❌ 错误：list 不支持随机访问
L.sort(); // ✅ list 自带排序成员函数
🧩 讲解：
std::sort() 只接受随机访问迭代器，因此 list 无法使用。
这体现了 STL 的类型约束思想。
🧠 记忆口诀
“指针像，接口广；
算法全，容器爽；
失效防，lambda 强；
范型一体，通用无疆。”
🧪 实践练习
✅ 练习 1：统计奇偶数数量
使用 std::count_if 与 lambda 判断奇偶数量。
✅ 练习 2：字符串转大写
用 std::transform(str.begin(), str.end(), str.begin(), ::toupper);
✅ 练习 3：自定义打印算法
用 std::for_each 打印容器元素并统计元素个数。
✅ 练习 4：验证迭代器失效
写一段代码在 vector 扩容后使用旧迭代器，观察崩溃现象。
🪄 创作与工程建议
- 尽量使用
auto简化迭代器声明。 - 对容器的修改操作前后不要复用旧迭代器。
- 在算法与容器混用时，善用 lambda 自定义行为。
- 阅读
<algorithm>文档，了解可用的通用算法（排序、搜索、过滤、聚合）。 - 若容器支持 range-based for，则优先使用它。
✅ 小结表
| 主题 | 要点 | 示例 |
|---|---|---|
| 迭代器类型 | 输入 / 输出 / 双向 / 随机 | vector, list |
| 遍历接口 | begin(), end(), rbegin() | 统一访问容器 |
| 算法库 | sort, find, count, for_each | 泛型算法 |
| Lambda | 使算法更灵活 | [&](int x){ return x>5; } |
| 失效规则 | 修改容器会破坏迭代器 | vector push_back() |
“算法与迭代器让 C++ 成为表达思想的语言，而不仅是机器的语言。”
是否希望我继续整理下一讲
👉 Lecture 5《Templates — Generic Programming in C++》（模板机制、函数模板、类模板、类型推断、Concepts），
保持同样风格并附中英对照代码讲解？