STL——迭代器
迭代器（Iterator）简介
迭代器是STL的核心组件，它类似于指针，提供了一种统一的方式来遍历容器中的元素。正是通过迭代器，STL的容器（如vector,list）和算法（如sort,find）得以解耦。算法通过迭代器操作数据，无需知道容器的具体类型。
迭代器类别（Iterator Categories）
为了使不同类型的迭代器能够支持不同的操作，C++ 标准库将迭代器分为以下几种类别，每种类别支持的操作能力逐级增强：
1、输入迭代器（Input Iterator）
2、输出迭代器（Output Iterator）
3、前向迭代器（Forward Iterator）
4、双向迭代器（Bidirectional Iterator）
5、随机访问迭代器（Random Access Iterator）
6、无效迭代器（Contiguous Iterator）（C++20 引入）
每个类别都继承自前一个类别，具备更强的功能。例如，双向迭代器不仅支持前向迭代器的所有操作，还支持反向迭代（即可以向后移动）。
STL迭代器按功能分为五类（从弱到强）：
| 类型 | 支持操作 | 示例容器 |
|---|---|---|
| 输入迭代器 | ++,*(只读，一次) | istream_iterator |
| 输出迭代器 | ++,*(只写，一次) | ostream_iterator |
| 前向迭代器 | ++,*(多次读写) | forward_list |
| 双向迭代器 | ++,--,* | list,map,set |
| 随机访问迭代器 | ++,--,*,+,-,[] | vector,deque,array |
无效迭代器（新） | 随机访问迭代器的所有功能，且元素在内存中连续排列 | 新的 C++ 容器如 |
const_iterator 与安全遍历
cbegin()/cend()返回只读迭代器(const_iterator)。
使用场景：
1、防止意外修改：当只需读取时，使用cbegin/cend相当于编译时保护
2、通用编程：在模板函数中，如果希望始终只读遍历，应使用cbegin()，这样无论传入const或非const容器，行为都一致安全。
std::vector<int> vec = {1, 2, 3}; // 只读遍历，安全 for (auto it = vec.cbegin(); it != vec.cend(); ++it) { // *it = 5; // 错误！不能修改 std::cout << *it; }迭代器失效
这是使用迭代器时最关键的问题之一。某些容器操作会使指向其元素的迭代器失效。
以std::vector为例：
| 操作 | 失效范围 | 原因与示例 |
|---|---|---|
| 尾部插入 | 可能全部失效（若触发重分配） | push_back导致容量不足，重新分配内存。 |
| 中间插入 | 插入点之后的所有迭代器 | insert导致元素后移，原有位置失效。 |
| 删除 | 删除点之后的所有迭代器 | erase导致元素前移。 |
安全操作指南：
插入后：重新获取迭代器（insert会返回指向新元素的迭代器）。
删除时：利用erase的返回值更新迭代器。
std::vector<int> v = {1, 2, 3, 4, 5, 6}; for (auto it = v.begin(); it != v.end(); /* 这里不递增 */) { if (*it % 2 == 0) { it = v.erase(it); // erase 返回下一个有效迭代器 } else { ++it; } }iterator_category的作用
iterator_category是迭代器类型中的一个别名，用于标识该迭代器所属的类别。它是标准库中迭代器特性（Iterator Traits） 的一部分，标准算法会根据迭代器的类别优化其行为。
为什么需要iterator_category
标准库中的算法（如std::sort、std::find等）需要知道迭代器支持哪些操作，以便选择最优的实现方式。例如：
- 对于随机访问迭代器，可以使用快速的随机访问算法（如快速排序）。
- 对于双向迭代器，只能使用适用于双向迭代的算法（如归并排序）。
- 对于输入迭代器，只能进行单次遍历，许多复杂算法无法使用。
通过指定iterator_category，你可以让标准算法了解你自定义迭代器的能力，从而选择合适的方法进行操作。
iterator_category的声明
在你的自定义迭代器类中，通过以下方式声明迭代器类别：
using iterator_category = std::bidirectional_iterator_tag;这表示该迭代器是一个双向迭代器，支持向前和向后遍历。
std::bidirectional_iterator_tag详解
std::bidirectional_iterator_tag是一个标签（Tag），用于标识迭代器类别。C++ 标准库中有多个这样的标签，分别对应不同的迭代器类别：
std::input_iterator_tag
std::output_iterator_tag
std::forward_iterator_tag
std::bidirectional_iterator_tag
std::random_access_iterator_tag
std::contiguous_iterator_tag（C++20）
这些标签本质上是空的结构体，用于类型区分。在标准算法中，通常会通过这些标签进行重载选择（Overload Resolution）或特化（Specialization），以实现针对不同迭代器类别的优化。
继承关系
迭代器标签是有继承关系的：
std::forward_iterator_tag继承自std::input_iterator_tag
std::bidirectional_iterator_tag继承自std::forward_iterator_tag
std::random_access_iterator_tag继承自std::bidirectional_iterator_tag
std::contiguous_iterator_tag继承自std::random_access_iterator_tag
这种继承关系反映了迭代器类别的能力层级。例如，双向迭代器具备前向迭代器的所有能力，加上反向遍历的能力。
迭代器特性（Iterator Traits）详解
C++ 提供了迭代器特性（Iterator Traits），通过模板类std::iterator_traits来获取迭代器的相关信息。通过这些特性，标准算法可以泛化地处理不同类型的迭代器。
迭代器特性包含的信息
std::iterator_traits提供以下信息：
iterator_category：迭代器类别标签。
value_type：迭代器指向的元素类型。
difference_type：迭代器间的距离类型（通常是std::ptrdiff_t）。
pointer：指向元素的指针类型。
reference：对元素的引用类型。
自定义迭代器与iterator_traits
当你定义自己的迭代器时，确保提供这些类型别名，以便标准库算法能够正确识别和使用你的迭代器。例如：
template<typename T> class Iterator { public: using iterator_category = std::bidirectional_iterator_tag; using value_type = T; using difference_type = std::ptrdiff_t; using pointer = T*; using reference = T&; // 其他成员函数... };这样，使用std::iterator_traits<Iterator<T>>时，就能正确获取迭代器的特性。