1.62、讲一讲迭代器失效及其解决方法

1. 序列式容器（如vector、deque）迭代器失效

• • vector
  • • 删除元素（如erase）后，指向被删除元素及其之后元素的迭代器全部失效，因为元素后移，内存布局改变。解决方法是使用erase函数的返回值，它返回下一个有效迭代器，推荐用此返回值继续遍历。
  • • 插入元素（如push_back）时，如果触发了容量扩展（重新分配内存），则所有迭代器失效。若未扩容，则插入点之后的迭代器失效，插入点之前的迭代器仍有效。
  • • 总结：任何可能导致内存重新分配的操作都会使所有迭代器失效，删除操作使得删除点及之后迭代器失效。
• • deque
  • • 在首尾插入或删除元素时，仅使end()迭代器失效，且指针和引用不失效。
  • • 在中间位置插入或删除元素，会使所有迭代器、指针和引用失效。
  • • 解决方法同样是操作后重新获取迭代器，避免使用旧迭代器。

2. 关联容器（如set、map、list）迭代器失效

• • list
  • • 插入和删除操作不会使其他迭代器失效，仅删除的元素对应的迭代器失效。
• • set、map及其多重版本
  • • 插入操作不会使任何迭代器失效。
  • • 删除操作仅使被删除元素的迭代器失效，其他迭代器保持有效。
  • • 解决方法是在删除时，先用erase返回的迭代器继续遍历，避免使用失效迭代器。

迭代器失效的通用解决方案

• • 使用erase返回的迭代器继续遍历，避免使用已失效的迭代器。
• • 操作容器后重新获取迭代器，尤其是对vector和deque等可能发生内存重分配的容器。
• • 避免在遍历时直接删除元素，可以先记录待删除元素，再统一删除，或使用安全的遍历删除模式。
• • 对vector等容器，若需频繁插入删除，考虑使用list或其他不易失效迭代器的容器。

总结：迭代器失效是容器结构变更引发的常见问题。vector和deque因连续存储和分段存储特性，迭代器失效规则较严格，尤其是扩容和中间插入删除操作。关联容器则较为宽松，失效范围有限。掌握各容器的失效规则，合理使用erase返回值和重新获取迭代器，是避免迭代器失效导致程序错误的关键。
（加入我的知识星球，免费获取账号，解锁所有文章。）
本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。