Iterators

迭代器（Iterator） 是 STL 的核心组件之一。它是对指针的泛化，提供了一套统一的接口来遍历不同的数据结构——无论底层是连续数组、链表还是红黑树，算法都通过迭代器访问元素，无需关心容器的内部实现。

正因如此，STL 的算法才能独立于容器存在：std::sort 不关心你传的是 vector 还是 deque，它只要求迭代器满足随机访问的要求。

一、迭代器与指针的关系

迭代器的语义是指针语义的推广。指针本身就是一个合法的迭代器：

int arr[] = {1, 2, 3, 4, 5};

// 用指针作为迭代器
std::sort(arr, arr + 5);
auto it = std::find(arr, arr + 5, 3);

标准库保证：任何接受迭代器的函数模板，也能接受普通指针。

迭代器的基本操作包括：

二、迭代器分类

C++17 起共有六类迭代器，按能力从弱到强排列。每一类都包含前一类的能力：

几点说明：

• 输入与输出迭代器是单遍的（single-pass）：只能遍历一次，it1 == it2 不保证有意义。它们主要用于流操作。
• 前向迭代器支持多遍遍历，可以保存副本后分别遍历。
• 连续迭代器是 C++17 正式加入的分类（此前 vector、string、array 的迭代器在实际使用中被当作独立类别）。它保证元素在内存中连续，因此 &*it 得到的地址可以像数组指针一样使用。

Tip

为什么分类重要？

每个算法都要求特定类别的迭代器。例如 std::sort 要求随机访问迭代器，因此不能用于 std::list（list 只提供双向迭代器）。这也是 std::list 自带成员函数 sort 的原因。

选错容器时，编译器报错通常就是「迭代器类别不满足要求」。

三、迭代器与容器对照

四、迭代器适配器

适配器在已有迭代器基础上改变行为，定义在 <iterator> 中。

1. 插入迭代器

插入迭代器把「赋值」变成「插入」，常用于向空容器写入：

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

// 不用预先分配空间
std::copy(src.begin(), src.end(), std::back_inserter(dst));
// dst = {1,2,3}

std::list<int> lst;
std::copy(src.begin(), src.end(), std::front_inserter(lst));
// lst = {3,2,1}（每次插入头部，顺序反转）

std::vector<int> v{1, 5};
std::copy(src.begin(), src.end(), std::inserter(v, v.begin() + 1));
// v = {1,1,2,3,5}

2. 反向迭代器

reverse_iterator 把递增变成递减，用于从后往前遍历：

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

for (auto it = v.rbegin(); it != v.rend(); ++it)
    std::cout << *it << ' ';   // 输出: 5 4 3 2 1

rbegin() 对应最后一个元素，rend() 对应第一个元素之前的位置。注意 *rbegin() 是最后一个元素，而解引用 rend() 是未定义行为。

3. 移动迭代器

move_iterator 解引用时返回右值引用，使算法执行移动而非拷贝：

std::vector<std::string> src{"hello", "world"};
std::vector<std::string> dst;

std::copy(std::make_move_iterator(src.begin()),
          std::make_move_iterator(src.end()),
          std::back_inserter(dst));
// dst 获得元素，src 中的字符串被移空

4. 流迭代器

流迭代器把输入输出流接入算法：

#include <iterator>

// 从 cin 读取整数，直到输入失败
std::vector<int> v;
std::copy(std::istream_iterator<int>(std::cin),
          std::istream_iterator<int>(),
          std::back_inserter(v));

// 输出到 cout，用空格分隔
std::copy(v.begin(), v.end(),
          std::ostream_iterator<int>(std::cout, " "));

五、迭代器操作函数

<iterator> 提供了几个通用的迭代器操作，它们会根据迭代器类别自动选择高效实现：

std::list<int> lst{1, 2, 3, 4, 5};

auto it = lst.begin();
std::advance(it, 3);                    // it 指向 4
auto it2 = std::next(lst.begin(), 2);   // it2 指向 3
auto n = std::distance(lst.begin(), it);  // 3

Tip

优先用 std::next 而非 it + n

it + n 只对随机访问迭代器有效，而 std::next 对所有前向以上迭代器都可用。在模板代码中应使用 std::next。

六、迭代器失效

迭代器失效是指容器修改后，原有的迭代器不再指向有效元素。这是使用 STL 时最容易出错的地方，规则因容器而异：

详细规则见各容器章节，例如 Vector · 迭代器失效。

七、C++20 的迭代器概念

C++20 用 Concepts 重新定义了迭代器体系，与 C++17 的「具名要求」相比，约束更精确、报错更清晰：

此外还有更基础的概念：indirectly_readable、indirectly_writable、weakly_incrementable、sentinel_for、sized_sentinel_for 等。

C++20 还引入了哨兵（sentinel）的概念：范围的起点和终点可以是不同类型，只要它们可以比较。这使 [begin, sentinel) 形式的范围更灵活。

关联类型也改用了新的别名模板：

std::iter_value_t<It>          // 迭代器的值类型
std::iter_reference_t<It>      // 解引用返回的引用类型
std::iter_difference_t<It>     // 距离类型

八、注意事项

• 不要把 end() 缓存起来跨修改使用。容器修改后 end() 可能失效，应在循环条件中实时获取。
• 删除元素时用 erase 的返回值。erase 返回下一个有效迭代器，直接 ++it 是未定义行为。
• 反向迭代器的 base() 有偏移。rit.base() 指向的是 rit 所指元素的下一个位置。
• std::distance 对非随机访问迭代器是 \(O(n)\)。在大链表上频繁调用会成为性能瓶颈。
• auto&& 与代理迭代器。vector<bool> 的迭代器返回代理对象而非 bool&，for (auto& x : vec) 无法编译，详见 Vector。
• 警惕悬垂迭代器。容器销毁或元素被删除后，指向它的迭代器立即失效。

九、相关章节

• Containers：各容器的迭代器类别与失效规则
• Algorithms：算法对迭代器的要求
• Vector：迭代器失效的典型案例
• List：双向迭代器与成员函数 sort