C++ 迭代器失效的问题

 

转载自：http://blog.csdn.net/zhongjiekangping/article/details/5624922

众所周知当使用一个容器的insert或者erase函数通过迭代器插入或删除元素"可能"会导致迭代器失效，因此很多建议都是让我们获取insert或者erase返回的迭代器，以便用重新获取新的有效的迭代器进行正确的操作：

view plaincopy to clipboardprint?
iter=vec.insert(iter);   
 iter=vec.erase(iter);      
  想想究竟为什么迭代器失效，原因也不难理解。以vector为例，当我们插入一个元素时它的预分配空间不够时，它会重新申请一段新空间，将原空间上的元素复制到新的空间上去，然后再把新加入的元素放到新空间的尾部，以满足vector元素要求连续存储的目的。而后原空间会被系统撤销或征做他用，于是指向原空间的迭代器就成了类似于“悬垂指针”一样的东西，指向了一片非法区域。如果使用了这样的迭代器会导致严重的运行时错误就变得很自然了。这也是许多书上叙述vector在insert操作后“可能导致所有迭代器实效”的原因。但是想到这里我不禁想到vector的erase操作的叙述是“会导致指向删除元素和删除元素之后的迭代器失效”。但是明显感觉erase带来失效要比insert来得轻得多。似乎“此失效非彼失效”，想想似乎也是这样的：erase操作是在原空间上进行的，假设有一个存有"12345"序列的vector<int>容器原本指向3的迭代器在我删除2之后无非变成指向4了，我只要注意别用到超过end位置的迭代器不就行了吗?

  说了这么多似乎可以归纳一下迭代器失效的类型了：

  1.由于容器元素整体“迁移”导致存放原容器元素的空间不再有效，从而使得指向原空间的迭代器失效。

  2.由于删除元素使得某些元素次序发生变化使得原本指向某元素的迭代器不再指向希望指向的元素。

  对于第一种类型没什么好就是的了，原因应该确定如此了。可对于第二种，我写了如下的代码

view plaincopy to clipboardprint?
vector<int> vec;   
for(int i=0;i<10;i++)   
vec.push_back(i);   
 
vector<int>::iterator iter =vec.begin()+2;   
vec.erase(iter);//注:这里真的不建议这么写   
cout<<*iter<<endl;   
for(vector<int>::iterator it=vec.begin();it!=vec.end();it++)   
cout<<*it<<endl; 

   按照我的猜测尽管我在注释的位置的写法很“危险”，但是我并未涉及到上面总结第一种失效类型的范畴。程序应该还是会如预期的一样删除在vec[2]位置上的2然后输出前移到vec[2]位置上的3，并输出0到10不含2的所有数字，于是vs2008的c++环境下运行一下,竟然一个是个无情的“红叉”。按道理说这种写法是绝对不对出现严重的运行时错误的，难道是猜测得不对吗？

   当时被这样的疑问困扰了几天，有一天突然想起一个关于容器迭代器作参数的例子，在vs2008下运行不了，但是在vc6.0下却可以，有人说是因为08采用了更为严格的类型检测机制。于是将上面的代码放到6.0里，果然得到了预期的效果，看来系统果然是这么处理的。至于08为什么不可以，现在我只能认为是采用了更加安全的检查机制。使得第二种类型的失效后果同样“不可饶恕”。

  这样我就又想到假如insert元素时原空间够用的话，是不是也不会产生第一类失效而产生第二类失效呢？

view plaincopy to clipboardprint?
vector<int> vec;   
for(int i=0;i<10;i++)   
    vec.push_back(i);   
       cout<<"capacity:"<<vec.capacity()<<endl;//查看预分配空间大小   
vector<int>::iterator iter =vec.begin()+2;   
vec.insert(iter,100);   
cout<<"capacity:"<<vec.capacity()<<endl;     
cout<<*iter<<endl;   
for(vector<int>::iterator it=vec.begin();it!=vec.end();it++)   
cout<<*it<<endl;  
   
  同样在vc6.0下，证明了假设是对的。但是上面的种种做法只是为了帮助我理解迭代器实效的原因，建议使用insert和erase操作时还是像许多书中介绍的如第一段代码那样的写法，这是一种好的且安全的习惯。总之一句话去相信“insert和erase操作后所有的迭代器都会失效”。


迭代器（iterator）是一个可以对其执行类似指针的操作（如：解除引用（operator*()）和递增（operator++()））的对象，我们可以将它理解成为一个指针。但它又不是我们所谓普通的指针，我们可以称之为广义指针，你可以通过sizeof（vector::iterator）来查看，所占内存并不是4个字节。

    首先对于vector而言，添加和删除操作可能使容器的部分或者全部迭代器失效。那为什么迭代器会失效呢？vector元素在内存中是顺序存储，试想：如果当前容器中已经存在了10个元素，现在又要添加一个元素到容器中，但是内存中紧跟在这10个元素后面没有一个空闲空间，而vector的元素必须顺序存储一边索引访问，所以我们不能在内存中随便找个地方存储这个元素。于是vector必须重新分配存储空间，用来存放原来的元素以及新添加的元素：存放在旧存储空间的元素被复制到新的存储空间里，接着插入新的元素，最后撤销旧的存储空间。这种情况发生，一定会导致vector容器的所有迭代器都失效。

我们看到实现上述所说的分配和撤销内存空间的方式以实现vector的自增长性，效率是极其低下的。为了使vector容器实现快速的内存分配，实际分配的容器会比当前所需的空间多一些，vector容器预留了这些额外的存储区，用来存放新添加的元素，而不需要每次都重新分配新的存储空间。你可以从vector里实现capacity和reserve成员可以看出这种机制。

    capacity和size的区别：size是容器当前拥有的元素个数，而capacity则指容器在必须分配新存储空间之前可以存储的元素总数。

    vector迭代器的几种失效的情况： 1.当插入（push_back）一个元素后，end操作返回的迭代器肯定失效。 2.当插入(push_back)一个元素后，capacity返回值与没有插入元素之前相比有改变，则需要重新加载整个容器，此时first和end操作返回的迭代器都会失效。 3.当进行删除操作（erase，pop_back）后，指向删除点的迭代器全部失效；指向删除点后面的元素的迭代器也将全部失效。

    deque迭代器的失效情况： 在C++Primer一书中是这样限定的： 1.在deque容器首部或者尾部插入元素不会使得任何迭代器失效。 2.在其首部或尾部删除元素则只会使指向被删除元素的迭代器失效。 3.在deque容器的任何其他位置的插入和删除操作将使指向该容器元素的所有迭代器失效。但是：我在vs2005测试发现第一条都不满足，不知为何？等以后深入STL以后慢慢的领会吧！

    只有list的迭代器好像很少情况下会失效。也许就只是在删除的时候，指向被删除节点的迭代器会失效吧，其他的还没有发现。