CS106L 第 6 讲：迭代器与指针

本讲义根据 Stanford CS106L Spring 2026 Lecture 6 重新组织。它不是逐页翻译，而是一份从问题出发、适合 C++ 初学者连续阅读的中文课程。

0. 这一节课究竟想解决什么问题？

上一节课，我们学习了很多容器：

std::vector
std::deque
std::set
std::map
std::unordered_set
std::unordered_map

它们内部保存数据的方式完全不同。

vector 的元素连续排列；
deque 通常由多个内存块组成；
set 和 map 通常使用树形结构；
unordered_set 和 unordered_map 通常使用哈希表。

但是，我们却可以用几乎相同的代码遍历它们：

for (const auto& elem : container) {
    // 使用 elem
}

这件事其实很神奇。

vector 可以通过下标访问：

v[0]
v[1]
v[2]

但 set 没有下标：

s[0];  // 不存在这种操作

map 的内部甚至可能是一棵树，unordered_map 的内部则可能是一张哈希表。

那么问题来了：

C++ 是怎样用一套统一的方式遍历这些完全不同的容器的？

答案就是本节课的主角：

迭代器 Iterator

学完迭代器之后，我们还会发现，迭代器的操作和 C++ 指针非常相似。因此后半节课会继续讲：

指针 Pointer 与内存 Memory

1. 先检查一下上一节课的容器知识

1.1 哪种容器在头部和尾部插入都很高效？

答案是：

std::deque

deque 是 double-ended queue，也就是“双端队列”。

std::deque<int> d;

d.push_back(10);   // 尾部插入
d.push_front(20);  // 头部插入

这两个操作通常都很高效。

相比之下，vector 在尾部插入很方便，但在头部插入会导致后面的元素整体移动。

1.2 哪些容器需要比较规则？

std::set 需要比较其中的元素。

std::map 需要比较其中的键。

例如：

std::set<int> numbers;
std::map<std::string, int> scores;

默认情况下，它们使用类似 < 的规则确定元素顺序。

如果我们存储自定义类型，可能就需要提供比较方式。

不想通过“大小关系”组织元素时，可以考虑：

std::unordered_set
std::unordered_map

它们使用的是：

哈希函数；
相等判断。

1.3 `unordered_set` 和 `set` 哪一个通常更快？

查找单个元素时：

unordered_set

通常更快。

它通过哈希值寻找元素，平均查找复杂度通常接近：

O(1)

而 set 一般通过平衡搜索树查找，复杂度通常是：

O(log n)

不过两者解决的问题并不完全相同：

std::set

会维护元素顺序，而：

std::unordered_set

不保证遍历顺序。

因此，不能简单理解为“unordered_set 永远比 set 好”。

第一部分：迭代器基础

2. 为什么普通下标不能解决所有遍历问题？

对于 vector，我们可以写：

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

for (std::size_t i = 0; i < v.size(); ++i) {
    const auto& elem = v[i];
    std::cout << elem << '\n';
}

这段循环包含四个部分：

for (初始化; 继续条件; 每轮后的移动) {
    const auto& elem = 获取当前位置的元素;
}

在 vector 中：

初始化位置      -> i = 0
继续条件        -> i < v.size()
移动到下一位置   -> ++i
取得元素        -> v[i]

可是换成 set：

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

我们就无法继续这样写：

s[0];  // 错误
s[1];  // 错误

因为 set 不是一个支持下标访问的连续数组。

所以我们需要一种比下标更加通用的东西。

它需要能够回答四个问题：

从哪里开始？
什么时候结束？
怎样移动到下一个元素？
怎样取得当前位置的元素？

这就是迭代器所提供的能力。

3. 把迭代器想象成抓娃娃机的爪子

课件用了一个很形象的比喻：抓娃娃机。

容器就像抓娃娃机中的一排玩具，迭代器则像机器上的爪子。

爪子能够做三件事：

抓取当前位置的玩具；
向前移动；
判断自己是否已经到达结束位置。

抓娃娃机本身，也就是容器，则负责告诉我们：

第一个位置在哪里；
结束位置在哪里。

在 C++ 中，它们分别对应：

container.begin()
container.end()

4. `begin()` 和 `end()`

假设我们有一个容器：

std::vector<char> chars{'d', 'a', 'w', 'g', 's'};

可以把它想象成：

 begin()
    ↓
  ['d']['a']['w']['g']['s'][   ]
                             ↑
                            end()

4.1 `begin()`

container.begin()

返回一个指向第一个元素的迭代器。

auto it = chars.begin();

此时 it 指向 'd'。

