文章目录
- 1、前言
- 2、情况一：底层空间改变的操作
- 3、情况二：指定位置元素的删除操作
- 4、g++编译器对迭代器失效检测
- 4.1 扩容
- 4.2 erase删除任意位置（非尾删）
- 4.3 erase尾删
- 5、总结
1、前言
**迭代器的主要作用就是让算法能够不用关心底层数据结构，其底层实际就是一个指针，或者是对指针进行了封装，比如：string的迭代器就是原生指针char，vector的迭代器就是原生态指针T 。因此迭代器失效，实际就是迭代器底层对应指针所指向的空间被销毁了，而使用一块已经被释放的空间，造成的后果是程序崩溃(即如果继续使用已经失效的迭代器，程序可能会崩溃)。
对迭代器失效我们了解了，那么现在我们就分析，在vector中哪些操作会导致迭代器失效。
2、情况一：底层空间改变的操作
存在底层空间改变的函数接口有：resize、reserve、insert、assign、push_back等。
产生的原因：
这几个接口都存在扩容的问题，扩容的时候存在异地扩容，当异地扩容后，原本的空间被释放，但是迭代器指的是被释放空间，这就会导致迭代器的失效问题，会引发程序崩溃的问题。
解决方法：
一旦存在扩容，扩容后对迭代器更新一次，重新给迭代器赋值即可。
举例：
我们看一下insert接口。
我们由图中可以看到，当我们需要在3之前插入数据30，但是空间已经满了，因此我们需要进行扩容，扩容是异地开空间，开好空间将旧空间的数据拷贝回来，并将旧空间释放掉，_start指向新的空间头部，但是it指的是旧空间的位置，这就是迭代器失效。我们记住it相对于_start的相对位置，在新空间开好后，更新it，让其指向新空间的相对位置。（方式：计算出it到_start的距离len，开好新空间后，更新it为新的_start+len）。
代码实现：
iterator insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _endOfStorage)
{
size_t len = pos - _start;//先记下_start到pos位置的距离，因为扩容后迭代器pos就会失效
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;//新的空间需要更新迭代器pos
}
iterator end = _finish - 1;
//挪动数据
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
return pos;
}
3、情况二：指定位置元素的删除操作
对于erase接口也会导致迭代器失效问题。那它是怎么导致的呢，我们来分析一下。
产生原因：
在erase删除pos位置元素后，pos位置之后的元素会往前搬移，没有导致底层空间的改变，理论上讲迭代器不应该会失效，但是：如果pos刚好是最后一个元素，删完之后pos刚好是end的位置，而end位置是没有元素的，那么pos就失效了。因此删除vector中任意位置上元素时，vs就认为该位置迭代器失效了。
#include <iostream>
using namespace std;
#include <vector>
int main()
{
int a[] = { 1, 2, 3, 4 };
vector<int> v(a, a + sizeof(a) / sizeof(int));
// 使用find查找3所在位置的iterator
vector<int>::iterator pos = find(v.begin(), v.end(), 3);
// 删除pos位置的数据，导致pos迭代器失效。
v.erase(pos);
cout << *pos << endl; // 此处会导致非法访问
return 0;
}
解决方法：
本质是因为尾删导致的迭代器失效问题，因此我们在尾删完后，返回it的下一个位置，我们的模拟实现是数据覆盖（it+1覆盖it），因此返回的还是it，一删之后 --_finish，当 it指的位置就是_finish 的时候正好也就停止了，因此也就解决了迭代器失效的问题。
代码实现：
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
//挪动数据
while (it < _endOfStorage)
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
4、g++编译器对迭代器失效检测
Linux下，g++编译器对迭代器失效的检测并不是非常严格，处理也没有vs2019下极端。
我们来看下面这几种情况下，代码在vs2019和g++下不同的表现。
4.1 扩容
int main()
{
vector<int> v{1,2,3,4,5};
for(size_t i = 0; i < v.size(); ++i)
cout << v[i] << " ";
cout << endl;
auto it = v.begin();
cout << "扩容之前，vector的容量为: " << v.capacity() << endl;
v.reserve(100);
cout << "扩容之后，vector的容量为: " << v.capacity() << endl;
while(it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}
g++下运行结果：
vs2019下运行结果：
vs2019下程序崩溃了。
结论：当扩容后迭代器就是失效的，g++下虽然能运行，但是结果出错了，vs下直接程序崩溃。
4.2 erase删除任意位置（非尾删）
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v{1,2,3,4,5};
vector<int>::iterator it = find(v.begin(), v.end(), 3);
v.erase(it);
cout << *it << endl;
while(it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}
g++下运行结果：
vs2019下运行结果：
结论：在非尾删的删除中，空间是没有变的，迭代器指的是还是那块空间，g++下迭代器没有失效，删除后后面的数据前移，it位置没失效，vs下只要是erase，就判断为迭代器失效了。
4.3 erase尾删
int main()
{
vector<int> v{1,2,3,4,5,6};
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
v.erase(it);
++it;
}
for (auto e : v)
cout << e << " ";
cout << endl;
return 0;
}
g++下运行结果：
vs2019下不用看，直接崩溃。
结论：当在尾删的时候，删除之后存在数据挪动，一挪动_finish与it是一个位置了，erase本就返回被删除位置的下一个位置，此时迭代器失效，再++it程序直接崩溃。
5、总结
本篇主要讲了扩容、插入、删除造成的迭代器失效，g++对迭代器失效检测的不严格，而vs对迭代器失效检测很严格，直接崩溃。
1、扩容一般都要更新迭代器，我们不知道哪一次的扩容是异地扩。
2、插入任意位置时，一旦存在扩容就要更新迭代器，本质就是扩容要更新迭代器。
3、删除任意位置时，g++下非尾删不考虑迭代器失效问题，尾删一定要注意迭代器失效问题；vs2019中删除就认定为迭代器失效，直接崩溃。
