c++ - 数组的物理存储方式(特别是维度大于 2 的数组)？

Question

我所知道的

我知道数组 int ary[] 可以用等效的“指针”格式表示:int* ary。但是，我想知道的是，如果这两者相同，那么数组的物理存储方式是怎样的？

我曾经认为元素是像数组 ary 一样在 ram 中彼此相邻存储的:

int size = 5;
int* ary = new int[size];
for (int i = 0; i < size; i++) { ary[i] = i; }

这(我相信)像这样存储在 RAM 中:...[0][1][2][3][4]...

这意味着我们随后可以通过将指针的位置增加索引来将 ary[i] 替换为 *(ary + i)。

问题

当我以同样的方式定义一个二维数组时，问题就来了:

int width = 2, height = 2;
Vector** array2D = new Vector*[height]
for (int i = 0; i < width; i++) {
    array2D[i] = new Vector[height];
    for (int j = 0; j < height; j++) { array2D[i][j] = (i, j); }
}

鉴于类 Vector 是我将 x 和 y 存储在一个基本单元中:(x, y)。

那么上面的内容究竟是如何存储的呢？

1. 逻辑上不能像 ...[(0, 0)][(1, 0)][(0, 1)][(1, 1)]... 因为这意味着第 (1, 0) 元素与第 (0, 1) 元素相同。

2. 它也不能存储在如下所示的二维数组中，因为物理 RAM 是一个 8 位数字的一维数组:

   • ...[(0, 0)][(1, 0)]...
   • ...[(0, 1)][(1, 1)]...

3. 也不能像...[&(0, 0)][&(1, 0)][&(0, 1)][&(1, 1)]那样存储...，给定 &(x, y) 是指向 (x, y) 位置的指针。这意味着每个内存位置只会指向另一个内存位置，而该值无法存储在任何地方。

先谢谢你。

Answer 1

什么 OP 正在努力处理动态分配的指向动态分配数组的指针数组。这些分配中的每一个都是位于存储中某处的自己的内存块。除了外部数组中的指针建立的逻辑连接外，它们之间没有任何连接。

试着形象化说我们做的

int ** twodee;
twodee = new int*[4];
for (int i = 0; i < 4; i++)
{
    twodee[i] = new int[4];
}

然后

int count = 1;
for (int i = 0; i < 4; i++)
{
    for (int j = 0; j < 4; j++)
    {
        twodee[i][j] = count++;
    }
}

所以我们应该以 twodee 看起来像

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15 16

对吧？

从逻辑上讲，是的。但在内存中布局 twodee 可能看起来像这个 batsmurph 疯狂的困惑:

您无法真正预测您的内存将位于何处，您将受制于处理分配的任何内存管理器以及存储中可能对您的内存高效使用的内容。这使得在您的头脑中布置动态分配的多维数组几乎是浪费时间。

当您深入了解现代 CPU 可以为您做些什么时，这有很多问题。 CPU 必须经常跳动，当它跳动时，它预测和预加载缓存的能力可能会受到影响。这意味着您的千兆赫兹计算机不得不在兆赫兹 RAM 上闲坐等待，这比它应该做的要多得多。

尽可能通过分配单个连续的内存块来避免这种情况。您可能会使用一些额外的代码将一维内存映射到其他维度，但您不会损失任何 CPU 时间。无论如何，只要您编译了 [i][j]，C++ 就会为您生成所有映射数学。