4.2 `end()`

container.end()

返回一个“尾后迭代器”。

它指向的是：

最后一个元素之后的位置。

不是最后一个元素。

['d']['a']['w']['g']['s'][尾后位置]
                              ↑
                             end()

因此下面的代码是错误的：

auto it = chars.end();
std::cout << *it;  // 未定义行为

因为 end() 根本没有指向一个真实元素。

4.3 为什么要让 `end()` 指向最后一个元素之后？

这样可以把遍历范围表示为：

[begin, end)

左边包含，右边不包含。

也就是：

从 begin() 开始；
一直处理到 end() 之前；
当迭代器等于 end() 时停止。

这种设计还有一个很漂亮的性质。

如果容器为空：

std::vector<int> v;

那么：

v.begin() == v.end()

循环从一开始就会发现已经结束，不需要专门判断容器是否为空。

5. 迭代器最核心的四种操作

5.1 获得起点

auto it = container.begin();

这里通常使用 auto，因为完整的迭代器类型可能很长。

5.2 向后移动一个位置

++it;

执行后，迭代器指向下一个元素。

5.3 解引用

auto& elem = *it;

这里的 *it 表示：

取得迭代器当前指向的元素。

这个操作叫作 dereference，中文一般称为“解引用”。

例如：

std::vector<int> v{10, 20, 30};

auto it = v.begin();

std::cout << *it;  // 10

++it;

std::cout << *it;  // 20

注意：只有当迭代器确实指向一个元素时，才能解引用。

*container.end();  // 错误：未定义行为

5.4 比较位置

if (it == container.end()) {
    // 已经到达结束位置
}

遍历时更常写成：

it != container.end()

意思是：

只要还没有到达结束位置，就继续。

6. 手动使用迭代器遍历 `set`

现在我们终于可以遍历没有下标的 set 了。

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

for (auto it = s.begin(); it != s.end(); ++it) {
    const auto& elem = *it;
    std::cout << elem << '\n';
}

逐部分理解：

auto it = s.begin()

让迭代器从第一个元素开始。

it != s.end()

只要还没有到达尾后位置，就继续循环。

++it

每轮结束后，移动到下一个元素。

const auto& elem = *it

取得当前位置的元素。

7. 范围 `for` 循环内部是怎样工作的？

平时写的：

for (auto elem : s) {
    std::cout << elem;
}

概念上接近下面的代码：

auto begin = s.begin();
auto end = s.end();

for (auto it = begin; it != end; ++it) {
    auto elem = *it;
    std::cout << elem;
}

真正的语言规则还会处理数组、临时对象、成员查找等细节，但现在可以先建立这个理解：

范围 for 循环的底层依赖 begin()、end()、++、* 和比较操作。

这解释了为什么完全不同的容器都能使用范围 for：

std::vector<int> v;
std::deque<int> d;
std::set<int> s;
std::map<std::string, int> m;

for (const auto& elem : v) { }
for (const auto& elem : d) { }
for (const auto& elem : s) { }
for (const auto& elem : m) { }

范围 for 不关心容器内部究竟是：

连续数组；
多段内存；
搜索树；
哈希表。

它只需要容器提供合适的迭代器。

这就是“抽象”的力量。

8. 遍历 `map` 时，迭代器指向什么？

对于：

std::map<std::string, int> ages{
    {"Chris", 31},
    {"CS106L", 42},
    {"Keith", 14},
    {"Nick", 51},
    {"Sean", 35}
};

map 中的每个元素不是单独的键，也不是单独的值，而是一个键值对。

for (const auto& pair : ages) {
    std::cout << pair.first << ' ';
    std::cout << pair.second << '\n';
}

其中：

pair.first

是键。

pair.second

是值。

使用迭代器时也是一样：

auto it = ages.begin();

std::cout << (*it).first;
std::cout << (*it).second;

因为这种写法有点麻烦，所以迭代器还提供了 ->：

std::cout << it->first;
std::cout << it->second;

下面两种写法等价：

(*it).first
it->first

更准确地说，map<K, V> 的元素类型接近：

std::pair<const K, V>

键是 const 的，因为直接修改键可能破坏 map 的排列结构。

9. 遍历有序容器和无序容器的区别

`map`

std::map<std::string, int> m;

遍历时，会按照键的比较顺序访问元素。

`unordered_map`

std::unordered_map<std::string, int> m;

遍历顺序没有可靠保证。

下面的代码当然可以执行：

for (const auto& [name, age] : m) {
    std::cout << name << ' ' << age << '\n';
}

但不要假设输出一定按照：

