欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

迭代器失效的几种情况

程序员文章站 2024-02-21 14:23:16
...

关于迭代器失效,,今天做一个总结。

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

1、对于序列式容器,比如vector,删除当前的iterator会使后面所有元素的iterator都失效。

举例如下:

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

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

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

看结果:
迭代器失效的几种情况

这是因为顺序容器内存是连续分配(分配一个数组作为内存),删除一个元素导致后面所有的元素会向前移动一个位置。(删除了一个元素,该元素后面的所有元素都要挪位置,所以,iter++,已经指向的是未知内存)。
所以对vector的任何操作,一旦引起控件重新配置,指向原vector的所有迭代器就都失效了。

但是erase方法可以返回下一个有效的iterator,这样删除后iter指向的元素后,返回的是下一个元素的迭代器,这个迭代器是vector内存调整过后新的有效的迭代器。

解决方法为:

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

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

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

2、对于链表型数据结构,比如list,使用了不连续分配的内存,删除运算使指向删除位置的迭代器失效,但是不会失效其他迭代器。

解决办法有两种:
与vector类似,erase(*iter)会返回下一个有效迭代器的值,或者erase(iter++)。

3、对于关联容器式(如map, set,multimap,multiset),删除当前的iterator,仅仅会使当前的iterator失效
举例如下:

void mapTest()
{
    map<int, string> dataMap;
    for (int i = 0; i < 10; 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);
        }
        /* cout<<iter->second<<endl;*/
    }
}

结果:
迭代器失效的几种情况

解决方法:
在erase时,返回值为void,所以我们需要递增当前iterator。
比如:

m.erase(iter++);//先把iter传值到erase里面,然后iter自增,然后执行erase。

如下:

for (iter = dataMap.begin(); iter != dataMap.end(); iter++)
    {
        int nKey = iter->first;
        string strValue = iter->second;
        if (nKey % 2 == 0)
        {
            dataMap.erase(iter++);
        }
        /* cout<<iter->second<<endl;*/
    }

这是因为map之类的容器,使用了红黑树来实现,虽然删除了一个元素,整棵树也会调整,以符合红黑树或者二叉树的规范,但是单个节点在内存中的地址没有变化,变化的是各节点之间的指向关系。

相关标签: 迭代器