c++ - 如何在 C++ 中安全地调整大向量的大小

Question

我在 C++ 中制作了一个素数查找器，它将素数写入 .txt 文件，但在找到第 102,144,001 个（2,084,058,601）后它崩溃了。它还将找到的素数存储在一个向量中，因此它不必除以小于当前检查数字平方根的每个数字，只需除以素数。它在每 (10,240n+1) 个找到素数之后调整存储素数的向量的大小，而 102,144,001 是 10,240n+1，因此它在调整大小时崩溃了。我使用了一个向量 unsigned __int64，所以当它崩溃时它使用了大约 780 兆字节，但我有 8 GB RAM。我应该使用vector.reserve()吗？（我不想在 50 分钟后再次崩溃......）

Answer 1

好吧，可用内存与可用内存不同。

cppreference表示向量的元素是连续存储的。因此，这不是您拥有多少 RAM 的问题，而是您在程序运行时拥有多少连续 RAM。如果向量必须是连续的，则该向量不能扩展超出连续内存的最大可用部分。

因此，当向量需要调整大小时，您也可能会遇到问题。如果向量与一大块连续内存相邻，它可以扩展成，那么很好；但是，如果向量的块太小，则它必须将自身复制到新位置……这需要时间。

deque容器可能是更好的选择，因为它不需要连续的存储位置。这使您可以利用更多可用 RAM 并避免在调整大小期间进行昂贵的复制操作。

（如果您担心标准是否保证向量是连续的（因此可能导致 OP 的问题），阅读此内容可能有助于阐明此问题。）

Answer 2

只有比 2084058601 的平方根少 4730 个素数。如果您在存储少量数据时内存不足，那么您做错了。

我最近编写了一个素数生成器，并用它来对前十亿个素数求和。它使用分段的 Eratosthenes 筛，并在每个分段的开头添加额外的筛分素数。内存使用对于位数组的大小是恒定的，并且对于筛选素数来说增长缓慢。你可能想看看它。

Answer 3

老实说，我怀疑这是你的问题。在 64 位操作系统上，您应该有足够的地址空间，因此只有在交换空间用完时才会遇到问题。

我猜你的问题是栅栏问题。事实上，您甚至认为您需要调整大小，链 push_back 应该绰绰有余。

你的崩溃的细节可能值得一看。您可能还想查看 std 向量在无法分配内存时抛出的异常。另一个问题是 io 可能比计算慢得多，如果您知道崩溃的最后一位数字而不是崩溃的方式，则可能是打印过多。