插入顺序；
字典序；
某个固定的哈希桶顺序。

程序运行环境、数据规模或重新哈希都可能影响遍历顺序。

第二部分：迭代器到底是什么类型？

10. 为什么我们经常使用 `auto`？

下面的代码很自然：

auto it = m.begin();
auto elem = *it;

如果写出部分完整类型，可能是：

std::map<int, int>::iterator it = m.begin();

完整类型不仅很长，而且实际实现细节有时更复杂。

标准库容器通常在类内部提供类型别名：

template <typename K, typename V>
class map {
public:
    using iterator = /* 某个复杂的迭代器类型 */;
};

于是我们可以通过：

std::map<int, int>::iterator

使用这个类型。

不过实际编程中，更推荐：

auto it = m.begin();

这里使用 auto 并不是因为我们“不知道类型”，而是因为：

编译器已经能够准确推导类型，没有必要把又长又重复的类型手写一遍。

11. `iterator` 是一个类型别名

你可以把：

using iterator = SomeLongIteratorType;

理解成：

给一个很长的类型取一个更方便的名字。

例如：

using Number = int;

Number x = 10;

这里 Number 就是 int 的别名。

标准库中的：

std::map<int, int>::iterator

也可以理解成 map 类为自己的迭代器类型准备的名字。

12. 为什么迭代器循环常写 `++it`，而不是 `it++`？

这两个表达式都会让迭代器前进。

区别在于返回值。

前置自增

++it;

先增加，再返回增加后的对象。

概念上的运算符形式类似：

Iterator& operator++();

它通常返回当前对象的引用。

后置自增

it++;

需要先保存旧值，再增加，最后返回旧值。

概念上的形式类似：

Iterator operator++(int);

它可能需要产生一个旧迭代器的副本。

如果我们根本不需要旧值：

for (...; ...; ++it)

那么使用前置自增更直接。

对于简单指针或经过优化的程序，性能差异可能不存在；但对一些复杂迭代器而言，前置自增可以避免不必要的复制。

所以一种常见习惯是：

++it

除非确实需要后置自增返回的旧值。

例如：

auto old = it++;

这里 old 指向增加前的位置，而 it 已经指向下一位置。

13. 跟踪迭代器的位置

观察代码：

std::map<int, int> m{
    {1, 2},
    {3, 4},
    {5, 6}
};

auto a = m.begin();
++a;

auto b = a;

++a;

auto c = ++a;

首先，m 中有三个元素：

{1, 2}  {3, 4}  {5, 6}  end

执行：

auto a = m.begin();

a 指向：

{1, 2}

执行：

++a;

a 指向：

{3, 4}

执行：

auto b = a;

复制迭代器之后，a 和 b 都指向：

{3, 4}

执行：

++a;

现在：

a -> {5, 6}
b -> {3, 4}

执行：

auto c = ++a;

a 从最后一个元素前进到 end()，然后把前进后的迭代器复制给 c。

最终：

a -> m.end()
b -> {3, 4}
c -> m.end()

注意：

a == c

但不能对它们解引用：

*a;  // 错误
*c;  // 错误

因为它们都等于 m.end()。

第三部分：不是所有迭代器都一样

14. 迭代器提供的能力不同

所有常见迭代器至少围绕这些操作工作：

auto it = c.begin();
++it;
*it;
it == c.end();

但有些迭代器还支持更多操作：

--it;       // 向后移动
it += n;    // 一次移动多个位置
it[n];      // 访问后面第 n 个位置
it1 < it2;  // 比较前后顺序
*it = value; // 修改或输出

迭代器会根据自己提供的能力被分为不同类别。

课件中介绍了：

Input Iterator，输入迭代器；
Output Iterator，输出迭代器；
Forward Iterator，前向迭代器；
Bidirectional Iterator，双向迭代器；
Random Access Iterator，随机访问迭代器。

这些名字不是在描述“数据是什么”，而是在描述：

这个迭代器允许我们做哪些操作。

15. 输入迭代器：可以读取当前位置

输入迭代器最重要的能力是读取：

auto elem = *it;

一个典型例子是：

std::istream_iterator<int>

它可以把输入流看成一串不断出现的元素。

#include <iostream>
#include <iterator>

int main() {
    std::istream_iterator<int> it(std::cin);
    std::istream_iterator<int> end;

    while (it != end) {
        std::cout << *it << ' ';
        ++it;
    }
}

这里：

std::istream_iterator<int> it(std::cin);

让 it 从标准输入读取整数。

而默认构造的：

std::istream_iterator<int> end;

代表输入流的结束状态。

用户输入：

10 20 30

