大向量 "Segmentation fault" 错误

Question

我从其他人关于 SO 的问题和答案中收集了大量非常有用的信息，并适当地搜索了这个问题的答案。不幸的是，我还没有找到解决这个问题的方法。

生成素数列表的函数如下：

void genPrimes (std::vector<int>* primesPtr, int upperBound = 10)
{
  std::ofstream log;
  log.open("log.txt");

  std::vector<int>& primesRef = *primesPtr;

  // Populate primes with non-neg reals
  for (int i = 2; i <= upperBound; i++)
    primesRef.push_back(i);
  log << "Generated reals successfully." << std::endl;
  log << primesRef.size() << std::endl;

  // Eratosthenes sieve to remove non-primes
  for (int i = 0; i < primesRef.size(); i++) {
    if (primesRef[i] == 0) continue;
    int jumpStart = primesRef[i];
    for (int jump = jumpStart; jump < primesRef.size(); jump += jumpStart) {
      if (primesRef[i+jump] == 0) continue;
      primesRef[i+jump] = 0;
    }
  }
  log << "Executed Eratosthenes Sieve successfully.\n";

  for (int i = 0; i < primesRef.size(); i++) {
    if (primesRef[i] == 0) {
      primesRef.erase(primesRef.begin() + i);
      i--;
    }
  }
  log << "Cleaned list.\n";
  log.close();
}

调用者：

  const int SIZE = 500;
  std::vector<int>* primes = new std::vector<int>[SIZE];
  genPrimes(primes, SIZE);

此代码运行良好。但是，当我将 SIZE 的值更改为更大的数字（比如 500000）时，编译器 returns a "segmentation error." 我对向量不够熟悉，无法理解这个问题。非常感谢任何帮助。

Answer 1

您正在访问 primesRef[i + jump]，其中 i 可能是 primesRef.size() - 1，jump 可能是 primesRef.size() - 1，导致越界访问。

它发生在 500 个限制下，只是您目前碰巧没有因越界访问而产生任何不良副作用。

另请注意，在此处使用 vector 是一个错误的选择，因为每次擦除都必须移动内存中的所有以下条目。

Answer 2

问题出在这里：

  // Populate primes with non-neg reals
  for (int i = 2; i <= upperBound; i++)
    primesRef.push_back(i);

您的向量中只有 N-2 个元素被推回，但随后尝试访问 N-1 处的元素（i+jump）。它没有在 500 上失败的事实只是幸运的是被覆盖的内存不是灾难性的。

Answer 3

您确定要这样做吗

 new std::vector<int> [500];

而不是

new std::vector<int> (500);

在后一种情况下，您要指定矢量的大小，您可以通过名为 'primes' 的变量获得其位置。

在前者中，您请求 space 500 个矢量，每个矢量的大小都是 STL 库需要的默认值。

那会是这样的（在我的系统上：24*500 字节）。在后一种情况下，500 长度的向量（只有一个向量）就是你所要求的。

编辑：查看用法 - 他只需要一个向量。

std::vector& primesRef = *primesPtr;

Answer 4

This code works well. However, when I change the value of SIZE to a larger number (say, 500000), ...

这可能会耗尽你的筹码，并且分配给它太多。您需要为您认为需要的所有 std::vector<int> 个实例分配动态内存。

为此，只需像这样使用嵌套 std::vetcor。

 std::vector<std::vector<int>> primes(SIZE);

相反。

但要直接开始，我严重怀疑您是否需要 SIZE 个向量实例来存储找到的所有素数，但只需要一个像这样初始化的素数：

 std::vector<int> primes(SIZE);

大向量 "Segmentation fault" 错误

Large vector "Segmentation fault" error

c++

vector

segmentation-fault