[转] C++ STL中map.erase(it++)用法原理解析

时间:2022-02-13 14:13:25

总结一下map::erase的正确用法。 
首先看一下在循环中使用vector::erase时我习惯的用法:

for(vector<int>::iterator it = vecInt.begin(); it != vecInt.end();)
{
if(*it == 0)
{
it = vecInt.erase(it);
}
else
{
it++;
}
}

  程序从一个vector中删除值为0的元素,利用了vector::erase函数根据iterator删除某个元素时会返回下一个元素的iterator的性质: 
http://www.cplusplus.com/reference/vector/vector/erase/

C++98
iterator erase (iterator position);

  

这一种用法是没有问题的。

然而当想当然的在map::erase上照搬上面erase的用法时,就有问题了,查看http://www.cplusplus.com/reference/map/map/erase/上的说明:

C++98
(1)
void erase (iterator position);
(2)
size_type erase (const key_type& k);
(3)
void erase (iterator first, iterator last);

  

如上所示,C++98中map::erase并没有返回值为iterator的原型函数。
那么问题来了it=map.erase(it),然后对it进行操作会发生什么呢?会发生传说中的“未定义的行为”!包括但不限于程序挂掉、机器死机、地球地震、宇宙毁灭等–原因是什么呢?在执行map.erase(it)之后,it这个iterator已经失效了,考虑C语言中一个失效释放了的指针,再次引用它会导致什么问题呢?

在循环中正确使用map::erase的方法是什么呢?如下:

for(map<int,int>::iterator it = mapInt.begin(); it != mapInt.end();)
{
if(it->second == 0)
{
mapInt.erase(it++);
}
else
{
it++;
}
}

  

在网上找mapInt.erase(it++)的说明,比较详细的一种解释为:
http://blog.csdn.net/lmh12506/article/details/9167653
该方法中利用了后缀++的特点,这个时候执行mapInt.erase(it++);这条语句分为三个过程
1、先把it的值赋值给一个临时变量做为传递给erase的参数变量

2、因为参数处理优先于函数调用,所以接下来执行了it++操作,也就是it现在已经指向了下一个地址。

3、再调用erase函数,释放掉第一步中保存的要删除的it的值的临时变量所指的位置。
然而个人感觉比较费解,意思是第一步先把it的值传给了函数调用的形参,然后又回去执行i+1的操作吗?这样总感觉it++的执行被硬生生的切成了两部分,只能硬记住这一结论。
直到后来看了《STL源码剖析》中的++i和i++实现方式的区别,然后某一天,再看到《More Effective C++》里的说明,突然开窍了,mapInt.erase(it++)的机理终于不再神秘。
其实在mapInt.erase(it++)中,it++确实是作为一个完整的执行过程,it++的具体实现代码其实类似以下:

// postfix form: fetch and increment
map<int, int>::iterator operator++(int)//通过一个多余的int参数与prefix++区分
{
map<int, int>::iterator tmp = *this; // fetch
increment(); // increment,map内部由红黑树实现,此函数负责指向下一个有序元素的iterator
return tmp; // return what was
}

  

上面代码的最终返回的值其实是tmp,tmp存储的是*this的旧值,this后来通过increment函数自增了,但是tmp的依然保持原值,最后将tmp返回赋值作为erase的参数,所以在mapInt.erase(it++)中,其实it++是作为一个整体执行完成了的,在传值给erase函数之前,it其自身其实已经+1了,不过后缀++返回的却是一个未执行+1操作的旧值,所以后面erase函数依然删除的是原it位置的值,同时该迭代器失效,然而之前it已经+1自增过了,所以不受其影响噢。
关于上面代码中调用的前缀++代码类似如下:

// prefix form: increment and fetch
map<int, int>::iterator& operator++()
{
increment(); // increment
return *this; // fetch
}

  

也正因为后缀++会比前缀++的操作多一个临时变量,并且其是以传值复制的方式返回给调用方,所以一般而言后缀++的效率会比前缀++效率低一些。

值得一提的是,在最新的C++11标准中,已经新增了一个map::erase函数执行后会返回下一个元素的iterator,然而不知道啥时候C++11才能达到现在C++98的覆盖程度,谨慎一点还是使用map.erase(it++)比较保险。

C++11
(1)
iterator erase (const_iterator position);
(2)
size_type erase (const key_type& k);
(3)
iterator erase (const_iterator first, const_iterator last);

  

最后,有的小伙伴可能会问为啥前缀++和后缀++的返回值一个是迭代器引用,一个却是迭代器传值?简单来说,前缀++返回的便是传参进来的迭代器,自然可以返回迭代器本身的引用,然而后缀++返回的是一个函数内部的临时变量,在函数执行完后便析构了,必然不能传引用。注意既然是通过传值的方式返回,对其返回值的修改对于原it是没有影响的,举例来说(it++)++的结果其实it只自增了一次,第二次++只是对其(it++)的返回值执行了++,对原it没有任何效果。

