迭代器：让遍历容器变成“点外卖”一样简单

迭代器到底是什么？为什么需要它？

想象你是一个班级的值日生，需要把全班同学的作业本收齐。如果同学们坐成一排，你可以从第一个同学开始，一个一个往后收。但如果同学们坐成环形、或者分散在不同教室呢？你可能需要不同的“收作业方案”。作为“收作业程序”，你希望有一个统一的步骤：每次只关注当前同学，然后移动到下一个，而不必管座位怎么排的。

在编程中，迭代器（iterator） 就是这样一个“统一步骤”。它像一根魔法棒，指向容器（比如数组、链表、集合）中的某个元素，然后你可以：

看看这个元素是什么（解引用）
移到下一个元素（递增）
判断是不是已经遍历完（比较结束迭代器）

有了迭代器，你不需要关心容器内部是内存连续的一块（像数组）还是用链条串起来的（像链表），你都能用完全相同的方式去遍历。就像点外卖，不管店家在后厨怎么炒菜，你只需要收餐、吃、然后给下一单。

STL中的迭代器有哪些“等级”？

C++的STL（标准模板库）给迭代器分了五个等级，能力越来越强。你可以想象成不同等级的“外卖骑士”：

等级	能力	生活类比
输入迭代器 (Input Iterator)	只能向前走，只能读一次，不能回头	像你看一次黑板上的题目，记下来后就不能再看，因为你擦掉了
输出迭代器 (Output Iterator)	只能向前走，只能写一次，不能回头	像用粉笔在黑板上写字，写完后不能擦掉重写
前向迭代器 (Forward Iterator)	可以向前走多次，既能读也能写	像一本只允许向前翻的书，可以反复看同一页，但不能翻回去
双向迭代器 (Bidirectional Iterator)	可以向前和向后移动	像遥控汽车，可以前进后退，但不能直接飞到终点
随机访问迭代器 (Random Access Iterator)	可以一下子跳到任意位置，还能比较大小	像电梯，可以直接按10楼，不用从1楼一层层爬

容器自带的“骑士等级”不同

不同的容器提供的迭代器等级不一样，就像不同的外卖店派出的骑士能力不同：

vector、deque、array：随机访问迭代器（最强）—— 可以直飞任何位置
list、set、map：双向迭代器 —— 只能往前或者往后走
forward_list：前向迭代器 —— 只能往前走，不能后退
istream_iterator（从输入流读）：输入迭代器 —— 只能读一次
ostream_iterator（往输出流写）：输出迭代器 —— 只能写一次

新手最容易犯的4个错误

初学迭代器时，下面这些坑很容易踩到：

错误1：把迭代器当成普通指针乱加减

list<int> lst = {1,2,3};
auto it = lst.begin();
// 错误！list的迭代器不支持 it+2，因为不是随机访问迭代器
// auto it3 = it + 2;  // 编译错误！

正确做法：对于list，只能一步一步移动：++it; ++it; 或者用 std::advance(it, 2);。

错误2：在遍历时修改容器导致迭代器失效

vector<int> vec = {1,2,3,4,5};
for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (*it == 3) {
        vec.erase(it);  // 删除元素后，it就“坏掉”了，不能再用它移动！
    }
}

结果：程序可能崩溃或出现奇怪行为。正确做法是用 it = vec.erase(it); 删除后更新迭代器，或者使用算法 remove-erase。

错误3：错误理解 `end()` 的含义

end() 指向的是最后一个元素之后的位置，不是最后一个元素。初学者常会这样做：

auto it = vec.end();
cout << *it;  // 错误！end()指向的位置没有元素，解引用是未定义行为

正确做法：如果想访问最后一个元素，用 *(vec.end()-1)（仅限支持随机访问的容器）或者 vec.back()。

错误4：在Python中一边遍历一边修改列表

vec = [10, 20, 30, 40, 50]
for x in vec:
    if x == 30:
        vec.remove(x)  # 这会导致遍历跳过下一个元素，结果不可预测

建议：如果要在遍历时修改，通常用列表推导式或复制一份。

完整示例：用C++和Python对比不同迭代器的用法

下面我们写一个完整的程序，展示不同容器的迭代器能力差异，以及常见操作。

C++ 完整代码

#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <iterator>
#include <algorithm> // 包含 find, sort 等算法
using namespace std;

