聊聊map和vector的迭代器失效问题（某公司招聘笔试试题）

逃离我推掉我的手 2022-03-19 10:26 173阅读 0赞

当删除一个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, 折磨你我， 何不提前防范呢？

再分享一下我老师大神的人工智能教程吧。零基础！通俗易懂！风趣幽默！还带黄段子！希望你也加入到我们人工智能的队伍中来！[https://blog.csdn.net/jiangjunshow][https_blog.csdn.net_jiangjunshow]

[https_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485