问题描述:
1个容器有大量元素，需要进行erase大部分数据的时候，需要遍历这些元素，然后释放item的空间，还要erase删除其item。
一个库，为了测试其性能的时候，需要保存所有外部使用者的数据，这里选取了map,vector和list.
为了简化问题，我写了下面测试代码来测试各个操作:
数据节点:
struct node
{
node(int i){data = i;}
int data;
} 1int _tmain(int argc, _TCHAR* argv[])
2{
3 typedef std::map<long,node*> Mptable;
4 typedef std::vector<node*> Vec;
5 typedef std::list<node*> List;
6
7 Mptable mapnode;
8 Vec vecnode;
9 List listnode;
10
11 for(int i = 1 ; i <= 100000 ; i++ )
12 {
13 mapnode [ i ] = new node(i);
14 vecnode.push_back( new node(i) );
15 listnode.push_back( new node(i));
16
}
17
18 long time = timeGetTime( );
19
20 for( Mptable::iterator itr = mapnode.begin() ; itr != mapnode.end() ; )
21 {
22 delete itr->second;
23 mapnode.erase( itr++ );
24 }
25
26 std::cout <<"map : spend " << timeGetTime() - time << " msec " << std::endl;
27
28
29 time = timeGetTime( );
30
31 for( Vec::iterator itr = vecnode.begin() ; itr != vecnode.end() ; )
32 {
33 delete *itr;
34 itr = vecnode.erase( itr );
35 }
36
37 std::cout <<"vector : spend " << timeGetTime() - time << " msec " << std::endl;
38
39
40 time = timeGetTime( );
41
42 for( List::iterator itr = listnode.begin() ; itr != listnode.end() ; )
43 {
44 delete *itr;
45 itr = listnode.erase( itr );
46 }
47
48 std::cout <<"list : spend " << timeGetTime() - time << " msec" << std::endl;
49
50
51 return 0;
52}
Release下运行结果:
map : spend 31 msec
vector : spend 3734 msec
list : spend 35 msec
发现map的速度最快，vector最慢，list相当。
其实vector就是一个Array,只是Array是静态大小，vector可以扩展，然后查看vector的erase的源码：
iterator erase(const_iterator _Where)
{ // erase element at where
_Move(_VIPTR(_Where) + 1, this->_Mylast,
_VIPTR(_Where));
_Destroy(this->_Mylast - 1, this->_Mylast);
--this->_Mylast;
return (_Make_iter(_Where));
}
有一个move操作，原来把当前iterator+1的往前移了，这样的话会遍历iterator后面所有的元素。
关于map的erase原理可以查看map的实现源码:
由于map的erase后有一个维护过程，其实map是一个RB-Tree，删除算法相对比较麻烦，删除某个item会查找下一个item替换删除的节点，同时还要考虑红和黑的节点处理。同时还要保证map的erase后，平衡且有序。
所以map的erase主要做:
1.刪除item.
2.让树平衡，且有序。
list其实是一个双向链表:
关于删除其实是0(1)的操作，我们查看list的erase的操作:
iterator erase(const_iterator _Where)
{ // erase element at _Where
#if _ITERATOR_DEBUG_LEVEL == 2
if (_Where._Getcont() != this || _Where._Ptr == this->_Myhead)
_DEBUG_ERROR("list erase iterator outside range");
_Nodeptr _Pnode = (_Where++)._Mynode();
_Orphan_ptr(*this, _Pnode);
#else /* _ITERATOR_DEBUG_LEVEL == 2 */
_Nodeptr _Pnode = (_Where++)._Mynode();
#endif /* _ITERATOR_DEBUG_LEVEL == 2 */
if (_Pnode != this->_Myhead)
{ // not list head, safe to erase
this->_Nextnode(this->_Prevnode(_Pnode)) =
this->_Nextnode(_Pnode);
this->_Prevnode(this->_Nextnode(_Pnode)) =
this->_Prevnode(_Pnode);
_Dest_val(this->_Alnod, _Pnode);
this->_Alnod.deallocate(_Pnode, 1);
--this->_Mysize;
}
return (_Make_iter(_Where));
}
主要代码删除就是下面删除部分:
对prev和next节点进行处理即可。
关于list的移除竟然比map还要慢.
PS：测试为单线程。
当为100W数据的时候:
map : spend 300 msec
list : spend 385 msec
咋list比map容器还要慢？
还是上面的代码不能说明问题。