浅谈c++ stl迭代器失效的问题
之前看《C++ Primier》的时候,也解到在顺序型窗口里insert/erase会涉及到迭代器失效的问题,并没有深究。今天写程序的时候遇到了这个问题。
1 莫名其妙的Erase
最初我的程序是酱紫的,别说话,我知道这样是有问题的,可这样是最直观的想法
int arr[]={0,1,2,3,4,5,6,7,8,9,10}; vector<int> a(arr,arr+sizeof(arr)/sizeof(*arr));for (auto it = a.begin(); it != a.end();++it ){ if ((*it)&1){ a.erase(it); } }
没错,程序崩溃!删除了迭代器it之后,it迭代器失效了,无法再进行++it操作了。
可是,当我觉得erase做的只是把it之后的元素向前移动一个位置而已,为什么迭代器失效了呢?我翻开《STL源码剖析》,SGI STL的vector<T,Alloc>::erase的源码是这样的:
iterator vector<T, Alloc>::erase(iterator position) { if (position + 1 != end()) copy(position + 1, finish, position); --finish; destroy(finish); return position; }
正如我所想,erase函数并没有对输入的position迭代器进行改写!我打印出调试信息,发现erase之后,迭代器的_Ptr成员,也就是指针的值并没有发生变化,而此指针所指的元素的确是下一个元素。那么为什么失效了呢?
我又查了《C++ Primier》,发现此书上的标准写法是这样的:
int arr[]={0,1,2,3,4,5,6,7,8,9,10}; vector<int> a(arr,arr+sizeof(arr)/sizeof(*arr)); for (auto it = a.begin(); it != a.end();){ if ((*it)&1){ it=a.erase(it); } else ++it; }
运行了一下,这样是没错的。我打印了调试信息,发现与之前一样,erase之后把结果赋给it,it里的成员_Ptr并没有发生变化。唯一的可能就是迭代器里还有别的标志,如果当前元素被删除之后,该迭代器也就“失效”了。《C++ Primier》并未对此作出过多解释,只是说,erase函数返回被删除元素的下一个元素的迭代器。
结论:在STL里,我们不能以指针来看待迭代器,指针是与内存绑定的,而迭代器是与容器里的元素绑定的,删除了之后,该迭代器就失效了,在对其重新赋值之前,不能再访问此迭代器。
2 更加小心冀冀地Insert
机智如我,自然会去探索一下insert之后,迭代器会怎样。于是:
vector<int> a; for (int i = 0; i < 10; ++i) { a.push_back(i); } for (auto it = a.begin(); it != a.end(); ++it){ if (*it == 5){ a.insert(it, 100); ++it; } }
你猜怎么着??
啥事儿没有!你可能会问,插入之后为什么要++it。插入之前,it指向5,在5之前插入100后,it指向100。这样下一次循环,it依然会指向5。相信我,你的程序会爆炸的!
我作了个++it之后,it又指向5,下一次循环就直接指向5之后的元素了,顺利完成插入工作。
世界和平~世界和平~我还真不确定。
突然想到,当插入元素过多,vector的capacity会增加,这时会不会问题呢?说干就干:
vector<int> a; for (int i = 0; i < 13; ++i) { a.push_back(i); } for (auto it = a.begin(); it != a.end(); ++it){ if (*it == 5){ a.insert(it, 100); ++it; } }
BOOM!果然崩溃了!也就是说插入之后的迭代器失效了。那之前的呢?
我决定粗暴地测试一下:
vector<int> a; for (int i = 0; i < 13; ++i) { a.push_back(i); } auto it1=a.begin(); for (auto it = it1; it != a.end(); ++it){ if (*it == 5){ a.insert(it, 100); it=it1; } }
我插入之后,直接让it指向begin(),然后单步调试。执行完it=it1还好好的,可再去执行++it还是崩溃了。
也就是说,capacity变化之后,所有的迭代器都失效了!这是当然了呀!capacity发生变化,容器内部做的不仅仅是增加capacity这么简单,因为容器所在内存后面可能没有足够的内存让我们使用,所以,容器要重新开辟一段足够大的内存来存储容器里的元素,当前内存会被释放。这样一来,迭代器自然失效了。
3 C++ Primier的总结
关于容器的迭代器失效的问题,C++ Primier用了一小节作了总结,我翻译成中文如下:
(1)增加元素到容器后
对于vector和string,如果容器内存被重新分配,iterators,pointers,references失效;如果没有重新分配,那么插入点之前的iterator有效,插入点之后的iterator失效;
对于deque,如果插入点位于除front和back的其它位置,iterators,pointers,references失效;当我们插入元素到front和back时,deque的迭代器失效,但reference和pointers有效;
对于list和forward_list,所有的iterator,pointer和refercnce有效。
(2)从容器中移除元素后
对于vector和string,插入点之前的iterators,pointers,references有效;off-the-end迭代器总是失效的;
对于deque,如果插入点位于除front和back的其它位置,iterators,pointers,references失效;当我们插入元素到front和back时,off-the-end失效,其他的iterators,pointers,references有效;
对于list和forward_list,所有的iterator,pointer和refercnce有效。
(3)在循环中refresh迭代器
当处理vector,string,deque时,当在一个循环中可能增加或移除元素时,要考虑到迭代器可能会失效的问题。我们一定要refresh迭代器。
int arr[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; deque<int> v(arr,arr+sizeof(arr)/sizeof(*arr)); for (auto it = v.begin(); it != v.end(); ) { if ((*it) & 1) { it = v.insert(it, *it); it += 2; } else it = v.erase(it); }
至于it+=2,很容易解释,insert之后,it指向新增加的元素,+2之后,it指向下一个要处理的元素。
(4)在循环不变式中不要store off-the-end迭代器
这个很容易理解了,增加或移除元素之后,off-the-end失效了,不store的话,每次从end()函数中取的都是最新的off-the-end,自然不会失效。
最后:《C++ Primier》是本好书。
以上就是小编为大家带来的浅谈c++ stl迭代器失效的问题全部内容了,希望大家多多支持猪先飞~
相关文章
- vector是表示可以改变大小的数组的序列容器,本文主要介绍了C++STL标准库std::vector的使用详解,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2022-03-06
pytorch::Dataloader中的迭代器和生成器应用详解
这篇文章主要介绍了pytorch::Dataloader中的迭代器和生成器应用详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-30- 索引并不是时时都会生效的,比如以下几种情况,将导致索引失效: 1.如果条件中有or,即使其中有条件带索引也不会使用(这也是为什么尽量少用or的原因) 注意:要想使用or,又想让索引生效,只能将or条件中的每个列都加上索引 ...2014-06-07
- 这篇文章主要介绍了微信jssdk在iframe页面失效问题的解决措施 的相关资料,需要的朋友可以参考下...2016-03-07
- 这篇文章主要介绍了C#特性-迭代器(上)及一些研究过程中的副产品,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了zlib库压缩和解压字符串STL string的实例详解的相关资料,希望通过本文能帮助到大家,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了Java Iterator(迭代器)的相关资料,文中示例代码非常详细,帮助大家更好的理解和学习,感兴趣的朋友可以了解下...2020-07-06
- 在本篇文章里小编给大家整理的是一篇关于java迭代器和for循环优劣详解内容,对此有兴趣的朋友们可以学习参考下。...2021-01-22
- 这篇文章主要介绍了C++ STL中的容器适配器实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-04-20
vector list map 遍历删除制定元素 防止迭代器失效的实例
下面小编就为大家带来一篇vector list map 遍历删除制定元素 防止迭代器失效的实例。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25- 下面小编就为大家带来一篇基于list循环删除元素,迭代器失效的问题详解。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- <STL 源码剖析>将其描述为空间配置器,理由是allocator可以将其它存储介质(例如硬盘)做为stl 容器的存储空间。由于内存是allocator管理的主要部分,因此,本文以STL内存管理为出发点介绍allocator...2020-04-25
- 这篇文章主要介绍了C++ 实现自定义类型的迭代器操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-11
stl常用算法(Algorithms)介绍(stl排序算法、非变序型队列)
这篇文章主要介绍了stl常用算法(Algorithms)介绍(stl排序算法、非变序型队列),需要的朋友可以参考下...2020-04-25- 在Python这门语言中,生成器毫无疑问是最有用的特性之一。与此同时,也是使用的最不广泛的Python特性之一。究其原因,主要是因为,在其他主流语言里面没有生成器的概念。本文将详细介绍python迭代器与生成器...2021-06-15
- 在ECMAScript 6增加了一个对象,它不是新的语法或新的内置对象,而一种协议( 迭代器协议),所有遵守这个协议的对象,都可以称之为迭代器,这篇文章主要给大家介绍了关于ECMAScript中迭代器的相关资料,需要的朋友可以参考下...2021-08-06
- 这篇文章主要介绍了Python生成器与迭代器,现在可以通过生成器来直接创建一个列表,是由于内存的限制,表的容量肯定是有限的,果我们需要一个包含几百个元素的列表,是每次访问的时候只访问其中的几个,剩下的元素不使用就很浪费内存空间,下面来了解具体内容...2021-11-02
stl容器set,map,vector之erase用法与返回值详细解析
在使用 list、set 或 map遍历删除某些元素时可以这样使用,如下所示...2020-04-25- 关于set,必须说明的是set关联式容器。set作为一个容器也是用来存储同一数据类型的数据类型,并且能从一个数据集合中取出数据,在set中每个元素的值都唯一,而且系统能根据元素的值自动进行排序...2020-04-25
java中LinkedList使用迭代器优化移除批量元素原理
本文主要介绍了java中LinkedList使用迭代器优化移除批量元素原理,文中通过示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-11-01