网站开发 鲁山,网站服务器放在哪里好,SEO网站价格,网站建设属于设备吗文章目录 1、前言2、情况一#xff1a;底层空间改变的操作3、情况二#xff1a;指定位置元素的删除操作4、g编译器对迭代器失效检测4.1 扩容4.2 erase删除任意位置#xff08;非尾删#xff09;4.3 erase尾删 5、总结 1、前言
**迭代器的主要作用就是让算法能够不用关心底… 文章目录 1、前言2、情况一底层空间改变的操作3、情况二指定位置元素的删除操作4、g编译器对迭代器失效检测4.1 扩容4.2 erase删除任意位置非尾删4.3 erase尾删 5、总结 1、前言
**迭代器的主要作用就是让算法能够不用关心底层数据结构其底层实际就是一个指针或者是对指针进行了封装比如string的迭代器就是原生指针charvector的迭代器就是原生态指针T 。因此迭代器失效实际就是迭代器底层对应指针所指向的空间被销毁了而使用一块已经被释放的空间造成的后果是程序崩溃(即如果继续使用已经失效的迭代器程序可能会崩溃)。 对迭代器失效我们了解了那么现在我们就分析在vector中哪些操作会导致迭代器失效。
2、情况一底层空间改变的操作
存在底层空间改变的函数接口有resize、reserve、insert、assign、push_back等。 产生的原因 这几个接口都存在扩容的问题扩容的时候存在异地扩容当异地扩容后原本的空间被释放但是迭代器指的是被释放空间这就会导致迭代器的失效问题会引发程序崩溃的问题。 解决方法 一旦存在扩容扩容后对迭代器更新一次重新给迭代器赋值即可。 举例 我们看一下insert接口。
我们由图中可以看到当我们需要在3之前插入数据30但是空间已经满了因此我们需要进行扩容扩容是异地开空间开好空间将旧空间的数据拷贝回来并将旧空间释放掉_start指向新的空间头部但是it指的是旧空间的位置这就是迭代器失效。我们记住it相对于_start的相对位置在新空间开好后更新it让其指向新空间的相对位置。方式计算出it到_start的距离len开好新空间后更新it为新的_startlen。 代码实现
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 vectorint main()
{int a[] { 1, 2, 3, 4 };vectorint v(a, a sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvectorint::iterator pos find(v.begin(), v.end(), 3);// 删除pos位置的数据导致pos迭代器失效。v.erase(pos);cout *pos endl; // 此处会导致非法访问return 0;
}解决方法 本质是因为尾删导致的迭代器失效问题因此我们在尾删完后返回it的下一个位置我们的模拟实现是数据覆盖it1覆盖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()
{vectorint 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()
{vectorint v{1,2,3,4,5};vectorint::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()
{vectorint 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中删除就认定为迭代器失效直接崩溃。