程序会依次读出：

10 20 30

直到：

输入结束；
或者下一个内容无法解析成整数。

15.1 可以直接用输入迭代器构造容器

std::istream_iterator<int> start(std::cin);
std::istream_iterator<int> end;

std::vector<int> numbers(start, end);

这段代码表示：

从 start 开始不断读取整数，直到 end，然后把读到的整数放入 vector。

15.2 为什么输入流通常只能单趟读取？

假设：

auto it1 = std::istream_iterator<int>(std::cin);
auto it2 = it1;

看起来好像 it1 和 it2 都在同一个位置。

但是输入流是一份正在被消耗的数据。

当我们执行：

++it1;

底层输入流已经向前读取了。

此时不能把 it2 当成一份完全独立、仍然停留在过去位置的游标。

所以输入迭代器常被称为：

单趟迭代器。

读过去的数据可能已经无法再次访问。

16. `operator->`：访问当前对象的成员

假设容器元素是一个结构体：

struct Student {
    std::string name;
    int score;
};

std::vector<Student> students{
    {"Alice", 95},
    {"Bob", 88}
};

取得第一个学生：

auto it = students.begin();

可以写：

std::cout << (*it).name;

也可以写得更自然：

std::cout << it->name;

两者的含义相同：

(*it).name
it->name

这个操作不仅适用于迭代器，也适用于指向对象的指针。

17. 输出迭代器：向当前位置写入内容

输入迭代器用于读取：

value = *it;

输出迭代器则用于写入：

*it = value;

17.1 向输出流写入

#include <iostream>
#include <iterator>

int main() {
    std::ostream_iterator<int> out(std::cout, ", ");

    *out = 10;
    ++out;

    *out = 20;
    ++out;

    *out = 30;
}

输出：

10, 20, 30,

对于流输出迭代器，++out 通常并不真的移动某块内存，但它提供了和普通迭代器一致的接口。

这很重要，因为标准库算法只需要按照统一方式操作迭代器。

17.2 向 `vector` 尾部写入

直接对空 vector 的 begin() 解引用是不行的：

std::vector<int> v;

auto it = v.begin();
*it = 10;  // 错误，没有现成元素

但可以使用后插入迭代器：

std::vector<int> v;

std::back_insert_iterator<std::vector<int>> it(v);

*it = 10;
++it;

*it = 20;
++it;

*it = 30;

它会在内部调用：

v.push_back(10);
v.push_back(20);
v.push_back(30);

最终：

v = {10, 20, 30}

实际编程中通常会写得更短：

auto it = std::back_inserter(v);

18. 前向迭代器：可以可靠地进行多趟遍历

前向迭代器不仅可以读取和向前移动，还具有“多趟保证”。

直观地说：

你可以复制一个迭代器，并把两个副本当成相互独立的位置记录器。

例如：

auto it1 = container.begin();
auto it2 = it1;

++it1;

此时：

it1 移动到下一个元素；
it2 仍然留在原来的元素。

这和输入流迭代器不同，因为容器中的数据不会因为一个迭代器向前移动就被“消耗”。

所有标准容器的普通迭代器，至少都具备前向迭代能力。

例如 unordered_set 和 unordered_map 的迭代器就是前向迭代器。

19. 双向迭代器：不仅能前进，还能后退

双向迭代器额外支持：

--it;

常见的双向迭代器包括：

std::map
std::set

以及 std::list。

例如：

std::map<std::string, int> m{
    {"apple", 1},
    {"banana", 2},
    {"cherry", 3}
};

auto it = m.end();
--it;

std::cout << it->first;   // cherry
std::cout << it->second;  // 3

为什么先从 end() 开始，再执行一次 --it？

因为：

最后一个元素   end()
     ↓          ↓
  [cherry] [尾后位置]

end() 指向最后一个元素之后。

后退一步才会到达最后一个真实元素。

不过这要求容器不是空的：

if (!m.empty()) {
    auto it = m.end();
    --it;
}

对空容器的 end() 执行 --it 是不合法的。

20. 随机访问迭代器：可以快速跳跃

随机访问迭代器支持：

it + n
it - n
it += n
it -= n
it[n]
it2 - it1
it1 < it2

常见的随机访问迭代器包括：

std::vector
std::deque

例如：

std::vector<int> v{10, 20, 30, 40, 50};

auto it = v.begin();

auto it2 = it + 3;

std::cout << *it2;  // 40

也可以：

std::cout << it[2];  // 30

这里：

it[2]

基本相当于：

*(it + 2)

20.1 “随机访问”不是随机选择

这个名字容易误解。

