C++初阶-迭代器失效和vector::insert函数的最终实现

1.vector::insert函数

1.1问题分析

1.2vector::insert函数的最终实现

1.3vector::insert函数的分析

2.第二种迭代器失效

3.第三种迭代器失效

4.迭代器失效deepseek的回答

1. 迭代器失效的原因

2. 不同容器的迭代器失效情况

（1）std::vector

（2）std::deque

（3）std::list / std::forward_list

（4）std::map / std::set（及 unordered_ 版本）

3. 如何避免迭代器失效？

（1）更新迭代器

（2）使用索引替代迭代器

（3）先收集再删除

（4）谨慎使用 reserve / rehash

4. 总结

5.总结

1.vector::insert函数

我们测试一下这个函数：

void func(const td::vector<int>& v)
{for (size_t i = 0; i < v.size(); i++){cout << v[i] << " ";}cout << endl;
}
void test()
{vector<int> v1; v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);func(v1);v1.insert(v1.begin(), 10);func(v1);v1.erase(v1.begin() + 3);func(v1);
}

那么运行结果为：

如果我们把代码改为如下形式：

void test()
{vector<int> v1; v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);func(v1);v1.insert(v1.begin(), 10);func(v1);v1.erase(v1.begin() + 3);func(v1);
}

则运行结果为：

也就是说insert函数是一定有问题的，这个需要我们调试分析一下代码：

1.1问题分析

我们发现在经过这个reserve后_start地址改变了，而这个pos地址不变，也就是说pos指向旧空间，但reserve函数在调用时会释放旧空间，it是_finish-1，而pos还是旧空间，在循环时一直判断it>=pos，那么就不会结束，会造成越界。

这种情况就是迭代器失效，pos指向旧空间，但扩容导致迭代器失效，本质上就是野指针了。

所以我们应该这样写：

1.2vector::insert函数的最终实现

//insert函数的实现2
void insert(iterator pos, const T& x)
{//判断是否合法assert(pos >= _start);assert(pos <= _finish);//判满if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator it = _finish - 1;//移动数据while (it >= pos){*(it + 1) = *it;--it;}*pos = x;++_finish;
}

1.3vector::insert函数的分析

这是一个比较浅的迭代器失效的问题，但是这里也提醒我们了一个很重要的点：需要注意函数调用后可能会导致迭代器失效的问题。

2.第二种迭代器失效

我们看如下代码：

void test()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);int i;cin >> i;auto it = v1.begin() + 1;v1.insert(it, 10);cout << *it << endl;
}

那么运行结果为：

不管我们输入0-3中的任意数字，最终打印结果一定不是最终值，这是因为再进行插入，那么最终会导致扩容，而扩容导致原地址失效，导致it为野指针，这个it的类型可以写为：td::vector<int>::iterator，所以导致了打印结果不正确。且insert是否扩容是不确定的，无法判断是否有迭代器失效。

那如果我们把insert改为如下定义：

void insert(iterator& pos, const T& x)
{//判断是否合法assert(pos >= _start);assert(pos <= _finish);//判满if (_finish == _end_of_storage){size_t len = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + len;}iterator it = _finish - 1;//移动数据while (it >= pos){*(it + 1) = *it;--it;}*pos = x;++_finish;
}

也就是说我们把第一个形参改为引用，这样就可以了吗？

用如下函数测试：

void test()
{vector<int> v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);int i;cin >> i;auto it = v1.begin() + 1;//不行v1.insert(it + 1, 10);//不行v1.insert(v1.begin(), 10);cout << *it << endl;
}

那么会有两个报错：

所以我们不能这样写！

所以我们最终解决办法就只能是再创建一个迭代器，否则很容易出错！

3.第三种迭代器失效

int main()
{std::vector<int>v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);auto it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){v1.erase(it);}++it;}for (const auto& e : v1){cout << e << " ";}cout << endl;return 0;
}

那么运行结果为：

首先声明一下：这里的是库里面的函数，而且如果测试都是没有其他问题的，但是如果你打印也会有问题。

为什么用erase也会失效？

首先我们若遇到偶数，判断出2为偶数，但是v1会直接跳过3的位置去判断下一个位置了，所以会导致结果不准确，然后最终非法访问？

那么我们改代码为如下形式：

int main()
{std::vector<int>v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);auto it = v1.begin();while (it != v1.end()){if (*it % 2 == 0){v1.erase(it);}else{++it;}}for (const auto& e : v1){cout << e << " ";}cout << endl;return 0;
}

为什么还是会有问题（这个取决于编译器，在g++下是运行正确的）？

这个取决于编译器，VS会认为erase、insert后的迭代器是失效的。可以任务迭代器有个标记，在经过这些过程后会改变标记，因为这是一个更加严格的检查！而在不同的编译器可能运行结果是不同的，所以我们在之后的学习中要把一段程序在多个编译器运行，保证它在每个编译器都能运行！

但是也要注意：erase在多数编译器中会只挪动数据，但有些编译器可能为了节省空间而缩容，所以单单erase也可能导致野指针！