[转] C++ STL中map.erase(it++)用法原理解析的更多相关文章

  1. C&plus;&plus;中的STL中map用法详解&lpar;转&rpar;

    原文地址: https://www.cnblogs.com/fnlingnzb-learner/p/5833051.html C++中的STL中map用法详解   Map是STL的一个关联容器,它提供 ...

  2. C&plus;&plus; STL 中 map 容器

    C++ STL 中 map 容器 Map是STL的一个关联容器,它提供一对一(其中第一个可以称为关键字,每个关键字只能在map中出现一次,第二个可能称为该关键字的值)的数据 处理能力,由于这个特性,它 ...

  3. STL中的Vector相关用法

    STL中的Vector相关用法 标准库vector类型使用需要的头文件:#include <vector>. vector 是一个类模板,不是一种数据类型,vector<int&gt ...

  4. stl中map的四种插入方法总结

    stl中map的四种插入方法总结方法一:pair例:map<int, string> mp;mp.insert(pair<int,string>(1,"aaaaa&q ...

  5. STL中map的使用

    知识点 C++中map提供的是一种键值对容器,里面的数据都是成对出现的.map内部自建一颗红黑树(一种非严格意义上的平衡二叉树),这颗树具有对数据自动排序的功能,所以在map内部所有的数据都是有序的. ...

  6. C&plus;&plus;&&num;160&semi;STL中Map的按Key排序和按Value排序

    map是用来存放<key, value>键值对的数据结构,可以很方便快速的根据key查到相应的value.假如存储学生和其成绩(假定不存在重名,当然可以对重名加以区 分),我们用map来进 ...

  7. STL中map与hash&lowbar;map的比较

    1. map : C++的STL中map是使用树来做查找算法; 时间复杂度:O(log2N) 2. hash_map : 使用hash表来排列配对,hash表是使用关键字来计算表位置; 时间复杂度:O ...

  8. STL中map与hash&lowbar;map容器的选择收藏

    这篇文章来自我今天碰到的一个问题,一个朋友问我使用map和hash_map的效率问题,虽然我也了解一些,但是我不敢直接告诉朋友,因为我怕我说错了,通过我查询一些帖子,我这里做一个总结!内容分别来自al ...

  9. C&plus;&plus; STL中Map的相关排序操作:按Key排序和按Value排序 - 编程小径 - 博客频道 - CSDN&period;NET

    C++ STL中Map的相关排序操作:按Key排序和按Value排序 - 编程小径 - 博客频道 - CSDN.NET C++ STL中Map的相关排序操作:按Key排序和按Value排序 分类: C ...

随机推荐

  1. Windows下Python工具pip的安装

    1.打开pip的文档官网 https://pip.pypa.io/en/stable/ ,进入installation.在installation里,我们需要的是get-pip.py这个脚本. 选中后 ...

  2. the basic index concept

    Computer Science An Overview _J. Glenn *shear _11th Edition Over the years numerous variations o ...

  3. Android -- 经验分享(二)

    目录                                                                                   自定义两个View进行画图,让 ...

  4. 安装 vsftpd

    (1)安装vsftpdsudo apt-get install vsftpd (2)配置sudo vi /etc/vsftpd.conf #anonymous_enable=YESlocal_enab ...

  5. QT 4&period;87 changes

    http://blog.qt.io/blog/2015/05/26/qt-4-8-7-released/ Qt 4.8.7 is a bug-fix release. It maintains bot ...

  6. Android:抄QQ照片选择器(按相册类别显示,加入选择题)

    这个例子的目的是为了实现类似至QQ照片选择功能.选择照片后,,使用类似新浪微博 微博 页面上显示. 先上效果图:     本例中使用的主要技术: 1.使用ContentProvider读取SD卡全部图 ...

  7. cocos2d-x 3&period;0rc1 创建project

    1.进入bin文件夹 2.打开CMD命令行窗口中输入命令,然后按Enter(-p 包名 -l 语言 -d 新project存储路径)

  8. Codeforces 437D The Child and Zoo&lpar;贪心&plus;并查集&rpar;

    题目链接:Codeforces 437D The Child and Zoo 题目大意:小孩子去參观动物园,动物园分非常多个区,每一个区有若干种动物,拥有的动物种数作为该区的权值.然后有m条路,每条路 ...

  9. MATLAB &&num;39&semi; &colon; &&num;39&semi; 官方解释

    1.冒号的作用 产生矢量,阵列标注以及for-loop迭代子 2.描述 冒号是MATLAB中最有用的操作符之一.它使用下述规则来创建有规则的空间矢量: j:k is the same as [j,j+ ...

  10. linux统计cdn日志慢请求

    ./stat_ip.sh live-https.log-0510.gz 1000 #首先用shell脚本可以统计出?日志慢请求查询时间超过?秒对应的ip和对应的调用次数(传两个参数) #!/bin/b ...