它不是说迭代器会随机跑到某个位置，而是说：

可以在近似常数时间内，直接跳到距离当前位置任意偏移的位置。

例如：

it + 1000

不需要真的执行一千次：

++it;

20.2 `deque` 支持随机访问，但不一定连续

std::deque

支持：

d[100]

它的迭代器也支持随机访问。

但这并不代表 deque 的所有元素一定像 vector 一样存放在一整块连续内存中。

“支持随机访问”和“底层内存连续”是两个不同的概念。

21. 不要让迭代器越界

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

auto it = v.begin();
it += 3;

现在：

it == v.end()

这是允许的。

但不能：

int& elem = *it;  // 未定义行为

因为 end() 不指向元素。

类似地，也不能让迭代器跑到合法范围之外：

it = v.begin() - 1;  // 不合法
it = v.end() + 1;    // 不合法

学习迭代器时要始终记住一个合法范围：

[begin(), end()]

其中 end() 可以用于比较，但不能解引用。

22. 为什么迭代器类别非常重要？

因为标准库算法会要求特定的迭代器能力。

例如：

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

std::sort(v.begin(), v.end());

这是合法的，因为 vector 提供随机访问迭代器。

std::sort 需要频繁地：

向前或向后跳跃；
比较位置；
交换不同位置的元素。

但下面的代码不能通过编译：

std::unordered_set<int> s{1, 5, 3, 4};

std::sort(s.begin(), s.end());  // 错误

unordered_set 提供的是前向迭代器，不是随机访问迭代器。

另外，集合元素也不能被 sort 随意交换，因为修改集合内部元素可能破坏容器结构。

对于：

std::set<int>

更没有必要调用 sort，因为它本来就会按照比较规则保持有序。

需要特别纠正课件中的一个简化：unordered_set 的迭代器不是双向迭代器，而是前向迭代器。

23. 为什么 C++ 不给所有迭代器提供全部操作？

看起来，我们似乎可以让所有迭代器都支持：

it + 100

即使底层是树，也可以连续执行一百次 ++it。

但这样会产生一个问题：

it + 100

看起来像是一个很快的随机访问操作，实际上却可能悄悄执行一百步。

C++ 的标准库通常不会为一个结构提供看起来很快、实际上很慢的操作。

例如：

vector_iterator + 100

可以快速计算目标位置。

但对于树形结构中的 map::iterator，寻找后面第一百个元素通常只能逐个前进。

因此，map::iterator 根本不提供：

it + 100

这样，代码所使用的操作能够更加真实地反映底层数据结构的能力。

24. 常见容器与迭代器能力

容器	典型迭代器能力	可以 `--it`	可以 `it + n`
`vector`	随机访问	可以	可以
`deque`	随机访问	可以	可以
`list`	双向	可以	不可以
`set`	双向	可以	不可以
`map`	双向	可以	不可以
`unordered_set`	前向	不可以	不可以
`unordered_map`	前向	不可以	不可以
`forward_list`	前向	不可以	不可以

这里的“不可以”通常会在编译阶段被发现，而不是等程序运行后再出错。

第四部分：从迭代器走向指针

25. 迭代器和指针有什么联系？

可以先用一句话区分：

迭代器指向容器中的某个元素；指针可以指向内存中的任意对象。

它们不是完全相同的东西，但提供了非常相似的操作：

*it
++it
it == end
it + n

指针也能做类似的事情：

*ptr
++ptr
ptr1 == ptr2
ptr + n

为了理解这种相似性，我们需要先了解一点内存。

第五部分：内存基础

26. 变量究竟放在哪里？

每个变量都需要存放在某个内存位置。

例如：

int x = 106;

计算机不仅要记住 x 的值是 106，还要把这些数据存放在内存中的某些字节里。

程序的虚拟地址空间可以粗略想象成：

高地址
┌──────────────────────┐
│ 操作系统相关区域       │
├──────────────────────┤
│ 栈 Stack              │
│ 局部变量、函数调用信息  │
│          ↓            │
│                      │
│          ↑            │
│ 堆 Heap               │
│ 动态分配的数据         │
├──────────────────────┤
│ 全局/静态变量          │
├──────────────────────┤
│ 程序指令 Text          │
└──────────────────────┘
低地址

这只是帮助理解的简化示意图。

真实系统会涉及：

虚拟内存；
地址随机化；
只读区域；
动态库；
内存映射；
不同操作系统的实现差异。

现在不需要掌握这些细节。

27. 内存通常按字节寻址

一个字节：

1 byte = 8 bits

内存中的每一个字节都可以对应一个地址。

