c++ - 使用巨大的 vector 在 C++ 程序中卡住

Question

我有一个 C++ 程序的问题。我觉得是内存的问题。在我的程序中，我习惯于创建一些巨大的 std::vector (我使用 reserve 来分配一些内存)。 vector 大小为 1 000 000，没关系，但如果我增加这个数字(大约一千万)，我的程序将卡住我的 PC，我只能等待崩溃(如果我幸运的话，或者程序结束) .我的 vector 包含一个名为 Point 的结构，其中包含一个 double vector 。

我使用 valgrind 来检查是否存在内存不足。但不是。按照它，没有问题。也许不建议使用对象 vector ？或者也许有一些系统参数要检查什么的？或者简单地说， vector 对于计算机来说太大了？

你怎么看这个？

Answer 1

免责声明

请注意，此答案假设了您机器的一些情况；确切的内存使用和错误可能性取决于您的环境。当然，当你不在 2d 点上计算时更容易崩溃，但是例如4d 点，例如在计算机图形学中很常见，或者更大的点用于其他数字目的。

关于您的问题

要分配的内存相当多:

#include <iostream>
#include <vector>
struct Point {
    std::vector<double> coords;
};
int main () {
    std::cout << sizeof(Point) << std::endl;
}

这会打印出 12，这是一个空 Point 的字节大小。如果您有二维点，请向每个元素添加另一个 2*sizeof(double)=8，即现在每个 Point 总共有 20 个字节。

对于数百万个元素，您请求数以百万计字节的 200 个数据，例如对于 2000 万个元素，您请求 4 亿字节。虽然这不会超过 std::vector 的最大索引，但操作系统可能没有那么多连续的可用内存。

此外，您的vector内存需要经常复制才能增长。例如，当您push_back 时会发生这种情况，因此当您已经有一个 400MiB vector 时，在下一次 push_back 时您可能会拥有旧版本的vector，加上新分配的 400MiB*X 内存，因此您可能很容易暂时超过 1000MiB，等等。

优化(高级；首选)

您是否需要一直存储数据？您可以使用不需要那么多存储空间的类似算法吗？您能否重构代码以减少存储空间？当您知道需要一些时间才能再次需要时，您能否提取一些数据？

优化(低级)

如果在创建外部 vector 之前知道元素的数量，请使用 std::vector 构造函数，它可以告诉您初始大小:

vector<Foo> foo(12) // initialize have 12 elements

当然你可以针对内存做很多优化；例如如果您知道您始终只有 2d 点，则只需将两个 double 作为成员:20 字节 -> 16 字节。当你真的不需要double的精度时，使用float:16 bytes -> 8 bytes。这是对 $2/5$ 的优化:

// struct Point { std::vector<double> coords; };   <-- old
struct Point { float x, y; }; // <-- new

如果这仍然不够，一个临时解决方案可以是 std::deque，或另一个非连续的容器:没有临时内存“加倍”，因为不需要调整大小；操作系统也不需要为您找到这样连续的内存块。

您还可以使用压缩机制、索引数据或定点数。但这取决于您的具体情况。

struct Point { signed char x, y; }; // <-- or even this? examine a proper type
struct Point { short x_index, y_index; };