STL中deque和list的效率比较

我在做项目的时候经常会遇到一些情况,是需要用到队列的。比如,我要维护消息队列,或者动画队列。STL中有两种容器胜任此项工作,它们分别是list和deque。list是基于链表实现的,而deque是基于动态数组实现的。《C++标准程序库》一书中介绍了两者的差别,但并没有比较两者的效率。由于今后我会经常地使用到这两种结构,因此我对两者的效率进行了一下测试。

测试的类型fuck定义如下:

struct fuck
{
int a,b,c;
}

测试平台为win7,环境为vc2010,stl版本为P.J. Plauger。

测试1:容器大小为十万个fuck,循环进行pop_back()和push_front()操作

int main()
{
int len = 100000;
list<fuck> l(len);
deque<fuck> d(len);

clock_t begin = clock();
for (int i=0; i {
d.push_front(d.back());
d.pop_back();
}
clock_t end = clock();
cout << end – begin << endl;

begin = clock();
for (int i=0; i {
l.push_front(l.back());
l.pop_back();
}
end = clock();
cout << end – begin << endl;
system(“pause”);
return 0;
}
测试结果:(毫秒)
deque   312    308    307    312
list        1046  1044  1043  1044

测试2:容器大小为十万个fuck,先使用pop_back清空,然后使用push_front插入十万个新的fuck

int main()
{
int len = 100000;
list<fuck> l(len);
deque<fuck> d(len);

clock_t begin = clock();
for (int i=0; i d.pop_back();
for (int i=0; i d.push_front(fuck());
clock_t end = clock();

begin = clock();
for (int i=0; i l.pop_back();
for (int i=0; i l.push_front(fuck());
end = clock();

return 0;
}
测试结果:(毫秒)
deque   97         96  
list        11756   11250 

这不科学……我也懒得再进行下去了

测试3:容器为空,然后使用push_front插入十万个新的fuck

int main()
{
int len = 100000;
list<fuck> l;
deque<fuck> d;

clock_t begin = clock();
for (int i=0; i<len; i++)
d.push_front(fuck());
clock_t end = clock();
cout << end – begin << endl;

begin = clock();
for (int i=0; i<len; i++)
l.push_front(fuck());
end = clock();
cout << end – begin << endl;
system(“pause”);
return 0;
}
测试结果:(毫秒)
deque   628    632    625    618
list         383    377    375    379

测试4:容器大小为十万个fuck,使用pop_back清空

int main()
{
int len = 100000;
list<fuck> l(len);
deque<fuck> d(len);

clock_t begin = clock();
for (int i=0; i<len; i++)
d.pop_back();
clock_t end = clock();
cout << end – begin << endl;

begin = clock();
for (int i=0; i<len; i++)
l.pop_back();
end = clock();
cout << end – begin << endl;
system(“pause”);
return 0;
}
测试结果:(毫秒)
deque   34         34  
list        10241   10326

事实证明,大规模的pop操作会使list慢得像吃屎,这让我很不解…… 当参照测试1的结果,我就更加不解了。希望有高手能够帮忙解答。

STL中deque和list的效率比较》上有3条评论

  1. deque在实现上是分段的,比如libc++里面是512个元素为一段,所以申请内存的时候是一段一段申请的
    list在实现上是node类型的,每次push/pop都会产生new/delete,效率自然没有deque高
    如果你找一个好的内存分配器,list的效率会提升一点,但是不会太多,因为cache missing.链表这种结构,不是CPU友好的结构,CPU很难推测出来list下一个节点的内存在那里…..

    • 一开始我是不明白deque的删除操作为何效率如此之高,我现在大概明白了。当deque执行pop_back()操作时,只是将末尾的迭代器向前移动一位;而当deque执行push_front()操作时,由于需要内存分配,因此花费时间远高于pop_back()。而对于list来说,删除和添加节点的花费是一样的。当然这只是我的猜测,我也没有仔细研究过deque的源码,因为我已经许久没有接触C++了……

  2. 环境:win7 64位, vs2017

    数据量:10w
    test1
    deque: 4 list: 5
    deque: 4 list: 5
    deque: 3 list: 6
    test2
    deque: 3 list: 11
    deque: 3 list: 10
    deque: 3 list: 11
    test3
    deque: 7 list: 8
    deque: 7 list: 9
    deque: 10 list: 6
    test4
    deque: 0 list: 4
    deque: 0 list: 3
    deque: 0 list: 3

    数据量100w:
    test1
    deque: 18 list: 66
    deque: 16 list: 67
    deque: 17 list: 65
    test2
    deque: 15 list: 97
    deque: 14 list: 96
    deque: 14 list: 95
    test3
    deque: 75 list: 71
    deque: 71 list: 74
    deque: 79 list: 74
    test4
    deque: 0 list: 30
    deque: 0 list: 38
    deque: 0 list: 32

    数据量:1000w
    test1
    deque: 557 list: 632
    deque: 555 list: 638
    deque: 567 list: 640
    test2
    deque: 482 list: 930
    deque: 489 list: 942
    deque: 469 list: 930
    test3
    deque: 829 list: 741
    deque: 823 list: 727
    deque: 817 list: 748
    test4
    deque: 4 list: 305
    deque: 6 list: 303
    deque: 5 list: 302

    结论:经过多年的软件和硬件发展,list没有那么慢了。不过从测试来看,deque大多数比list好,最差情况也是基本相等。尤其是deque的pop操作(包括pop_front和pop_back)都很快,只是移动了指针,但list应该做了delete之类的操作。

发表评论

电子邮件地址不会被公开。 必填项已用*标注