当前位置 博文首页 > 好习惯成就伟大:聊聊map和vector的迭代器失效问题(某公司招聘
?当删除一个STL容器(比如map, vector)中的某个元素时, 会引起迭代器失效, 所以, 我们务必提高警惕。 ?某次笔试, 我遇到这样一个题目: 删除map<int, int>中value为5的倍数的元素。 该题看起来很自然很简单, 实则有迭代器失效的陷阱。
?
????????如果对迭代器失效问题一无所知, 则很容易写出如下的错误代码:
?
#include <iostream>
#include <map>
using namespace std;
?
typedef map<int, int> Map;
typedef map<int, int>::iterator MapIt;
?
void print(Map &m)
{
?? ?MapIt it;
?? ?for(it = m.begin(); it != m.end(); it++)
?? ?{
?? ??? ?cout << it->second << " ";
?? ?}
?
?? ?cout << endl;
}
?
void deleteValueFromMap(Map &m, int n = 5)
{
?? ?MapIt it;
?? ?for(it = m.begin(); it != m.end(); it++)
?? ?{
?? ??? ?if(0 == it->second % n)
?? ??? ?{
?? ??? ??? ?m.erase(it);
?? ??? ?}
?? ?}
}
?
int main()
{
?? ?Map m;
?? ?int i = 0;
?? ?for(i = 0; i < 21; i++)
?? ?{
?? ??? ?m[i] = i;
?? ?}
?
?? ?print(m);
?
?? ?deleteValueFromMap(m); // 程序崩溃
?
?? ?return 0;
}
???????运行上述程序, 结果程序崩溃, 什么原因呢? 原来, 对于关联的容器map来说,?m.erase(it);后, it就失效了, 而for循环中有it++, 自然而然会出问题啊。 那怎么办呢? 且看:
?
?
#include <iostream>
#include <map>
using namespace std;
?
typedef map<int, int> Map;
typedef map<int, int>::iterator MapIt;
?
void print(Map &m)
{
?? ?MapIt it;
?? ?for(it = m.begin(); it != m.end(); it++)
?? ?{
?? ??? ?cout << it->second << " ";
?? ?}
?
?? ?cout << endl;
}
?
void deleteValueFromMap(Map &m, int n = 5)
{
?? ?MapIt it;
?? ?MapIt tmp;
?? ?for(it = m.begin(); it != m.end(); /*不能再自增了*/)
?? ?{
?? ??? ?if(0 == it->second % n)
?? ??? ?{
?? ??? ??? ?tmp = it++;
?? ??? ??? ?m.erase(tmp);
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?it++;
?? ??? ?}
?? ?}
}
?
int main()
{
?? ?Map m;
?? ?int i = 0;
?? ?for(i = 0; i < 21; i++)
?? ?{
?? ??? ?m[i] = i;
?? ?}
?
?? ?print(m);
?
?? ?deleteValueFromMap(m); // 程序ok
?? ?print(m);
?
?? ?return 0;
}
???????结果为:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 6 7 8 9 11 12 13 14 16 17 18 19
?
?
???????当然, 上述程序也可以继续简化为:
?
#include <iostream>
#include <map>
using namespace std;
?
typedef map<int, int> Map;
typedef map<int, int>::iterator MapIt;
?
void print(Map &m)
{
?? ?MapIt it;
?? ?for(it = m.begin(); it != m.end(); it++)
?? ?{
?? ??? ?cout << it->second << " ";
?? ?}
?
?? ?cout << endl;
}
?
void deleteValueFromMap(Map &m, int n = 5)
{
?? ?MapIt it;
?? ?for(it = m.begin(); it != m.end(); /*不能再自增了*/)
?? ?{
?? ??? ?if(0 == it->second % n)
?? ??? ?{
?? ??? ??? ?m.erase(it++);
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?it++;
?? ??? ?}
?? ?}
}
?
int main()
{
?? ?Map m;
?? ?int i = 0;
?? ?for(i = 0; i < 21; i++)
?? ?{
?? ??? ?m[i] = i;
?? ?}
?
?? ?print(m);
?
?? ?deleteValueFromMap(m); // 程序ok
?? ?print(m);
?
?? ?return 0;
}
???????结果ok.
?
?
???????有的朋友肯定会问,?m.erase(it++);就不会产生迭代器失效么? 确实不会! 为什么呢? 这样从it++说起, 为了简便起见, 我们用p++来代替吧。 看程序:
?
#include <iostream>
using namespace std;
?
int main()
{
?? ?char szTest[] = "abcdefg";
?? ?char *p = szTest;
?
?? ?cout << *p++ << endl;
?
?? ?return 0;
}
????????大家都知道, 结果为a. ?但是, 很多人错误地以为是先执行*p, 然后执行p++, 其实, 这是个天大的误解。 大家可以查一下*和++的执行顺序, 虽然*和++的优先级相同, 但此处采取的是右结合方式, 实际上先执行的是p++, 不过, p++的返回值是原来的p, 也就是说, *p++的值还是a.?
?
????????所以, 在m.erase(it++);中,it++先执行, 此时还没有erase, 程序自然不会崩溃. 当it++执行完后, 已经指向了下一个元素了, 但it++的返回值还是当前元素, 此时再删除它, 合情合理。
????????OK, ?map的迭代器失效问题, 我们先介绍到这里。
?
?
?????????那vector又是怎样的现象呢? 看程序:
?
#include <iostream>
#include <vector>
using namespace std;
?
typedef vector<int> Vec;
typedef vector<int>::iterator VecIt;
?
void print(Vec &v)
{
?? ?VecIt it;
?? ?for(it = v.begin(); it != v.end(); it++)
?? ?{
?? ??? ?cout << *it << " ";
?? ?}
?
?? ?cout << endl;
}
?
void deleteValueFromVector(Vec &v, int n = 5)
{
?? ?VecIt it;
?? ?for(it = v.begin(); it != v.end(); it++)
?? ?{
?? ??? ?if(0 == *it % n)
?? ??? ?{
?? ??? ??? ?v.erase(it);
?? ??? ?}
?? ?}
}
?
int main()
{
?? ?Vec v;
?? ?int i = 0;
?? ?for(i = 0; i < 21; i++)
?? ?{
?? ??? ?v.push_back(i); // 不能再傻傻地用下标了
?? ?}
?
?? ?print(v);
?
?? ?deleteValueFromVector(v); // 程序崩溃
?? ?print(v);
?
?? ?return 0;
}
???????运行程序, 结果程序也崩溃, 可见, vector也存在迭代器失效的问题, 怎么改呢? 如下:
?
?
#include <iostream>
#include <vector>
using namespace std;
?
typedef vector<int> Vec;
typedef vector<int>::iterator VecIt;
?
void print(Vec &v)
{
?? ?VecIt it;
?? ?for(it = v.begin(); it != v.end(); it++)
?? ?{
?? ??? ?cout << *it << " ";
?? ?}
?
?? ?cout << endl;
}
?
void deleteValueFromVector(Vec &v, int n = 5)
{
?? ?VecIt it;
?? ?for(it = v.begin(); it != v.end(); /*不能再自增了*/)
?? ?{
?? ??? ?if(0 == *it % n)
?? ??? ?{
?? ??? ??? ?v.erase(it); // vector元素自动向前挪动了(关联的map容器元素不会自动挪动), 所以不能再把it进行++了
?? ??? ?}
?? ??? ?else
?? ??? ?{
?? ??? ??? ?it++;
?? ??? ?}
?? ?}
}
?
int main()
{
?? ?Vec v;
?? ?int i = 0;
?? ?for(i = 0; i < 21; i++)
?? ?{
?? ??? ?v.push_back(i); // 不能再傻傻地用下标了
?? ?}
?
?? ?print(v);
?
?? ?deleteValueFromVector(v); // 程序ok
?? ?print(v);
?
?? ?return 0;
}
????????结果为:
?
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 3 4 6 7 8 9 11 12 13 14 16 17 18 19
????????可见, vector迭代器失效的问题也不容忽视。
??????
????????总之, 下次说到迭代器失效(尤其涉及到容器大小的改变, 比如删除, 插入)时, 一定要留个心眼。 ?在实际编程中, 如果稍不注意, 则可能引起非常难以捕捉的bug, 折磨你我, 何不提前防范呢?
————————————————
版权声明:本文为CSDN博主「涛歌依旧」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/stpeace/article/details/46507451