C++ map容器erase的正确姿势

       之前在代码中使用map::erase函数时,误搬了vector::erase的用法,导致Server down掉了,好在在测试环境就及时发现了问题,在上线前进行了补救==。
       以下总结一下map::erase的正确用法。
       首先看一下在循环中使用vector::erase时我习惯的用法:

1
2
3
4
5
6
7
8
9
10
11
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的性质:看这里
       C++98

1
iterator erase(iterator position);

       这一种用法是没有问题的。
       然而当想当然的在map::erase上照搬上面erase的用法时,就有问题了,查看 cplusplus 上的说明:
       C++98

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

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

1
2
3
4
5
6
7
8
9
10
11
for(map<int,int>::iterator it = mapInt.begin(); it != mapInt.end();)
{
    if(it->second == 0)
    {
        mapInt.erase(it++);
    }
    else
    {
        it++;
    }
}

       在网上找mapInt.erase(it++)的说明,比较详细的一种解释为:看这里
       该方法中利用了后缀++的特点,这个时候执行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++的具体实现代码其实类似以下:

1
2
3
4
5
6
7
// postfix form: fetch and increment
map<intint>::iterator operator++(int)//通过一个多余的int参数与前缀++区分
{
    map<intint>::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自增过了,所以不受其影响噢。
       关于上面代码中调用的前缀++代码类似如下:

1
2
3
4
5
6
// prefix form: increment and fetch
map<intint>::iterator& operator++()
{
    increment(); // increment
    return *this// fetch
}

       也正因为后缀++会比前缀++的操作多一个临时变量,并且其是以传值复制的方式返回给调用方,所以一般而言后缀++的效率会比前缀++效率低一些。
       值得一提的是,在最新的C++11标准中,已经新增了一个map::erase函数执行后会返回下一个元素的iterator,然而不知道啥时候C++11才能达到现在C++98的覆盖程度,谨慎一点还是使用map.erase(it++)比较保险。
       C++11

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

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

文章目录