C++认识容器的迭代器

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;
    }
}

程序输出结果:

2
4
anhui 1
shandong 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个建议.李健.机械工业出版社.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程心路

你不知道的 equals 和 ==

i1 == i2 和 i1.equals(i2) 这两个都是 true,大多数人应该可以答对。后面的 i3 == i4 和 i3.equals(i4) 估计就...

892
来自专栏架构说

topK总结(初稿)

问题1 在n个有序数组中,求topK 假定有20个有序数组,每个数组有500个数字,降序排列,数字类型32位uint数值,现在需要取出这10000个数字中最大的...

38715
来自专栏猿人谷

C++ 模板学习

1. 模板的概念。 我们已经学过重载(Overloading),对重载函数而言,C++的检查机制能通过函数参数的不同及所属类的不同。正确的调用重载函数。例如,为...

25110
来自专栏程序员互动联盟

【编程基础】C++比C牛逼的七个点

1. 函数检测增强 ? 在C语言中,重复定义多个同名的全局变量是合法的,在C++中,不允许定义多个同名的全局变量。 C语言中多个同名的全局变量最终会被链接到全局...

3565
来自专栏信数据得永生

JavaScript 编程精解 中文第三版 六、对象的秘密

3016
来自专栏Golang语言社区

Go语言中的Array、Slice、Map和Set使用详解

Array(数组) 内部机制 在 Go 语言中数组是固定长度的数据类型,它包含相同类型的连续的元素,这些元素可以是内建类型,像数字和字符串,也可以是结构类型,元...

7565
来自专栏小樱的经验随笔

python学习笔记之运算符

目录 前言 软件环境 身份运算符 算术运算符 比较运算符 位移运算符 自变运算符 位运算符 逻辑运算符 成员关系运算符 Python真值表 最后 前言 在前面的...

3323
来自专栏Golang语言社区

Go语言中的Array、Slice、Map和Set使用详解

Array(数组) 内部机制 在 Go 语言中数组是固定长度的数据类型,它包含相同类型的连续的元素,这些元素可以是内建类型,像数字和字符串,也可以是结构类型,元...

3338
来自专栏Java架构师进阶

Java 常见的 30 个误区与细节!

1、在Java中,没有goto语句。因为大量使用goto语句会降低程序的可读性和可维护性,所以Java语言取消了goto的使用。同时,为了避免程序员自行使用go...

873
来自专栏流媒体

STL(二)map/multimapmapmultimap

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

1173

扫码关注云+社区

领取腾讯云代金券