为什么指针算法适用于非连续的二维数组？

Question

我的理解是，如果一个人在本地声明一个二维数组：int 2darr[x][y]，它不是一个指针数组，其中每个指针指向它自己的一维数组，而是一个一维数组处理器执行 *(2darr + (row x nCols) + col).

类型的指针运算

在这种情况下，语法糖 2darr[row][col] 背后的指针算法是有意义的，因为我们的二维数组实际上只是一个大小为 nRows x nCols.[=18 的连续内存块=]

然而，动态分配二维数组的一种方法是首先分配一个大小为 nRows 的指针数组，然后为每个指针分配一个大小为 nCols 的任何类型的数组我们想要。在那种情况下，我们的行不一定连续存储在内存中；每行都可以存储在内存中完全不同的位置，我们的指针数组中的一个指针指向它的第一个元素。

鉴于此，我不明白我们如何仍然可以通过 2darr[row][col] 访问二维数组中的数据。由于我们的行不能保证连续存储，因此类型 *(2darr + (row x nCols) + col) 的指针算法根本不能保证工作。

Answer 1

您的数组 2darr 是 个数组 的数组。

例如，这样的定义

int aa[2][3];

是一个包含两个元素的数组，每个元素又是一个包含三个 int 值的数组。

记忆中是这样的

+----------+----------+----------+----------+----------+----------+
| aa[0][0] | aa[0][1] | aa[0][2] | aa[1][0] | aa[1][1] | aa[1][2] |
+----------+----------+----------+----------+----------+----------+

关于指针运算的部分可能让您感到困惑，对于任何数组（或指针！）a 和索引 i，表达式 a[i] 等于 *(a + i).

使用上面的 "formula" 没有数组数组，你用 aa[i] 得到的是另一个数组。 IE。 *(aa + i) 是另一个数组，您又可以在其上使用索引，如 (*(aa + i))[j]。第二级索引当然也可以使用指针算法来编写，如 *(*(aa + i) + j).

如果没有数组 aa，您所显示的表达式将是 *(aa + i * 3 + j)，但对于数组的数组，这是不正确的。我的意思是它不会语义正确。这是因为 *(aa + i * 3 + j) 实际上与 aa[i * 3 + j] 相同，后者在 aa 的情况下是数组。表达式 aa[i * 3 + j]（因此 *(aa + i * 3 + j)）的类型为 int[3]。它不是单个 int 元素。

你的表达式，形式为 *(a + row * ncol + col) 只有当你只有一个数组时才是正确的。喜欢

int bb[6];  // 6 = 2 * 3

现在这个数组可以使用*(bb + i * 3 + j)（或bb[i * 3 + j]）进行索引，结果将是单个int值。

使用指向指针的指针实现的“二维”数组（实际上不是）也称为 jagged array，它不必是连续的。这意味着 *(2darr + (row x nCols) + col) 表达式确实无效。

再举个简单的例子：

int **pp;

pp = malloc(sizeof *pp * 2);  // Two elements in the "outer" array
for (size_t i = 0; i < 2; ++i)
{
    pp[i] = malloc(sizeof **pp * 3);  // Three elements in the "inner" array
}

上面的代码创建了一个与上面的 aa 相似的 "two-dimensional" 数组。最大的区别是它的内存布局，类似于

+-------+-------+
| pp[0] | pp[1] |
+-------+-------+
 |       |
 |       v
 |       +----------+----------+----------+
 |       | pp[1][0] | pp[1][1] | pp[1][2] |
 |       +----------+----------+----------+
 v
 +----------+----------+----------+
 | pp[0][0] | pp[0][1] | pp[0][2] |
 +----------+----------+----------+

对于外部数组，pp[i] 仍然等于 *(pp + i)，但是 aa[i] 导致三个 int 元素的数组，pp[i]是指向 int 的指针（即 int *）。

由于您可以对指针使用数组索引语法，因此可以对 pp[i] 中的指针进行索引，然后您就有了 "two-dimensional" 语法 pp[i][j].

虽然 *(pp + i * 3 + j) 表达式无效，因为内存不连续，但上面显示的所有其他指针算法都是。例如（如图所示）pp[i] 等于 *(pp + i)。但是因为那是一个可以索引的指针，所以(*(pp + i))[j]也是有效的，*(*(pp + i) + j).

