勤能补拙,Expter

成都游戏Coder,记录游戏开发过程的笔记和心得!

一个关于容器选取的删除问题。


问题描述:
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) + 1this->_Mylast,
            _VIPTR(_Where));
        _Destroy(
this->_Mylast - 1this->_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容器还要慢?
还是上面的代码不能说明问题。

posted on 2011-01-14 14:58 expter 阅读(2351) 评论(2)  编辑 收藏 引用 所属分类: 其他学习笔记工作笔记算法与数据结构

评论

# re: 一个关于容器选取的删除问题。 2011-01-17 18:42 小笨象

如果vector从最后一个开始删除呢?
有没有试过?  回复  更多评论   

# re: 一个关于容器选取的删除问题。 2011-01-18 00:09 expter

@小笨象
你说那个确实可以提高效率。

只是不解禁用优化后,list比map快,不禁用map缺比list快。。
  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理