STL（Standard Template Library）中的迭代器失效（iterator invalidation）是指对容器进行某些操作后，原有的迭代器变得无效，再使用这些迭代器会导致未定义行为（例如崩溃或逻辑错误）。下面是常见 STL 容器的迭代器失效情况总结：

一、vector

说明：

vector是动态数组，可能会在扩容时重新分配内存，因此多数修改操作都可能导致迭代器失效。

安全操作：

1.push_back：可能导致迭代器失效（只要是引起了重新分配）。 

1
2
3
4
5
std::vector<int> v{1, 2, 3};
auto it = v.begin();
std::cout << *it << std::endl;
v.push_back(4);
std::cout << *it << std::endl;

​ image-20250603110057092

要避免这种情况就需要使用reserve去提前分配好内存或者是更新好的迭代器

1
2
3
4
5
6
7
std::vector<int> v{1, 2, 3};
//v.reserve(10); 提前分配好内存
auto it = v.begin();
std::cout << *it << std::endl;
v.push_back(4);
it = v.begin(); //更新迭代器
std::cout << *it << std::endl;

2.insert / erase：可能使 插入/删除点之后的所有迭代器失效。

1
2
3
4
5
std::vector<int> v{1, 2, 3};
auto it = v.begin();
std::cout << *it << std::endl;
v.insert(it, 5);
std::cout << *it << std::endl;

3.resize / clear：所有迭代器都失效。

4.reserve：可能导致所有迭代器失效（如果重新分配内存）。

二 deque

✅ 安全操作：

  • push_front / push_back：所有迭代器失效。
  • insert / erase：插入点及其之后的迭代器失效。
  • clear / resize：所有迭代器失效。

特点：

deque 内部是分段数组结构，所以即使不扩容，有时也会失效。

三、list（双向链表）和 forward_list（单向链表）

✅ 安全操作：

  • insert / erase：仅影响被插入/删除位置的迭代器。
  • push_back / push_front：不影响任何迭代器。
  • clear：所有迭代器失效。

特点：

链表结构，节点之间不依赖内存连续，因此非常稳定，是迭代器最安全的容器之一。

四、set / multiset / map / multimap（底层红黑树）

✅ 安全操作：

  • insert：不影响现有迭代器。
  • erase：只使被删除元素的迭代器失效。
  • clear：所有迭代器失效。

特点：

由于是基于树结构的容器，插入不会改变其他元素的位置，因此迭代器通常比较稳定。

五、unordered_set / unordered_map（底层哈希表）

✅ 安全操作：

  • insert：可能导致所有迭代器失效（如果扩容）。
  • erase：只使被删除元素的迭代器失效。
  • rehash / clear：所有迭代器失效。

特点：

扩容时，哈希表会重新组织桶，因此扩容操作风险很高。

六、常见迭代器失效示例

1
2
3
4
5
6
7
8
cpp复制编辑std::vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4);  // 可能导致 it 失效
*it = 10;        // 未定义行为（如果失效）
cpp复制编辑std::list<int> lst = {1, 2, 3};
auto it = lst.begin();
lst.push_back(4);  // 不影响 it
*it = 10;          // 安全

七、如何安全处理迭代器失效

  • 操作容器后立即重新获取迭代器。
  • 使用返回的新迭代器（例如 insert 和 erase 通常返回一个有效的迭代器）。
  • 对于频繁插入删除的操作，优先选择 list 或 map，避免 vector。
  • 如果必须使用 vector，考虑使用 reserve() 提前分配内存。