C++容器——迭代器使用的一个陷阱

• 在项目开发中遇到一个很诡异的bug：使用迭代器循环删除一个std::set容器里的几个元素，但最后发现容器里的对应元素并没有被删除干净，为了说明这个场景，我们来看一个代码片段，这是我为了重现该问题，弄了的一段测试代码。

  int numList[6]={1,2,2,3,3,3};
  //1.set add
  set<int> numSet;
  for(int i=0;i<6;i++)
  {
      //2.1insert into set
      numSet.insert(numList[i]);
  }
  //2.travese set
  for(set<int>::iterator it=numSet.begin() ;it!=numSet.end();it++)
  {
      cout<<*it<<" occurs "<<endl;
  }
  cout<<"before delete numSet.size()= "<<numSet.size()<<endl;
  for(set<int>::iterator it = numSet.begin(); it != numSet.end(); it++)
  {
      cout<<"delete " <<*it <<endl;
      numSet.erase(it);
  }
  cout<<"after delete numSet.size()= "<<numSet.size()<<endl;

  这段测试代码的功能很简单，构造一个set容器，把几个数字塞进去，然后通过它的迭代器循环清除里面的元素，大家可以想一下for循环前后的这两句log输出的是什么。

• 这是输出的结果

  before delete numSet.size()= 3
  delete 1
  after delete numSet.size()= 2

• 是不是和你们很多人预想的不太一样，for循环只循环了一次就跳出去了，那说明第一次循环结束再回到for循环条件判断时it!=umSet.end()不成立了，it指向了容器的end，验证一下。

  for(set<int>::iterator it=numSet.begin();(cout<< (it == numSet.end() ? "end":"not end")<<endl, it!=numSet.end());it++) {
      cout<<"delete " <<*it <<endl;
      numSet.erase(it);
      cout<< (it == numSet.end() ? "end":"not end")<<endl;
  }

  输出结果：

  before delete numSet.size()=3
  not end
  1 delete
  not end
  end
  after delete numSet.size()=2

  确实是这样，在网上查阅了一下使用迭代器删除元素的方法，有两条注意事项：

  1.对于关联容器（如map，set，multimap，multiset），删除当前的iterator，仅仅会使当前的iterator失效，只要在erase时，递增当前的iterator即可。这是因为map之类的容器，使用了红黑树来实现，插入，删除一个结点不会对其他结点造成影响。

• 这样对于关联容器，正确的使用迭代器的方法是这样：

  for(set<int>::iterator it=numSet.begin(); it!=numSet.end());) {
      cout<<"delete " <<*it <<endl;
      numSet.erase(it++);
  }

  2.对于序列式容器（如vector，deque，list等），删除当前的iterator会使后面所有元素的iterator都失效。这是因为vector，deque使用了连续分配的内存，删除一个元素导致后面所有的元素会向前移动一个位置。不过erase方法可以返回下一个有效的iterator。

• 而对于序列容器，正确的方法应该是这样：

  for(set<int>::iterator it=numSet.begin(); it!=numSet.end());) {
      cout<<"delete " <<*it <<endl;
      it = numSet.erase(it);
  }

就是这么一个很小的点，都怪平时使用的时候太过于理所当然了，迭代器的使用还是要小心，此为记。