Lecture 6 (Week 3 - Thursday): 迭代器与指针 (Iterators & Pointers)

目录 · ← l5 · l7 →

Lecture 6 (Week 3 - Thursday): 迭代器与指针 (Iterators & Pointers)

概述

本讲回答上一讲遗留的问题：”for-each 循环（for (const auto& elem : container)）到底是怎么工作的？”答案是迭代器（iterators）：一个在容器中”跟踪当前位置、能前进、能取值”的抽象。你将掌握迭代器的四件套接口（begin/end/++/*/==）、五大迭代器分类（Input / Output / Forward / Bidirectional / Random Access），并理解指针与内存的基本模型——指针是指向内存中任意对象的”地址数字”，迭代器与指针接口同构。这是 STL 泛型算法（L10 的 std::sort 等）能作用于所有容器的基础，也是 A2（Marriage Pact）中”存指针到 queue”与指针悬垂问题（Q2）的知识来源。

核心特性与语法详解

1. 为什么需要迭代器

定义与目的：用下标遍历（for (size_t i = 0; i < v.size(); ++i) v[i]）只对连续容器（vector）有效；std::set/std::map 没有下标、内部不是数组，无法用索引。我们需要一个对所有容器统一的遍历抽象。

核心语法（四件套）：

auto it = c.begin();        // 1. 初始化：指向容器第一个元素
++it;                       // 2. 前进：移动到下一个元素
auto& elem = *it;           // 3. 解引用：取得当前元素（it == end() 时未定义！）
it == c.end()               // 4. 比较：判断是否走完了

设计意图与最佳实践：课堂用”抓娃娃机”作比喻——迭代器是那只”爪子”：能抓玩具（*it）、能向前移（++it）；容器是那台机器：告诉你从哪里开始（begin()）、何时停止（end()）。容器与迭代器协作，才构成遍历。

2. begin() 与 end() 的语义

定义与目的：begin() 返回指向第一个元素的迭代器（容器非空时）；end() 返回past-the-end 迭代器——指向最后一个元素之后一个位置，它从不指向任何元素，只作为”走完了吗？”的哨兵。

核心语法：

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

机制：
- 空容器：begin() == end()，循环体一次都不执行。这是循环能安全处理空容器的基础。
- 对 end() 解引用（*c.end()）是未定义行为——end 后面没有元素。
- --e（先 auto e = c.end(); --e;）可得到最后一个元素的迭代器（要求双向迭代器）。

3. for-each 循环的展开（编译器做了什么）

定义与目的：for (auto elem : s) 是迭代器循环的语法糖。

核心语法（幻灯片给出的等价展开）：

// 你写的：
for (auto elem : s) { std::cout << elem; }
// 编译器看到的：
auto b = s.begin();
auto e = s.end();
for (auto it = b; it != e; ++it) {
    auto elem = *it;
    std::cout << elem;
}

机制：因此 for-each 对任何提供 begin/end 与迭代器四件套的类型都成立——这正是它能同时遍历 vector、map、set、deque、unordered_* 的原因（上一讲的课后小测即由此引出）。

4. 迭代器的类型：为什么那么长，以及 auto / using

定义与目的：std::map<int, int>::iterator 这类类型名极其冗长。

核心语法：

std::map<int, int> m {{1,2},{3,4},{5,6}};
auto it = m.begin();                    // C++11 起：让编译器推断
auto elem = *it;                        // elem 是 std::pair<int, int>
// 显式写法（C++98 风格）：
std::map<int, int>::iterator it2 = m.begin();

机制：<map> 头文件内部有 using iterator = /* 某种迭代器类型 */;（using 是类型别名，等价于 C 的 typedef）。*m.begin() 的类型是 std::pair<const int, int>，所以 auto elem = *it; 得到的是 pair 的拷贝。幻灯片提醒：”Iterator types are really long, so we like to use auto with iterators.”

5. `++it` 还是 `it++`？

定义与目的：前缀与后缀自增语义不同，代价不同。

核心语法（迭代器类的两个重载）：

