首页 > 编程语言 >C++中不同容器下迭代器失效的情况

C++中不同容器下迭代器失效的情况

时间:2024-03-10 10:11:59浏览次数:28  
标签:iterator 迭代 ++ iter erase C++ 失效

C++中不同容器下迭代器失效的情况

迭代器失效分三种情况考虑,也是分三种数据结构考虑,分别为数组型,链表型,树型数据结构。

数组型数据结构:该数据结构的元素是分配在连续的内存中,insert和erase操作,都会使得删除点和插入点之后的元素挪位置,所以,插入点和删除掉之后的迭代器全部失效,也就是说insert(iter)(或erase(iter)),然后在iter++,是没有意义的。解决方法:erase(*iter)的返回值是下一个有效迭代器的值。 iter =cont.erase(iter);

链表型数据结构:对于list型的数据结构,使用了不连续分配的内存,删除运算使指向删除位置的迭代器失效,但是不会失效其他迭代器.解决办法两种,erase(*iter)会返回下一个有效迭代器的值,或者erase(iter++).

树形数据结构: 使用红黑树来存储数据,插入不会使得任何迭代器失效;删除运算使指向删除位置的迭代器失效,但是不会失效其他迭代器.erase迭代器只是被删元素的迭代器失效,但是返回值为void,所以要采用erase(iter++)的方式删除迭代器。

注意:经过erase(iter)之后的迭代器完全失效,该迭代器iter不能参与任何运算,包括iter++,*ite

一、序列式容器(数组式容器)

对于序列式容器(如vector,deque),序列式容器就是数组式容器,删除当前的iterator会使后面所有元素的iterator都失效。这是因为vetor,deque使用了连续分配的内存,删除一个元素导致后面所有的元素会向前移动一个位置。所以不能使用erase(iter++)的方式,还好erase方法可以返回下一个有效的iterator。
迭代器失效

void vectorTest()
{
    vector<int> container;
    for (int i = 0; i < 10; i++)
    {
        container.push_back(i);
    }

    vector<int>::iterator iter;
     for (iter = container.begin(); iter != container.end(); iter++)
    {
            if (*iter > 3)
              container.erase(iter);
    }

     for (iter = container.begin(); iter != container.end(); iter++)
    {
            cout<<*iter<<endl;
    }
}

对于序列式容器,比如vector,删除当前的iterator会使后面所有元素的iterator都失效。这是因为顺序容器内存是连续分配(分配一个数组作为内存),删除一个元素导致后面所有的元素会向前移动一个位置。(删除了一个元素,该元素后面的所有元素都要挪位置,所以,iter++,已经指向的是未知内存)。

但是erase方法可以返回下一个有效的iterator。所以代码做如下修改,就OK了

vector<int>::iterator iter;
    for (iter = container.begin(); iter != container.end();)
    {
            if (*iter > 3) {
                iter = container.erase(iter);
            }
            else {
                iter ++;
            }

    }

二、关联式容器

对于关联容器(如map, set,multimap,multiset),删除当前的iterator,仅仅会使当前的iterator失效,只要在erase时,递增当前iterator即可。这是因为map之类的容器,使用了红黑树来实现,插入、删除一个结点不会对其他结点造成影响。erase迭代器只是被删元素的迭代器失效,但是返回值为void,所以要采用erase(iter++)的方式删除迭代器。

//测试错误的Map删除元素
void mapTest()
{
    map<int, string> dataMap;


    for (int i = 0; i < 100; i++)
    {
           string strValue = "Hello, World";

            stringstream ss;
            ss<<i;
            string tmpStrCount;
            ss>>tmpStrCount;
            strValue += tmpStrCount;
            dataMap.insert(make_pair(i, strValue));
    }

    cout<<"MAP元素内容为:"<<endl;
     map<int, string>::iterator iter;
    for (iter = dataMap.begin(); iter != dataMap.end(); iter++)
    {
            int nKey = iter->first;
            string strValue = iter->second;
            cout<<strValue<<endl;
    }

    cout<<"内容开始删除:"<<endl;
    //删除操作引发迭代器失效
    for (iter = dataMap.begin(); iter != dataMap.end();iter++)
    {
            int nKey = iter->first;
            string strValue = iter->second;

           if (nKey % 2 == 0)
                dataMap.erase(iter);    //错误
    }
}

解析:dataMap.erase(iter)之后,iter就已经失效了,所以iter无法自增,即iter++就会出bug.解决方案,就是在iter失效之前,先自增。
修改代码

void mapTest()
{
    map<int, string> dataMap;


    for (int i = 0; i < 100; i++)
    {
           string strValue = "Hello, World";

            stringstream ss;
            ss<<i;
            string tmpStrCount;
            ss>>tmpStrCount;
            strValue += tmpStrCount;
            dataMap.insert(make_pair(i, strValue));
    }

    cout<<"MAP元素内容为:"<<endl;
    map<int, string>::iterator iter;
    for (iter = dataMap.begin(); iter != dataMap.end(); iter++)
    {
            int nKey = iter->first;
            string strValue = iter->second;
            cout<<strValue<<endl;
    }

    cout<<"内容开始删除:"<<endl;
    for (iter = dataMap.begin(); iter != dataMap.end();)
    {
            int nKey = iter->first;
            string strValue = iter->second;

           if (nKey % 2 == 0)
           {
                dataMap.erase(iter++);
                auto a = iter;

           }
/*
if (nKey % 2 == 0)
         {
               map<int, string>::iterator tmpIter = iter;
           iter++;
               dataMap.erase(tmpIter);
               //dataMap.erase(iter++)  

         }
这样也可以
*/
           else {
               iter ++;
           }
    }
}

