总结一下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没有任何效果。