想象：

地址       数据
0x1000    01010101
0x1001    00001111
0x1002    11000000
0x1003    00110011

在 64 位程序中，地址通常使用 64 位大小的值表示，但这并不意味着程序真的可以使用全部 2^64 字节内存。

它只是地址表示和虚拟地址空间的概念。

28. 一个对象可能占用多个字节

例如很多常见平台中：

sizeof(int) == 4

也就是一个 int 占用四个字节。

不过 C++ 并不保证 int 在所有平台上永远都是 32 位。它通常是 32 位，但准确大小应通过：

sizeof(int)

查看。

假设：

int x = 106;

并且 x 占四个字节：

地址       x 所占用的字节
0x1000    ...
0x1001    ...
0x1002    ...
0x1003    ...

对象的地址通常指它所占内存中地址最低的那个字节：

x 的地址 = 0x1000

29. 大端序和小端序

一个多字节整数究竟怎样分布在几个字节中，由字节序决定。

常见的有：

Big Endian，大端序；
Little Endian，小端序。

现代个人计算机通常使用小端序。

不过目前最重要的是理解：

一个整数可能占用多个连续字节，而它有一个起始地址。

不需要现在手动背诵每个字节如何排列。

第六部分：指针

30. 指针保存一个对象的地址

int x = 106;
int* px = &x;

逐部分理解。

`int*`

int* px;

表示：

px 是一个指向 int 的指针。

它保存的不是普通整数值，而是某个 int 对象的地址。

`&x`

&x

表示取得变量 x 的地址。

因此：

int* px = &x;

就是：

取得 x 的地址，并把这个地址存入指针 px。

可以画成：

px
┌──────────┐
│ 0x1000   │──────┐
└──────────┘      │
                  ▼
地址 0x1000
┌──────────┐
│ x = 106  │
└──────────┘

31. `x`、`px` 和 `*px` 分别是什么？

int x = 106;
int* px = &x;

`x`

std::cout << x;

输出 x 中保存的值：

`px`

std::cout << px;

输出指针保存的地址，可能类似：

0x7ffc1234abcd

每次运行时，实际地址都可能不同。

`*px`

std::cout << *px;

表示：

前往 px 保存的地址，取得那个地址上的 int 对象。

因为 px 指向 x，所以：

*px

就是 x。

输出：

32. 可以通过指针修改原变量

int x = 106;
int* px = &x;

*px = 200;

std::cout << x;  // 200

执行：

*px = 200;

不是在修改指针保存的地址，而是在修改：

指针所指向的对象。

由于 px 指向 x，所以 x 变成了 200。

33. `*` 在不同位置有不同含义

初学时很容易混淆。

声明中的 `*`

int* px;

表示 px 的类型是“指向 int 的指针”。

表达式中的 `*`

*px

表示解引用，取得指针所指向的对象。

因此：

int* px = &x;

左边的 * 是类型声明的一部分。

而：

std::cout << *px;

这里的 * 是解引用操作。

34. `&` 也有多种含义

取得地址

int* px = &x;

这里的 &x 表示取得地址。

声明引用

int& ref = x;

这里的 & 表示 ref 是一个引用。

范围循环里的引用

for (const auto& elem : container)

这里的 & 也表示引用，不是“取得地址”。

C++ 中一些符号会根据上下文承担不同作用，这是初学阶段需要慢慢适应的地方。

35. 指针可以指向各种对象

指向整数

int x = 106;
int* px = &x;

指向结构体

struct StanfordID {
    std::string name;
};

StanfordID id{"rfern"};
StanfordID* p = &id;

std::cout << p->name;

这里：

p->name

等价于：

(*p).name

指向 `vector` 对象

std::vector<int> v;
std::vector<int>* p = &v;

p->push_back(10);

等价于：

(*p).push_back(10);

指向 `vector` 中的元素

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

int* p = &v[0];

此时 p 指向第一个整数，而不是指向整个 vector 对象。

下面两个指针类型完全不同：

std::vector<int>* p1 = &v;  // 指向 vector 对象
int* p2 = &v[0];            // 指向 vector 中的 int 元素

36. `vector` 的元素存放在连续内存中

这是 vector 的重要性质。

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

可以想象成：

地址递增 →
┌───┬───┬───┬───┬───┐
│ 1 │ 2 │ 3 │ 4 │ 5 │
└───┴───┴───┴───┴───┘

元素之间紧挨着存放。

如果一个 int 占四个字节，那么相邻两个元素的起始地址通常相差四个字节。

不过进行指针运算时，不需要自己乘 sizeof(int)，C++ 会根据指针类型自动处理。

