一、什么叫迭代器失效先看一个简单的std::vectorint nums {10, 20, 30}; auto it nums.begin(); std::cout *it std::endl;此时it ↓ ┌────┬────┬────┐ │ 10 │ 20 │ 30 │ └────┴────┴────┘it保存的是一个能够定位到nums中第一个元素的位置。但是如果容器发生变化nums.push_back(40);并且这次push_back()触发了扩容那么 vector 会申请新内存 ↓ 把10、20、30搬到新内存 ↓ 插入40 ↓ 释放旧内存例如原来0x1000 ┌────┬────┬────┐ │ 10 │ 20 │ 30 │ └────┴────┴────┘扩容后0x5000 ┌────┬────┬────┬────┬────┬────┐ │ 10 │ 20 │ 30 │ 40 │ │ │ └────┴────┴────┴────┴────┴────┘但是原来的it可能还指向0x1000而原来的内存已经释放。这时再std::cout *it std::endl;就是未定义行为这就是迭代器失效 Iterator Invalidation它本质上就是容器修改以后原来迭代器所依赖的元素位置、节点或者底层内存已经发生变化继续使用旧迭代器不再安全。除了迭代器pointer reference也可能一起失效。例如int *p nums[0]; int ref nums[1]; nums.push_back(40);如果发生扩容iterator pointer reference都可能失效。二、vector为什么最容易出现迭代器失效vector底层使用连续内存因此有两类特别常见的失效问题。1. 扩容导致全部失效例如std::vectorint nums {1, 2, 3}; auto it nums.begin(); nums.push_back(4); std::cout *it std::endl;如果size capacity那么push_back()需要重新分配内存。于是原来的所有迭代器 所有指针 所有引用都会失效。所以如果提前知道元素数量可以std::vectorint nums; nums.reserve(1000);提前准备容量。然后for (int i 0; i 1000; i) { nums.push_back(i); }只要没有超过已经预留的容量就不会因为扩容反复搬迁底层数组所以reserve()是减少 vector 扩容型迭代器失效的一种重要方法。但要注意reserve()只能减少因为重新分配内存造成的失效并不能解决所有 vector 迭代器失效问题。2. erase导致当前位置以及后面的迭代器失效例如std::vectorint nums {10, 20, 30, 40}; auto it nums.begin() 1; nums.erase(it);原来10 20 30 40 ↑ it删除 20 后10 30 40因为30和40需要向前移动所以被删除位置以及后面的迭代器都会失效。因此下面这种写法是危险的for (auto it nums.begin(); it ! nums.end(); it) { if (*it 20) { nums.erase(it); } }问题在于nums.erase(it);之后it已经失效但是循环后面还执行it相当于继续操作一个已经失效的迭代器。正确写法for (auto it nums.begin(); it ! nums.end(); ) { if (*it 20) { it nums.erase(it); } else { it; } }为什么因为erase(it)会返回被删除元素后面的下一个有效迭代器例如10 20 30 40 ↑ it erase(it) ↓ 10 30 40 ↑ 返回新的it所以这是删除元素时非常重要的写法it container.erase(it);三、不同STL容器的失效规则并不一样不是所有 STL 容器都和 vector 一样。1. vectorvector连续内存所以比较容易因为元素搬迁导致失效。常见情况重新分配内存 ↓ 全部迭代器、引用、指针失效而erase ↓ 删除位置以及之后的迭代器失效2. liststd::list底层通常是双向链表例如Node1 ↔ Node2 ↔ Node3 ↔ Node4每个节点相对独立。所以插入一个节点Node1 ↔ Node2 ↔ New ↔ Node3通常不会移动其他节点。因此insert ↓ 原来的其他迭代器通常仍然有效删除erase(Node2)也通常只会使指向Node2的迭代器失效其他节点Node1 Node3 Node4没有搬家。所以其他迭代器通常仍然有效。这也是链式容器的重要特点。3. map / setmap、set通常是树结构插入新元素时通常不会使已有元素的迭代器失效删除某个元素时只有指向被删除元素的迭代器失效所以for (auto it m.begin(); it ! m.end(); ) { if (it-second 0) { it m.erase(it); } else { it; } }同样是比较安全的删除写法。4. unordered_map / unordered_set这一类要特别注意哈希表普通插入不一定导致已有迭代器失效但是如果插入触发rehash哈希桶重新组织。那么已有迭代器可能全部失效例如std::unordered_mapint, int table; auto it table.find(1); table.insert({100, 100});如果插入过程中触发 rehashbucket数量变化 ↓ 元素重新分布 ↓ 原迭代器失效所以如果已经知道大概会存多少元素可以table.reserve(10000);减少频繁 rehash。这里和vector::reserve()思路很像。一个是减少扩容一个是减少rehash四、实际开发中怎么避免迭代器失效第一种方法容器修改以后不要盲目继续使用旧迭代器。例如auto it nums.begin(); nums.push_back(100); // 如果可能发生扩容 // 不继续使用原it it nums.begin();也就是容器结构改变以后 ↓ 必要时重新获取迭代器第二种方法删除元素时使用 erase 的返回值。错误for (auto it nums.begin(); it ! nums.end(); it) { if (*it % 2 0) { nums.erase(it); } }正确for (auto it nums.begin(); it ! nums.end(); ) { if (*it % 2 0) { it nums.erase(it); } else { it; } }这个模式建议直接记住如果删除 ↓ it erase(it) 如果不删除 ↓ it第三种方法不要在 range-for 中随便修改容器结构。例如for (auto x : nums) { if (x 10) { nums.push_back(100); } }range-for 底层实际上会使用类似begin end iterator如果push_back()导致 vector 扩容循环内部使用的迭代器也会失效所以这种修改非常危险。如果确实需要遍历过程中新增/删除最好重新设计第一阶段遍历 ↓ 记录要修改的内容 第二阶段 ↓ 统一修改容器例如std::vectorint toAdd; for (int x : nums) { if (x 10) { toAdd.push_back(100); } } nums.insert(nums.end(), toAdd.begin(), toAdd.end());这样不会在遍历原容器过程中直接破坏迭代器。第四种方法vector已知大小时提前reserve。例如std::vectorTask tasks; tasks.reserve(10000); for (int i 0; i 10000; i) { tasks.push_back(Task{}); }减少扩容 ↓ 内存地址变化 ↓ 全部迭代器失效第五种方法有时可以保存下标而不是长期保存vector迭代器。例如size_t index 2;然后nums.push_back(100); std::cout nums[index] std::endl;即使 vector 扩容底层地址变了 但第2个元素的位置语义仍然可以通过下标重新计算相比auto it nums.begin() 2;长期保存下标有时更加安全。但是要注意如果在index前面插入或删除元素 下标对应的元素本身也会发生变化所以下标不是万能解决方案只是适合某些 vector 场景。五、面试中迭代器失效应该怎么回答如果面试官问什么叫迭代器失效可以回答迭代器失效是指容器经过插入、删除、扩容或 rehash 等操作以后原来的迭代器不再能够安全定位原来的元素。如果继续解引用或移动这个迭代器就可能产生未定义行为。如果继续问vector什么时候会发生迭代器失效可以回答vector 如果发生重新分配内存比如push_back导致容量不足而扩容那么原来的所有迭代器、指针和引用都会失效。erase不一定重新分配内存但由于后面的元素会向前移动所以被删除位置以及之后的迭代器会失效。如果问怎么避免可以回答第一不要在容器结构发生变化以后继续使用旧迭代器第二遍历删除时使用erase的返回值更新迭代器第三vector 如果能够预估容量可以提前reserve减少扩容第四不要在 range-for 中随意插入或删除当前容器如果修改后仍需访问元素可以重新获取迭代器或者在适合的场景保存下标。如果继续问为什么list插入通常不会导致其他迭代器失效可以回答因为 list 是节点式存储每个节点独立分配插入新节点只需要修改相邻节点的指针不需要移动其他节点因此已有节点的地址通常不会发生变化。删除时一般也只有指向被删除节点的迭代器失效。如果继续问unordered_map为什么会迭代器失效可以回答当插入元素导致 rehash 时哈希表会重新建立 bucket并重新组织元素所在的桶所以已有迭代器会失效。可以通过提前reserve或合理设置 bucket 数量减少频繁 rehash。最后可以把常见容器简单记成vector ↓ 扩容全部失效 erase删除位置及之后失效list ↓ 插入其他迭代器通常不失效 删除只删除节点的迭代器失效map / set ↓ 插入已有迭代器通常有效 删除被删除元素失效unordered_map / unordered_set ↓ rehash ↓ 迭代器失效实际开发中最值得记住的代码就是for (auto it container.begin(); it ! container.end(); ) { if (needDelete(*it)) { it container.erase(it); } else { it; } }以及一个原则容器发生结构性修改 ↓ 先考虑旧迭代器是否还有效 ↓ 不确定时不要继续使用迭代器失效本质上不是“迭代器坏掉了”而是它原来记录的位置 已经无法再代表原来的元素只要把这一点理解清楚vector扩容、erase、unordered_map rehash等问题就比较容易判断了。0voice · GitHub