也是有效的

Answer 2

用SomeType A[M][N]定义的数组和用指向指针数组的指针实现的数组都可以作为A[i][j]访问的原因是由于下标运算符的工作方式，指针的工作方式算术运算，以及数组到指针的自动转换。

一个关键的区别是，在A[i][j]中使用指针，A[i]是一个指针，其值从内存中获取，然后与[j]一起使用。相反，在 A[i][j] with arrays 中， A[i] 是一个数组，其作为指针的值基于数组本身；表达式中数组的使用被转换为指向其第一个元素的指针。指针的 A[i] 和数组的 A[i] 下一步都需要使用指针，但第一个是从内存中的指针加载，第二个是从数组存储在内存中的位置计算。

首先，考虑一个数组定义为：

SomeType A[M][N];

鉴于此，当对表达式 A[i][j] 求值时，求值过程为：

A是一个数组。
在这种情况下¹，数组自动转换为指向其第一个元素的指针。我们称之为 p。 A是一个M个元素的数组，每个数组都是SomeType个N个元素的数组。所以 p 是指向 SomeType.

N

p 替换了 A，所以表达式现在是 p[i][j].
下标的定义表示E1[E2]等同于(*(E1+E2))。（为了简洁起见，我省略了正式定义中的括号。）当我们将其应用于第一个下标时，p[i][j] 变为 (*(p+i)[j].
接下来，计算p+i。指针运算以指向的类型为单位。由于 p 指向 N 个元素的数组，因此 p+i 从第一个数组（索引为 0）移动到索引为 i 的数组。我们称之为 q.
现在我们有 (*q)[j]，其中 q 指向 A 的元素 i。请注意，此元素 q 指向的是 N 个元素的数组 SomeType.
由于q指向一个数组，*q是数组。
此数组自动转换为指向其第一个元素的指针。我们称之为 r。 r指向数组的第一个元素q指向.
现在我们有 (r)[j]，或者，去掉括号 r[j]，其中 r 指向数组的元素 0，即 i 的元素 [=] 23=].
同样，下标的定义表示这与 (*(r+j)) 相同。
通过指针运算r+j指向数组的元素j。
由于r+j指向元素j，*(r+j)是数组的元素j。
因此 A[i][j] 是由 A 中的 i 索引的数组的元素 j。

现在考虑一个用指向指针的指针实现的二维数组，如下代码所示：

SomeType **A = malloc(M * sizeof *A);
for (size_t i = 0; i < M; ++j)
    A[i] = malloc(N * sizeof *A[i]);

（我们假设所有 malloc 调用都成功。在生产代码中，应对它们进行测试。）

鉴于此，当对表达式 A[i][j] 求值时，求值过程为：

A是指向SomeType的指针。
根据下标的定义，A[i][j]等同于(*(A+i))[j]。
通过指针运算，A+i 从 A 指向的位置移动到它后面的 i 个元素。在这种情况下，A 指向指针（特别是指向 SomeType 的指针），因此指针运算的元素就是那些指针。所以 A+i 指向第一个指针之外的 i 个指针。我们称之为 q.
现在我们有 (*q)[j]，其中 q 指向我们创建的指针数组中的元素 i。
因为q指向一个指针，所以*q就是那个指针。我们称之为 r。 r 指向分配给其中一个 malloc 调用的第一个元素（SomeType）。
现在我们有 (r)[j]，或者，去掉括号 r[j]，其中 r 指向指针数组中的元素 i。
同样，下标的定义表示这与 (*(r+j)) 相同。
通过指针运算r+j指向第一个元素r指向的数组的元素j。
由于r+j指向元素j，*(r+j)是数组的元素j。
因此 A[i][j] 是由 A 中的 i 索引的数组的元素 j。

脚注

¹ 类型为“array of type”的表达式被转换为指向数组第一个元素的指针，除非它是 sizeof、_Alignof 或一元 & 的操作数，或者是用于初始化数组的字符串文字。

为什么指针算法适用于非连续的二维数组？

Why does pointer artihmetic work with non-contiguous 2d arrays?

c

arrays

pointers

memory

pointer-arithmetic

脚注