C++标准模板库（STL）的设计核心之一是将数据容器与通用算法分离，而迭代器正是连接两者的关键抽象。迭代器模式在经典设计模式中被定义为提供一种方法顺序访问聚合对象中的各个元素，而不暴露其内部表示。STL没有照搬面向对象版本的迭代器接口，而是利用模板和运算符重载，让迭代器的行为接近原生指针，同时通过traits机制提供类型信息。这种融合使STL算法可以独立于容器具体类型工作。
迭代器在STL中并非简单的指针包装，而是根据访问能力划分为输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器五个类别。每个容器都会暴露自己的迭代器类型，例如std::vector<int>::iterator属于随机访问迭代器，std::list<int>::iterator属于双向迭代器。这种分类让算法能够通过迭代器类别判断可用的操作，也直接决定了不同容器能配合哪些标准算法。
一、STL迭代器类型体系与容器映射
STL中迭代器类别与容器的对应关系并非随意分配。std::vector和std::deque内部使用连续或分段连续内存，支持通过下标快速定位，因此它们的迭代器具备随机访问能力，能够执行it + n、it - n、it[n]以及比较运算。std::list是双向链表，节点在内存中不连续，无法通过简单加减整数跳转，所以只提供双向迭代器，支持++和--。std::forward_list只支持单向遍历，对应前向迭代器。关联容器std::set、std::map、std::multiset、std::multimap底层为红黑树，遍历时按中序移动，也属于双向迭代器。无序容器std::unordered_map和std::unordered_set底层为哈希表，迭代器实际是前向迭代器，因为桶与链表之间的跳转无法保证双向移动。
这种映射关系带来的直接影响是算法对迭代器类别的要求。例如std::sort要求随机访问迭代器，因为快速排序需要频繁的随机定位和交换。std::list虽然提供了成员函数sort，但传std::sort(list.begin(), list.end())会编译失败或行为未定义，因为list的迭代器不满足随机访问要求。相反，std::find只需要前向迭代器，因此几乎所有标准容器都能使用。理解迭代器类型体系，有助于在需要遍历或修改容器时选择最合适的算法组合。
下面的代码展示了如何通过std::iterator_traits获取迭代器类别，并验证vector与list的差异。
#include <iostream>
#include <vector>
#include <list>
#include <iterator>
template <typename Iterator>
void print_iterator_category(Iterator it) {
typename std::iterator_traits<Iterator>::iterator_category category;
if (typeid(category) == typeid(std::random_access_iterator_tag)) {
std::cout << "random access iterator\n";
} else if (typeid(category) == typeid(std::bidirectional_iterator_tag)) {
std::cout << "bidirectional iterator\n";
} else if (typeid(category) == typeid(std::forward_iterator_tag)) {
std::cout << "forward iterator\n";
} else {
std::cout << "other iterator\n";
}
}
int main() {
std::vector<int> v{1,2,3};
std::list<int> l{1,2,3};
print_iterator_category(v.begin());
print_iterator_category(l.begin());
return 0;
}
运行结果会显示vector对应random access iterator，list对应bidirectional iterator。这个类别信息在泛型编程中非常重要，算法可以通过编译器分派选择不同实现，而无需关心具体容器类型。
二、迭代器失效规则与容器操作
使用迭代器遍历容器时，最容易被忽略的问题是迭代器失效。不同容器在插入或删除元素后，原有迭代器可能不再指向合法位置，继续使用会导致未定义行为。std::vector在push_back触发扩容时，所有指向原存储空间的迭代器、指针和引用都会失效，因为内存被整体搬迁。即使不发生扩容，向中间位置insert或erase也会使插入点之后的所有迭代器失效，因为元素位置发生了移动。
std::list在插入元素后原有迭代器不会失效，删除元素时只有指向被删元素的迭代器失效，其他迭代器依然有效。std::deque在两端插入时指针和引用可能失效，但迭代器不一定失效；在中间插入则会失效所有迭代器。关联容器在插入后迭代器不失效，删除时只有被删元素的迭代器失效。这些规则直接源于底层存储结构，编写容器操作代码时必须遵守。
以下示例演示了vector删除元素时常见的迭代器错误用法与正确用法。
#include <iostream>
#include <vector>
int main() {
std::vector<int> v{1,2,3,4,5};
// 错误：erase后迭代器已失效，执行++可能越界
for (auto it = v.begin(); it != v.end(); ++it) {
if (*it == 3) {
v.erase(it); // it失效，++it未定义
}
}
// 正确：利用erase返回下一个有效迭代器
std::vector<int> v2{1,2,3,4,5};
for (auto it = v2.begin(); it != v2.end(); ) {
if (*it == 3) {
it = v2.erase(it);
} else {
++it;
}
}
for (int x : v2) {
std::cout << x << ' ';
}
std::cout << '\n';
return 0;
}
对于std::list，由于删除元素只会使被删迭代器失效，可以提前保存下一个迭代器再删除。但为了兼容所有容器，推荐统一使用erase返回迭代器的方式更新循环变量。当需要大量删除元素时，还可以考虑std::remove_if配合lambda表达式，再调用成员erase范围删除，这样既能避免逐个失效判断，也能减少移动次数。
另外，reserve可以提前预留容量，避免vector因扩容导致迭代器失效。如果在遍历过程中必须动态插入元素，应优先使用list或deque，或者先收集待插入数据，遍历结束后再统一插入。
三、自定义容器如何实现STL兼容迭代器
要让自定义容器能够直接使用std::find、std::copy、std::sort等标准算法，关键是为容器实现符合STL要求的迭代器类型。迭代器类需要提供五个关键typedef：iterator_category、value_type、difference_type、pointer和reference。对于随机访问迭代器，还需要实现构造函数、拷贝赋值、解引用operator*、箭头operator->、前/后置++、前/后置--、加减整数、比较运算符，以及下标运算。
下面实现一个简化的动态数组容器SimpleVec，内部使用裸指针管理内存，并定义随机访问迭代器。通过嵌套iterator类暴露上述typedef，使std::iterator_traits能够正确识别其类别。
#include <iostream>
#include <algorithm>
#include <cstddef>
template <typename T>
class SimpleVec {
T* data_ = nullptr;
size_t size_ = 0;
public:
SimpleVec() = default;
explicit SimpleVec(std::initializer_list<T> init) {
data_ = new T[init.size()];
for (auto& val : init) data_[size_++] = val;
}
~SimpleVec() { delete[] data_; }
SimpleVec(const SimpleVec&) = delete;
SimpleVec& operator=(const SimpleVec&) = delete;
class iterator {
T* ptr_;
public:
using iterator_category = std::random_access_iterator_tag;
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;
explicit iterator(T* p = nullptr) : ptr_(p) {}
T& operator*() const { return *ptr_; }
T* operator->() const { return ptr_; }
iterator& operator++() { ++ptr_; return *this; }
iterator operator++(int) { iterator tmp = *this; ++ptr_; return tmp; }
iterator& operator--() { --ptr_; return *this; }
iterator operator--(int) { iterator tmp = *this; --ptr_; return tmp; }
iterator& operator+=(difference_type n) { ptr_ += n; return *this; }
iterator operator+(difference_type n) const { return iterator(ptr_ + n); }
iterator operator-(difference_type n) const { return iterator(ptr_ - n); }
difference_type operator-(const iterator& other) const { return ptr_ - other.ptr_; }
T& operator[](difference_type n) const { return ptr_[n]; }
bool operator==(const iterator& other) const { return ptr_ == other.ptr_; }
bool operator!=(const iterator& other) const { return ptr_ != other.ptr_; }
bool operator<(const iterator& other) const { return ptr_ < other.ptr_; }
bool operator<=(const iterator& other) const { return ptr_ <= other.ptr_; }
bool operator>(const iterator& other) const { return ptr_ > other.ptr_; }
bool operator>=(const iterator& other) const { return ptr_ >= other.ptr_; }
};
iterator begin() { return iterator(data_); }
iterator end() { return iterator(data_ + size_); }
size_t size() const { return size_; }
T& operator[](size_t i) { return data_[i]; }
};
int main() {
SimpleVec<int> sv{5, 1, 4, 2, 3};
std::sort(sv.begin(), sv.end());
for (auto it = sv.begin(); it != sv.end(); ++it) {
std::cout << *it << ' ';
}
std::cout << '\n';
return 0;
}
以上迭代器通过内部指针运算获得了随机访问能力，std::sort识别到iterator_category为random_access_iterator_tag后，会启用快速排序实现。如果希望实现双向迭代器，可以把iterator_category改为bidirectional_iterator_tag，并去掉加减整数、下标比较等运算符。对于前向迭代器，进一步去掉--操作即可。
自定义迭代器时还要注意类型推导：建议在迭代器类内部直接定义五个typedef，而不是依赖std::iterator基类，因为C++17起std::iterator已被弃用。同时，如果需要支持const迭代器，可以额外定义const_iterator类，或者通过模板参数控制引用类型。完整的随机访问迭代器还应提供friend operator+和operator-的全局重载，以便it + n和n + it两种写法都成立。