为什么列表迭代比向量迭代C++更快

Question

我有以下代码:

main() {
  vector<int> v (1000,0);
  list<int> l (1000,0);

  clock_t begin,end;

  cout <<"Vector size: "<<v.size()<<endl;
  cout <<"List size: "<<l.size()<<endl;

  begin=clock();
  for (int i=0;i<1000000;i++)
    for (vector <int>::iterator it=v.begin();it!=v.end();it++);
  end=clock();

  cout <<v[0]<<endl;
  cout << "Vector iteration: " << (double)(end-begin)/CLOCKS_PER_SEC <<endl;


  begin=clock();
  for (int i=0;i<1000000;i++)
    for (list <int>::iterator it=l.begin();it!=l.end();it++);
  end=clock();

  list <int>::iterator it=l.begin();
  cout << *it <<endl;
  cout << "List iteration: " << (double)(end-begin)/CLOCKS_PER_SEC <<endl;
}

总是,我得到的结果是向量迭代是(大约)18.3秒,列表迭代是(大约)11.7秒.这怎么可能？我的测量有问题吗？

谢谢你的帮助!

Answer 1

根据您列出的时间(每个10-20秒),您似乎确定您正在编译已禁用优化¹.这使得您的结果基本没有意义.

对我的(大约7岁)机器进行快速测试,启用优化后,矢量时间为0,列表时间为1.2-1.5秒(VC++为1.2,g ++为1.5).

在禁用优化的情况下,它们都会减速(很多).使用VC++,我看到向量大约需要38秒,列表需要43秒.使用g ++,那些更像是向量的36秒和列表的29秒.后者(大致)匹配你所看到的(以我的显然较旧/较慢的计算机为模),所以我猜你使用g ++并禁用了优化.

结论:您所看到的几乎可能完全是代码编写方式的工件(例如,可能是向量代码中的额外函数调用).它与向量或列表本身的固有效率完全无关.

1. 只是为了完整性:我想你只需要在一台非常古老,缓慢的计算机上运行代码,就可以得到至少接近该范围的结果.由于我们谈论的速度比当前的计算机大约慢20倍,因此可以想象一下150到233(左右)的奔腾可能会产生这样的结果.有了这么老的CPU,优化当前代码的一些假设可能并不真正适用,所以我认为几乎可以想象某些东西可能会反击得太厉害,以至于你最终会让列表变得更快.即便如此,我也不会真正期待它,但是由于编译器期望的CPU与您运行它的CPU之间存在这样的不匹配,几乎任何事情都是可能的.