一、什么是迭代器

在 C++ 中，迭代器（Iterator） 是容器与算法之间的桥梁，也是 STL（标准模板库）的核心组件之一。

简单理解：迭代器是面向对象版本的指针，用来遍历、访问容器（vector/string/map/list 等）中的元素。

• 原生指针可以访问数组元素；
• 迭代器可以统一访问所有 STL 容器元素。

STL 设计理念：算法不依赖容器，容器也不依赖算法，二者全部通过迭代器交互，实现代码复用。

二、迭代器基本语法与使用

2.1 迭代器定义格式

容器类型::iterator 迭代器名;

2.2 基础遍历示例（以 vector 为例）

#include <iostream>
#include <vector>
using namespace std;

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

    // 1. 定义迭代器
    vector<int>::iterator it;

    // 2. 遍历容器
    // begin()：指向第一个元素
    // end()：指向「最后一个元素的下一个位置」（哨兵位，不可解引用）
    for (it = v.begin(); it != v.end(); ++it) {
        cout << *it << " ";  // *it 解引用，取迭代器指向的元素
    }

    return 0;
}

输出：

10 20 30 40 50 

关键要点

1. begin()：返回指向首元素的迭代器。
2. end()：返回指向尾后位置的迭代器，不能解引用。
3. 遍历条件固定：it != v.end()，不建议用 <（部分容器迭代器不支持比较大小）。
4. *it：解引用，获取当前元素；it->成员：访问对象成员。

2.3 常量迭代器 const_iterator

如果只读不修改容器元素，推荐使用 const_iterator，安全性更高：

vector<int>::const_iterator cit;
for (cit = v.cbegin(); cit != v.cend(); ++cit) {
    cout << *cit << " ";
    // *cit = 100;  // 报错：常量迭代器禁止修改元素
}

2.4 反向迭代器 reverse_iterator

从容器末尾向前遍历：

vector<int>::reverse_iterator rit;
for (rit = v.rbegin(); rit != v.rend(); ++rit) {
    cout << *rit << " ";
}

• rbegin()：指向最后一个元素
• rend()：指向第一个元素的前一个位置

三、迭代器的五大分类（核心重点）

根据功能强弱、支持操作，C++ 将迭代器分为 5 大类，功能从弱到强依次升级。不同容器默认提供的迭代器类型不同，直接决定了该容器能使用哪些 STL 算法。

迭代器层级流程图

3.1 各类迭代器详解

1. 输入迭代器（Input Iterator）

功能：只读、单向遍历，只能 ++，不能 --，只能读取一次。支持操作：*it、it++、==/!=典型场景：istream_iterator（流输入迭代器）。

2. 输出迭代器（Output Iterator）

功能：只写、单向遍历，只能 ++，不能读取原有值。支持操作：*it = 值、it++典型场景：ostream_iterator、back_inserter。

3. 前向迭代器（Forward Iterator）

继承输入 + 输出迭代器能力，单向可读写，只能向后遍历。支持：++、读写元素、相等判断。对应容器：forward_list（单向链表）、unordered_map/unordered_set。

4. 双向迭代器（Bidirectional Iterator）

在前向迭代器基础上，支持向前 / 向后移动（++ / --）。不支持：下标访问、加减数字（it + n）。对应容器：list（双向链表）、map、set。

5. 随机访问迭代器（Random Access Iterator）

功能最强，完全等价于原生指针。支持所有操作：++/--、it + n / it - n、[]下标、大小比较 < > <= >=。对应容器：vector、string、deque。

容器与迭代器类型对照表

容器	迭代器类型	能否随机访问
vector / string / deque	随机访问迭代器	✅ 支持
list / map / set	双向迭代器	❌ 不支持
forward_list / unordered_xxx	前向迭代器	❌ 不支持

四、C++11 简化写法：auto 与范围 for

4.1 auto 自动推导迭代器类型

不用手写冗长的 容器::iterator：

vector<int> v = {1,2,3};
for (auto it = v.begin(); it != v.end(); ++it) {
    cout << *it << " ";
}

4.2 范围 for 循环（最简洁遍历）

底层本质也是迭代器，编译器自动调用 begin() / end()：

// 只读
for (int x : v) {
    cout << x << " ";
}

// 可修改（引用）
for (int& x : v) {
    x *= 2;
}

五、迭代器失效问题（高频踩坑点）

迭代器失效：容器扩容、增删元素后，原有迭代器变成野指针，再次使用会程序崩溃。不同容器失效规则不同，是面试 + 实战重点。

5.1 vector 迭代器失效

vector 是连续内存，扩容 / 插入 / 删除都会导致失效：

1. 插入元素：空间不足触发扩容 → 整个容器内存重新分配，所有迭代器全部失效。
2. 删除元素：被删除元素之后的所有迭代器失效，前面的保留。

错误示例（崩溃代码）：

vector<int> v = {1,2,3,4};
auto it = v.begin() + 2;
v.insert(v.begin(), 100); // 扩容，it 彻底失效
cout << *it; // 未定义行为，崩溃

解决方案：增删元素后重新获取迭代器。

5.2 list 迭代器失效

list 是链表，内存不连续：

• 删除当前迭代器指向元素：仅当前迭代器失效，其他迭代器完全有效。
• 插入元素：所有迭代器都不失效。

5.3 map /set 迭代器失效

基于红黑树：

• 插入元素：所有迭代器有效。
• 删除元素：仅被删除节点的迭代器失效，其余不变。

六、迭代器配合 STL 算法使用

STL 算法全部依靠迭代器传参，格式统一：算法名(起始迭代器, 结束迭代器, ...)。

示例：

#include <algorithm>
vector<int> v = {5, 2, 9, 1};

// 排序：[begin, end) 左闭右开区间
sort(v.begin(), v.end());

// 查找元素
auto pos = find(v.begin(), v.end(), 9);
if (pos != v.end()) {
    cout << "找到元素：" << *pos << endl;
}

所有算法遵循 左闭右开区间 [begin, end)，这是 STL 统一规范。

七、手写简易迭代器（理解底层原理）

为了彻底弄懂，我们实现一个极简版数组容器 + 自定义迭代器，模拟 STL 底层逻辑：

// 自定义简易容器
template<typename T>
class MyVector {
private:
    T* _data;
    size_t _size;
public:
    // 自定义迭代器（本质就是封装指针）
    class Iterator {
    private:
        T* _ptr;
    public:
        Iterator(T* p) : _ptr(p) {}

        // 解引用
        T& operator*() { return *_ptr; }
        // 前置 ++
        Iterator& operator++() {
            _ptr++;
            return *this;
        }
        // 不等判断
        bool operator!=(const Iterator& other) {
            return _ptr != other._ptr;
        }
    };

    MyVector(T* arr, size_t n) {
        _size = n;
        _data = new T[n];
        for (size_t i = 0; i < n; ++i)
            _data[i] = arr[i];
    }

    ~MyVector() { delete[] _data; }

    Iterator begin() { return Iterator(_data); }
    Iterator end()   { return Iterator(_data + _size); }
};

// 测试
int main() {
    int arr[] = {100, 200, 300};
    MyVector<int> mv(arr, 3);

    for (auto it = mv.begin(); it != mv.end(); ++it) {
        cout << *it << " ";
    }
    return 0;
}

STL 迭代器底层绝大多数就是对原生指针的封装，重载了 *、++、!= 等运算符，对外提供统一访问接口。