迭代器失效的几种情况
关于迭代器失效,,今天做一个总结。
迭代器失效分三种情况考虑,也是三种数据结构考虑,分别为数组型,链表型,树型数据结构。
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之类的容器,使用了红黑树来实现,虽然删除了一个元素,整棵树也会调整,以符合红黑树或者二叉树的规范,但是单个节点在内存中的地址没有变化,变化的是各节点之间的指向关系。
上一篇: 无重复字符的最长子串(力扣)
下一篇: OpenGL学习笔记之绘制三角形
推荐阅读
-
迭代器失效的几种情况
-
python中实现迭代器(iterator)的方法示例
-
iOS json解析出错的几种情况总结
-
在内存储器小于文件大小的情况下,大文件中快速查找定位一行
-
看看PHP迭代器的内部执行过程_PHP教程
-
iOS json解析出错的几种情况总结
-
Python中 迭代( iteration )、迭代对象( iterable )、迭代器( iterator)、生成器(generator) 的关系详细讲解
-
Python的迭代器(iterator)和生成器(generator)
-
Python中的生成器(generator)和迭代器(Iterator)
-
ES的迭代器Iterator和生成器Generator