讨论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.