动态2D数组如何存储在内存中？

Question

2D数组如何存储在内存中？

我想到了以下方法,其中行存储为重要的内存块.

| _ __ _ __ _ __ || _ __ _ __ _ __ |__ _ __ _ __| _ __ _ __ _ _ | ... | _ __ _ __ _ __ |

这些元素像(i,j) - > n*i + j一样被加入,其中n是矩阵的维数(假设它是nxn).

但是,如果我想添加一个新列怎么办？我必须更新每一行中的每个第(n + 1)个元素,并将它们移到右边,但这在计算上太昂贵了.

另一种选择是将矩阵复制到新位置,并使用新列的元素动态更新行.但如果阵列很大,这也不太有效.

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

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

我不是要求使用指针和实际RAM内存的C实现,我只是对在内存中存储动态2d数组的理论方法感到好奇,因此很容易为其添加新的行或列.

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

Answer 1

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

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

这将是分配动态一维数组的常用技术的二维扩展。