引言：迭代器的核心价值

在 C++ 标准模板库 (STL) 中，迭代器扮演着 "胶水" 的角色，它连接了容器与算法，使算法能够独立于具体容器类型工作。这种抽象机制带来了极大的灵活性 —— 同一个排序算法可以作用于向量 (vector)、链表 (list) 或数组 (array)，只需它们提供兼容的迭代器。

迭代适配器则是在基础迭代器之上的增强，通过包装现有迭代器，提供反向遍历、插入操作等特殊行为，进一步扩展了迭代器的能力。本文将系统解析迭代器的分类、实现原理及迭代适配器的应用场景。

一、迭代器基础：概念与分类

1.1 迭代器的本质

迭代器本质上是一种泛化的指针，它重载了*、->、++等运算符，使开发者能够以统一的方式访问容器中的元素，而不必关心容器的内部实现细节。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <vector>
#include <list>
#include <iostream>

// 通用打印函数，适用于任何提供输入迭代器的容器
template<typename Iterator>
void print_range(Iterator begin, Iterator end) {
    while (begin != end) {
        std::cout << *begin << " ";
        ++begin;
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> vec = {1, 2, 3, 4};
    std::list<std::string> lst = {"Hello", "World"};
    
    print_range(vec.begin(), vec.end());  // 输出：1 2 3 4
    print_range(lst.begin(), lst.end());  // 输出：Hello World
    
    return 0;
}

1.2 迭代器的五种类型

C++ 标准根据迭代器支持的操作，将其分为五类，形成一个层次结构：

  1. 输入迭代器 (Input Iterator)
    • 支持：++、*、->、==、!=
    • 特性：只能读取元素，单向移动，同一元素只能读一次
    • 典型用途：从流中读取数据 (istream_iterator)
  2. 输出迭代器 (Output Iterator)
    • 支持：++、*
    • 特性：只能写入元素，单向移动，同一位置只能写一次
    • 典型用途：向流中写入数据 (ostream_iterator)
  3. 前向迭代器 (Forward Iterator)
    • 支持输入迭代器的所有操作
    • 特性：可多次读写同一元素，单向移动
    • 典型用途：单向链表 (forward_list)
  4. 双向迭代器 (Bidirectional Iterator)
    • 支持前向迭代器的所有操作
    • 增加：--操作（反向移动）
    • 典型用途：双向链表 (list)、集合 (set)
  5. 随机访问迭代器 (Random Access Iterator)
    • 支持双向迭代器的所有操作
    • 增加：+=、-=、[]、随机访问
    • 典型用途：向量 (vector)、数组 (array)、字符串 (string)

迭代器类型决定了可在其上使用的算法 —— 例如，sort算法要求随机访问迭代器，而find算法只需输入迭代器。

二、迭代适配器：扩展迭代器功能

迭代适配器是包装现有迭代器并改变其行为的对象，它们不直接访问容器，而是通过底层迭代器工作。STL 提供了三种主要的迭代适配器：反向迭代器、插入迭代器和流迭代器。

2.1 反向迭代器 (Reverse Iterator)

反向迭代器将迭代方向反转，使++操作实际移动到前一个元素，--操作移动到后一个元素。通过rbegin()和rend()可以获取容器的反向迭代器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <vector>
#include <iostream>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    
    // 正向遍历
    std::cout << "正向遍历: ";
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 反向遍历
    std::cout << "反向遍历: ";
    for (auto it = numbers.rbegin(); it != numbers.rend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出结果：

1
2
正向遍历: 1 2 3 4 5 
反向遍历: 5 4 3 2 1

反向迭代器与正向迭代器可以通过base()方法相互转换，但需要注意它们指向的位置关系：反向迭代器rit对应的正向迭代器rit.base()指向的是rit当前指向元素的下一个元素。

2.2 插入迭代器 (Insert Iterator)

插入迭代器将赋值操作 (*it = value) 转换为插入操作，适用于在容器中插入元素而非覆盖现有元素。STL 提供三种插入迭代器：

  1. back_insert_iterator：在容器末尾插入（要求容器支持push_back()）
  2. front_insert_iterator：在容器开头插入（要求容器支持push_front()）
  3. insert_iterator：在指定位置插入（要求容器支持insert()）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <vector>
#include <list>
#include <iterator>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> source = {1, 2, 3};
    std::vector<int> dest1;
    std::list<int> dest2;
    
    // 使用back_inserter在dest1末尾插入
    std::copy(source.begin(), source.end(), 
              std::back_inserter(dest1));
    
    // 使用front_inserter在dest2开头插入（会逆序）
    std::copy(source.begin(), source.end(), 
              std::front_inserter(dest2));
    
    // 使用inserter在指定位置插入
    std::vector<int> dest3 = {10, 20, 30};
    std::copy(source.begin(), source.end(),
              std::inserter(dest3, dest3.begin() + 1));
    
    // 输出结果
    std::cout << "dest1: ";
    for (int x : dest1) std::cout << x << " ";  // 1 2 3
    
    std::cout << "\ndest2: ";
    for (int x : dest2) std::cout << x << " ";  // 3 2 1
    
    std::cout << "\ndest3: ";
    for (int x : dest3) std::cout << x << " ";  // 10 1 2 3 20 30
    
    return 0;
}

插入迭代器解决了算法与容器大小的矛盾 —— 算法无需关心目标容器是否有足够空间，只需专注于元素的复制或转换。

2.3 流迭代器 (Stream Iterator)

流迭代器将输入输出流视为序列，允许我们像操作容器一样操作流。主要包括：

  • istream_iterator：从输入流读取数据
  • ostream_iterator：向输出流写入数据
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <vector>
#include <iterator>
#include <algorithm>

int main() {
    // 从标准输入读取整数直到文件结束
    std::cout << "请输入一些整数（按Ctrl+D结束）: ";
    std::istream_iterator<int> in_iter(std::cin);
    std::istream_iterator<int> eof;  // 流结束迭代器
    
    std::vector<int> numbers(in_iter, eof);  // 直接用流迭代器初始化向量
    
    // 排序
    std::sort(numbers.begin(), numbers.end());
    
    // 使用ostream_iterator输出，元素间用", "分隔
    std::cout << "排序结果: ";
    std::copy(numbers.begin(), numbers.end(),
              std::ostream_iterator<int>(std::cout, ", "));
    std::cout << std::endl;
    
    return 0;
}

流迭代器的强大之处在于能将算法直接应用于流操作，例如可以用std::transform对流数据进行处理后直接输出。

三、迭代器的失效问题

当容器的内部结构发生变化时（如插入、删除元素），迭代器可能会失效，使用失效的迭代器会导致未定义行为。不同容器的迭代器失效规则不同：

  • vector：
    • 插入元素可能导致所有迭代器失效（当需要重新分配内存时）
    • 删除元素导致被删除元素后的所有迭代器失效
  • list：
    • 插入元素不会导致任何迭代器失效
    • 删除元素只导致指向被删除元素的迭代器失效
  • map/set：
    • 插入元素不会导致任何迭代器失效
    • 删除元素只导致指向被删除元素的迭代器失效

安全删除示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 安全删除vector中的元素
std::vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.begin(); it != vec.end(); ) {
    if (*it % 2 == 0) {
        it = vec.erase(it);  // erase返回下一个有效迭代器
    } else {
        ++it;
    }
}

// 安全删除list中的元素
std::list<int> lst = {1, 2, 3, 4, 5};
for (auto it = lst.begin(); it != lst.end(); ) {
    if (*it % 2 == 0) {
        it = lst.erase(it);
    } else {
        ++it;
    }
}