我试图找到所有的素数不大于n使用Eratosthenes'Sieve算法，我有以下代码，在载体和C数组实现的筛子，我每时每刻都在进行中发现，几乎，C数组总是快点。
使用向量：
int countPrimes_vector(int n) {
int res = 0;
vector<char>bitmap(n);
memset(&bitmap[0], '1', bitmap.size() * sizeof( bitmap[0]));
//vector<bool>bitmap(n, true); Using this one is even slower!!
for (int i = 2; i<n; ++i){
if(bitmap[i]=='1')++res;
if(sqrt(n)>i)
{
for(int j = i*i; j < n; j += i) bitmap[j] = '0';
}
}
return res;
}
用C数组：
int countPrimes_array(int n) {
int res = 0;
bool * bitmap = new bool[n];
memset(bitmap, true, sizeof(bool) * n);
for (int i = 2; i<n; ++i){
if(bitmap[i])++res;
if(sqrt(n)>i)
{
for(int j = i*i; j < n; j += i) bitmap[j] = false;
}
}
delete []bitmap;
return res;
}
测试代码：
clock_t t;
t = clock();
int a;
for(int i=0; i<10; ++i)a = countPrimes_vector(8000000);
t = clock() - t;
cout<<"time for vector = "<<t<<endl;
t = clock();
int b;
for(int i=0; i<10; ++i)b = countPrimes_array(8000000);
t = clock() - t;
cout<<"time for array = "<<t<<endl;
输出：
time for vector = 32460000
time for array = 29840000
我已经测试过很多次，和C数组总是更快。 什么是它背后的原因是什么？
常听，对于性能vector和C阵列是相同的， vector应当总是用于作为一个标准容器。 这是说法正确，或至少一般说来？ 在什么情况下，数组c应该是首选？
编辑：
正如下面的评论表明，接通优化后-O2或-O3 （最初将其用编译g++ test.cpp ）之间的时间差vector和C阵列不再有效，在某些场合vector是比C数组更快。
你比较包含这可以解释的差异不一致，而另一个因素可能是没有足够的优化的编译的结果。 一些实施方式中有很多在调试附加代码建立STL的，例如MSVC确实界限向量元件上检查访问产生在调试版本中速度的减少显著。
下面的代码显示了两者之间更密切的性能，不同的是可能只是缺乏样品（ideone有5秒的超时限制）。
#include <vector>
#include <cmath>
#include <cstring>
int countPrimes_vector(int n) {
int res = 0;
std::vector<bool> bitmap(n, true);
for (int i = 2; i<n; ++i){
if(bitmap[i])
++res;
if(sqrt(n)>i)
{
for(int j = i*i; j < n; j += i) bitmap[j] = false;
}
}
return res;
}
int countPrimes_carray(int n) {
int res = 0;
bool* bitmap = new bool[n];
memset(bitmap, true, sizeof(bool) * n);
for (int i = 2; i<n; ++i){
if(bitmap[i])++res;
if(sqrt(n)>i)
{
for(int j = i*i; j < n; j += i) bitmap[j] = false;
}
}
delete []bitmap;
return res;
}
#include <chrono>
#include <iostream>
using namespace std;
void test(const char* description, int (*fn)(int))
{
using clock = std::chrono::steady_clock;
using ms = std::chrono::milliseconds;
auto start = clock::now();
int a;
for(int i=0; i<9; ++i)
a = countPrimes_vector(8000000);
auto end = clock::now();
auto diff = std::chrono::duration_cast<ms>(end - start);
std::cout << "time for " << description << " = " << diff.count() << "ms\n";
}
int main()
{
test("carray", countPrimes_carray);
test("vector", countPrimes_vector);
}
现场演示： http://ideone.com/0Y9gQx
time for carray = 2251ms
time for vector = 2254ms
虽然在某些运行的CARRAY为1-2毫秒慢。 再次，这是一个共享的资源不足的样本。
---编辑---
在您的主要意见，你问“为什么优化可以有所作为。”
std::vector<bool> v = { 1, 2, 3 };
bool b[] = { 1, 2, 3 };
我们有3种元素的两个“数组” S，所以考虑以下几点：
v[10]; // illegal!
b[10]; // illegal!
STL的调试版本往往能抓住这个运行过程中的时间（以及某些情况下，编译时）。 数组访问可能只是导致错误数据或崩溃。
此外，该STL是使用许多小的成员函数调用类的东西实施size()并且因为vector是一个类， []实际上是通过一个函数调用（facaded operator[]
编译器可以消除许多的这些，但是这是最优化。 如果你不优化，事遂所愿
std::vector<int> v;
v[10];
做一些事情大致是这样：
int* data() { return M_.data_; }
v.operator[](size_t idx = 10) {
if (idx >= this->size()) {
raise exception("invalid [] access");
}
return *(data() + idx);
}
而即使数据是一个“可以内联”的功能，使调试容易，没有优化的代码，使得IT的了。 当你建立与优化，编译器可以识别的是，这些功能的实现是如此微不足道它能刚刚替补其实现到调用点，并迅速卷起所有上述的简化像操作更加阵列的访问。
例如，在上述情况下，可以先减少operator[]至
v.operator[](size_t idx = 10) {
if (idx >= this->size()) {
raise exception("invalid [] access");
}
return *(M_.data_ + idx);
}
而且，由于无需调试编译可能消除了边界检查，就变成
v.operator[](size_t idx = 10) {
return *(M_.data_ + idx);
}
所以现在的内衬可以减少
x = v[1];
至
x = *(v.M_.data_ + 1); // comparable to v.M_.data_[1];
有一个小小的惩罚。 的c阵列涉及该数据块在存储器中且装配到指向块的寄存器的单个本地变量，您的引用是直接相对的是：
与载体，不过，你有矢量对象，它是一个指向数据，尺寸和容量可变：
vector<T> // pseudo code
{
T* ptr;
size_t size;
size_t capacity;
}
如果你计算的机器指令，向量将有3个变量初始化和管理。
当你写
x = v[1];
鉴于上述近似矢量的，你说的线沿线的东西：
T* ptr = v.data();
x = ptr[1];
但是编译器与优化建设，以识别，它可以做循环之前的第一线足够时通常聪明，但是这也容易花费寄存器。
T* ptr = v.data(); // in debug, function call, otherwise inlined.
for ... {
x = ptr[1];
}
所以，你可能看屈指可数的机器指令每次测试功能的重复，或在现代化的处理器，也许纳秒或两个额外的挂钟时间。