int main() {
    // 1. vector 提供随机访问迭代器（最强）
    vector<int> vec = {10, 20, 30, 40, 50};
    cout << "=== vector ===" << endl;
    // 用迭代器遍历
    cout << "正向遍历: ";
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        cout << *it << " ";      // 解引用得元素
    }
    cout << endl;

    // 随机访问能力：直接跳转
    auto it = vec.begin();
    cout << "it[2] = " << it[2] << endl;          // 30，等于 *(it+2)
    cout << "*(it+3) = " << *(it+3) << endl;      // 40
    cout << "最后一个元素: " << *(vec.end()-1) << endl; // 50

    // 还能比较大小：it1 < it2 表示 it1 在 it2 前面
    auto it1 = vec.begin() + 1;  // 指向20
    auto it2 = vec.begin() + 3;  // 指向40
    cout << "it1 < it2 ? " << (it1 < it2) << endl; // 1 (true)

    // 2. list 提供双向迭代器（无随机访问）
    list<int> lst = {100, 200, 300, 400};
    cout << "\n=== list ===" << endl;
    cout << "正向遍历: ";
    for (auto it = lst.begin(); it != lst.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;

    // 支持 --it 后退
    auto lit = lst.end();
    --lit; // 指向400
    cout << "最后一个元素: " << *lit << endl;
    // 但不支持 it+2： // 错误！list的迭代器不能 +
    // auto lit2 = lit + 2; // 编译错误

    // 3. set 也提供双向迭代器，但元素是常量（不能修改）
    set<int> s = {9, 3, 7, 1};
    cout << "\n=== set ===" << endl;
    cout << "set元素自动排序: ";
    for (auto it = s.begin(); it != s.end(); ++it) {
        cout << *it << " ";  // 输出: 1 3 7 9
        // *it = 5; // 错误！set的迭代器是 const_iterator，不能修改
    }
    cout << endl;

    // 4. 使用通用算法 find（只需要输入迭代器能力）
    // vector 的迭代器是随机访问，肯定能满足输入迭代器的要求
    auto found = find(vec.begin(), vec.end(), 30);
    if (found != vec.end()) {
        // 计算位置：随机访问迭代器支持减法
        int position = found - vec.begin();
        cout << "\n在vector中找到30，位置是: " << position << endl;
    }

    // 5. 注意：算法 sort 需要随机访问迭代器，所以不能用于list
    // sort(lst.begin(), lst.end()); // 编译错误！list的迭代器不支持
    // list 有自己的sort成员函数
    lst.sort(); // 正确

    return 0;
}

输出示例：

=== vector ===
正向遍历: 10 20 30 40 50 
it[2] = 30
*(it+3) = 40
最后一个元素: 50
it1 < it2 ? 1

=== list ===
正向遍历: 100 200 300 400 
最后一个元素: 400

=== set ===
set元素自动排序: 1 3 7 9 

在vector中找到30，位置是: 2

Python 等价功能

Python 没有像 C++ 那样严格的迭代器分类，但我们可以通过一些技巧模拟。Python 的 for 循环底层就是迭代器，但通常只能单向移动。可以用 reversed() 向后，用索引实现随机访问。

# Python 中的迭代器演示
from collections.abc import Iterator, Iterable

print("=== Python 迭代器基础 ===")

# 1. 列表（list）本身不是迭代器，但它是可迭代的，可以用 iter() 获得迭代器
vec = [10, 20, 30, 40, 50]
print("列表是可迭代的吗?", isinstance(vec, Iterable))   # True
print("列表本身是迭代器吗？", isinstance(vec, Iterator)) # False

# 获取迭代器
it = iter(vec)
print("\n手动用 next 遍历:")
print(next(it))  # 10
print(next(it))  # 20

# 用 for 循环（本质就是不断 next）
print("\nfor 循环遍历:")
for x in vec:
    print(x, end=" ")
print()

# 2. 随机访问——直接用下标（不是迭代器功能，而是容器本身支持）
print("\n随机访问:")
print("vec[2] =", vec[2])       # 30

# 3. 反向遍历——reversed() 返回反向迭代器（只能向后）
print("\n反向遍历:")
for x in reversed(vec):
    print(x, end=" ")
print()

# 4. 集合 set 也是可迭代的，但元素无序
s = {9, 3, 7, 1}
print("\nset 遍历（无序）:")
for x in s:
    print(x, end=" ")
print()

# 5. 注意：Python 迭代器不能后退，但可以用 itertools 或者转换为列表再索引
# 比如要获取第三个元素，不能用迭代器跳转，只能用下标
print("\n用下标获取第三个元素:", vec[2])

# 6. 通用查找函数——用 in 操作符（需要容器支持迭代）
print("30 在 vec 中吗?", 30 in vec)  # 等价于遍历比较

输出：

=== Python 迭代器基础 ===
列表是可迭代的吗? True
列表本身是迭代器吗？ False

手动用 next 遍历:
10
20

for 循环遍历:
10 20 30 40 50 

随机访问:
vec[2] = 30

反向遍历:
50 40 30 20 10 

set 遍历（无序）:
1 3 7 9 

用下标获取第三个元素: 30
30 在 vec 中吗? True

总结：记住三个要点

迭代器是“万能钥匙”：不管容器是数组、链表还是哈希表，只要它提供迭代器，你就可以用相同的方式遍历。
迭代器等级决定能力：C++ 中等级越高，能做的操作越多（比如跳跃、比较大小）。如果你需要排序，只能用随机访问迭代器（比如 vector 的）；如果只是找元素，输入迭代器就够了。
小心迭代器“坏掉”：不要在遍历时随意修改容器（插入/删除），否则迭代器可能失效。C++ 中 vector 的 push_back 也可能导致所有迭代器失效。

接下来学什么？

输入和输出迭代器：用于处理数据流（如文件读写），只能单次通过。
迭代器适配器（如 back_inserter、ostream_iterator）：让你把算法输出直接插入到容器或流中。
迭代器失效规则：不同容器在插入/删除后，哪些迭代器会失效？这是写健壮代码的关键。

掌握了迭代器，你就拥有了操作容器的“通用语言”，后面学习算法（如排序、查找、复制）时会更加顺畅。

迭代器概念与分类体系