发现forward_list不比list插入更快啊.

weichuang02

C++11的forward_list在cppreference上面是这样说的:

Forward list is a container which supports fast insertion and removal of elements from anywhere from the container. Fast random access is not supported. It is implemented as singly-linked list and essentially does not have any overhead compared to its implementation in C. Compared to std::list this container provides more space efficient storage, when bidirectional iteration is not needed.

    号称插入和删除更快。但是我在windows上面的VC10测试了一下release版，发现不是这么回事。我用windows的高精计时器跑了一下，list的插入操作用了6106ms，forward_list用了6199ms。运行了很多次forward_list都多用了1.5%的时间。这是为什么呢，难道我的代码本身有问题?

1. 
   
2. #include "stdafx.h"
   
3. #include<Windows.h>
   
4. #include<forward_list>
   
5. #include<list>
   
6. using namespace std;
   
7. LARGE_INTEGER Frequency,PerformanceCount1,PerformanceCount2;
   
8. void fTime1(){
   
9.     QueryPerformanceCounter(&PerformanceCount1);
   
10. }
    
11. void fTime2(){   
    
12.     QueryPerformanceCounter(&PerformanceCount2);
    
13.     int tdiff=static_cast<int>((
    
14.         ((PerformanceCount2.QuadPart - PerformanceCount1.QuadPart) * 1000)/Frequency.QuadPart));
    
15.     printf("%d\n",tdiff);
    
16. }
    
17. int main(void){
    
18.     const size_t nLoop=20000000;
    
19.     QueryPerformanceFrequency(&Frequency);
    
20.     {
    
21.         fTime1();
    
22.         list<int> li;
    
23.         for(int i=0;i<nLoop;++i){
    
24.             li.push_front(i);
    
25.         }
    
26.         auto it=li.begin();
    
27.         ++it;
    
28.         for(int i=0;i<nLoop;++i){
    
29.             li.insert(it,i);//相当于insert_after begin();
    
30.         }
    
31.         fTime2();
    
32.     }
    
33.     {
    
34.         fTime1();
    
35.         forward_list<int> fi;
    
36.         for(int i=0;i<nLoop;++i){
    
37.             fi.push_front(i);
    
38.         }
    
39.         for(int i=0;i<nLoop;++i){
    
40.             fi.insert_after(fi.begin(),i);
    
41.         }
    
42.         fTime2();
    
43.     }
    
44.     return 0;
    
45. }
    

复制代码

bruceteen

“号称插入和删除更快” ------ 没看出洋文原文中有这一句话

俺洋文暴烂，只有高考时及格一次（150分的卷子正好90分），试着翻译一下：
Forward list is a container which supports fast insertion and removal of elements from anywhere from the container. Fast random access is not supported. It is implemented as singly-linked list and essentially does not have any overhead compared to its implementation in C. Compared to std::list this container provides more space efficient storage, when bidirectional iteration is not needed.
前向列表是一个能够在任意位置快速插入和删除的容器（列表都这特性，前向列表当然也具有这特性），但不支持快速随机存取。
它是用单向链表实现的，相比较于它的C实现而言没有什么额外开销。相较于std::list而言，此容器耗费的空间更少，因为它是单向的，不是双向的。

bruceteen

比较快慢，起码代码应该是一样的吧

auto it=li.begin();
++it;
for(int i=0;i<nLoop;++i){
    li.insert(it,i);
}

另一个是

for(int i=0;i<nLoop;++i){
    fi.insert_after(fi.begin(),i);
}

有这么比较的吗？

幻の上帝

没说有快吧。主要是省空间（节点指针；另外至少C++11要求list::size()是O(1)的，而forward_list不用）。