结论：erase（it）以后，不同平台实现有差异，但是我们统一认为it失效了！我们在用完了一个后需要进行迭代器的更新！

4.迭代器失效deepseek的回答

通过deepseek我们可以更加深入的了解迭代器失效的问题，也方便了我们之后避免此类问题。以下是deepseek的搜索结果：

在 C++ 中，迭代器（iterator） 是指向容器（如 vector、list、map 等）元素的抽象指针。但某些操作会导致迭代器失效（invalidated），即它不再指向有效的元素，继续使用会导致未定义行为（UB），如程序崩溃或数据错误。

1. 迭代器失效的原因

迭代器失效通常发生在容器结构被修改时，例如：

插入元素（insert, push_back, emplace 等）
删除元素（erase, pop_back, clear 等）
容器扩容（如 vector 的 reserve 或自动增长）

失效的根本原因是：

内存重新分配（如 vector 扩容，旧迭代器指向被释放的内存）
元素位置移动（如 vector 插入/删除导致后续元素位移）
数据结构变化（如 unordered_map 的 rehash）

2. 不同容器的迭代器失效情况

不同容器对迭代器失效的敏感程度不同：

（1）`std::vector`

操作	迭代器失效情况
`push_back` / `emplace_back`	可能失效（如果触发扩容，所有迭代器失效；否则仅 `end()` 失效）
`insert` / `emplace`	可能失效（插入点及之后的迭代器失效，如果扩容则全部失效）
`erase`	被删元素及之后的迭代器失效
`pop_back`	仅 `end()` 失效
`clear` / `resize`	所有迭代器失效
`reserve`	不影响现有迭代器（除非 `capacity` 改变）

示例：

std::vector<int> v = {1, 2, 3};
auto it = v.begin() + 1; // 指向 2
v.push_back(4);          // 可能扩容，it 失效！
// std::cout << *it;     // 未定义行为（UB）！

（2）`std::deque`

操作	迭代器失效情况
`push_back` / `push_front`	通常不影响现有迭代器（除非重新分配）
`insert` / `emplace`	所有迭代器失效
`erase`	被删元素及之后的迭代器失效
`pop_back` / `pop_front`	仅被删元素的迭代器失效
`clear`	所有迭代器失效

特点：

deque 是分段连续存储，头尾插入通常不影响中间迭代器。
但 insert 可能导致所有迭代器失效（因为可能重新分配）。

（3）`std::list` / `std::forward_list`

操作	迭代器失效情况
`push_back` / `push_front`	不影响现有迭代器
`insert` / `emplace`	不影响其他迭代器
`erase`	仅被删元素的迭代器失效
`pop_back` / `pop_front`	仅被删元素的迭代器失效
`clear`	所有迭代器失效

特点：

list 是双向链表，forward_list 是单向链表。
插入/删除只影响当前节点，其他迭代器仍然有效。

示例：

std::list<int> l = {1, 2, 3};
auto it = ++l.begin(); // 指向 2
l.erase(it);           // it 失效，但其他迭代器仍然有效

（4）`std::map` / `std::set`（及 `unordered_` 版本）

操作	迭代器失效情况
`insert` / `emplace`	不影响现有迭代器
`erase`	仅被删元素的迭代器失效
`clear`	所有迭代器失效

特点：

基于红黑树（map/set）或哈希表（unordered_map/unordered_set）。
插入/删除通常不影响其他迭代器（除非 rehash，如 unordered_map 扩容）。

unordered_map 的 rehash 问题：

std::unordered_map<int, int> m;
auto it = m.begin();
m.reserve(1000); // 可能触发 rehash，it 失效！
// std::cout << it->first; // UB！

3. 如何避免迭代器失效？

（1）更新迭代器

某些操作（如 erase）会返回新的有效迭代器：

std::vector<int> v = {1, 2, 3};
auto it = v.begin() + 1;
it = v.erase(it); // it 现在指向 3（原 2 被删）

（2）使用索引替代迭代器

vector 可以用 [] 或 at() 访问：

std::vector<int> v = {1, 2, 3};
size_t idx = 1;
v.erase(v.begin() + idx); // 用索引计算新迭代器

（3）先收集再删除

避免在循环中直接删除：

std::vector<int> v = {1, 2, 3, 4, 5};
std::vector<int> to_remove = {2, 4};
for (auto val : to_remove) {v.erase(std::remove(v.begin(), v.end(), val), v.end());
}

（4）谨慎使用 `reserve` / `rehash`

vector / unordered_map 扩容会导致所有迭代器失效：

std::vector<int> v = {1, 2, 3};
auto it = v.begin();
v.reserve(100); // 可能扩容，it 失效！

4. 总结

容器	插入操作	删除操作	扩容/rehash
`vector`	可能失效	可能失效	全部失效
`deque`	通常安全	部分失效	可能失效
`list`	安全	仅当前失效	不适用
`map/set`	安全	仅当前失效	不适用
`unordered_map`	安全	仅当前失效	全部失效（rehash）