发现list的remove操作比find+erase要慢，为什么?该怎么解决

发现list的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;}

这个程序运行了40-50s的时间。
如果我把for循环当中的remove换成我注释掉了的
li::iterator it=find(vli.begin(),vli.end(),pSort[ i ]);
if(it!=vli.end())vli.erase(it);

再次运行，发现所用时间在15s左右。
这是为什么呢?



[解决办法]
因为remove是删除所有的，所以每次遍历整个链表找到所有的。
find,erase很明显就删一个，扫描量少。

查看更多 下一篇