★ FEATURED ARTICLE 前言迭代器iterator是 C 标准库把「容器」和「算法」解耦的那层抽象算法只要求迭代器支持某些操作不关心底层是数组、链表还是红黑树。std::find只要求输入迭代器std::reverse要求双向迭代器std::sort要求随机访问迭代器——这三档要求对应三组能力选错容器就会在编译期报错。最常见的误解是「迭代器就是指针」。指针确实满足随机访问迭代器的要求但迭代器是一个更宽的概念std::list的迭代器只能前后移动std::istream_iterator甚至不能保存多个副本同时遍历。另一个误解是「迭代器失效只会发生在erase之后」——vector的push_back一旦触发扩容之前保存的所有迭代器、指针、引用全部失效继续使用是未定义行为。本文先讲迭代器的五类分类与iterator_traits再讲标准算法对迭代器档位的要求然后给出各容器的失效规则表最后手写一个满足前向迭代器要求的自定义迭代器并说明 C20 的 concepts 如何把约束前移到编译期。代码基准为 C17。一、迭代器的五个类别1.1 能力递进标准把迭代器按支持的操作分成五类C20 之前是 tag 类型C20 之后另有 concept 版本类别支持的操作典型来源输入迭代器input*it读、it、单遍扫描std::istream_iterator输出迭代器output*it v写、it、单遍std::back_insert_iterator前向迭代器forward输入能力 可多遍、可保存副本std::forward_list、std::unordered_map双向迭代器bidirectional前向 --itstd::list、std::map、std::set随机访问迭代器random access双向 it n、it[n]、it1 - it2、比较大小std::vector、std::deque、std::stringC20 在此基础上增加了连续迭代器contiguous iterator概念std::contiguous_iterator要求元素在内存中连续存放std::vector、std::array、std::string满足std::deque不满足。能力是单向包含的随机访问迭代器一定满足前向迭代器的要求反之不成立。std::sort只接受随机访问迭代器所以对std::list调用std::sort是编译错误应当用成员函数list.sort()。1.2 iterator_traits算法需要知道迭代器指向的类型但迭代器可能是指针也可能是类。std::iterator_traits负责统一提取五个关联类型关联类型含义value_type元素类型去掉 constdifference_type两个迭代器相减的类型通常为std::ptrdiff_tpointer指向元素的指针类型reference解引用返回的引用类型iterator_category能力类别标签对指针标准库提供了特化所以std::iterator_traitsint*::value_type是int。对自己的迭代器类只要在类内定义这五个类型别名iterator_traits就能正常工作。C17 起继承std::iterator基类的老写法被弃用该基类在 C17 标记为 deprecated应当直接写五个using声明。C20 的 concept 版本不再强制要求这些 typedef但为了兼容 C17 的算法仍然建议写全。1.3 begin/end 与半开区间标准库统一使用半开区间[begin, end)begin指向第一个元素end指向最后一个元素的下一个位置不指向任何实际元素解引用是 UB。// 适用于 C17#include vectorstd::vectorint v{1, 2, 3};auto first v.begin(); // 指向 1auto last v.end(); // 尾后位置不能解引用这种约定的好处是空区间可以自然表示begin end循环条件统一写成it ! end不需要额外判断。cbegin()/cend()返回 const 迭代器rbegin()/rend()返回反向迭代器对 const 容器调用begin()得到的本来就是 const 迭代器。1.4 迭代器辅助函数iterator提供了一组不修改容器、只操作迭代器的工具函数作用复杂度std::advance(it, n)原地前进n步n可为负双向以上随机访问 O(1)否则 O(n)std::next(it, n)返回前进n步后的副本同上std::prev(it, n)返回后退n步后的副本双向以上std::distance(first, last)计算元素个数随机访问 O(1)否则 O(n)std::back_inserter(c)生成尾部插入迭代器每次插入摊还 O(1)std::inserter(c, it)生成指定位置插入迭代器取决于容器std::front_inserter(c)生成头部插入迭代器取决于容器std::distance对输入迭代器是 O(n) 的而且会消耗迭代器如果之后还要用得自己保存副本。对std::list频繁调用std::distance是常见的性能陷阱std::list::size()在 C11 起是 O(1) 的直接用成员函数即可。二、算法对迭代器档位的要求不同的标准算法对迭代器有最低要求选错会在实例化时产生一长串模板错误算法最低要求说明std::find输入迭代器单遍扫描即可std::copy输入 → 输出源和目标可以是不同容器std::fill前向迭代器需要多次写入同一区间std::reverse双向迭代器需要从两端向中间交换std::sort随机访问迭代器需要下标式跳跃和 O(1) 距离std::stable_sort随机访问迭代器稳定版本额外内存std::lower_bound前向迭代器随机访问更快非随机访问时比较次数仍为 O(log n)但移动是 O(n)std::sort不能用于std::list不只是因为「效率低」而是因为list的迭代器不支持it n和it1 - it2模板实例化直接失败。链表排序要用list.sort()它内部做归并排序不需要随机访问。std::lower_bound是个容易误解的例子它在前向迭代器上也能工作但因为std::advance是线性移动总复杂度退化为 O(n)。二分查找的 O(log n) 只在随机访问迭代器上成立。三、迭代器失效规则迭代器失效iterator invalidation指容器修改后之前获得的迭代器不再指向有效元素。继续使用失效迭代器是 UB表现可能是崩溃、读到旧值、或者「看起来正常」。容器操作失效范围std::vectorpush_back触发扩容全部迭代器、指针、引用std::vectorpush_back未扩容仅end()std::vectorinsert/erase插入/删除点及之后std::vectorreserve全部若容量变化std::dequepush_front/push_back全部迭代器引用仍有效std::deque中间insert/erase全部迭代器std::listinsert不失效std::listerase仅被删元素std::map/std::setinsert不失效std::map/std::seterase仅被删元素std::unordered_*insert触发 rehash全部迭代器引用仍有效std::unordered_*erase仅被删元素std::vector的规则可以用一句话概括只要发生了重新分配所有迭代器一起失效没有重新分配时插入点之前的迭代器仍然有效。std::deque的规则更反直觉push_front不会让元素的引用失效但会让所有迭代器失效因为deque的迭代器内部保存了「当前在哪个段」的信息头部插入可能改变段的组织方式。std::unordered_*的 rehash 只影响迭代器指向元素的指针和引用仍然有效因为节点本身没有移动。3.1 erase 循环的正确写法// 适用于 C17for (auto it v.begin(); it ! v.end(); ) {if (*it % 2 0) {it v.erase(it); // erase 返回下一个有效迭代器} else {it;}}不能写成v.erase(it); it;——erase之后it已经失效再自增是 UB。对std::list、std::map同理erase返回被删元素的下一个迭代器C11 起。C20 为多数容器增加了std::erase_if可以直接std::erase_if(v, pred)不必手写循环但需要注意它的支持情况依赖标准库版本。四、自定义迭代器4.1 一个只读的整数区间下面的IntRange表示[0, stop)的整数序列迭代器满足前向迭代器的要求// 适用于 C17#include cstddef#include iteratorclass IntRange {public:class iterator {public:using iterator_category std::forward_iterator_tag;using value_type int;using difference_type std::ptrdiff_t;using pointer const int*;using reference const int;iterator() default;explicit iterator(int v) : value_(v) {}reference operator*() const { return value_; }pointer operator-() const { return value_; }iterator operator() {value_;return *this;}iterator operator(int) {iterator tmp *this;value_;return tmp;}bool operator(const iterator other) const { return value_ other.value_; }bool operator!(const iterator other) const { return !(*this other); }private:int value_ 0;};explicit IntRange(int stop) : stop_(stop) {}iterator begin() const { return iterator(0); }iterator end() const { return iterator(stop_); }private:int stop_;};要点reference写成const intoperator*返回成员的引用。如果按值返回int这个迭代器最多只能算输入迭代器因为前向迭代器要求解引用结果能绑定到引用。operator(int)返回的是自增前的副本所以先拷贝再自增顺序不能反。iterator_category用std::forward_iterator_tag算法据此选择实现。迭代器内部只存一个intbegin()和end()各自构造比较的是值而不是地址因此不同IntRange对象的迭代器也能比较——对本例是合理的但一般容器不应鼓励跨容器比较。4.2 让它和标准算法配合// 适用于 C17#include algorithm#include iostream#include numericint main() {IntRange range(10);auto it std::find(range.begin(), range.end(), 7);if (it ! range.end()) {std::cout *it \n;}int sum std::accumulate(range.begin(), range.end(), 0);std::cout sum \n;return 0;}std::find只要求输入迭代器std::accumulate也只要求输入迭代器所以这个自定义迭代器可以直接使用。若换成std::sort编译会失败因为它需要随机访问能力——这正是迭代器分类的意义把「能力不足」变成编译期错误而不是运行期崩溃。4.3 C20 的约束写法C20 起可以用 concept 直接约束模板参数// 需要 C20#include concepts#include iteratortemplate std::forward_iterator Itstd::size_t count_all(It first, It last) {std::size_t n 0;for (; first ! last; first) n;return n;}std::forward_iterator会检查迭代器是否满足一整套表达式要求。和 C17 的 tag 分派相比错误信息更直接也不再依赖五个 typedef 是否写全。不过各编译器对 concepts 和 ranges 的支持时间不同跨工具链使用前应查对应的支持表。常见坑点❌for (auto it v.begin(); it ! v.end(); it) v.erase(it);✅it v.erase(it);或在 else 分支里自增erase之后原迭代器失效再自增是 UB。❌ 保存vector的迭代器后调用push_back✅ 扩容后重新获取迭代器或改用下标 扩容会重新分配内存所有迭代器、指针、引用一起失效。❌ 对std::list调用std::sort✅ 用list.sort()成员函数std::sort要求随机访问迭代器链表不满足。❌ 解引用end()或对它做--✅ 只在[begin, end)内解引用--end()仅对双向以上合法end()是尾后位置不指向任何元素。❌ 用std::distance反复计算list的长度✅ 用list.size()C11 起 O(1)std::distance对非随机访问迭代器是 O(n)。❌ 认为unordered_maprehash 会让元素的引用失效✅ 记住 rehash 只失效迭代器引用和指针仍有效 节点本身没有移动失效的是迭代器里的桶位置信息。❌ 自定义迭代器时只写operator*和operator✅ 补齐五个关联类型和/!算法通过iterator_traits取类型缺一个就可能实例化失败。❌ 在范围 for 里修改容器结构插入/删除✅ 先收集待删元素循环结束后统一处理 范围 for 内部持有的迭代器会失效。总结主题关键结论分类输入/输出 → 前向 → 双向 → 随机访问能力单向递进traits五个关联类型让算法统一读取迭代器信息区间始终是[begin, end)end不可解引用算法匹配sort要随机访问reverse要双向find只要输入失效vector扩容全失效节点容器只失效被删元素自定义五个 typedef 解引用 自增 比较C20concepts 把能力约束前移到编译期迭代器的本质是「用类型描述能力」容器承诺自己提供哪一档迭代器算法声明自己需要哪一档编译器负责把不匹配的组合拦下来。理解这一点就不会再问「为什么list不能用sort」这类问题而会自然地去看算法的复杂度要求和容器的失效规则。真正需要警惕的是失效规则因为它不会在编译期报错。写任何「遍历中修改容器」的代码之前先查一遍对应容器的失效表比事后靠崩溃堆栈定位要可靠得多。
阅读完成 · 觉得有帮助？
