C++ vector 与数组(时间)

Question

我这里有两个程序，它们都在执行完全相同的任务。他们只是将 bool 数组/vector 设置为真值。使用 vector 的程序运行需要 27 秒，而涉及大小为 5 倍的数组的程序需要不到 1 秒。我想知道为什么会有如此大的差异的确切原因？是载体真的那么低效吗？

使用 vector 编程

#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

int main(){
 const int size = 2000;
 time_t start, end;
 time(&start);
 vector<bool> v(size);
 for(int i = 0; i < size; i++){
  for(int j = 0; j < size; j++){
   v[i] = true;
  }
 }
 time(&end);
 cout<<difftime(end, start)<<" seconds."<<endl;
}

运行时间 - 27 秒

使用数组编程

#include <iostream>
#include <ctime>

using namespace std;

int main(){
 const int size = 10000; // 5 times more size
 time_t start, end;
 time(&start);
 bool v[size];
 for(int i = 0; i < size; i++){
  for(int j = 0; j < size; j++){
   v[i] = true;
  }
 }
 time(&end);
 cout<<difftime(end, start)<<" seconds."<<endl;
}

运行时间 - < 1 秒

平台 - Visual Studio 2008操作系统 - Windows Vista 32 位 SP 1处理器 Intel(R) Pentium(R) Dual CPU T2370 @ 1.73GHz内存 (RAM) 1.00 GB

谢谢

阿玛雷

Answer 1

您使用的是 bool 的 std::vector 而这不是您认为的那样!

bool vector 是一个不应该存在的 SCSS 子模板特化，实际上在每个位中存储 1 个 bool。由于屏蔽和移位逻辑，对其的访问更加复杂，因此肯定会慢一些。

Click here for some info on vector of bool.

此外，您可能正在运行未优化的构建(考虑到您列出的时间，几乎可以肯定的是，27 秒对于 400 万次迭代来说是离谱的)。标准模板库非常依赖优化器来执行内联函数调用和删除临时对象等操作。缺少这种优化会导致 vector of bool 的性能下降特别严重，因为当你索引它时它必须返回一个代理对象，因为你不能获取位的地址，所以 operator [] 无法返回引用。

Click here for more info on proxied containers (后半部分是关于bool的vector)

此外，许多 STL 实现具有有用的调试位，这些位不是标准的一部分，可帮助您发现错误，但实际上会降低性能。您需要确保在您的优化构建中禁用了这些。

一旦您打开优化器，进行正确的设置(即没有打开 STL 调试)，并且实际上在两个循环中测试相同的东西，您会发现几乎没有区别。

我必须让你的循环更大才能在我的机器上进行测试，但这里有两个你的 bool 循环 vector 在我的机器上的构建，显示了优化器标志对 STL 代码的影响

$ g++ main.cpp 
$ ./a.out 
17 seconds.
$ g++ -O2 main.cpp 
$ ./a.out 
1 seconds.