三、链表式容器

对于链表式容器(如list),删除当前的iterator,仅仅会使当前的iterator失效,这是因为list之类的容器,使用了链表来实现,插入、删除一个结点不会对其他结点造成影响。只要在erase时,递增当前iterator即可,并且erase方法可以返回下一个有效的iterator。

方式一:递增当前iterator

for (iter = cont.begin(); it != cont.end();)
{
   (*iter)->doSomething();
   if (shouldDelete(*iter))
      cont.erase(iter++);
   else
      ++iter;
}

方式二:通过erase获得下一个有效的iterator

for (iter = cont.begin(); iter != cont.end();)
{
   (*it)->doSomething();
   if (shouldDelete(*iter))
      iter = cont.erase(iter);  //erase删除元素,返回下一个迭代器
   else
      ++iter;
}

标签:iterator,迭代,++,iter,erase,C++,失效
From: https://www.cnblogs.com/AndreaDO/p/18063517

相关文章

  • C++左值右值完美转发转移
    左值(Lvalue)与右值(Rvalue)英文含义:左值(Lvalue):Locatorvalue,意味着它指向一个具体的内存位置。右值(Rvalue):Readvalue,指的是可以读取的数据,但不一定指向一个固定的内存位置。定义左值:指的是一个持久的内存地址。左值可以出现在赋值操作的左侧或右侧。例如,变量、数组的元素......
  • [c++] c++ 中的左右值
    c++中的左右值前言:最近又需要再次复习一下关于c++中lvaue和rvalue相关的知识。左值和右值简单看inta=1;这条语句,对于左边的a,我们是可以对其取地址的,而对于右边的1来说,我们无法对其去地址。对于能够取地址的a,位于=左边,我们就将其称之为左值,对于像1这样的......
  • jQuery中使用箭头函数,调用$(this)失效?
    1.问题在jQuery中使用箭头函数,最后调用$(this)发现无效?$(function(){//鼠标经过$('.nav>li').mouseover(()=>{//$(this)jQuery当前元素this不要加引号//show()显示元素hide()隐藏元素$(this).children('ul').show();}......
  • C++ 17新特性
    C++17是C++语言的一个重要版本,引入了许多新特性和改进,以提高开发效率和代码质量。以下是一些常用的C++17新特性:结构化绑定(StructuredBindings):允许以声明式语法将复合类型(如元组、数组、结构体)中的成员绑定到变量上,从而简化代码并提高可读性。#include<tuple>std::tup......
  • C++ Qt开发:QNetworkInterface网络接口组件
    Qt是一个跨平台C++图形界面开发库,利用Qt可以快速开发跨平台窗体应用程序,在Qt中我们可以通过拖拽的方式将不同组件放到指定的位置,实现图形化开发极大的方便了开发效率,本章将重点介绍如何运用QNetworkInterface组件实现查询详细的网络接口参数。在Qt网络编程中,QNetworkInterface是......
  • python迭代器、生成器与可迭代对象
    迭代(Iteration)如果给定一个list或tuple,我们可以通过for循环来遍历这个list或tuple,这种遍历我们称为迭代(Iteration),这些可以直接作用于for循环的对象统称为可迭代对象:Iterable方法是通过collections.abc模块的Iterable类型判断,一个对象是否为可迭代对象>>>fromcollections.......
  • C++ Qt开发:QHostInfo主机地址查询组件
    Qt是一个跨平台C++图形界面开发库,利用Qt可以快速开发跨平台窗体应用程序,在Qt中我们可以通过拖拽的方式将不同组件放到指定的位置,实现图形化开发极大的方便了开发效率,本章将重点介绍如何运用QHostInfo组件实现对主机地址查询功能。在Qt网络编程中,QHostInfo是一个强大而灵活的组件......
  • 【C/C++】四舍五入、向上取整、向下取整
    #include<stdio.h>#include<stdint.h>doublecustom_pow(doublebase,intexponent){doubleresult=1.0;if(exponent>=0){for(inti=0;i<exponent;i++){result*=base;}}else{......
  • C++习题
    打印菱形 #include<iostream>usingnamespacestd;intmain(){cout<<"*"<<endl;cout<<"***"<<endl;cout<<"*"<<endl;return0;} 进制转换#include<iostream>#include<iomanip&g......
  • c++小知识(2)
    一、引用和指针的区别:指针:从本质上讲就是存放变量地址的一个变量,在逻辑上是独立的,它可以被改变,包括其所指向的地址的改变和其指向的地址中所存放的数据的改变。引用:是一个别名,它在逻辑上不是独立的,它的存在具有依附性,所以引用必须在一开始就被初始化,而且其引用的对......