STL中vector迭代器老调重弹的失效问题


    我们都很了解,STL中迭代器遍历的时候,有个很严峻的问题,失效。但是,我们一直没有对失效下过严格的定义。最早,接触迭代器失效时,是从别人的博客上了解的。当时对整体也没一个明确的概念,只是看博客上写了插入的时候可能会失效,就这么记下了。到现在,自己看了STL中插入的源码,才开始了解,插入的时候,迭代器失效是个什么原因。

插入时迭代器失效

插入的时候,如果当前集合的大小已达到最大容量,此时,集合会成倍地扩展内存,重新分配一块新的内存,然后将旧的数据拷贝到新内存块上,再将旧内存数据释放。

    当遇到扩展内存的时候,原来的迭代器就都无效了。因为它们指向的内存已被释放,它们成为了悬垂指针。而这就是我们说的第一种失效:迭代器指向的空间被释放,迭代器成为悬垂指针

stl_vector.h

  iterator insert(iterator __position, const _Tp& __x) {
    //在指定位置插入内存
    size_type __n = __position - begin();
    //判断集合中的结束指针_M_finish是否指向内存块的结束指针;并且插入的位置是否是集合的_M_finish指向的结束位置
    if (_M_finish != _M_end_of_storage && __position == end()) {
     //集合未满,且是插入在集合末尾,则直接使用未指针的空间,调用构造函数构造集合元素。
      construct(_M_finish, __x);
     //递增结束指针_M_finish
      ++_M_finish;
    }
    else
      _M_insert_aux(__position, __x);  //调用新方法插入
    return begin() + __n;
  }

template <class _Tp, class _Alloc>
void 
vector<_Tp, _Alloc>::_M_insert_aux(iterator __position, const _Tp& __x)
{
  if (_M_finish != _M_end_of_storage) {
    //集合有足够空间
    construct(_M_finish, *(_M_finish - 1));
    ++_M_finish;
    _Tp __x_copy = __x;
    //向后拷贝,first,last,result。先从last-1处拷贝到result-1,然后依次
   //递减result和last,直到first == last.即从后往前拷贝
    copy_backward(__position, _M_finish - 2, _M_finish - 1);
    *__position = __x_copy;
  }
  else {
    //集合空间不足,获取旧集合的大小
    const size_type __old_size = size();
    //判断旧集合的大小是否为0,如果是,则新集合长度设置为1,反之,则双倍扩展。
    const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
    iterator __new_start = _M_allocate(__len);
   //设置新集合的结束指针指向起始指针
    iterator __new_finish = __new_start;  
    __STL_TRY {
      //将旧集合中拷贝[_M_start, __position)处的元素到新集合中,并设置新集合的结束指针
      __new_finish = uninitialized_copy(_M_start, __position, __new_start);
     //构造x的集合元素,插入到新集合此时的尾部
      construct(__new_finish, __x);
      ++__new_finish;
       //从旧集合中拷贝[__position, _M_finish)处的元素到新集合的尾部中
      __new_finish = uninitialized_copy(__position, _M_finish, __new_finish);
    }
    //如果上面代码有抛出异常,则释放新集合的空间,将异常继续向上抛出
    __STL_UNWIND((destroy(__new_start,__new_finish), 
                  _M_deallocate(__new_start,__len)));
    //析构集合中的元素
    destroy(begin(), end());
    //释放集合分配的空间
    _M_deallocate(_M_start, _M_end_of_storage - _M_start);
   //设置新集合的起始指针,结束指针为当前集合的起始和结束指针
    _M_start = __new_start;
    _M_finish = __new_finish;
    _M_end_of_storage = __new_start + __len;
  }
}
从上面代码,很清晰的看出,插入的时候,如果遇到集合扩张,那么旧的迭代器就会指向已被释放的空间。

删除时迭代器失效

迭代器删除的代码非常简单,就几行。让我们先看下源码。

stl_vector.h

//删除一个迭代器  
iterator erase(iterator __position) {
    if (__position + 1 != end())
      //如果删除的迭代器不是指向结束指针的前一个元素
     //那么就要拷贝[__position+1, _M_finish) 到以__position为起始的空间中.
   //用通俗的话说,就是从position+1开始,整体向前挪一个位置
      copy(__position + 1, _M_finish, __position);
   //递减结束指针
    --_M_finish;
    //析构结束指针的元素。因为结束指针是不可用的。
    destroy(_M_finish);
   
   //返回删除的位置
    return __position;
  }
从源码中,我们看到,删除时,被没有空间被重新分配的问题。所以,旧的迭代器不会出现插入时的那种失效问题。但是认真的我们会发现,集合中的元素,范围[__position, _M_finish)内的元素,整体向前挪动了一个位置。所以,此时旧的迭代器指向的对象,实际上是指向了原来对象的下一个元素。


    所以我们说,第二种失效:迭代器指向的对象发生改变,被替换,不是原来的对象。

对于删除的迭代器问题,我们可以看一段示例代码,验证下我们的分析是否是正确。

 vct_erase.cpp  

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template<class T>
int Print(vector<T> & vct)
{
        for(int i = 0; i < vct.size(); ++i)
        {
                cout<<vct[i]<<",";
        }

        cout<<endl;
}

int main()
{
        int a[10] = {1,3,5,7,9,10,12,14,20,23};
        vector<int> demo(a, a+10);

        Print(demo);

        vector<int>::iterator it = find(demo.begin(), demo.end(), 14);

        demo.erase(it);
        cout<<*it<<endl;

        Print(demo);

运行结果如下:

1,3,5,7,9,10,12,14,20,23,
20
1,3,5,7,9,10,12,20,23,
    很明显,被删除的迭代器it,原来指向的是待删除的元素14,调用了erase后,it指向了14的下一个元素20.这是在g++编译器上。听说在vs2008上,这么写是不被支持的,有时间我再验证下vs是否有更严格的检查机制。

总结

总结分析来看,在具体的类型上看,迭代器失效是有两种:1.迭代器成为悬垂指针;2.迭代器指向的对象被替换。那么,从抽象的层次上看,又好像可以归纳为一种:迭代器不再指向原来的对象,所以无效




评论

发表评论