c++ - vector 和数组之间的性能差距

Question

我试图解决 a coding problem in C++计算小于非负数的素数个数n .

所以我首先想出了一些代码:

int countPrimes(int n) {
    vector<bool> flag(n+1,1);
    for(int i =2;i<n;i++)
    {
        if(flag[i]==1)
            for(long j=i;i*j<n;j++)
                flag[i*j]=0;
    }
    int result=0;
    for(int i =2;i<n;i++)
        result+=flag[i];
    return result;
}

这需要 88 毫秒并使用 8.6 MB 内存。然后我把我的代码改成:

int countPrimes(int n) {
    // vector<bool> flag(n+1,1);
    bool flag[n+1] ;
    fill(flag,flag+n+1,true);
    for(int i =2;i<n;i++)
    {
        if(flag[i]==1)
            for(long j=i;i*j<n;j++)
                flag[i*j]=0;
    }
    int result=0;
    for(int i =2;i<n;i++)
        result+=flag[i];
    return result;
}

这需要 28 毫秒和 9.9 MB。我真的不明白为什么在运行时间和内存消耗上都有这样的性能差距。我已阅读相关问题，例如 this one和 that one但我还是一头雾水。

编辑:替换 vector<bool> 后，我使用 11.5 MB 内存将运行时间减少到 40 毫秒与 vector<char> .

Answer 1

std::vector<bool>不像任何其他 vector 。 documentation说:

std::vector<bool> is a possibly space-efficient specialization of std::vector for the type bool.

这就是它使用的内存可能比数组少的原因，因为它可能用一个字节表示多个 bool 值，例如位集。它还解释了性能差异，因为访问它不再那么简单了。根据文档，它甚至不必将其存储为连续数组。