发现list的remove操作比find+erase要慢,为什么?该怎么解决
发现list的remove操作比find+erase要慢,为什么?
网上很多人说list的remove要比erase快。
我用VC测试了一下,发现并非如此,生成50000个随机数,逐个删除:
如果我把for循环当中的remove换成我注释掉了的
li::iterator it=find(vli.begin(),vli.end(),pSort[ i ]);
if(it!=vli.end())vli.erase(it);
再次运行,发现所用时间在15s左右。
这是为什么呢?
------解决方案--------------------
因为remove是删除所有的,所以每次遍历整个链表找到所有的。
find,erase很明显就删一个,扫描量少。
网上很多人说list的remove要比erase快。
我用VC测试了一下,发现并非如此,生成50000个随机数,逐个删除:
- C/C++ code
#include"stdafx.h" #include<windows.h> #include<algorithm> #include<iostream> #include<iterator> #include<string> #include<deque> #include<list> #include<map> #include<vector> using namespace std; int main(void){ #define LOOP 50000 #define TOTAL LOOP*2 typedef int valuetype; typedef list<valuetype> li; int* pRand=new int[TOTAL]; int* pSort=new int[TOTAL]; for(int i=0;i<TOTAL;++i){ pRand[i]=rand(); } copy(pRand,pRand+(TOTAL),pSort); sort(pSort,pSort+(TOTAL),less<int>()); { li vli; for(int i=0;i<TOTAL;++i){ vli.push_back(pRand[i]); } DWORD ret1=GetTickCount(); for(int i=0;i<TOTAL;++i){ //li::iterator it=find(vli.begin(),vli.end(),pSort[ i ]); //if(it!=vli.end())vli.erase(it); vli.remove(pSort[ i ]); } DWORD ret2=GetTickCount(); cout<<"list shrink:"<<ret2-ret1<<endl; } return 0; }
如果我把for循环当中的remove换成我注释掉了的
li::iterator it=find(vli.begin(),vli.end(),pSort[ i ]);
if(it!=vli.end())vli.erase(it);
再次运行,发现所用时间在15s左右。
这是为什么呢?
------解决方案--------------------
因为remove是删除所有的,所以每次遍历整个链表找到所有的。
find,erase很明显就删一个,扫描量少。