对于以下代码:
my_container.erase(iter);
其中my_container是STL的某种容器,iter是指向这个容器中某个元素的迭代器。如果不是在for,while循环中,
这种方式删除元素没有问题,如果是在for,while中对m_container迭代,删除其中符合条件的所有元素,就可能出现问题。
如果是在for,while中对m_container迭代,删除其中符合条件的所有元素,就可能出现问题。
问题是:
在迭代容器的时候删除元素,可能导致迭代器失效(invalidation of iterators),产生未定义行为
(undefined behavior);
例如,对某个迭代器解引用所获得的值并不是执行erase()前这个迭代器指向的值,还有可能对未指向任何
元素的迭代器的解引用赋值而引发程序crash。
类似的问题代码像这样:
std::vector<int> my_container;
for (int i = 0; i < 100; ++i) {
my_container.push_back(i);
}
std::vector<int>::iterator it = my_container.begin();
for (it != my_container.end(); it++) {
if (*it % 2 == 1) {
my_container.erase(it);
}
}
my_container.erase(it)之后,it及其后面的迭代器已经失效,不应该再使用这些迭代器。再执行it++,其行为是未定义的。
其他容器也会遇到迭代器失效的问题:
对于vector 被删除元素的迭代器以及指向后面元素的迭代器全部失效。
对于deque 在首部或尾部删除元素则只会使指向被删除元素的迭代器失效,任何其他位置的插入和删除操作将使指向该容器元素的
所有迭代器失效。
对于list 仅有指向被删除元素的迭代器失效。
对于(mulit)map ,(multi)set 仅有指向被删除元素的迭代器失效。
所以Golden Rule是:尽量不要使用容器的插入删除操作之前的迭代器。
为什么不同容器迭代器失效情况有差别?这与实现各容器的数据结构有关。
如何在迭代容器时删除其中的元素?各容器通用的做法如下:
std::vector<int>::iterator it = my_container.begin();
for (it != my_container.end();/**blank*/ ) {
if (*it % 2 == 1) {
my_container.erase(it++);
}
else{
it++;
}
}
my_container.erase(it++) 巧妙得在执行erase()之前,it 先自增,指向被删除元素后面的元素,而给erase()传递的是未自增的it迭代器,
以定位要删除的元素。如果元素的值为奇数,则删除此元素,it指向下一个元素,如果元素的值为偶数,则检查下一个元素的值。整个迭代过程中
迭代器就不会失效了。
上段代码中两个不同分支出现了i++操作,下面的代码示例显示了如何防止遗忘其中任何一个分支的i++操作。
MyContainer::iterator it = myContainer.begin();
While(it != myContainer.end()){
MyContainer::iterator curIt = it;
if (*curIt == matchingValue) {
myContainer.erase(curIt);
}
}
对于vector ,deque, list, 另一种可行的方式是:
std::vector<int>::iterator it = my_container.begin();
for (it != my_container.end();/**blank*/ ) {
if (*it % 2 == 1) {
it = my_container.erase(it);
}
else{
it++;
}
}
上面代码可行的原因是vector::erase() 返回一个新的迭代器,指向被删除元素的后面的元素。可以继续使用新的迭代器。
而出于某种未知的原因(multi)map::erase(), (multi)set::erase()没有返回这样的迭代器。(从C++11开始也支持返回迭代器了).
但是对于vector,诸如在0到99个数中删除所有奇数的问题,可以使用STL的remove(),remove_if()优化性能。代码如下:
bool isOdd(int value)
{
return (value % 2) == 1;
}
my_container.erase( std::remove_if(m_container.begin(), m_container.end(), isOdd), m_container.end());
让我们再看看不使用remove_if()的版本:
for (it != my_container.end();/**blank*/ ) {
if (*it % 2 == 1) {
it = my_container.erase(it);
}
else{
it++;
}
}
如果你阅读过erase()源码或了解它是如何工作的,性能问题就显而易见:erase()删除一个元素的操作是被删除元素后面的所有元素依次
向前移动一个元素的位置,然后删除最后一个元素,时间复杂度为O(n^2)。
remove(),remove_if()的时间复杂度为O(n),删除元素的操作如下所示:
template<class ForwardIt, class UnaryPredicate>
ForwardIt remove_if(ForwardIt first, ForwardIt last, UnaryPredicate p)
{
ForwardIt result = first;
for (; first != last; ++first) {
if (!p(*first)) {
*result++ = *first;
}
}
return result;
}
从前向后遍历容器所有元素,将待保留的元素向前移动,占据待删除的元素的位置,remove_if()返回新的元素范围(begin,end)中的end,
记为new_end_of_range ,再调用erase()删除从new_end_of_range到my_container.end()之间的所有元素。
实际上,remove_if() 没有删除容器中的任何元素,它没有改变my_container.end(), 调用remove_if()后容器元素个数不会改变!!删除元素的工作
交给了erase().
Scott Meyers在他的”Effective STL”中关于此问题的讨论中也使用了remove_if(),由此看来,他的确是提出了一些让STL effective的建议。
深入学习STL迭代器失效问题:
在google中搜索 stl iterator invalidation rules 可以获得很多有关STL迭代器失效的有关内容。
References:
1. STL remove_if()
http://en.cppreference.com/w/cpp/algorithm/remove
2.More C++ Idioms/Erase-Remove http://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Erase-Remove
3.Effective STL, Item 32 - Scott Meyers
4.Cpp Invalid Iterators [对各种迭代器失效的情况进行了讲解分类]
http://www.angelikalanger.com/Conferences/Slides/CppInvalidIterators-DevConnections-2002.pdf
5.以下是stackoverflow上关于在迭代时删除容器中元素的讨论:
http://stackoverflow.com/questions/1604588/iterate-vector-remove-certain-items-as-i-go
http://stackoverflow.com/questions/3747691/stdvector-iterator-invalidation?rq=1
http://stackoverflow.com/questions/2874441/deleting-elements-from-stl-set-while-iterating?rq=1
http://stackoverflow.com/questions/1038708/erase-remove-contents-from-the-map-or-any-other-stl
-container-while-iterating/1038761#1038761
http://stackoverflow.com/questions/799314/difference-between-erase-and-remove?rq=1
Author: Garyelephant ,转载请注明来自http://garyelephant.me
分享到:
相关推荐
STL是高效的C++程序库,是大量类模板和函数模板的聚集,主要的组成部分包括容器、迭代器、算法、函数等。其中容器是存放对象的集合,使用类模板方式; 选代器是容器与算法的粘合剂,是所谓的泛型指针, 使用类模板方式...
一个STL容器类可能为了使用一个特定类型的数据而创建一个迭代器。作为指针,必须能够使用*操作符类获取数据。你还可以使用其他数学操作符如++。典型的,++操作符用来递增迭代器,以访问容器中的下一个对象。如果迭代...
X-CUBE-STL-H7 safety manual 安全手册
用于初步学习STL容器方便后续的算法学习, 来源于《算法笔记》, 适用于初学者,强力推荐这本书, 非常简单的把C、C++的STL、基础数据结构的实现、查找算法、排序算法、二分思想、贪心思想的起源思想
C++ STL迭代器机制剖析 -- C++经典书籍哦
下面小编就为大家带来一篇关于STL的erase()陷阱-迭代器失效问题的总结。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
标准程序库—自修教程与参考手册----c++stl
X-CUBE-STL-H7 安全库使用手册
之前看《C++ Primier》的时候,也解到在顺序型窗口里insert/erase会涉及到迭代器失效的问题,并没有深究。今天写程序的时候遇到了这个问题。 1 莫名其妙的Erase 最初我的程序是酱紫的,别说话,我知道这样是有问题的...
STL -容器,string容器
装配体1 - 防滑垫-4.STL.stl
VTk例子数据
3D-numpy-stl.zip,简单的库,使处理stl文件(和一般的3d对象)快速和容易。,3D建模使用专门的软件来创建物理对象的数字模型。它是3D计算机图形的一个方面,用于视频游戏,3D打印和VR,以及其他应用程序。
Stl-thumb是用于STL文件的快速轻量级缩略图生成器。 它可以在Linux和Windows的文件管理器中显示STL文件的预览。 它是用Rust编写的,并使用OpenGL。 安装 视窗 Stl-thumb需要64位Windows 7或更高版本。 最新版本并...
X-CUBE-STL 莱茵安全认证证书
matlab开发-surf2stl。从表面数据写入STL文件。
计算部分的数量 前提, 目标, 结果 前提: 学生需要掌握以下机能 • 树- 了解树的表示方法 • Map容器- 了解如何日用标准库中的map容器以及迭代器 • 递归- 了解如何构造一个递归的解决方案去解决一个问题