跳到主要内容

迭代器分类与失效规则总表

迭代器是 STL 的黏合剂。写出通用代码的前提是知道"手上这个迭代器能做什么"，写出安全代码的前提是知道"什么时候它会失效"。

一、五类迭代器​

类别能力典型代表
输入迭代器 Input单遍读、++std::istream_iterator
输出迭代器 Output单遍写、++std::ostream_iterator、back_inserter
前向迭代器 Forward多遍读写、++std::forward_list
双向迭代器 Bidirectional加 --std::list、std::map
随机访问迭代器 RandomAccess加 +=、-、下标std::vector、std::deque、裸指针

C++20 进一步把随机访问拆成"连续迭代器（contiguous）"，vector 的迭代器满足，deque 不满足，因此 vector 的元素可以安全地传给 memcpy。

二、算法对迭代器的要求​

算法最低要求
std::find / count输入迭代器
std::copy输入 + 输出
std::reverse双向
std::sort随机访问
std::stable_sort随机访问
std::nth_element随机访问
std::binary_search前向（实际要求有序，随机访问更高效）

把 list 传给 std::sort 会得到一长串模板报错。正确做法是 lst.sort()，或先拷贝到 vector。

三、各容器失效规则​

容器插入删除备注
vector扩容时全部失效；否则插入点后失效删除点后失效引用、指针同样失效
deque两端插入只失效迭代器，不失效引用中间删除失效全部引用稳定性优于 vector
list不失效任何迭代器仅被删元素失效节点式容器优势
forward_list同上同上只能前向
map/set不失效任何迭代器仅被删元素失效红黑树节点稳定
unordered_map/unordered_setrehash 时全部失效仅被删元素失效引用在 rehash 后仍有效（节点不变）
std::string扩容时全部失效删除点后失效c_str() 同步失效

注意 unordered_map 的微妙之处：rehash 会让迭代器失效，但元素引用与指针仍然有效，因为节点本身没有移动。

四、通用遍历写法​

template <class Container>
void dump(const Container& c) {
    for (typename Container::const_iterator it = c.begin(); it != c.end(); ++it) {
        std::cout << *it << "\n";
    }
}

C++11 以后直接：

template <class Container>
void dump(const Container& c) {
    for (const auto& x : c) std::cout << x << "\n";
}

五、需要"删除当前元素"的通用写法​

C++11 起，顺序容器与关联容器的 erase 都返回下一个迭代器：

for (auto it = c.begin(); it != c.end(); ) {
    if (shouldDrop(*it)) it = c.erase(it);
    else ++it;
}

forward_list 例外：没有 erase(it)，要用 erase_after(it) 或 remove_if。

六、插入迭代器​

#include <iterator>

std::vector<int> dst;
std::copy(src.begin(), src.end(), std::back_inserter(dst));      // push_back
std::copy(src.begin(), src.end(), std::inserter(dst, dst.begin())); // insert
std::copy(src.begin(), src.end(), std::ostream_iterator<int>(std::cout, " ")); // 输出

back_inserter 是"输出迭代器适配器"，让只支持覆盖写入的算法变成追加写入。C++98 里同样可用。

七、反向与常量迭代器​

for (auto it = v.rbegin(); it != v.rend(); ++it) use(*it);

// const 正确性
const std::vector<int>& cv = v;
for (auto it = cv.begin(); it != cv.end(); ++it) use(*it);   // const_iterator

从 iterator 转 const_iterator 是隐式允许的，反向不行。需要显式转换时用 std::next(v.begin(), i) 之外的方式，或 C++11 的 std::make_move_iterator 等适配器。

八、迭代器 vs 下标 vs 指针​

场景推荐
顺序遍历范围 for
需要位置、删除元素迭代器 + erase 返回值
数值索引、密集访问下标（vector 专用）
需要 C 接口data()（C++11 起）
需要跨容器通用迭代器 + 模板

九、调试技巧​

  • 开启调试模式：libstdc++ 用 -D_GLIBCXX_DEBUG，会检查迭代器越界、失效访问；
  • ASan：-fsanitize=address 能抓到访问已释放内存；
  • 不要比较不同容器的迭代器，也不要在 end() 上解引用；
  • 不要保存迭代器跨操作：任何修改容器的操作前，先确认失效规则。

迭代器的复杂度是 C++ 通用性的代价。规则记住了，剩下的就是手感。