（C++）错误的map删除 *** 作和STL中容器的迭代器的底层实现机制1.错误的map删除 *** 作2.STL中容器的迭代器的底层实现机制参考文献

概述（C++）错误的map删除 *** 作和STL中容器的迭代器的底层实现机制1.错误的map删除 *** 作2.STL中容器的迭代器的底层实现机制参考文献

1.错误的map删除 *** 作

假设有个map容器，用于存储大学班级中各个家乡省份对应的学生数，key为省份中文全拼，value为学生数。现需要删除人数为0的记录，删除代码如下：

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

猛一看，没问题，仔细一看，有巨坑，STL容器的删除和插入 *** 作隐藏的陷阱主要有如下两条。
（1）对于节点式容器(map, List, set)元素的删除，插入 *** 作会导致指向该元素的迭代器失效，其他元素迭代器不受影响；
（2）对于顺序式容器(vector，string，deque)元素的删除、插入 *** 作会导致指向该元素以及后面的元素的迭代器失效。

所以，在删除一个元素的时候，是没有什么问题的。即：

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

但是，当删除多个元素时，程序会出现崩溃。原因是通过迭代器删除指定的元素时，指向那个元素的迭代器将失效，如果再次对失效的迭代器进行++ *** 作，则会带来未定义行为，程序崩溃。解决方法有二，还是以上面的map容器为例，示例删除 *** 作的正确实现：

方法一：当删除特定值的元素时，删除元素前保存当前被删除元素的下一个元素的迭代器。

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

如何更加简洁的实现该方法呢？下面给出该方法的《Effective STL》一书的具体实现：

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

该实现方式利用了后置++ *** 作符的特性，在erase *** 作之前，迭代器已经指向了下一个元素。

再者map.erase()返回指向紧接着被删除元素的下一个元素的迭代器，所以可以实现如下：

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

方法二：当删除满足某些条件的元素，可以使用remove_copy_if & swap方法。先通过函数模板remove_copy_if 按照条件拷贝（copy）需要的元素到临时容器中，剩下未被拷贝的元素就相当于被“删除（remove）”了，然后在将两个容器中的元素交换（swap）即可，可以直接调用map的成员函数swap。参考代码：

#include <iostream>#include <string>#include <map>#include <algorithm>#include <iterator>  using namespace std;map<string,int> mapCount;//不拷贝的条件bool notcopy(pair<string,int> key_value){    return key_value.second==0;}int main(){    mapCount.insert(make_pair("tanwan",0));    mapCount.insert(make_pair("anhui",1));    mapCount.insert(make_pair("shanghai",0));    mapCount.insert(make_pair("shandong",1));    map<string,int> mapCountTemp;//临时map容器    //之所以要用迭代器适配器inserter函数模板是因为通过调用insert()成员函数来插入元素，并由用户指定插入位置    remove_copy_if(mapCount.begin(),mapCount.end(),inserter(mapCountTemp,mapCountTemp.begin()),notcopy);    mapCount.swap(mapCountTemp);//实现两个容器的交换    cout<<mapCount.size()<<endl;     //输出2    cout<<mapCountTemp.size()<<endl; //输出4    for(map<string,int>::iterator it=mapCount.begin();it!=mapCount.end();++it)    {        cout<<it->first<<" "<<it->second<<endl;    }}

程序输出结果：

24anhui 1shandong 1

这种方法的缺点：虽然实现两个map的交换的时间复杂度是常量级，一般情况下，拷贝带来的时间开销会大于删除指定元素的时间开销，并且临时map容器也增加了空间的开销。

2.STL中容器的迭代器的底层实现机制

提到STL，必须要马上想到其主要的6个组成部件，分别是：容器、迭代器、算法、仿函数、适配器和空间分配器，迭代器是连接容器和算法的一种重要桥梁。

STL中容器迭代器的本质是类对象，其作用类似于数据库中的游标（cursor），除此之外迭代器也是一种设计模式。我们可以对它进行递增（或选择下一个）来访问容器中的元素，而无需知道它内部是如何实现的。其行为很像指针，都可以用来访问指定的元素。但是二者是完全不同的东西，指针代表元素的内存地址，即对象在内存中的存储位置，而迭代器则代表元素在容器中的相对位置。

