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

Question

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

Answer 1

嗯，可用内存与可用内存不同。

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

因此，当 vector 需要调整大小时，您也可能会遇到问题。如果 vector 与它可以扩展到的一大块连续内存相邻，那就太好了；然而，如果 vector 在一个太小的 block 中，那么它必须将自己复制到一个新位置……这需要时间。

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

(如果您担心标准是否保证 vector 是连续的(因此可能导致 OP 的问题)，reading this 和 this 可能有助于阐明问题。)