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