很早就决定要好好研究一下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.