【转】失效迭代器(Invalidating Iterators)

 
当一个容器变化时,指向该容器中元素的迭代器可能失效。这使得在迭代器变化期间改变容器容易出现问题。在这方面,不同的容器提供不同的保障:
vectors: 引起内存重新分配的插入运算使所有迭代器失效,插入也使得插入位置及其后位置的迭代器失效,删除运算使得删除位置及其后位置的迭代器失效.
vector的push_back操作可能没事,但是一旦引发内存重分配,所有迭代器都会失效;
vector的insert操作插入点之后的所有迭代器失效;但一旦引发内存重分配,所有迭代器都会失效;
vector的erase操作插入点之后的所有迭代器失效;
vector的reserve操作所有迭代器失效(因为它导致内存重分配);

list/map: 插入不会使得任何迭代器失效;删除运算使指向删除位置的迭代器失效,但是不会失效其他迭代器.
deque的insert操作所有迭代器失效;
deque的erase操作所有迭代器失效;

1. 对于关联容器(如map, set, multimap,multiset),删除当前的iterator,仅仅会使当前的iterator失效,只要在erase时,递增当前iterator即可。这是因为map之类的容器,使用了红黑树来实现,插入、删除一个结点不会对其他结点造成影响。erase迭代器只是被删元素的迭代器失效,但是返回值为void,所以要采用erase(iter++)的方式删除迭代器。
for (iter = cont.begin(); it != cont.end();)
{
   (*iter)->doSomething();
   if (shouldDelete(*iter))
      cont.erase(iter++);
   else
      ++iter;
}

2. 对于序列式容器(如vector,deque),删除当前的iterator会使后面所有元素的iterator都失效。这是因为vetor,deque使用了连续分配的内存,删除一个元素导致后面所有的元素会向前移动一个位置。所以不能使用erase(iter++)的方式,还好erase方法可以返回下一个有效的iterator。
for (iter = cont.begin(); iter != cont.end();)
{
   (*it)->doSomething();
   if (shouldDelete(*iter))
      iter = cont.erase(iter); 
   else
      ++iter;
}
3. 对于list来说,它使用了不连续分配的内存,并且它的erase方法也会返回下一个有效的iterator,因此上面两种方法都可以使用。

删除数组中某个元素后连续重复的元素,例如 1,1,2,3,3,1,1,1,4,0 ---> 1, 2,3,1,4,0。给出问题的一个正确的实现:
[cpp] view plaincopy
 
  1. #include <iostream>  
  2. #include <vector>  
  3. using namespace std;  
  4.   
  5. int main(int argc, char* argv[])  
  6. {  
  7.    int a[] = {1, 1, 3, 3, 3, 2, 4, 1, 1, 1, 0};  
  8.    int size = sizeof(a)/sizeof(a[0]);  
  9.   
  10.   
  11.    vector<int> vec(a, a+size);  
  12.   
  13.   
  14.    vector<int>::iterator iter = vec.begin();  
  15.    int previous = *iter;  
  16.    ++iter;  
  17.    for (; iter != vec.end();)  
  18.    {          
  19.       if(*iter == previous)  
  20.       {  
  21.          iter = vec.erase(iter);  
  22.       }  
  23.       else  
  24.       {  
  25.          previous = *iter;  
  26.          ++iter;  
  27.       }      
  28.    }  
  29.   
  30.   
  31.    for(iter = vec.begin(); iter != vec.end(); ++iter)  
  32.    {  
  33.       cout << *iter << endl;  
  34.    }  
  35.      
  36.    return 0;  
  37. }  
PS. 不过实际上这个问题,用vector来实现不是很适合,因为每次删除一个元素,都会引起vector的一个resize操作。resize的时间复杂度是O(n),整个的resize操作要花费O(n^2)。最好是选择list最为容器,list最适合那些需要在容器中间做插入、删除的例子。

【转】失效迭代器(Invalidating Iterators)

上一篇:APIO 2019 桥梁


下一篇:hdp 2.06 安装备忘