发现stl的deque做随机的删除比list还要快啊
下面这个程序，构造了有5万个整数的deque和list,做查找和删除操作。发现deque比list要快。
我是在VC下面做的，deque大概花了11s，list花了将尽26s。

不是说list做删除/插入操作更快的么? 很疑惑啊。

C/C++ code

#include"stdafx.h"#include<algorithm>#include<iostream>#include<iterator>#include<string>#include<deque>#include<list>#include<vector>using namespace std;int main(void){#define LOOP 50000        typedef int valuetype;        typedef deque<valuetype> di;        typedef list<valuetype> li;        {                di vdi;                for(int i=0;i<LOOP;++i){                        vdi.push_back(1);                        vdi.push_back(2);                }                DWORD ret1=GetTickCount();                        for(int i=0;i<LOOP*2;++i){                        di::iterator it=find(vdi.begin(),vdi.end(),2);                        if(it!=vdi.end())vdi.erase(it);                }                DWORD ret2=GetTickCount();                        cout<<"deque shrink:"<<ret2-ret1<<endl;        }        {                li vli;                for(int i=0;i<LOOP;++i){                        vli.push_back(1);                        vli.push_back(2);                }                DWORD ret1=GetTickCount();                        for(int i=0;i<LOOP*2;++i){                        li::iterator it=find(vli.begin(),vli.end(),2);                        if(it!=vli.end())vli.erase(it);                }                DWORD ret2=GetTickCount();                        cout<<"list shrink:"<<ret2-ret1<<endl;        }        return 0;}

[解决办法]
你添的数据都一样，因此查找和删除不是在头部就是尾部，这样明显deque快
[解决办法]
list的遍历比deque慢很多，所以数据类型比较小的话还是用deque比较好。
[解决办法]
你把find的时间也算进去了，list是双链表，遍历速度慢
li::iterator it=find(vli.begin(),vli.end(),pSort[i]);
[解决办法]
你在deque的中间进行删除数据试试，看看那个快，你不是用了5万个数吗，你对deque的第24000个数进行删除和对list的第24000个数删除试试，看看哪个快？
[解决办法]
find函数影响了你的测试结果。

以下测试方法：建立2000个list,2000个deque，每个list和每个deque均拥有2000个元素。
第1个list删除自己的第1个元素，第1个deque删除自己的第1个元素；
第2个list删除自己的第2个元素，第2个deque删除自己的第2个元素；
……
第2000个list删除它的第2000个元素，第2000个deque删除自己的第2000个元素；

最后统计2000个list总共删除2000次元素的时间，2000个deque删除2000次元素的时间。

C/C++ code

#include"stdafx.h"#include<windows.h>#include<algorithm>#include<iostream>#include<iterator>#include<string>#include<deque>#include<list>#include<vector>using namespace std;int main(void){#define ARRAY_COUNT 2000    typedef int valuetype;    typedef vector<valuetype> vi;    typedef deque<valuetype> di;    typedef list<valuetype> li;    li *pListArray = new li[ARRAY_COUNT];    di *pDequeArray = new di[ARRAY_COUNT];    vi *pVectorArray = new vi[ARRAY_COUNT];    for(int i=0; i<ARRAY_COUNT; ++i){        for (int j = 0; j < ARRAY_COUNT; j++)        {            pListArray[i].push_back(j);            pDequeArray[i].push_back(j);            pVectorArray[i].push_back(j);        }    }    vi::iterator *viArray = new vi::iterator[ARRAY_COUNT];    di::iterator *diArray = new di::iterator[ARRAY_COUNT];    li::iterator *liArray = new li::iterator[ARRAY_COUNT];    for (int i = 0; i < ARRAY_COUNT; i++)    {         viArray[i] = find(pVectorArray[i].begin(), pVectorArray[i].end(), i);         diArray[i] = find(pDequeArray[i].begin(), pDequeArray[i].end(), i);         liArray[i] = find(pListArray[i].begin(), pListArray[i].end(), i);    }    {        DWORD ret1=GetTickCount();        for(int i=0;i<ARRAY_COUNT;++i){            pVectorArray[i].erase(viArray[i]);        }        DWORD ret2=GetTickCount();        cout<<"vector erase:"<<ret2-ret1<<endl;    }    {        DWORD ret1=GetTickCount();        for(int i=0;i<ARRAY_COUNT;++i){            pDequeArray[i].erase(diArray[i]);        }        DWORD ret2=GetTickCount();        cout<<"deque erase:"<<ret2-ret1<<endl;    }    {        DWORD ret1=GetTickCount();        for(int i=0;i<ARRAY_COUNT;++i){            pListArray[i].erase(liArray[i]);        }        DWORD ret2=GetTickCount();        cout<<"list erase:"<<ret2-ret1<<endl;    }    delete[] pListArray;    delete[] pDequeArray;    delete[] pVectorArray;    return 0;}