stl容器erase删除元素后iterator迭代器出错

Posted on | In , | |
Words count in article: 532 | Reading time ≈ 2

stl容器erase删除元素后iterator迭代器出错

erase容器中元素的时候，迭代器会失效

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

其实就是没有影响

1
2
3
4
5
6
7
8
for (iter = cont.begin(); it != cont.end();)
{
   (*iter)->doSomething();
   if (shouldDelete(*iter))
      cont.erase(iter++);
   else
      ++iter;
}

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

就是有影响

1
2
3
4
5
6
7
8
for (iter = cont.begin(); iter != cont.end();)
{
   (*it)->doSomething();
   if (shouldDelete(*iter))
      iter = cont.erase(iter); //erase方法可以返回下一个有效的iterator
   else
      ++iter;
}

对于list来说，它使用了不连续分配的内存，并且它的erase方法也会返回下一个有效的iterator，因此上面两种方法都可以使用。

例子

删除数组中某个元素后连续重复的元素，例如 1，1，2，3，3，1，1，1，4，0 —> 1， 2，3，1，4，0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <vector>
using namespace std;

int main(int argc, char* argv[])
{
   int a[] = {1, 1, 3, 3, 3, 2, 4, 1, 1, 1, 0};
   int size = sizeof(a)/sizeof(a[0]);

   vector<int> vec(a, a+size);

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

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

不过实际上这个问题，用vector来实现不是很适合，因为每次删除一个元素，都会引起vector的一个resize操作。resize的时间复杂度是O(n)，整个的resize操作要花费O(n^2)。最好是选择list最为容器，list最适合那些需要在容器中间做插入、删除的例子。

Donate? comment?