37. 数组指针与指针运算

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

int* arr = &v[0];

最开始：

arr
 ↓
[1][2][3][4][5]

输出当前元素：

std::cout << *arr << ' ';  // 1

前进一个元素：

arr += 1;
std::cout << *arr << ' ';  // 2

再前进一个元素：

++arr;
std::cout << *arr << ' ';  // 3

向后跳两个元素：

arr += 2;
std::cout << *arr << ' ';  // 5

比较地址：

if (arr == &v[4]) {
    std::cout << "At last index";
}

输出：

1 2 3 5 At last index

38. `arr + 1` 到底增加了多少？

假设：

int* arr;

执行：

arr + 1

不是简单地让内存地址数值增加一个字节，而是让它前进一个 int 的距离。

如果：

sizeof(int) == 4

底层地址可能从：

0x1000

移动到：

0x1004

如果是：

double* p;

并且 double 占八个字节，那么：

p + 1

可能让地址前进八个字节。

所以指针类型非常重要，它告诉编译器：

每次前进一步，应当跨过多大的对象。

39. 更现代的写法：`data()`

课件使用：

int* arr = &v[0];

但当 v 为空时，访问：

v[0]

是不合法的。

现代 C++ 中通常可以写：

int* arr = v.data();

对于非空 vector，它会返回指向第一个元素的指针。

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

int* arr = v.data();

std::cout << *arr;  // 1

40. 指针也不能随便越界

对于：

std::vector<int> v{1, 2, 3};
int* p = v.data();

可以让指针指向：

第一个元素
第二个元素
第三个元素
尾后位置

尾后位置可以用于比较，但不能解引用。

int* end = v.data() + v.size();

if (p != end) {
    std::cout << *p;
}

不能做：

std::cout << *end;  // 未定义行为

这和迭代器的 end() 完全相似。

第七部分：迭代器为什么那么像指针？

41. 用指针遍历连续元素

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

int* p = v.data();
int* end = v.data() + v.size();

for (; p != end; ++p) {
    std::cout << *p << ' ';
}

42. 用迭代器遍历

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

auto it = v.begin();
auto end = v.end();

for (; it != end; ++it) {
    std::cout << *it << ' ';
}

两段代码几乎一样。

对应关系是：

指针	迭代器
`v.data()`	`v.begin()`
`v.data() + v.size()`	`v.end()`
`++p`	`++it`
`*p`	`*it`
`p == end`	`it == end`
`p + n`	`it + n`，仅随机访问迭代器

因此可以说：

迭代器模仿了指针的接口。

43. `vector::iterator` 就是指针吗？

可以暂时把：

std::vector<T>::iterator

想象成类似：

T*

因为它们支持非常相似的操作。

概念上可以想象：

template <typename T>
class vector {
public:
    using iterator = T*;
};

但这不是标准所保证的真实实现。

某些标准库实现中，vector::iterator 可能确实接近普通指针；另一些实现中，它可能是一个包装类，用于：

调试越界访问；
记录所属容器；
检查迭代器是否合法。

因此正确说法是：

vector 的迭代器在行为上像随机访问指针，但不应该依赖它的具体底层类型一定是 T*。

44. 为什么 `map` 的迭代器不能只是普通指针？

vector 的元素连续排列，因此前往下一个元素可能只是增加地址。

但 map 通常是一棵树：

            42
          /    \
        31      51
       /       /  \
     14       35  ...

在树中，“下一个元素”并不一定在当前节点后面的连续内存中。

迭代器可能需要记住或计算：

当前树节点；
父节点；
左子树和右子树；
中序遍历中的下一个位置。

所以 map::iterator 往往是一个真正的类对象，它重载了：

operator*
operator->
operator++
operator--
operator==

这样使用者仍然可以写：

++it;
*it;
it->first;

却不需要知道树是怎样遍历的。

这也为下一节课的“类”埋下了伏笔：

template <typename K, typename V>
class map {
public:
    using iterator = /* 一个自定义迭代器类 */;
};

第八部分：容易踩的坑

45. 永远不要解引用 `end()`

错误：

auto it = v.end();
std::cout << *it;

正确：

if (it != v.end()) {
    std::cout << *it;
}

46. `end()` 不是最后一个元素

需要最后一个元素，并且迭代器支持双向移动时，可以写：

if (!container.empty()) {
    auto it = container.end();
    --it;

    std::cout << *it;
}

对于 vector 也可以使用：

container.back()

47. 不要对所有迭代器都使用 `+`

错误地假设：

auto it = set.begin();
it += 5;  // 不支持

