我试图理解为什么当我似乎有足够的(虚拟？)可用内存时我会收到 std::bad_alloc 异常。 本质上，我有一个素数生成器(Eratosthenes 筛法(尚未分段))，我在其中为指示器数组更新 bool 值，然后为我在命令行指定的范围内找到的素数更新整数。

我有 1GB 内存(其中一些会被我的操作系统 (ubuntu 10.04) 占用，并且可能其中一些不可用作堆内存(我在这里错了吗？))和 2.8 GB 交换空间(我相信这是在安装 Ubuntu 时为我自动设置的)

如果我将上限设置为 600000000，那么我需要 0.6 GB 的内存用于我的指标数组和大约 30000000*4 字节(略微高估，因为有 26355867 个小于 500000000 的素数)用于我的素数数组，并且一些变数在这里和那里；这意味着我要求大约 .72(+ 可忽略不计)GB 的内存，我认为应该由我可用的交换空间覆盖(我知道触摸这些东西会使我的程序慢得可笑)。但是我得到了 std::bad_allocs。

谁能指出我在这里遗漏了什么？ (在粘贴我的最后一个错误之前将 long long ints 更改为 ints 的最后一件事是段错误(尽管我的数字远低于 2 ^ 31 所以我看不到我溢出的地方) - 仍在尝试找出一个)

我的代码如下(并且没有剥夺我自己对更快算法等的调查的好处。我会很感激这里的任何代码改进!(即如果我犯了重大的禁忌) ))

主要.cpp

#include <iostream>
#include <cmath>
#include "Prime.hpp"
#include <ctime>
#include <stdio.h>
#include <cstring>

//USAGE: execute program with the nth prime you want and an upper bound for finding primes --too high may cause bad alloc
int main(int argc, const char *argv[])
{
    int a = strlen(argv[1]);
    clock_t start = clock();
    if(argc != 2)
    {
        std::cout << "USAGE: Enter a positive inputNumber <= 500000000.\n"
          << "This inputNumber is an upper bound for the primes that can be found\n";
        return -1;
    }
    const char* primeBound = argv[1];
    int inputNum = 0;
    for(int i = 0; i < strlen(argv[1]); i++)
    {
    if(primeBound[i] < 48 || primeBound[i] > 57 || primeBound[0] == 48)
    {
        std::cout << "USAGE: Enter a positive inputNumber <= 500000000.\n"
              << "This inputNumber is an upper bound for the primes that can be found\n";
        return -1;
    }
    inputNum = (int)(primeBound[i]-48) + (10 * inputNum);
    }
    if(inputNum > 600000000)//getting close to the memory limit for this machine (1GB - memory used by the OS):
                   //(each bool takes 1 byte and I'd be asking for more than 500 million of these 
                   //and I'd also asking for over 100000000 bytes to store the primes > 0.6 GB)
    {
    std::cout << "USAGE: Enter a positive inputNumber <= 500000000.\n"
          << "This inputNumber is an upper bound for the primes that can be found\n";
        return -1;
    }

    Prime p(inputNum);
    std::cout << "the largest prime less than " << inputNum << " is: " << p.getPrime(p.getNoOfPrimes()) << "\n";
    std::cout << "Number of primes: " << p.getNoOfPrimes() << "\n";
    std::cout << ((double)clock() - start) / CLOCKS_PER_SEC << "\n";
  return 0;
}

总理.hpp

#ifndef PRIME_HPP
#define PRIME_HPP
#include <iostream>
#include <cmath>

class Prime
{
    int lastStorageSize;
    bool* primeIndicators;
    int* primes;
    int noOfPrimes;

    void allocateIndicatorArray(int num);
    void allocatePrimesArray();
    void generateIndicators();
    void generatePrimeList();
    Prime(){}; //forcing constructor with param = size

    public:
        Prime(int num);
    int getNoOfPrimes();
    int getPrime(int nthPrime);
    ~Prime(){delete [] primeIndicators; delete [] primes;}
};

#endif

主要.cpp

#include "Prime.hpp"
#include <iostream>

//don't know how much memory I will need so allocate on the heap
void Prime::allocateIndicatorArray(int num)
{
    try
    {
        primeIndicators = new bool[num];
    }
    catch(std::bad_alloc ba)
    {
    std::cout << "not enough memory :[";
    //if I'm looking for a particular prime I might have over-allocated here anyway...might be worth
    //decreasing num and trying again - if this is possible!
    }
    lastStorageSize = num;
}