要自定义一个迭代器，就要重载迭代器一些基本 *** 作符：*（解引用）、++（自增）、==（等于）、!=（不等于）、=（赋值），以便它在range for语句中使用。range for是C++11中新增的语句，如我们对一个集合使用语句for （auto i : collection ） 时，它的含义其实为：

for(auto __begin = collection.begin(),auto __end = collection.end();__begin!=__end;++__begin){     i = *__begin;    ...//循环体}

begin和end是集合的成员函数，它返回一个迭代器。如果让一个类可以有range for的 *** 作，它必须满足以下几条：
（1）拥有begin和end函数，它们均返回迭代器 ，其中end函数返回一个指向集合末尾，但是不包含末尾元素的值，即用集合范围来表示，一个迭代器的范围是 [ begin, end ） 一个左闭右开区间。
（2）必须重载++、！=和解引用（*）运算符。迭代器看起来会像一个指针，但是不是指针。迭代器必须可以通过++最后满足！=条件，这样才能够终止循环。

下面给出最简单的实现代码。我们定义一个CPPCollection类，里面有个字符串数组，我们让它能够通过range for将每个字符串输出来。

class CPPCollection {public:    //迭代器类    class Iterator    {    public:        int index;//元素下标        CPPCollection& outer;        Iterator(CPPCollection &o, int i):outer(o), index(i){}        voID operator++()        {            index++;        }        std::string operator*() const        {            return outer.str[index];        }        bool operator!=(Iterator i)        {            return i.index!=index;        }    };public:    CPPCollection()    {        string strTemp[10]={"a", "b", "c", "d", "e", "f", "g", "h", "i", "j"};        int i=0;        for(auto strIt:strTemp)        {            str[i++]=strIt;        }    }    Iterator begin()    {        return Iterator(*this,0);    }    Iterator end()    {        return Iterator(*this, 10);    }private:    std::string str[10];};

我们定义了个内部的嵌套类Iterator,并为它重载了++、*、！=运算符。由于C++中的内部嵌套类与外围的类没有联系，为了访问外部类对象的值，我们必须要传入一个引用（或指针，本例中传入引用）。Iterator的自增方法其实就是增加内部的一个索引值。判断！=的方法是和另外一个迭代器做比较，这个迭代器一般是集合的末尾，当我们的索引值等于末尾的索引值end时，认为迭代器已经达到了末尾。 在CPPCollection类中，定义了begin（）、end（）分别返回开头、结束迭代器，调用如下代码：

　　CPPCollection cpc;　　for (auto i : cpc)　　{    　　std::cout <<i<<std::endl;　　}　　//或者　　CPPCollection cpc;　　for(CPPCollection::Iterator i= cpc.begin();i!=cpc.end();++i)　　{        std::cout<<*i<<std::endl;   }

即可遍历集合中的所有元素了。

在泛型算法中，为了对集合中的每一个元素进行 *** 作，我们通常要传入集合的迭代器头、迭代器尾，以及谓词，例如std::find_if（vec.begin(),vec.end(),…），这种泛型算法其实就是在迭代器的首位反复迭代，然后运行相应的行为。

---

参考文献

[1]编写高质量代码：改善C++程序的150个建议.李健.机械工业出版社.

相关文章：

C# 2.0 Specification(迭代器)（二）

C#中使用迭代器处理等待任务_基础知识

C# 2.0 Specification(迭代器)（一） 总结

以上是内存溢出为你收集整理的（C++）错误的map删除 *** 作和STL中容器的迭代器的底层实现机制1.错误的map删除 *** 作2.STL中容器的迭代器的底层实现机制参考文献全部内容，希望文章能够帮你解决（C++）错误的map删除 *** 作和STL中容器的迭代器的底层实现机制1.错误的map删除 *** 作2.STL中容器的迭代器的底层实现机制参考文献所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。