Iterator& operator++();      // 前缀 ++it：先自增，返回指向同一对象的引用
Iterator  operator++(int);   // 后缀 it++：自增，但返回旧值的拷贝

机制：迭代器是完整的对象，拷贝它比拷贝 int 贵得多。后缀版本为了返回旧值必须做一次拷贝，因此循环里统一写 ++it。Bjarne 的原话：”++i is sometimes faster than, and is never slower than, i++… why not just write ++i instead? You never lose anything, and you sometimes gain something.”

6. 迭代器分类（五大类型）

定义与目的：不是所有迭代器生而平等——不同容器支持的操作不同，按”能力”分级；算法（如 std::sort）会要求最低级别的迭代器。
分类（能力从弱到强）：
- Input（输入）：最基本，只能读：auto elem = *it;。单遍（single-pass）语义，如流迭代器。
- Output（输出）：只能写：*it = elem;。
- Forward（前向）：Input 的加强，支持多遍遍历（multi-pass guarantee：it1 == it2 蕴含 ++it1 == ++it2，即同一个迭代器可以反复前进、重走同一段）。所有 STL 容器迭代器都至少是 Forward。为什么流不是？——流读一次就没了，无法重放，所以流迭代器只是 Input。
- Bidirectional（双向）：Forward 之上支持 --it 后退。std::map、std::set 的迭代器属于此类（红黑树节点只能沿链前后移动）。
- Random Access（随机访问）：最强大，支持 it += n、it - n、it[n]、it1 < it2 等”任意跳转与比较”。std::vector、std::deque 的迭代器属于此类（底层连续/近连续内存）。
机制与为什么重要：std::sort 需要随机访问迭代器（它要反复跳跃划分区间）。std::sort(vec.begin(), vec.end()) ✅ 可编译；std::sort(set.begin(), set.end()) ❌ 编译失败——set 的迭代器只是双向的。C++ 的设计哲学：”不提供注定慢的方法“：在红黑树上做 it + 5 是 O(n) 的慢操作，所以 map/set 的迭代器干脆不提供随机访问，让错误在编译期暴露。

7. 指针与内存（Pointers and Memory）

定义与目的：迭代器指向容器元素；指针指向内存中的任意对象。理解指针前先理解内存。
内存基础：
- 每个变量都住在内存的某个地址；程序的所有地址构成地址空间（64 位系统从 0x0 到 2^64-1）。
- 内存按字节寻址：每个字节一个编号；对象的地址 = 它最低字节的地址。int 占 32 位 = 4 字节，int x = 106; 的地址是其 4 个字节中最低的那个（字节序有大小端之分，演示常用 Big Endian，实际多为 Little Endian）。

取地址与解引用：

int x = 106;
int* px = &x;      // & = 取地址运算符：得到 x 的地址
std::cout << *px;  // * = 解引用：顺着地址取回对象，打印 106

指针就是”一个数字”：px 里存的不过是一个无符号整数（地址值，如 0x50527c），打印 px 看到的就是这个数。
指针可以指向任何对象：结构体 StanfordID* p = &id; p->name;（-> 等价于 (*p).）、std::vector<int>* p = &v;、数组元素 int* arr = &v[0];。

数组指针算术（vector 是连续内存，所以指针算术成立）：

int* arr = &v[0];
arr += 1;  // 前进一个 int（不是 1 字节！按所指类型缩放）
++arr;
if (arr == &v[4]) ...

迭代器与指针同构：vector<T>::iterator 的底层类型几乎就是 T*（真实实现中不是裸指针，但接口完全一致：初始化、+=、++、*、==）。所以对 vector 而言，指针遍历和迭代器遍历写起来一模一样。

代码示例与逐步解说（核心）

示例 1：用迭代器遍历 std::set（幻灯片示例，含 for-each 对照）

// C++11
#include <iostream>
#include <set>

