deque的顺序访问性能为何比vector差了10-20倍

deque的顺序访问性能为什么比vector差了10-20倍?
从数据结构和算法的角度讲,vector/deque随机访问某个元素的时间复杂度都是O(1)，但是vector是C++标准规定了要用连续存储的，而deque是分块，下标访问操作需要计算一次位置。但是他们两个的顺序访问性能不应该差了10-20倍吧。下面的小程序是我用VC2010编译的release版运行的高精度计时器，运行的结果是

实验1: 采用[]下标访问，vector用了3秒，而deque用了60秒(一分钟)。
实验2: 采用迭代器顺序访问，vector用了2秒，deque用了21秒。

这个差距也太大了点。为什么会这样呢?

实验1代码:

C/C++ code


#include "stdafx.h" 
#include<Windows.h> 
#include<vector> 
#include<deque> 
#include<list> 
using namespace std; 
LARGE_INTEGER Frequency,PerformanceCount1,PerformanceCount2; 
void fTime0(){ QueryPerformanceFrequency(&Frequency); } 
void fTime1(){ 
     QueryPerformanceCounter(&PerformanceCount1); 
} 
void fTime2(){    
     QueryPerformanceCounter(&PerformanceCount2); 
     int tdiff=static_cast<int>((  
         ((PerformanceCount2.QuadPart - PerformanceCount1.QuadPart) * 1000)/Frequency.QuadPart)); 
     printf("%d,",tdiff); 
} 
int main(int argc,char*[]){ 
     size_t s=argc*262144; 
     fTime0(); 
     { 
         vector<int> vi(s); 
         fTime1(); 
         for( int j=0;j<10000;++j) 
         { 
             for( decltype(s) l=0;l<s;++l ) 
             { 
                 vi[l]=argc; 
                 vi[l]+=l; 
             } 
         } 
         fTime2(); 
     } 
     { 
         deque<int> di(s); 
         fTime1(); 
         for( int j=0;j<10000;++j) 
         { 
             for( decltype(s) l=0;l<s;++l ) 
             { 
                 di[l]=argc; 
                 di[l]+=l; 
             } 
         } 
         fTime2(); 
     } 
  
     return 0; 
}

实验2代码:

C/C++ code


int main(int argc,char*[]){ 
     size_t s=argc*262144; 
     fTime0(); 
     { 
         vector<int> vi(s); 
         fTime1(); 
         for( int j=0;j<10000;++j) 
         { 
             for( auto it=vi.begin();it!=vi.end();++it ) 
             { 
                 *it=argc; 
                 *it+=j; 
             } 
         } 
         fTime2(); 
     } 
     { 
         deque<int> di(s); 
         fTime1(); 
         for( int j=0;j<10000;++j) 
         { 
             for( auto it=di.begin();it!=di.end();++it ) 
             { 
                 *it=argc; 
                 *it+=j;            } 
         } 
         fTime2(); 
     } 
     return 0; 
}

deque的顺序访问性能为何比vector差了10-20倍

相关推荐