为什么在C++中，3D向量在内存中比1D向量占用更多空间？

Question

我意外地发现，STL向量可以按以下方式定义：

vector < float > test;
test.resize(10000 * 10000 * 5);

相比以下定义，占用的RAM空间显著更少:

std::vector<std::vector<std::vector< float > > > test;

test.resize(10000);
for(int i = 0;i <  10000;i++)
{
test[i].resize(10000);
for(int j = 0;j <  10000;j++)
{
test[i][j].resize(5);
}
}

线性向量法（顶部）使用正确数量的RAM（2GB），就像手动计算一样。那么我的问题是，为什么3D向量比线性向量使用更多的RAM，在这个例子中，我发现它显著地多（约4GB）。

- Single Entity

---

为什么你要向 resize 传递浮点数值？ - Jonathon Reinhart

懒惰主要是什么意思？这相关吗？ - Single Entity

第一个使用一个内存块。你只需要一个足够大的块，而不是在内存中找到大量分散的小块，更不用说存储指向具有更多指针的内存块的指针了。每个10000指针到10000指针可能是800MB。 - chris

创建10,000个浮点数和创建10,000个向量对象之间存在很大的差异。 - PaulMcKenzie

Answer 1

在前一种情况下，您有：

sizeof(vector<float>)                  // outermost vector
  + 10000 * 10000 * 5 * sizeof(float)  // xyz space

在后者中，您将拥有：

sizeof(vector<vector<vector<float>>>)      // outermost vector
  + 10000 * sizeof(vector<vector<float>>)  // x axis
  + 10000 * 10000 * sizeof(vector<float>)  // xy plane
  + 10000 * 10000 * 5 * sizeof<float>      // xyz space

任何类型 T 的 sizeof(vector<T>) 的典型值为 3 * sizeof(T*)，我相信这也是标准允许的最小值——容量必须与大小不同，因为 reserve() 必须更改 capacity() 的值，但不能更改 size() 的值。

- Jon Purdy

---

双指针向量如何管理begin、end和capacity三个元素？实践中，分配块本身也有开销。 - Yakk - Adam Nevraumont

@Yakk：你说得对，我开始怀疑自己了。已经修复。 - Jon Purdy

嗯，这个向量可以作弊，使用“malloc”块中的信息来计算容量... - Yakk - Adam Nevraumont

Answer 2

向量类需要使用额外的指针来占用内存。当您分配一个 1D 向量时，您只有 1 个指针和它所指向的大块内存。在向量的向量的向量的情况下，您有 10,000 * 10,000 * 5 个向量，每个向量都有一个 4 字节的指针，占用额外的 20 亿字节，仅用于保存位置信息。

编辑：

正如 Andrey 在评论中指出的那样，你实际上没有设置 10,000 * 10,000 * 5 个向量，而是：

1D - 顶层向量为其下面的 10,000 个向量分配空间

2D - 每个这些 10,000 个向量又设置了另外 10,000 个向量

3D - 最后一层只是实际数据...

因此，您拥有 10,000 个初始向量以及下面的 10,000 * 10,000 个向量，总共有 100,010,000 个向量。另一个用户提到每个向量占用大约 20 个字节的空间（用于存储内存指针以及类中的其他成员，如大小、容量等），因此您最终会占用约 20 亿字节的空间。

- Mike

---

所以在一维向量中，它使用一个内存块和一个指针，在三维向量中，它使用一个内存块和（1 + 10000 + 10000）个指针。 - cdxf

实际上，只有1 + 10,000 + 10,000 * 10,000 = 100,010,001个向量。然而，每个向量都包含两个指针（或一个指针和一个大小），因此在32位机器上需要大约800MB的空间。 - ach

其余的解释是因为大多数实现将5*sizeof(float)四舍五入到32字节。这会导致高达12 * 100.000.000 = 1200MB的开销。 - ach

Answer 3

向量类具有一些额外的开销。至少有一个指针和一个用于大小的字段。在MS Visual Studio中，sizeof（std :: vector）为20或24（启用迭代器调试）。实际大小将取决于实现。

- jaket

Answer 4

每个向量对象都有一个开销 - 因为它们可以是可变长度，所以需要指向起始点、已使用位的大小和其容量的指针。

如果您有一个固定大小的三维形状，其中高度、宽度和长度已知，您可以将其转换为一维数组。这将是最有效的方法。

要做到这一点，给定 x、y、z，您可以找到索引 x + width * ((z * height) + y) 进行转换。

- Ed Heal