第四节 · 游走于每一处 · 迭代器

在学习 string 和 vector 时，我们已经多次见到了迭代器（Iterator）。迭代器是 C++ 标准库的核心概念之一，它提供了一种统一的方式来访问容器中的元素。

如果把容器比作一条街道，元素比作街道上的房子，那么迭代器就像是一个邮递员——它知道如何从一家走到另一家，而不需要知道街道的具体布局。

---

什么是迭代器

迭代器是一种类似指针的对象，它可以：

• 指向容器中的某个元素

• 通过递增/递减移动到相邻的元素

• 通过解引用访问它指向的元素

最简单的理解方式：迭代器就是"泛化的指针"。

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

// 获取指向第一个元素的迭代器
vector<int>::iterator it = v.begin();

// 解引用，获取元素的值
cout << *it << endl;  // 10

// 移动到下一个元素
++it;
cout << *it << endl;  // 20

// 移动到上一个元素
--it;
cout << *it << endl;  // 10

---

begin() 和 end()

每个标准库容器都提供 begin() 和 end() 成员函数：

• begin()：返回指向第一个元素的迭代器

• end()：返回指向最后一个元素之后的位置的迭代器（不是最后一个元素！）

容器: [ 10 | 20 | 30 | 40 | 50 ]
       ↑                         ↑
     begin()                   end()

end() 指向的是一个"虚拟"的位置，不能解引用。它的作用是标记遍历的终点。

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

// 使用迭代器遍历
for (vector<int>::iterator it = v.begin(); it != v.end(); ++it)
{
    cout << *it << " ";
}
cout << endl;
// 输出: 10 20 30 40 50

// 使用 auto 简化
for (auto it = v.begin(); it != v.end(); ++it)
{
    cout << *it << " ";
}
cout << endl;

---

迭代器的运算

不同类型的迭代器支持不同的运算。对于 vector 和 string，它们的迭代器是随机访问迭代器，支持所有运算：

vector<int> v = {10, 20, 30, 40, 50};
auto it = v.begin();

// 递增递减
++it;       // 移动到下一个
--it;       // 移动到上一个

// 加减整数
it = it + 2;    // 向前移动 2 个位置
it = it - 1;    // 向后移动 1 个位置

// 复合赋值
it += 2;
it -= 1;

// 迭代器之间的减法
auto begin = v.begin();
auto end = v.end();
cout << "元素个数: " << (end - begin) << endl;  // 5

// 比较运算
if (it < v.end())
    cout << *it << endl;

// 下标运算
auto it2 = v.begin();
cout << it2[2] << endl;  // 等同于 *(it2 + 2)，输出 30

---

const 迭代器

如果你不想（或不能）通过迭代器修改元素，可以使用 const 迭代器：

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

// const_iterator：只能读取，不能修改
vector<int>::const_iterator cit = v.cbegin();
cout << *cit << endl;  // 可以读取
// *cit = 100;         // 错误！不能修改

// cbegin() 和 cend() 返回 const_iterator
for (auto it = v.cbegin(); it != v.cend(); ++it)
{
    cout << *it << " ";
}

当容器本身是 const 的时候，begin() 和 end() 也会返回 const_iterator。

---

反向迭代器

如果想从后往前遍历，可以使用反向迭代器：

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

// rbegin() 指向最后一个元素
// rend() 指向第一个元素之前的位置
for (auto it = v.rbegin(); it != v.rend(); ++it)
{
    cout << *it << " ";
}
cout << endl;
// 输出: 50 40 30 20 10

注意：反向迭代器的 ++ 操作是向前移动（即向数组开头方向）。

---

迭代器失效

使用迭代器时需要特别注意：某些操作可能会导致迭代器失效。

vector<int> v = {1, 2, 3, 4, 5};
auto it = v.begin() + 2;  // 指向 3

v.push_back(6);  // 可能导致 it 失效！

// 此时使用 it 是危险的
// cout << *it << endl;  // 未定义行为

会导致迭代器失效的操作包括：

• push_back()：可能导致 vector 重新分配内存

• insert()：插入点之后的所有迭代器失效

• erase()：删除点及之后的所有迭代器失效

• clear()：所有迭代器失效

安全的做法是在这些操作后重新获取迭代器：

v.push_back(6);
it = v.begin() + 2;  // 重新获取迭代器

---

在遍历时删除元素

一个常见的错误是在遍历时删除元素：

// 错误示范！
vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); ++it)
{
    if (*it % 2 == 0)
        v.erase(it);  // 危险！删除后 it 失效，++it 将导致未定义行为
}

正确的做法：

// 正确做法
vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); )
{
    if (*it % 2 == 0)
        it = v.erase(it);  // erase 返回下一个有效迭代器
    else
        ++it;
}
// v 现在是 {1, 3, 5}

---

迭代器与算法

标准库的算法几乎都是通过迭代器来操作容器的：

#include <algorithm>
#include <vector>

vector<int> v = {5, 2, 8, 1, 9};

// 排序
sort(v.begin(), v.end());

// 查找
auto it = find(v.begin(), v.end(), 8);
if (it != v.end())
    cout << "找到了: " << *it << endl;

// 只对部分元素排序
sort(v.begin(), v.begin() + 3);  // 只排序前 3 个元素

// 反转
reverse(v.begin(), v.end());

// 复制
vector<int> dest(5);
copy(v.begin(), v.end(), dest.begin());

这就是迭代器的强大之处：算法只需要知道如何使用迭代器，而不需要知道具体是什么容器。同一个 sort 算法可以用于 vector、deque、普通数组等任何支持随机访问的容器。

---

迭代器的类型

C++ 定义了几种迭代器类型，按功能从弱到强排列：

1. 输入迭代器：只能单向读取

2. 输出迭代器：只能单向写入

3. 前向迭代器：可以单向多次读写

4. 双向迭代器：可以双向移动（如 list）

5. 随机访问迭代器：支持所有运算（如 vector、deque、普通数组）

不同的算法对迭代器有不同的要求。比如 sort 需要随机访问迭代器，而 find 只需要输入迭代器。

---

迭代器是连接容器和算法的桥梁，是 C++ 泛型编程的基石。理解迭代器，你就能更好地使用标准库的强大功能。

习题

• 使用迭代器遍历一个 vector，将其中所有偶数翻倍。

• 使用反向迭代器，将一个字符串倒序输出。

• 编写一个函数，使用迭代器在 vector 中查找第一个大于给定值的元素。