void Prime::allocatePrimesArray()
{
    //could probably speed up generateIndicators() if, using some prime number theory, I slightly over allocate here
    //since that would cut down the operations dramatically (a small procedure done many times made smaller)
    try
    {
        primes = new int[lastStorageSize];
    }
    catch(std::bad_alloc ba)
    {
    std::cout << "not enough memory :[";
    //if I'm looking for a particular prime I might have over-allocated here anyway...might be worth
    //decreasing num and trying again - if this is possible!
    }
}
void Prime::generateIndicators()
{
    //first identify the primes -- if we see a 0 then start flipping all elements that are multiples of i starting from i*i (these will not be prime)
    int numPrimes = lastStorageSize - 2; //we'll be starting at i = 2 (so numPrimes is at least 2 less than lastStorageSize)
    for(int i=4; i < lastStorageSize; i+=2)
    {
        primeIndicators[i]++; //dispense with all the even numbers (barring 2 - that one's prime)
    numPrimes--;
    }
    //TODO here I'm multiple counting the same things...not cool >;[
    //may cost too much to avoid this wastage unfortunately
    for(int i=3; i < sqrt(double(lastStorageSize)); i+=2) //we start j at i*i hence the square root
    {
        if(primeIndicators[i] == 0)
    {
            for(int j = i*i; j < lastStorageSize; j = j+(2*i)) //note: i is prime, and we'll have already sieved any j < i*i
        {
        if(primeIndicators[j] == 0)
        {
            numPrimes--;//we are not checking each element uniquely yet :/
                    primeIndicators[j]=1;
        }
        }
    }
    }
    noOfPrimes = numPrimes;
}
void Prime::generatePrimeList()
{
    //now we go and get the primes, i.e. wherever we see zero in primeIndicators[] then populate primes with the value of i
    int primesCount = 0;
    for(int i=2;i<lastStorageSize; i++)
    {
        if(primeIndicators[i] == 0)
        {
        if(i%1000000 = 0)
        std::cout << i << " ";
            primes[primesCount]=i;
            primesCount++;
        }
    }
}
Prime::Prime(int num)
{
    noOfPrimes = 0;
    allocateIndicatorArray(num);
    generateIndicators();
    allocatePrimesArray();
    generatePrimeList();
}

int Prime::getPrime(int nthPrime)
{
    if(nthPrime < lastStorageSize)
    {
        return primes[nthPrime-1];
    }
    else
    {
    std::cout << "insufficient primes found\n";
    return -1;
    }
}

int Prime::getNoOfPrimes()
{
    return noOfPrimes;
}

虽然我在四处阅读，但有人对此有任何见解吗？

编辑 出于某种原因，我决定开始使用 lastStorageSize 整数而不是 noOfPrime 来更新我的素数列表!感谢 David Fischer 发现了那个!

我现在可以超过 600000000 作为上限

最佳答案

您可以在程序中使用的内存量受以下两者中较小者的限制:1) 可用虚拟内存，2) 可用地址空间。

如果您在具有平坦内存模型的平台上将程序编译为 32 位可执行文件，则单个进程的可寻址空间的绝对限制为 4GB。在这种情况下，您有多少交换空间是完全无关紧要的。您不能在平面内存 32 位程序中分配超过 4GB 的空间，即使您仍然有大量可用交换空间。此外，这 4GB 可用地址中的很大一部分将保留用于系统需要。

在这样的 32 位平台上分配大量交换空间确实有意义，因为它可以让您同时运行多个进程。但它无法克服每个特定进程的 4GB 地址空间障碍。

基本上，可以将其视为电话号码可用性问题:如果某个地区使用 7 位电话号码，那么一旦您用完该地区可用的 7 位电话号码，就不再为该地区生产更多电话有任何意义 - 它们将无法使用。通过添加交换空间，您实际上是在“制造电话”。但是您已经用完可用的“电话号码”。

当然，对于平面内存模型 64 位平台，同样的问题正式存在。然而，64 位平台的地址空间非常庞大，不再是瓶颈(你知道，“64 位应该对每个人都足够了”:))

关于c++ - std::bad_alloc 不进入交换空间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13557312/