讨论vector的删除操作

很早就决定要好好研究一下C++标准模板库的实现,不过到现在为止,也只是对vector了解多一点, 呵呵。今天又看了关于vector::erase()方法的讨论帖,就在终端里man std::vector了一下, 以前看的,已不大记得了,现在再来分析分析。

注意:我研究的是GNU的c++4.4.1版本,而且关于erase()方法有两个,如下:

iterator erase(iterator __first, iterator __last);
iterator erase(iterator __position);

我这里只关注第二个,因为其中道理是一样的。

直接解读源码是最有效的方法,代码如下:

template<typename _Tp, typename _Alloc>
typename vector<_Tp, _Alloc>::iterator
vector<_Tp, _Alloc>::erase(iterator __position)
{
     if (__position + 1 != end())
            _GLIBCXX_MOVE3(__position + 1, end(), __position);
     --this->_M_impl._M_finish;
     this->_M_impl.destroy(this->_M_impl._M_finish);
     return __position;
}

代码还是相当简单的,vector是一个模板类,所以它是一个模板函数是肯定的。 erase()的参数是一个迭代器,stl库各个类的迭代器底层实现各不相同,但是对外接口是一致的, 这也本来是迭代器的初衷,就是希望隐藏各数据结构的差异性,实现通用一致的迭代功能。 而vector的迭代器其实就是普通的指针啦!

源码中首先判断__position是不是指向了end()迭代器的前一个位置,如果不是, 那就将__position后面的所有所有元素都举家迁移,迁移到以__position开始的位置, 这样__position原来所指向的值就被覆盖了,画图表示就是这样的:

1 2 3 4 5 6 7 8 end
        ^
        +--__position
1 2 3 5 6 7 8 8 end
        ^
        +--__position

这样__position所指向的5就被如愿的删除掉了。

那么,这里为什么要做一个if判断呢,想想吧,如果__position指向的是8, 那么把后面的空值向前移是完全没有必要的,要知道如果vector中存放是一个巨大的结构体, 赋值操作,或者说是内存拷贝是很花时间的。

接下来的--this->_M_impl.M_finish;,便是把末尾指针减减,此时的末尾指针(上图中用end表示)就指向了最后那个8, 也就是第二个8,到此其实删除的目地也就达到了,但按照c语言的习惯,还要把最后清为\0, 更重要的是为了释放内存,防止内存泄漏,所以就有必要调用一下_M_impl.destroy()。最好返回__position迭代器。 其实你可以想到,__position并没有发生任何改变,它只是逛了一圈,就离开了。

以下是删除一段数据项的函数源码,你可以发现,其实是一样的覆盖伎俩:

template<typename _Tp, typename _Alloc>
typename vector<_Tp, _Alloc>::iterator
vector<_Tp, _Alloc>::erase(iterator __first, iterator __last)
{
     if (__last != end())
           _GLIBCXX_MOVE3(__last, end(), __first);
     _M_erase_at_end(__first.base() + (end() - __last));
     return __first;
}

如果你足够坏,呵呵,将末尾指针传进去,即MyVector.erase(MyVector.end());,结果当然是运行出错啦。我的测试代码为:

#include <iostream>
#include <vector>
using namespace std;

template<typename T>
void printout(T & obj)
{
     /* 显示所有元素 */
     for (typename T::iterator it=obj.begin();it!=obj.end();++it)
     {
           cout<<(*it)<<" ";
     }
     cout<<endl<<"|++++++++++++++++++++++++++++++++++++++++|"<<endl;
}

int main(int argc,char **argv)
{
     int a[] = {1,2,3,4,5,6,7,8};
     vector<int> v(a,a+8);         //用一个数组来初始化向量
     printout(v);                  //打印出结果
     v.erase(v.begin()+4);         //这里将5删除
     printout(v);                  //打印出结果
     cout<<v[7]<<endl;             //你可能会奇怪,空出来的位置值是多少
     v.erase(v.end());             //是否可以删除end()迭代器呢?
     printout(v);                  //打印出结果

     return 0;
}

运行结果为:

1 2 3 4 5 6 7 8 
|++++++++++++++++++++++++++++++++++++++++|
1 2 3 4 6 7 8 
|++++++++++++++++++++++++++++++++++++++++|
8
Segmentation fault

这时有两点要说明,第一,这样的群体移位是很花时间的,第二,不同的库实现不一样, 删除元素后,指针是否有效,是指向前一个了,还是指向了后一个了, 程序员不能太依赖于理想情况,要编写非常robust代码,请自己作好各方面考虑。 我就不在此多嘴了,库的作者更有发言权:

Note This operation could be expensive and if it is frequently used the user should consider using std::list. The user is also cautioned that this function only erases the elements, and that if the elements themselves are pointers, the pointed-to memory is not touched in any way. Managing the pointer is the user's responsibility.

发表于 2010年04月21日 06:47   评论:0   阅读:2121  



回到顶部

首页 | 关于我 | 关于本站 | 站内留言 | rss
python logo   django logo   tornado logo