問題描述:
1個容器有大量元素，需要進行erase大部分數(shù)據(jù)的時候，需要遍歷這些元素，然后釋放item的空間，還要erase刪除其item。
一個庫，為了測試其性能的時候，需要保存所有外部使用者的數(shù)據(jù)，這里選取了map,vector和list.
為了簡化問題，我寫了下面測試代碼來測試各個操作:
數(shù)據(jù)節(jié)點:
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下運行結(jié)果:
map : spend 31 msec
vector : spend 3734 msec
list : spend 35 msec
發(fā)現(xiàn)map的速度最快，vector最慢，list相當。
其實vector就是一個Array,只是Array是靜態(tài)大小，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后面所有的元素。
關(guān)于map的erase原理可以查看map的實現(xiàn)源碼:
由于map的erase后有一個維護過程，其實map是一個RB-Tree，刪除算法相對比較麻煩，刪除某個item會查找下一個item替換刪除的節(jié)點，同時還要考慮紅和黑的節(jié)點處理。同時還要保證map的erase后，平衡且有序。
所以map的erase主要做:
1.刪除item.
2.讓樹平衡，且有序。
list其實是一個雙向鏈表:
關(guān)于刪除其實是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節(jié)點進行處理即可。
關(guān)于list的移除竟然比map還要慢.
PS：測試為單線程。
當為100W數(shù)據(jù)的時候:
map : spend 300 msec
list : spend 385 msec
咋list比map容器還要慢？
還是上面的代碼不能說明問題。