前言迭代器失效Iterator Invalidation是 C 里最阴的一类 bug—— 它往往不崩溃而是读到垃圾数据或者偶尔崩溃换个编译选项、换个数据量就复现不了。根源在于迭代器本质是一个指针或指针的封装。当容器重新分配内存、移动元素时原来的迭代器就指向了不该指的地方。本文把各容器的失效规则讲清楚并说清为什么会失效—— 理解了底层结构就不用死记硬背。一、什么是迭代器失效std::vectorint v {1, 2, 3, 4, 5}; auto it v.begin(); // 指向 v[0] v.push_back(6); // 可能触发扩容重新分配内存 std::cout *it; // ❌ it 指向已释放的内存 → 未定义行为迭代器失效 迭代器不再指向它原本指向的元素甚至指向已释放的内存。标准对失效迭代器的定义是任何使用包括解引用、递增、比较都是未定义行为不只是解引用。二、各类容器失效规则总表容器操作迭代器引用/指针vectorpush_back/insert触发扩容全部失效全部失效push_back未扩容全部失效*未失效insert未扩容插入点及之后失效插入点及之后失效erase删除点及之后失效删除点及之后失效resize/reserve/shrink_to_fit可能全部失效可能全部失效dequepush_front/push_back全部失效未失效⚠️insert/erase中间全部失效全部失效pop_front/pop_back全部失效除被删的未失效listinsert未失效未失效erase仅被删元素的失效仅被删的失效map / set / multimap / multisetinsert未失效未失效erase仅被删元素的失效仅被删的失效unordered_map / unordered_setinsert触发 rehash全部失效未失效⚠️insert未 rehash未失效未失效erase仅被删元素的失效仅被删的失效rehash/reserve全部失效未失效\*标准对vector::push_back未扩容时的迭代器状态没有明确规定视为可能全部失效。libstdc 实践中end()会失效前面的迭代器通常有效但不要依赖。⚠️ 标红的两种情况和直觉相反deque和unordered_*在特定操作下迭代器失效但引用/指针仍有效。原理在第五、六节解释。三、vector为什么会全部失效3.1 根本原因连续内存vector的元素存在一块连续的堆内存上begin() end() ↓ ↓ [ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ ][ ] capacity 7 ↑ size() 5迭代器就是指向这块内存的裸指针。3.2 扩容时发生了什么push_back时如果size() capacity()就需要扩容// libstdc 的扩容逻辑简化 size_type _M_check_len(size_type n) const { const size_type max_size this-max_size(); const size_type len this-size(); if (max_size - len n) throw ...; const size_type new_len len std::max(len, n); // ★ 翻倍 return std::min(new_len, max_size); }实际过程在堆上申请一块更大的内存通常是原来的 2 倍把所有元素拷贝/移动过去释放原来那块内存← 关键释放后所有指向旧内存的指针/迭代器全部悬垂扩容前 it ── [ 1 ][ 2 ][ 3 ] 旧内存 扩容后 [ 1 ][ 2 ][ 3 ][ ][ ][ ] 新内存 it ── ✗还指向已释放的旧内存3.3erase为什么只影响删除点及之后std::vectorint v {1, 2, 3, 4, 5}; auto it v.begin() 3; // 指向 4 v.erase(v.begin() 1); // 删除 2 // 内部把 [3,4,5] 整体前移一位 → {1, 3, 4, 5} // it 原来指向下标 3 的 4现在下标 3 是 5 // it 没有悬垂但指向的东西变了这就是读到垃圾数据却不崩溃的典型场景—— 迭代器还指在合法内存里但内容已经不是原来那个了。3.4 正确的删除写法// ❌ 经典错误erase 后继续用旧迭代器 for (auto it v.begin(); it ! v.end(); it) { if (*it % 2 0) v.erase(it); // it 已失效it 是 UB } // ✅ 正确用 erase 的返回值 for (auto it v.begin(); it ! v.end(); ) { if (*it % 2 0) it v.erase(it); // erase 返回下一个有效位置 else it; } // ✅ 更简洁C20 std::erase_if std::erase_if(v, [](int x) { return x % 2 0; });3.5 扩容后的正确做法std::vectorint v; v.reserve(1000); // ★ 提前 reserve避免中途扩容 for (int i 0; i 1000; i) v.push_back(i); // 全程不会扩容迭代器/引用始终有效这也是reserve除了性能之外的第二个价值保证迭代器稳定性。四、list / map / set为什么只有被删的失效因为它们是基于节点的容器node-based。list: head → [A] ⇄ [B] ⇄ [C] ⇄ [D] ↑ 节点各自独立分配在堆上 map/set: 每个元素是一个独立的红黑树节点插入新分配一个节点改几个指针已有节点纹丝不动→ 迭代器全部有效。删除只释放被删节点其他节点不受影响→ 只有被删节点的迭代器失效。std::listint lst {1, 2, 3, 4, 5}; auto it std::next(lst.begin(), 2); // 指向 3 lst.push_front(0); // 插入 std::cout *it; // ✅ 仍是 3 lst.erase(lst.begin()); // 删除别的元素 std::cout *it; // ✅ 仍是 3 lst.erase(it); // 删除 it 自己 // 此时 it 才失效这就是为什么边遍历边删除在list上是安全的for (auto it lst.begin(); it ! lst.end(); ) { if (*it % 2 0) it lst.erase(it); // 安全 else it; }⚠️ 但vector上同样的代码是危险的第三节 3.4因为erase会移动后续元素。五、deque最反直觉的一个deque是分段连续的中控数组map: [ ptr0 ][ ptr1 ][ ptr2 ][ ptr3 ] ↓ ↓ ↓ ↓ [缓冲区0][缓冲区1][缓冲区2][缓冲区3] 每段固定大小、连续deque的迭代器不是裸指针而是一个包含 4 个字段的结构template typename T struct _Deque_iterator { T* _M_cur; // 当前元素 T* _M_first; // 当前缓冲区的头 T* _M_last; // 当前缓冲区的尾 T** _M_node; // 指向中控数组中的位置 };为什么push_front/push_back让所有迭代器失效但引用仍然有效引用/指针deque插入时不移动已有元素不是 vector 那种整体搬家只是可能在两端新增缓冲区或者扩展中控数组。元素本身还在原地所以引用有效。迭代器迭代器内部存了_M_first和_M_last缓冲区的边界。当中控数组重新分配时所有迭代器的_M_node指向的位置都变了即使中控数组没变迭代器里的边界信息也可能过期。所以标准规定迭代器全部失效。这是最容易被误用的地方std::dequeint dq {1, 2, 3}; int ref dq[1]; // 引用元素 2 auto it dq.begin() 1; // 迭代器指向元素 2 dq.push_front(0); std::cout ref; // ✅ 有效仍是 2 std::cout *it; // ❌ 迭代器已失效实践建议需要长期持有位置时deque上用索引而不是迭代器。六、unordered_*rehash 的双重性unordered_map/unordered_set也是节点式容器桶里挂的是链表元素节点各自独立分配。为什么 rehash 后迭代器失效、引用有效rehash 做的事申请一个更大的桶数组遍历所有元素重新计算桶下标把节点重新链接到新桶里释放旧的桶数组关键元素节点本身没有被移动或重新分配只是链表的指针变了。rehash 前 buckets[0] → [A] → [C] buckets[1] → [B] rehash 后 buckets[0] → [A] buckets[1] → [B] buckets[2] → [C] ↑ 节点 A、B、C 的地址完全没变所以迭代器失效因为迭代器记录了在哪个桶、桶里什么位置桶结构全变了引用/指针有效因为节点地址没变std::unordered_mapstd::string, int m; m[a] 1; auto ref m[a]; // 引用 auto it m.find(a); // 迭代器 m.reserve(1000); // 触发 rehash ref 42; // ✅ 有效 std::cout it-second; // ❌ 迭代器已失效这是标准明确保证的行为也是unordered_map相对map唯一不落下风的稳定性保证。七、检测工具迭代器失效是 UB编译器默认不会报错。但三大标准库都提供了调试模式7.1 GCC / libstdcg -D_GLIBCXX_DEBUG -g main.cpp -o main启用后迭代器会被替换成带容器指针的检查版越界或跨容器访问会直接报错/usr/include/c/13/debug/vector:442: In function: std::debug::vector_Tp, _Allocator::operator[] Error: attempt to subscript container with out-of-bounds index 5, but container only holds 3 elements.⚠️注意_GLIBCXX_DEBUG会改变 ABI不能和未启用该宏编译的目标文件混链。7.2 MSVC// 项目属性 → C/C → 预处理器 → 添加 _ITERATOR_DEBUG_LEVEL2或在代码里必须在包含任何 STL 头文件之前#define _ITERATOR_DEBUG_LEVEL 2 #include vectorDebug 模式下 MSVC 默认就是 2会出现这类断言_DEBUG_ERROR(vector iterators incompatible);⚠️ 混用不同_ITERATOR_DEBUG_LEVEL编译的库会导致链接错误这也是 MSVC 上Debug 能跑 Release 崩的常见原因。7.3 Clang / libcclang -D_LIBCPP_HARDENING_MODE_LIBCPP_HARDENING_MODE_DEBUG main.cpp旧版用-D_LIBCPP_DEBUG17.4建议在 CI 里跑一遍调试模式# CI 配置示意 - name: Debug 模式测试 run: g -D_GLIBCXX_DEBUG -g -fsanitizeaddress,undefined test.cpp-fsanitizeaddress和-D_GLIBCXX_DEBUG搭配使用基本能覆盖绝大多数迭代器失效和越界问题。八、实战案例案例 1扩容导致的悬垂// ❌ 崩溃 std::vectorint v; int first v[0]; // 还没元素本身就是 UB v.push_back(1); int r v[0]; for (int i 0; i 1000; i) v.push_back(i); // 多次扩容 r 5; // ❌ r 指向已释放内存修复先reserve或用索引代替引用。案例 2erase 后继续遍历// ❌ 经典错误 std::vectorint v{1,2,3,4,5,6}; for (auto it v.begin(); it ! v.end(); it) { if (*it % 2 0) v.erase(it); }修复用it v.erase(it)不。案例 3在范围 for 里修改容器// ❌ 范围 for 内部的迭代器是隐式的你不知道它什么时候失效 std::vectorint v{1,2,3,4,5}; for (int x : v) { if (x 3) v.push_back(99); // 扩容 → 范围 for 的迭代器失效 }修复不要在遍历中修改容器大小或者用索引遍历并提前 reserve。案例 4跨容器使用迭代器std::vectorint a{1,2,3}, b{4,5,6}; auto it a.begin(); // ❌ 比较来自不同容器的迭代器是 UB if (it b.begin()) { }即使是 Debug 模式也可能查不出来Release 下迭代器就是裸指针地址不同自然不等。启用_GLIBCXX_DEBUG后会报 iterators from different containers。案例 5保存end()的值std::vectorint v{1,2,3}; auto e v.end(); v.push_back(4); // 扩容 if (e ! v.end()) { } // ❌ e 已失效规则不要缓存end()每次重新调用。九、避坑清单场景做法已知元素数量提前reserve一举解决性能和失效两个问题遍历中删除it c.erase(it)不要it遍历中插入用索引遍历或改用std::list/ 节点式容器需要长期持有位置用索引不要用迭代器需要长期持有元素如果是deque/unordered_*用引用/指针插入时更稳定缓存end()不要每次重取跨容器比较永远不要CI 检测-D_GLIBCXX_DEBUG -fsanitizeaddress,undefined十、总结记住底层结构就不用背规则结构插入时元素会移动吗失效范围连续内存vector会扩容 / 中间插入大范围失效分段连续deque两端不会中间会迭代器全失效引用不失效节点式list/map/set不会只有被删的失效节点式 桶unordered_*节点不动桶结构会变rehash 时迭代器全失效引用不失效三条最实用的结论vector上用reserve—— 既是性能优化也是迭代器稳定性保障。遍历中删除永远用it c.erase(it)的模式。需要长期持有的位置在vector上用索引、在deque/unordered_*上用引用。迭代器失效之所以危险是因为它大多数时候不报错。开发阶段就开着调试模式比事后排查崩溃便宜得多。本文规则依据 C17/20 标准实测环境 GCC 13 / MSVC 19.38 / Clang 17。如果帮到你欢迎点赞收藏。 C++中迭代器失效的实现
前言迭代器失效Iterator Invalidation是 C 里最阴的一类 bug—— 它往往不崩溃而是读到垃圾数据或者偶尔崩溃换个编译选项、换个数据量就复现不了。根源在于迭代器本质是一个指针或指针的封装。当容器重新分配内存、移动元素时原来的迭代器就指向了不该指的地方。本文把各容器的失效规则讲清楚并说清为什么会失效—— 理解了底层结构就不用死记硬背。一、什么是迭代器失效std::vectorint v {1, 2, 3, 4, 5}; auto it v.begin(); // 指向 v[0] v.push_back(6); // 可能触发扩容重新分配内存 std::cout *it; // ❌ it 指向已释放的内存 → 未定义行为迭代器失效 迭代器不再指向它原本指向的元素甚至指向已释放的内存。标准对失效迭代器的定义是任何使用包括解引用、递增、比较都是未定义行为不只是解引用。二、各类容器失效规则总表容器操作迭代器引用/指针vectorpush_back/insert触发扩容全部失效全部失效push_back未扩容全部失效*未失效insert未扩容插入点及之后失效插入点及之后失效erase删除点及之后失效删除点及之后失效resize/reserve/shrink_to_fit可能全部失效可能全部失效dequepush_front/push_back全部失效未失效⚠️insert/erase中间全部失效全部失效pop_front/pop_back全部失效除被删的未失效listinsert未失效未失效erase仅被删元素的失效仅被删的失效map / set / multimap / multisetinsert未失效未失效erase仅被删元素的失效仅被删的失效unordered_map / unordered_setinsert触发 rehash全部失效未失效⚠️insert未 rehash未失效未失效erase仅被删元素的失效仅被删的失效rehash/reserve全部失效未失效\*标准对vector::push_back未扩容时的迭代器状态没有明确规定视为可能全部失效。libstdc 实践中end()会失效前面的迭代器通常有效但不要依赖。⚠️ 标红的两种情况和直觉相反deque和unordered_*在特定操作下迭代器失效但引用/指针仍有效。原理在第五、六节解释。三、vector为什么会全部失效3.1 根本原因连续内存vector的元素存在一块连续的堆内存上begin() end() ↓ ↓ [ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ ][ ] capacity 7 ↑ size() 5迭代器就是指向这块内存的裸指针。3.2 扩容时发生了什么push_back时如果size() capacity()就需要扩容// libstdc 的扩容逻辑简化 size_type _M_check_len(size_type n) const { const size_type max_size this-max_size(); const size_type len this-size(); if (max_size - len n) throw ...; const size_type new_len len std::max(len, n); // ★ 翻倍 return std::min(new_len, max_size); }实际过程在堆上申请一块更大的内存通常是原来的 2 倍把所有元素拷贝/移动过去释放原来那块内存← 关键释放后所有指向旧内存的指针/迭代器全部悬垂扩容前 it ── [ 1 ][ 2 ][ 3 ] 旧内存 扩容后 [ 1 ][ 2 ][ 3 ][ ][ ][ ] 新内存 it ── ✗还指向已释放的旧内存3.3erase为什么只影响删除点及之后std::vectorint v {1, 2, 3, 4, 5}; auto it v.begin() 3; // 指向 4 v.erase(v.begin() 1); // 删除 2 // 内部把 [3,4,5] 整体前移一位 → {1, 3, 4, 5} // it 原来指向下标 3 的 4现在下标 3 是 5 // it 没有悬垂但指向的东西变了这就是读到垃圾数据却不崩溃的典型场景—— 迭代器还指在合法内存里但内容已经不是原来那个了。3.4 正确的删除写法// ❌ 经典错误erase 后继续用旧迭代器 for (auto it v.begin(); it ! v.end(); it) { if (*it % 2 0) v.erase(it); // it 已失效it 是 UB } // ✅ 正确用 erase 的返回值 for (auto it v.begin(); it ! v.end(); ) { if (*it % 2 0) it v.erase(it); // erase 返回下一个有效位置 else it; } // ✅ 更简洁C20 std::erase_if std::erase_if(v, [](int x) { return x % 2 0; });3.5 扩容后的正确做法std::vectorint v; v.reserve(1000); // ★ 提前 reserve避免中途扩容 for (int i 0; i 1000; i) v.push_back(i); // 全程不会扩容迭代器/引用始终有效这也是reserve除了性能之外的第二个价值保证迭代器稳定性。四、list / map / set为什么只有被删的失效因为它们是基于节点的容器node-based。list: head → [A] ⇄ [B] ⇄ [C] ⇄ [D] ↑ 节点各自独立分配在堆上 map/set: 每个元素是一个独立的红黑树节点插入新分配一个节点改几个指针已有节点纹丝不动→ 迭代器全部有效。删除只释放被删节点其他节点不受影响→ 只有被删节点的迭代器失效。std::listint lst {1, 2, 3, 4, 5}; auto it std::next(lst.begin(), 2); // 指向 3 lst.push_front(0); // 插入 std::cout *it; // ✅ 仍是 3 lst.erase(lst.begin()); // 删除别的元素 std::cout *it; // ✅ 仍是 3 lst.erase(it); // 删除 it 自己 // 此时 it 才失效这就是为什么边遍历边删除在list上是安全的for (auto it lst.begin(); it ! lst.end(); ) { if (*it % 2 0) it lst.erase(it); // 安全 else it; }⚠️ 但vector上同样的代码是危险的第三节 3.4因为erase会移动后续元素。五、deque最反直觉的一个deque是分段连续的中控数组map: [ ptr0 ][ ptr1 ][ ptr2 ][ ptr3 ] ↓ ↓ ↓ ↓ [缓冲区0][缓冲区1][缓冲区2][缓冲区3] 每段固定大小、连续deque的迭代器不是裸指针而是一个包含 4 个字段的结构template typename T struct _Deque_iterator { T* _M_cur; // 当前元素 T* _M_first; // 当前缓冲区的头 T* _M_last; // 当前缓冲区的尾 T** _M_node; // 指向中控数组中的位置 };为什么push_front/push_back让所有迭代器失效但引用仍然有效引用/指针deque插入时不移动已有元素不是 vector 那种整体搬家只是可能在两端新增缓冲区或者扩展中控数组。元素本身还在原地所以引用有效。迭代器迭代器内部存了_M_first和_M_last缓冲区的边界。当中控数组重新分配时所有迭代器的_M_node指向的位置都变了即使中控数组没变迭代器里的边界信息也可能过期。所以标准规定迭代器全部失效。这是最容易被误用的地方std::dequeint dq {1, 2, 3}; int ref dq[1]; // 引用元素 2 auto it dq.begin() 1; // 迭代器指向元素 2 dq.push_front(0); std::cout ref; // ✅ 有效仍是 2 std::cout *it; // ❌ 迭代器已失效实践建议需要长期持有位置时deque上用索引而不是迭代器。六、unordered_*rehash 的双重性unordered_map/unordered_set也是节点式容器桶里挂的是链表元素节点各自独立分配。为什么 rehash 后迭代器失效、引用有效rehash 做的事申请一个更大的桶数组遍历所有元素重新计算桶下标把节点重新链接到新桶里释放旧的桶数组关键元素节点本身没有被移动或重新分配只是链表的指针变了。rehash 前 buckets[0] → [A] → [C] buckets[1] → [B] rehash 后 buckets[0] → [A] buckets[1] → [B] buckets[2] → [C] ↑ 节点 A、B、C 的地址完全没变所以迭代器失效因为迭代器记录了在哪个桶、桶里什么位置桶结构全变了引用/指针有效因为节点地址没变std::unordered_mapstd::string, int m; m[a] 1; auto ref m[a]; // 引用 auto it m.find(a); // 迭代器 m.reserve(1000); // 触发 rehash ref 42; // ✅ 有效 std::cout it-second; // ❌ 迭代器已失效这是标准明确保证的行为也是unordered_map相对map唯一不落下风的稳定性保证。七、检测工具迭代器失效是 UB编译器默认不会报错。但三大标准库都提供了调试模式7.1 GCC / libstdcg -D_GLIBCXX_DEBUG -g main.cpp -o main启用后迭代器会被替换成带容器指针的检查版越界或跨容器访问会直接报错/usr/include/c/13/debug/vector:442: In function: std::debug::vector_Tp, _Allocator::operator[] Error: attempt to subscript container with out-of-bounds index 5, but container only holds 3 elements.⚠️注意_GLIBCXX_DEBUG会改变 ABI不能和未启用该宏编译的目标文件混链。7.2 MSVC// 项目属性 → C/C → 预处理器 → 添加 _ITERATOR_DEBUG_LEVEL2或在代码里必须在包含任何 STL 头文件之前#define _ITERATOR_DEBUG_LEVEL 2 #include vectorDebug 模式下 MSVC 默认就是 2会出现这类断言_DEBUG_ERROR(vector iterators incompatible);⚠️ 混用不同_ITERATOR_DEBUG_LEVEL编译的库会导致链接错误这也是 MSVC 上Debug 能跑 Release 崩的常见原因。7.3 Clang / libcclang -D_LIBCPP_HARDENING_MODE_LIBCPP_HARDENING_MODE_DEBUG main.cpp旧版用-D_LIBCPP_DEBUG17.4建议在 CI 里跑一遍调试模式# CI 配置示意 - name: Debug 模式测试 run: g -D_GLIBCXX_DEBUG -g -fsanitizeaddress,undefined test.cpp-fsanitizeaddress和-D_GLIBCXX_DEBUG搭配使用基本能覆盖绝大多数迭代器失效和越界问题。八、实战案例案例 1扩容导致的悬垂// ❌ 崩溃 std::vectorint v; int first v[0]; // 还没元素本身就是 UB v.push_back(1); int r v[0]; for (int i 0; i 1000; i) v.push_back(i); // 多次扩容 r 5; // ❌ r 指向已释放内存修复先reserve或用索引代替引用。案例 2erase 后继续遍历// ❌ 经典错误 std::vectorint v{1,2,3,4,5,6}; for (auto it v.begin(); it ! v.end(); it) { if (*it % 2 0) v.erase(it); }修复用it v.erase(it)不。案例 3在范围 for 里修改容器// ❌ 范围 for 内部的迭代器是隐式的你不知道它什么时候失效 std::vectorint v{1,2,3,4,5}; for (int x : v) { if (x 3) v.push_back(99); // 扩容 → 范围 for 的迭代器失效 }修复不要在遍历中修改容器大小或者用索引遍历并提前 reserve。案例 4跨容器使用迭代器std::vectorint a{1,2,3}, b{4,5,6}; auto it a.begin(); // ❌ 比较来自不同容器的迭代器是 UB if (it b.begin()) { }即使是 Debug 模式也可能查不出来Release 下迭代器就是裸指针地址不同自然不等。启用_GLIBCXX_DEBUG后会报 iterators from different containers。案例 5保存end()的值std::vectorint v{1,2,3}; auto e v.end(); v.push_back(4); // 扩容 if (e ! v.end()) { } // ❌ e 已失效规则不要缓存end()每次重新调用。九、避坑清单场景做法已知元素数量提前reserve一举解决性能和失效两个问题遍历中删除it c.erase(it)不要it遍历中插入用索引遍历或改用std::list/ 节点式容器需要长期持有位置用索引不要用迭代器需要长期持有元素如果是deque/unordered_*用引用/指针插入时更稳定缓存end()不要每次重取跨容器比较永远不要CI 检测-D_GLIBCXX_DEBUG -fsanitizeaddress,undefined十、总结记住底层结构就不用背规则结构插入时元素会移动吗失效范围连续内存vector会扩容 / 中间插入大范围失效分段连续deque两端不会中间会迭代器全失效引用不失效节点式list/map/set不会只有被删的失效节点式 桶unordered_*节点不动桶结构会变rehash 时迭代器全失效引用不失效三条最实用的结论vector上用reserve—— 既是性能优化也是迭代器稳定性保障。遍历中删除永远用it c.erase(it)的模式。需要长期持有的位置在vector上用索引、在deque/unordered_*上用引用。迭代器失效之所以危险是因为它大多数时候不报错。开发阶段就开着调试模式比事后排查崩溃便宜得多。本文规则依据 C17/20 标准实测环境 GCC 13 / MSVC 19.38 / Clang 17。如果帮到你欢迎点赞收藏。