众所周知当使用一个容器的insert或者erase函数通过迭代器插入或删除元素"可能"会导致迭代器失效,因此很多建议都是让我们获取insert或者erase返回的迭代器,以便用重新获取新的有效的迭代器进行正确的操作:
iter=vec.insert(iter); iter=vec.erase(iter);
想想究竟为什么迭代器失效,原因也不难理解。以vector为例,当我们插入一个元素时它的预分配空间不够时,它会重新申请一段新空间,将原空间上的元素复制到新的空间上去,然后再把新加入的元素放到新空间的尾部,以满足vector元素要求连续存储的目的。而后原空间会被系统撤销或征做他用,于是指向原空间的迭代器就成了类似于“悬垂指针”一样的东西,指向了一片非法区域。如果使用了这样的迭代器会导致严重的运行时错误就变得很自然了。这也是许多书上叙述vector在insert操作后“可能导致所有迭代器实效”的原因。但是想到这里我不禁想到vector的erase操作的叙述是“会导致指向删除元素和删除元素之后的迭代器失效”。但是明显感觉erase带来失效要比insert来得轻得多。似乎“此失效非彼失效”,想想似乎也是这样的:erase操作是在原空间上进行的,假设有一个存有"12345"序列的vector<int>容器原本指向3的迭代器在我删除2之后无非变成指向4了,我只要注意别用到超过end位置的迭代器不就行了吗?
说了这么多似乎可以归纳一下迭代器失效的类型了:
1.由于容器元素整体“迁移”导致存放原容器元素的空间不再有效,从而使得指向原空间的迭代器失效。
2.由于删除元素使得某些元素次序发生变化使得原本指向某元素的迭代器不再指向希望指向的元素。
对于第一种类型没什么好就是的了,原因应该确定如此了。可对于第二种,我写了如下的代码
vector<int> vec; for(int i=0;i<10;i++) vec.push_back(i); vector<int>::iterator iter =vec.begin()+2; vec.erase(iter);//注:这里真的不建议这么写 cout<<*iter<<endl; for(vector<int>::iterator it=vec.begin();it!=vec.end();it++) cout<<*it<<endl;
按照我的猜测尽管我在注释的位置的写法很“危险”,但是我并未涉及到上面总结第一种失效类型的范畴。程序应该还是会如预期的一样删除在vec[2]位置上的2然后输出前移到vec[2]位置上的3,并输出0到10不含2的所有数字,于是vs2008的c++环境下运行一下,竟然一个是个无情的“红叉”。按道理说这种写法是绝对不对出现严重的运行时错误的,难道是猜测得不对吗?
当时被这样的疑问困扰了几天,有一天突然想起一个关于容器迭代器作参数的例子,在vs2008下运行不了,但是在vc6.0下却可以,有人说是因为08采用了更为严格的类型检测机制。于是将上面的代码放到6.0里,果然得到了预期的效果,看来系统果然是这么处理的。至于08为什么不可以,现在我只能认为是采用了更加安全的检查机制。使得第二种类型的失效后果同样“不可饶恕”。
这样我就又想到假如insert元素时原空间够用的话,是不是也不会产生第一类失效而产生第二类失效呢?
vector<int> vec; for(int i=0;i<10;i++) vec.push_back(i); cout<<"capacity:"<<vec.capacity()<<endl;//查看预分配空间大小 vector<int>::iterator iter =vec.begin()+2; vec.insert(iter,100); cout<<"capacity:"<<vec.capacity()<<endl; cout<<*iter<<endl; for(vector<int>::iterator it=vec.begin();it!=vec.end();it++) cout<<*it<<endl;
同样在vc6.0下,证明了假设是对的。但是上面的种种做法只是为了帮助我理解迭代器实效的原因,建议使用insert和erase操作时还是像许多书中介绍的如第一段代码那样的写法,这是一种好的且安全的习惯。总之一句话去相信“insert和erase操作后所有的迭代器都会失效”。
迭代器(iterator)是一个可以对其执行类似指针的操作(如:解除引用(operator*())和递增(operator++()))的对象,我们可以将它理解成为一个指针。但它又不是我们所谓普通的指针,我们可以称之为广义指针,你可以通过sizeof(vector::iterator)来查看,所占内存并不是4个字节。
首先对于vector而言,添加和删除操作可能使容器的部分或者全部迭代器失效。那为什么迭代器会失效呢?vector元素在内存中是顺序存储,试想:如果当前容器中已经存在了10个元素,现在又要添加一个元素到容器中,但是内存中紧跟在这10个元素后面没有一个空闲空间,而vector的元素必须顺序存储一边索引访问,所以我们不能在内存中随便找个地方存储这个元素。于是vector必须重新分配存储空间,用来存放原来的元素以及新添加的元素:存放在旧存储空间的元素被复制到新的存储空间里,接着插入新的元素,最后撤销旧的存储空间。这种情况发生,一定会导致vector容器的所有迭代器都失效。
我们看到实现上述所说的分配和撤销内存空间的方式以实现vector的自增长性,效率是极其低下的。为了使vector容器实现快速的内存分配,实际分配的容器会比当前所需的空间多一些,vector容器预留了这些额外的存储区,用来存放新添加的元素,而不需要每次都重新分配新的存储空间。你可以从vector里实现capacity和reserve成员可以看出这种机制。
capacity和size的区别:size是容器当前拥有的元素个数,而capacity则指容器在必须分配新存储空间之前可以存储的元素总数。
vector迭代器的几种失效的情况: 1.当插入(push_back)一个元素后,end操作返回的迭代器肯定失效。 2.当插入(push_back)一个元素后,capacity返回值与没有插入元素之前相比有改变,则需要重新加载整个容器,此时first和end操作返回的迭代器都会失效。 3.当进行删除操作(erase,pop_back)后,指向删除点的迭代器全部失效;指向删除点后面的元素的迭代器也将全部失效。
deque迭代器的失效情况: 在C++Primer一书中是这样限定的: 1.在deque容器首部或者尾部插入元素不会使得任何迭代器失效。 2.在其首部或尾部删除元素则只会使指向被删除元素的迭代器失效。 3.在deque容器的任何其他位置的插入和删除操作将使指向该容器元素的所有迭代器失效。但是:我在vs2005测试发现第一条都不满足,不知为何?等以后深入STL以后慢慢的领会吧!
只有list的迭代器好像很少情况下会失效。也许就只是在删除的时候,指向被删除节点的迭代器会失效吧,其他的还没有发现。
相关推荐
c++迭代器失效问题,描述c++中各种集合的迭代器使用
主要介绍了C++迭代器失效的几种情况总结,文中代码非常详细,帮助大家更好的了解学习,感兴趣的朋友可以参考下
关于迭代器失效的一些认识 关于迭代器失效的一些认识 关于迭代器失效的一些认识
之前看《C++ Primier》的时候,也解到在顺序型窗口里insert/erase会涉及到迭代器失效的问题,并没有深究。今天写程序的时候遇到了这个问题。 1 莫名其妙的Erase 最初我的程序是酱紫的,别说话,我知道这样是有问题的...
下面小编就为大家带来一篇关于STL的erase()陷阱-迭代器失效问题的总结。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
NULL 博文链接:https://jacky-dai.iteye.com/blog/1088098
谷歌开源团队同时也表示,C++ B-tree容器也不是没有缺点,与标准STL容器不同的是,修改C++ B-tree容器,会令所有未在该容器中的迭代器失效。出于这个原因,谷歌在该库中还增加了一个“安全”容器版本,安全容器中的...
9.2.2 使迭代器失效的容器操作 271 9.3 顺序容器的操作 272 9.3.1 容器定义的类型别名 272 9.3.2 begin和end成员 273 9.3.3 在顺序容器中添加元素 273 9.3.4 关系操作符 277 9.3.5 容器大小的操作 278 9.3.6 访问...
9.3.6 容器操作可能使迭代器失效 315 9.4 vector对象是如何增长的 317 9.5 额外的string操作 320 9.5.1 构造string的其他方法 321 9.5.2 改变string的其他方法 322 9.5.3 string搜索操作 325 9.5.4 ...
9.3.6 容器操作可能使迭代器失效 315 9.4 vector对象是如何增长的 317 9.5 额外的string操作 320 9.5.1 构造string的其他方法 321 9.5.2 改变string的其他方法 322 9.5.3 string搜索操作 325 9.5.4 ...
这与 Google 的原始项目不同,因为容器的行为更像现代 STL (C++17),并且几乎是直接替换(迭代器失效除外,见下文); 对于包括支持emplace和try_emplace在地图和值不需要有一个默认的构造函数。 与通常使用红黑树...
1.连续内存序列容器(vector,string,deque) 序列容器的erase方法返回值是指向紧接在被删除元素之后的元素的有效迭代器,可以根据这个返回值来安全...关联容器的erase方法没有返回值,被删除的迭代器失效,所以删除前必须
最后才发现原来是自己对“容器insert之后迭代器会失效”的理解不够透彻。 题目如下: 假定iv是一个int的vector,下面的程序存在什么错误?你将如何修改? auto iter = iv.begin(); auto mid = iv.begin() + iv.size...
④一旦内从重分配,和原vector相关的指针,引用,迭代器都失效。内存重分配耗时很长 二、头文件、using声明 头文件:#include using声明:using std::vector; 三、初始化 vector v1; ==>v1是一个空的vector ...
官方资源查询示例JavaC / C ++ Facebook Fizz整数溢出漏洞(CVE-2019-3560) 在libssh2中吃错误代码Itergator-迭代器失效的库和查询( 博客文章) Java脚本Etherpad CVE-2018-6835 C# C#Zip Slip演示GitHub动作: ...
lazy_map的客户端必须知道迭代器可以在任何标准的写操作中失效(与std::unordered_map不同,后者保证了迭代器在擦除时的稳定性)。 lazy_map提供了两个非标准方法move_value和move以移出键的值。 lazy_map保证迭代器...
Java与C/C++的编译器对比 物理机如何处理并发问题? Java内存模型 什么是Java内存模型? Java内存模型的目标? 主内存与工作内存 内存间的交互操作 原子性、可见性、有序性 volatile 什么是 volatile? 为什么基于 ...