int main() {
    std::set<int> s {1, 2, 3, 4};

    // 手写迭代器循环（set 没有下标，只能这样遍历）
    for (auto it = s.begin(); it != s.end(); ++it) {
        std::cout << *it << ' ';
    }
    std::cout << '\n';

    // for-each 是上面这段的语法糖（编译器自动展开）
    for (auto elem : s) {
        std::cout << elem << ' ';
    }
    std::cout << '\n';
    return 0;
}

代码做什么：用两种等价方式打印 1 2 3 4（set 自动升序）。
特性机制解说：s.begin() 是 std::set<int>::iterator；++it 沿红黑树的中序遍历移动到下一个节点；*it 解引用取出节点里的 int；it != s.end() 用哨兵判断结束。注意迭代器是双向的——s.begin() 没有下标、it += 2 会编译失败，这正体现了”容器实现决定迭代器能力”。

示例 2：迭代器四件套与空容器（幻灯片接口逐条演示）

// C++11
#include <iostream>
#include <vector>

int main() {
    std::vector<char> v {'d', 'a', 'w', 'g', 's'};

    auto it = v.begin();              // 1. 初始化：指向 'd'
    ++it;                             // 2. 前进：指向 'a'
    auto& elem = *it;                 // 3. 解引用：拿到元素的引用
    std::cout << elem << '\n';        // a
    std::cout << (it == v.end() ? "at end\n" : "not at end\n");  // not at end

    ++it; ++it; ++it; ++it;           // 4 次前进：'w' → 'g' → 's' → 哨兵位
    std::cout << (it == v.end() ? "reached end\n" : "not end\n"); // reached end

    std::vector<int> empty;
    std::cout << (empty.begin() == empty.end()
                      ? "empty: begin == end\n" : "?\n");
    return 0;
}

