一个动态的二维数组在内存中是如何存储的？

Question

二维数组在内存中是如何存储的？

我考虑了以下方法，其中行作为连续的内存块进行存储。 |___ ___ ___||___ ___ ___||___ ___ ___|...|___ ___ ___|

元素可以通过 (i,j) -> n*i+j 访问，其中n是矩阵的尺寸（假设它是nxn）。

但是如果我想要添加一个新列怎么办？我必须更新每一行中的第(n+1)个元素，并将它们向右移动，但这太耗费计算资源了。

另一个选择是将矩阵复制到一个新位置，并即时使用新列的元素更新行。但是如果数组很大，这也不太高效。

最后我想到的第三种选择是为每一行分配固定数量的内存，当我添加新列时，我不必将行向右移动。

我不能在内存中留下空隙，所以所有块都必须是连续的。

还有其他更有效的方法吗？

- flowerpower

---

你们处理的是什么样的数据规模？是10个元素还是1,000,000个元素？ - Martin Kristiansen

Answer 1

如果您知道您将创建一个需要扩展的2D数组，一种方法是在每个维度上分配比您需要的更多的大小。跟踪实际大小和已分配大小，当实际大小超过所分配的大小时，请执行以下操作：

• 将分配的大小加倍
• 将所有数据从旧数组复制到新数组
• 释放旧数组

这将是动态分配1D数组的常见技术的2D扩展。

- Greg Hewgill

---

好主意，但我想知道它是否违反了他要求内存连续的要求。 - Jim Clay

那个要求是在最初的问题提出之后添加的。我不知道“块”是指“特定行”还是“整个数据结构”。 - Greg Hewgill

我指的是内存中不能有空隙。假设我想将它存储在二进制文件中，我认为这会适合我的内存情景。 - flowerpower

在这种情况下，您有几个选择：（1）将内存存储在一个连续的块中，这意味着当您添加新列时必须重新排列所有内容；（2）使用像我建议的存储布局，但仅将活动数据元素写入二进制文件；（3）允许在二进制文件中存在间隙（您需要在其上添加标题以描述以下数据的形状）。 - Greg Hewgill

Answer 2

如果您需要数组在内存中扩展并连续，一种实现方法是简单地使用一个一维数组并“伪造”第二个维度。

如果您的初始一维数组比所有二维数组所需的空间更多，它不需要在内存中移动（可能避免了间隙）。但是，根据您的实现方式，使其中一个子数组增长的插入可能需要将后面的元素向下移动（您也可以在数组中留下间隙，但我认为这违反了您的无间隙要求）。

如果您确实需要两个维度，则格雷格的答案是正确的选择。如果您知道数据的大小，那么就会更容易。

- cjh