set 是双向迭代器，只能一步一步移动：

++it;
--it;

需要通用地移动若干步时，可以使用：

std::advance(it, 5);

但对非随机访问迭代器，它可能真的执行五次 ++it。

48. 容器修改可能让迭代器和指针失效

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

auto it = v.begin();
int* p = v.data();

v.push_back(4);

如果 push_back 导致 vector 重新申请更大的内存，原来的：

it
p

可能都已经失效。

之后继续使用它们可能产生未定义行为。

这是因为 vector 可能从旧内存搬到一块新的、更大的连续内存。

初学阶段先记住：

修改容器后，不要理所当然地认为旧迭代器仍然有效。

不同容器、不同操作的失效规则并不相同，之后会继续学习。

49. 不要依赖 `unordered_map` 的遍历顺序

std::unordered_map<std::string, int> m{
    {"Alice", 1},
    {"Bob", 2},
    {"Carol", 3}
};

下面的输出顺序不保证和插入顺序相同：

for (const auto& [name, score] : m) {
    std::cout << name << '\n';
}

需要排序输出时，可以：

使用 std::map；
或把数据复制到 vector 后排序。

第九部分：动手练习

练习一：补全手写迭代器循环

请补全：

std::set<int> numbers{2, 4, 6, 8};

for (____________________;
     ____________________;
     ____________________) {

    const auto& value = __________;
    std::cout << value << '\n';
}

答案：

std::set<int> numbers{2, 4, 6, 8};

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

    const auto& value = *it;
    std::cout << value << '\n';
}

练习二：找出错误

std::vector<int> v{10, 20, 30};

auto it = v.end();
std::cout << *it;

问题：

v.end()

指向尾后位置，不能解引用。

一种修改方式：

auto it = v.end();

if (!v.empty()) {
    --it;
    std::cout << *it;  // 30
}

练习三：预测输出

std::vector<int> v{10, 20, 30, 40};

auto it = v.begin();

std::cout << *it << ' ';
it += 2;
std::cout << *it << ' ';
--it;
std::cout << *it;

过程：

开始指向 10
向后跳两个位置，指向 30
后退一个位置，指向 20

输出：

10 30 20

练习四：使用 `->`

struct Book {
    std::string title;
    int pages;
};

std::vector<Book> books{
    {"C++ Primer", 976},
    {"Effective Modern C++", 334}
};

auto it = books.begin();

请输出第一本书的信息。

答案：

std::cout << it->title << '\n';
std::cout << it->pages << '\n';

等价写法：

std::cout << (*it).title << '\n';
std::cout << (*it).pages << '\n';

练习五：指针修改变量

int x = 5;
int* p = &x;

*p += 10;

std::cout << x;

输出：

因为：

*p

就是指针所指向的 x。

练习六：判断操作是否合法

std::set<int> s{1, 2, 3};
auto it = s.begin();

下面哪些合法？

++it;
--it;
it += 2;
std::cout << *it;

答案：

++it;             // 合法
--it;             // 合法，前提是不会退到 begin() 之前
it += 2;          // 不合法，set 不是随机访问迭代器
std::cout << *it; // 合法，前提是 it 不等于 end()

练习七：手写范围循环的近似版本

把：

for (const auto& value : v) {
    std::cout << value << '\n';
}

改写为迭代器形式：

auto begin = v.begin();
auto end = v.end();

for (auto it = begin; it != end; ++it) {
    const auto& value = *it;
    std::cout << value << '\n';
}

你现在已经能够读懂这段代码

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

int main() {
    std::map<std::string, int> scores{
        {"Alice", 95},
        {"Bob", 88},
        {"Carol", 92}
    };

    for (auto it = scores.begin(); it != scores.end(); ++it) {
        std::cout << it->first
                  << ": "
                  << it->second
                  << '\n';
    }
}

可以把它逐句翻译成：

auto it = scores.begin();

让迭代器从 map 的第一个键值对开始。

it != scores.end()

只要还没有到达尾后位置，就继续。

++it

移动到下一个键值对。

it->first

访问当前键。

it->second

访问当前值。

最重要的不是记住某一段固定代码，而是理解这套统一协议：

从 begin 开始
不断 ++
通过 * 或 -> 访问元素
到达 end 时停止

无论底层是连续数组、双端队列、哈希表还是搜索树，迭代器都为我们提供了一种统一的遍历方式。

课件提供的在线练习地址：

https://106b.vercel.app/iterators

下一节课将进一步学习“类”，并回答本节最后留下的问题：

template <typename K, typename V>
class map {
public:
    using iterator = ?????;
};