代码做什么：完整走一遍 begin/++/*/== 四件套，并验证空容器的 begin() == end()。
特性机制解说：end() 返回的哨兵不指向元素——it 走过第 5 个元素后与 end() 相等，此刻若执行 *it 就是未定义行为。空容器时 begin()==end()，任何”从头走到尾”的循环体自然执行零次，这就是 for-each 能安全处理空容器的原因。

示例 3：用迭代器做递归二分查找（课堂代码 binary-search.cpp 补全）

// C++11
#include <iostream>
#include <iterator>   // std::distance
#include <vector>

// 在 [begin, end) 区间内递归查找 value（区间为半开区间）
bool binarySearch(std::vector<int>::iterator begin,
                  std::vector<int>::iterator end, int value) {
    if (begin >= end) {                    // 1. 基准情形：区间为空
        return false;
    }

    auto mid = begin + (std::distance(begin, end) / 2);   // 2. 中点迭代器

    if (*mid == value) {                   // 3. 命中
        return true;
    }
    if (*mid > value) {
        return binarySearch(begin, mid, value);           // 左半 [begin, mid)
    }
    return binarySearch(mid + 1, end, value);             // 右半 [mid+1, end)
}

int main() {
    std::vector<int> data = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int testValues[] = {23, 2, 91, 40};    // 命中 / 首边界 / 尾边界 / 未命中

    std::cout << "Recursive Iterator Binary Search Test:\n";
    for (int val : testValues) {
        std::cout << "Searching for " << val << ": "
                  << (binarySearch(data.begin(), data.end(), val)
                          ? "SUCCESS" : "FAILURE") << '\n';
    }
    return 0;
}

代码做什么：对有序 vector 递归二分查找；begin/end 是迭代器而非下标，体现”用迭代器表达区间”。
特性机制解说：
- begin >= end 依赖随机访问迭代器才有的比较运算——若把参数换成 std::set<int>::iterator 将无法编译（二分查找本来就需要随机访问）。
- begin + n 是”跳过 n 个元素”的随机访问运算；std::distance(begin, end) 计算两个迭代器之间的元素个数。
- 区间写作 [begin, end)（左闭右开）是 STL 的通用约定：左端点包含、右端点（end）不包含。递归分治时天然用 [begin, mid) 与 [mid+1, end) 表达左右两半。
- 把区间当”值”传来传去，正是迭代器比下标优雅的地方：同一套代码可推广到 deque 等随机访问容器。

示例 4：指针基础——取地址、解引用、指向任意对象（幻灯片示例）

// C++11
#include <iostream>
#include <string>
#include <vector>

struct StanfordID {
    std::string name;
};

int main() {
    int x = 106;
    int* px = &x;                 // & 取地址：px 保存 x 的地址
    std::cout << x << '\n';       // 106
    std::cout << *px << '\n';     // 106（* 解引用）
    std::cout << px << '\n';      // 0x…（地址本身，一个"数字"）

    StanfordID id {"rfern"};
    StanfordID* p = &id;
    auto name = p->name;          // -> 等价于 (*p).name

    std::vector<int> v {1, 2, 3, 4, 5};
    int* arr = &v[0];             // 指向 vector 底层连续数组的首元素
    std::cout << *arr << ' ';     // 1
    arr += 1; std::cout << *arr << ' ';   // 2（指针算术按 int 大小缩放）
    ++arr;    std::cout << *arr << ' ';   // 3
    arr += 2; std::cout << *arr << ' ';   // 5
    if (arr == &v[4]) std::cout << "At last index";
    std::cout << '\n';
    return 0;
}

代码做什么：展示 & 取地址、* 解引用、-> 成员访问、以及指向 vector 内部数组的指针算术，输出 106 106 0x… 1 2 3 5 At last index。
特性机制解说：px 里存的只是一个地址数字；*px 让编译器”按 int* 的类型信息去那地址读取 4 字节”。arr += 1 前进的不是 1 字节而是 1 个 int（4 字节）——指针算术按所指类型的大小缩放，这正是 int* 与 char* 区别的根源。vector 保证元素连续存放，所以 &v[0] 之后可以放心做数组式指针算术；若指向 set 的节点则完全无效（节点不连续）。

示例 5：迭代器与指针的接口同构（幻灯片对照）

// C++11
#include <iostream>
#include <vector>

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

    // 用裸指针遍历 vector 的底层数组
    int* p = &v[0];
    for (int* q = p; q != p + 5; ++q) std::cout << *q << ' ';
    std::cout << '\n';

    // 用迭代器遍历——接口一模一样
    for (auto it = v.begin(); it != v.end(); ++it) std::cout << *it << ' ';
    std::cout << '\n';

    // 随机访问操作逐条对照
    auto it = v.begin();
    it += 1; std::cout << *it << ' ';             // 2
    ++it;    std::cout << *it << ' ';             // 3
    it += 2; std::cout << *it << ' ';             // 5
    if (it == v.end() - 1) std::cout << "At last element";
    std::cout << '\n';
    return 0;
}

代码做什么：先用指针、再用迭代器，走完全相同的”初始化 → 随机访问 → 前进 → 比较”路线，输出两遍 1 2 3 4 5 与 2 3 5 At last element。
特性机制解说：幻灯片指出，vector<T>::iterator 底层类型几乎就是 T*（”In the real STL implementation, the actual type is not T*. But for all intents and purposes, you can think of it this way.”）。两者共享同一接口：*、++、+=、==、<。区别在于：迭代器是类型安全、容器感知的抽象（对 map/set 会是另一种实现），且自带 end() 哨兵约定；指针则更”原始”，可以指向内存里任何地方——包括不该碰的地方。这就是 A2 中”存指针”需要小心的原因。

与旧标准（如C++98）的对比

迭代器是 C++98 就有的 STL 核心设施：begin()/end()/++/*/==、五大分类、std::distance/std::advance 在 C++98 里都已存在。本讲真正的新东西是使用体验：
C++98 的冗长遍历：for (std::map<std::string, int>::const_iterator it = m.begin(); it != m.end(); ++it)——类型名长到令人窒息，还容易写错 const_iterator。C++11 的 auto + 范围 for 让遍历变成 for (const auto& p : m)，由编译器生成迭代器循环。幻灯片正是用”set 没有下标 → 只能迭代器”来引出这一点。
C++11 起：auto 推断迭代器类型；范围 for（for (auto elem : s)）正式成为语法糖；cbegin()/cend() 提供只读迭代器。
C++20 ranges：std::ranges::sort、视图（views）把”迭代器对”升级为”范围”抽象，但仍建立在迭代器之上；课程 L10 之后会展开。
指针方面：裸指针与手动 new/delete 是 C++98 时代的内存管理常态，极易泄漏；C++11 的智能指针（std::unique_ptr 等）把”指针”封装成 RAII 对象（课程 L16 详细讲）。本讲先理解裸指针的机制，后续再学安全封装。
对比 C：指针与指针算术（arr + i）直接继承自 C；C++ 的迭代器是 C 指针思想的安全泛化——把”指针能做的操作”抽象成接口，让每个容器都能提供。

