在STL(标准模板库)中经常会碰到要删除容器中部分元素的情况,本人在编程中就经常编写这方面的代码,在编码和测试过程中发现在STL中删除容器有很多陷阱,网上也有不少网友提到如何在STL中安全删除元素这些问题。本文将讨论编程过程中最经常使用的两个序列式容器vector、list中安全删除元素的方法和应该注意的问题, 其它如queue、stack等配接器容器(container adapter),由于它们有专属的操作行为,没有迭代器(iterator),不能采用本文介绍的删除方法,至于deque,它与vector的删除方法一样。STL容器功能强大,but no siliver bullet,如果你使用不当,也将让你吃尽苦头。
1.手工编写for循环代码删除STL序列式容器中元素的方法<o:p></o:p>
例如,你能看出以下代码有什么问题?
例1:
#include <iostream>
#include <vector>
using namespace std;
void main( ) {
vector<int> vectInt;
int i;
// 初始化vector容器
for (i = 0; i < 5; i++ ) {
vectInt.push_back( i );
}
// 以下代码是要删除所有值为4的元素
vector<int>::iterator itVect = vectInt.begin();
for ( ; itVect != vectInt.end(); ++itVect ) {
if ( *itVect == 4 ) {
vectInt.erase( itVect );
}
}
int iSize = vectInt.size();
for ( i = 0 ; i < iSize; i++ ) {
cout << " i= " << i << ", " << vectInt[ i ] << endl;
}
<o:p></o:p>
}
例2:
#include <iostream>
#include <vector>
using namespace std;
void main( ) {
vector<int> vectInt;
int i;
// 初始化vector容器
for ( i = 0; i < 5; i++ ) {
vectInt.push_back( i );
if ( 3 == i ) {
// 使3的元素有两个,并且相临。这非常关键,否则将发现不了bug。
// 具体解释见下。
vectInt.push_back( i );
}
}
vector<int>::iterator itVect = vectInt.begin();
vector<int>::iterator itVectEnd = vectInt.end(); // 防止for多重计算
// 以下代码是要删除所有值为3的元素
for ( ; itVect != itVectEnd; ++itVect ) {
if ( *itVect == 3 ) {
itVect = vectInt.erase( itVect );
}
}
int iSize = vectInt.size();
for ( i = 0 ; i < iSize; i++ ) {
cout << " i= " << i << ", " << vectInt[ i ] << endl;
}
例3:
#include <iostream>
#include <vector>
using namespace std;
void main( ) {
vector<int> vectInt( 5 );
int i;
vectInt[ 0 ] = 0;
vectInt[ 1 ] = 1;
vectInt[ 2 ] = 2;
vectInt[ 3 ] = 3;
vectInt[ 4 ] = 4; // 替换为 vectInt[ 4 ] = 3;试试
vector<int>::iterator itVect = vectInt.begin();
vector<int>::iterator itVectEnd = vectInt.end(); // 防止for多重计算
// 以下代码是要删除所有值为3的元素
for ( ; itVect != itVectEnd; ) {
if ( *itVect == 3 ) {
itVect = vectInt.erase( itVect );
}
else {
++itVect;
}
}
int iSize = vectInt.size();
for ( i = 0 ; i < iSize; i++ ) {
cout << " i= " << i << ", " << vectInt[ i ] << endl;
}
}
<o:p></o:p>
分析:
这里最重要的是要理解erase成员函数,它删除了itVect迭代器指向的元素,并且返回要被删除的itVect之后的迭代器,迭代器相当于一个智能指针,指向容器中的元素,现在删除了这个元素,将导致内存重新分配,相应指向这个元素的迭代器之后的迭代器就失效了,但erase成员函数返回要被删除的itVect之后的迭代器。
例1将导致程序未定义的错误,在windows中即是访问非法内存,程序当掉。因为vectInt.erase( itVect );调用后itVect之后的迭代器已无效了,所以当执行++itVect后,*itVect访问了非法内存。例1也是初学者最容易犯的错误,这个错误也比较容易发现。
例2可能会导致不能把vectInt中所有为3的元素删除掉。因为第一次删除成功时,itVect = vectInt.erase( itVect );itVect为指向3之后的位置,之后再执行++itVect,itVect就掉过了被删除元素3之后的元素3,导致只删除了一个为3的元素,这个bug比较隐蔽,因为如果不是两个均为3的元素相临,就将很难捕捉到这个bug,程序有可能在一段时间运行良好,但如碰到容器中两值相同的元素相临,则程序就要出问题。
例3,对于本例你可能要说程序没有任何问题,解决了上面的两个bug,程序也运行正常。但且慢,你把 “vectInt[ 4 ] = 4;” 这一行改为 “vectInt[ 4 ] = 3;”试试,一运行,程序当掉,访问非法内存!你疑惑不解:从程序看不出bug,而且我还把vectInt.end()放在外面计算以防止for多重计算,提高效率。哈哈,问题就出在最后一句话!算法大师Donald Knuth有一句名言:不成熟的优化是一切恶果的根源( Permature optimization is the root of all evil )。由于在for循环中要删除元素,则vectInt.end()是会变化的,所以不能在for循环外计算,而是每删除一次都要重新计算,所以应放在for循环内。那你要问,为什么把 “vectInt[ 4 ] = 4;” 这一行改为 “vectInt[ 4 ] = 3;”程序就会当掉,而不改程序就很正常呢?这就跟vector的实现机制有关了。下面以图例详细解释。
vectInt的初始状态为:
<o:p></o:p>
| end
0 1 2 3 4 <o:p></o:p>
删除3后,
<o:p></o:p>
|新的end | 原来的end
0 1 2 4 4 <o:p></o:p>
<o:p></o:p>
<o:p></o:p>
<o:p></o:p>
注意上面“新的end”指向的内存并没有被清除,为了效率,vector会申请超过需要的内存保存数据,删除数据时也不会把多余的内存删除。
然后itVect再执行++itVect,因为此时*itVect等于4,所以继续循环, 这时itVect 等于“新的end”但不等于“原来的end”(它即为itVectEnd),所以继续,因为 *itVect访问的是只读内存得到的值为4,不等于3,故不删除,然后执行++itVect此时itVect等于itVectEnd退出循环。从上面过程可以看出,程序多循环了一次(删除几次,就要多循环几次),但程序正常运行。
如果把 “vectInt[ 4 ] = 4;” 这一行改为 “vectInt[ 4 ] = 3;”过程如下:<o:p></o:p>
<o:p></o:p>
<o:p></o:p>
| end
0 1 2 3 3 <o:p></o:p>
<o:p></o:p>
删除3后,
<o:p></o:p>
|新的end |原来的 end
0 1 2 3 3 <o:p></o:p>
<o:p></o:p>
<o:p></o:p>
删除第2个3后,
<o:p></o:p>
|新的end |原来的 end
0 1 2 3 3 <o:p></o:p>
<o:p></o:p>
这时itVect 等于“新的end”但不等于“原来的end”(它即为itVectEnd),所以继续,因为 *itVect访问的是只读内存得到的值为3,等于3,所以执行删除,但因为*itVect访问的是只读内存不能删除,所以程序当掉。
综上,我们知道当要删除的值在容器末尾时,会导致程序删除非法内存,程序当掉;即使程序正常运行,也是for循环多执行了等于删除个数的循环。所以把vectInt.end()放在for循环外面执行,完全是错误的。对于list容器,list.end()在删除过程中是不会变的,可以把它放在for循环外面计算,但由于list.end()是个常量,把list.end()放在for循环中计算编译器应该可以优化它。从安全考虑,除非你能保证for循环中不会改变容器的大小,否则都应该对容器的值在for循环中计算,对于 vectInt.size()这样的计算,也应该在for循环中计算,不要因为微小的优化而导致程序出错。
<o:p></o:p>
正确的方法:
例4:
#include <iostream>
#include <vector>
using namespace std;
void main( ) {
vector<int> vectInt;
int i;
分享到:
相关推荐
基于springboot大学生就业信息管理系统源码数据库文档.zip
基于java的驾校收支管理可视化平台的开题报告
时间序列 原木 间隔5秒钟 20241120
毕业设计&课设_基于 Vue 的电影在线预订与管理系统:后台 Java(SSM)代码,为毕业设计项目.zip
基于springboot课件通中小学教学课件共享平台源码数据库文档.zip
基于java的网上购物商城的开题报告
Delphi人脸检测与识别Demo1fdef-main.zip
基于java的咖啡在线销售系统的开题报告
基于java的自助医疗服务系统的开题报告.docx
内容概要:本文档全面介绍了Visual Basic(VB)编程语言的基础知识和高级应用。首先概述了VB的基本特性和开发环境,随后详细讲述了VB的数据类型、变量、运算符、控制结构、数组、过程与函数、变量作用域等内容。接着介绍了窗体设计、控件使用、菜单与工具栏的设计,文件操作、数据库访问等关键知识点。最后讨论了VB的学习方法、发展历史及其在桌面应用、Web应用、数据库应用、游戏开发和自动化脚本编写等领域的广泛应用前景。 适合人群:初学者和中级程序员,尤其是希望快速掌握Windows桌面应用开发的人群。 使用场景及目标:①掌握VB的基础语法和开发环境;②学会使用VB创建复杂的用户界面和功能完整的应用程序;③理解数据库操作、文件管理和网络编程等高级主题。 其他说明:Visual Basic是一种简单易学且功能强大的编程语言,尤其适合用于开发Windows桌面应用。文中不仅覆盖了基础知识,还包括了大量的实用案例和技术细节,帮助读者快速提升编程技能。
基于java的疫情期间高校防控系统开题报告.docx
基于springboot+vue社区老年人帮扶系统源码数据库文档.zip
基于java的超市商品管理系统的开题报告.docx
基于SpringBoot房屋买卖平台源码数据库文档.zip
xdu限通院23微处理器系统与应用大作业(两只老虎),适应于汇编语言keil软件,
<项目介绍> - 新闻类网站系统,基于SSM(Spring、Spring MVC、MyBatis)+MySQL开发,高分成品毕业设计,附带往届论文 - 不懂运行,下载完可以私聊问,可远程教学 1、该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.md文件(如有),仅供学习参考, 切勿用于商业用途。 --------
基于java的学生网上请假系统的开题报告.docx
社会经济繁荣发展的今天,电子商务得到了飞速发展,网上交易越来越彰显出其独特的优越性,在人们的日常生活中,出现了各种类型的交易网站。其中一个就是车辆易主交易网站,它是一个服务于用户买卖二手车辆的交易网站,为用户提供了平等互利、方便快捷的网上交易平台,通过这一类型的网站,用户可自由出售和购买车辆。 本课题主要根据车辆本身的特性,充分发挥互联网的特点与优势,构建一个以二手车辆为商品、基于互联网平台的车辆易主业务交易管理系统,并根据车辆易主业务交易管理系统的应用需求,进行需求分析,进而对网站系统作规划设计。采用IDEA为运行平台,以SSH为框架,运用HTML语言、JSP技术、MySql数据库、JSP与后台数据库链接等关键技术建设二手车网上交易系统,构建车辆易主交易系统的会员注册与登录,网站首页展示、用户发布商品车辆,用户求购商品车辆,分页浏览、购物系统、用户后台管理、管理员用户后台管理等功能,并使这些功能得以实现并更好为用户服务。网站整体构建完成且测试成功后,用户可以进入网站进行注册、登录,登录后,用户可以在网站上发布自己的闲置车辆或者寻找想要购买的车辆,还可以收藏车辆,管理发布和收藏的车辆,
SQLite3的向量扩展库,windows dll,版本0.1.5
基于C++实现(控制台)商品库存管理系统