C++奇怪的std :: bad_alloc异常

Question

所以我有以下代码:

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int MAXN = 1000000;
int isNotPrime[MAXN];
vector<int> primes;

void sieve()
{
    for(int i = 2; i <= sqrt(MAXN); ++i)
    {
        if(isNotPrime[i]) continue;
        for(int j = i*i; j <= MAXN; j += i)
        {
            isNotPrime[j] = true;
        }
    }
    for(int i = 2; i <= MAXN; ++i)
    {
        if(!isNotPrime[i])
        {
            primes.push_back(i);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    sieve();
    return 0;
}

我无法理解的是为什么我的程序在执行时会抛出一个std :: bad_alloc异常.更令人难以置信的是,当我交换线条int isNotPrime[MAXN];并且vector<int> primes;程序按预期执行时.像这样交换:

vector<int> primes;
int isNotPrime[MAXN];

Answer 1

问题出在这里:

for(int i = 2; i <= MAXN; ++i)

检查应该是i < MAXN.(或者,使数组具有大小MAXN + 1.)

在某些时候,isNotPrime[MAXN] = true;执行会溢出数组的边界,从而导致未定义的行为.在实践中,这会覆盖下一个变量(primes)的一些内部字段,这会混淆std::vector实现,可能会导致它请求大量内存.

这也解释了为什么切换变量顺序"修复"它,因为现在你正在乱涂其他东西而不是primes.