关键要点

迭代器四件套：auto it = c.begin(); → ++it → *it → it != c.end()；end() 是”过去末尾”的哨兵，永远不要解引用 end()。
for-each 就是迭代器循环：for (auto elem : s) 被编译器展开为 begin/end/++/* 循环，所以它对一切提供 begin/end 的容器统一有效；空容器由 begin()==end() 天然处理。
迭代器按能力分级：Input(读) → Output(写) → Forward(多遍) → Bidirectional(可退) → Random Access(可跳)；std::sort 等算法要求随机访问，map/set 只给双向——”不给慢方法”。
循环里写 ++it 而不是 it++：前缀不拷贝旧值，”never slower, sometimes faster”（Bjarne）。
指针 = 内存地址 = 一个数字：& 取地址、* 解引用、-> 访问成员；指针算术按所指类型缩放；vector<T>::iterator 与 T* 接口同构。

常见陷阱与注意事项

解引用 end()：*c.end()、c.end()[0] 都是未定义行为；越界访问（如对 size 3 的 vector，it += 3 后再 *it，幻灯片专门演示过）同样 UB——迭代器不像下标有 at() 帮你检查。
对空容器解引用 begin()：空容器 begin()==end()，*v.begin() 是 UB；先判空或依赖循环条件。
滥用 it++：把 i++ 的坏习惯带到迭代器上，每次迭代白做一次对象拷贝；统一 ++it。
指针/迭代器算术越界：arr += 100 超出数组边界后再解引用是 UB；arr == &v[4] 这类比较也只在同一数组内才有定义。
迭代期间修改容器：insert/erase 会使迭代器失效（vector 扩容可能使全部失效），之后再用旧迭代器是 UB——本讲先记住现象，L13（特殊成员函数）与后续课程会讲透容器与迭代器的生命周期。
存指针后容器析构（A2 Q2 的核心）：把指向 set 元素的指针存进 queue，一旦 set 出作用域，指针就悬垂（dangling）——解引用是 UB。指针”指向谁”的责任完全在程序员。

关联作业提示

A2: Marriage Pact 是迭代器与指针的实战舞台：

Part 2 find_matches：遍历 std::set<std::string> students 找与你同缩写的人。set 没有下标，只能用本讲的迭代器循环或 for-each（for (const auto& name : students)）；作业提示也明确建议回看”Thursday’s lecture on iterators and pointers”。
存指针到 std::queue：匹配成功时把 &name（指向 set 中字符串的地址，注意不能存局部变量 name 的地址，要存 *it/元素的地址）push 进 std::queue<const std::string*>。
Q2 简答题：”为什么存指针而不存字符串？set 出作用域后指针会怎样？”——答案要用到本讲的指针模型：拷贝整个字符串昂贵、指针廉价；set 的节点在插入后地址稳定（不像 vector 扩容会搬移），所以 set 存活期间指针有效；一旦 set 析构，指针悬垂，解引用即 UB。这正是”指针指向的对象生命周期由程序员负责”的体现。
binary-search.cpp 的区间思维：[begin, end) 半开区间约定在 A2 遍历 set、以及未来一切 STL 算法（std::sort、std::find）中反复出现，务必内化。

Share on

Bluesky Facebook LinkedIn Mastodon X (formerly Twitter)

Runguo Li