当使用malloc时，C如何为2D（3D...）数组分配空间？

Question

我有一个问题不太理解C语言如何为二维数组（或更高维数组）分配空间，特别是在使用malloc等函数时。以这个问题中的程序为例。

首先定义了一个一维指针数组，然后把指向1D数据（在本例中是字符串）的指针放入第一个1D数组的每个盒子中。因此不能保证整个2D数组是连续的（上一行的最后一个单元格后面是下一行的第一个单元格）。每个1D数据数组可能相距很远，只有它们的指针是连续的。我的理解是否正确？还是我漏掉了什么？如果您能帮我澄清这个问题，我会非常感激。

- makhlaghi

---

另一种分配二维数组的方法是使用单个缓冲区，然后根据二维坐标进行索引。8 * 8 = 64。分配一个单独的64字节缓冲区，索引= x + y * 8。 - Justin Meiners

因此，像上面的问题一样定义一个二维数组确实是不连续的。谢谢。我知道如何关联8x8=64个空间，你能给我一个例子吗？我如何基于2D坐标进行索引？谢谢。 - makhlaghi

Answer 1

根据访问方式的不同，有多种方法来实现它。您可以确保数组的主体是连续的，也可以避免这样做。对于字符串数组，通常不需要使数组主体连续。对于整数或双精度的二维（等等）数组，通常会使数组主体连续。

在这些示例中，数组的数据类型是通用类型T，假定为数字类型，因此可以将数组元素分配为0。这些示例没有检查内存分配错误；生产代码应该进行检查。

使用计算索引访问数组-连续的数组主体。

int n1 = 5;
int n2 = 6;

T *a = malloc(n1 * n2 * sizeof(T));

for (int i = 0; i < n1; i++)
    for (int j = 0; j < n2; j++)
        a[i * n2 + j] = 0;

free(a);

双下标数组访问 — 连续的数组体

int n1 = 5;
int n2 = 6;

T **a = malloc(n1 * sizeof(T*));
T  *b = malloc(n1 * n2 * sizeof(T));

for (int i = 0; i < n1; i++)
    a[i] = &b[i * n2];

for (int i = 0; i < n1; i++)
    for (int j = 0; j < n2; j++)
        a[i][j] = 0;

free(b);
free(a);

使用双下标访问数组——不连续的数组体

int n1 = 5;
int n2 = 6;

T **a = malloc(n1 * sizeof(T*));

for (int i = 0; i < n1; i++)
    a[i] = malloc(n2 * sizeof(T));

for (int i = 0; i < n1; i++)
    for (int j = 0; j < n2; j++)
        a[i][j] = 0;

for (int i = 0; i < n1; i++)
    free(a[i]);
free(a);

- Jonathan Leffler

---

非常感谢您提供完整的示例，我现在完全明白了。 - makhlaghi

只有一个问题：使用计算索引的“连续数组体”似乎比使用双下标的“连续数组体”更简单（因此更快），我是正确的吗？ - makhlaghi

这是一个乘法和加法速度与内存访问速度的问题。现在，计算速度往往比内存访问速度快，但双下标的符号便利性也不可忽略。这是一个权衡取舍的游戏。选择适合自己的方法；如果性能很重要，就进行性能测试。 - Jonathan Leffler

Answer 2

方法1（指向缓冲区的指针，非连续）

您是正确的，不能保证数据是连续的，实际上很可能不是。顶层数组（行）只是指针的一维数组（每个元素都是它自己的指针）。这些指针各自指向它们自己的实际对象的一维数组。这些缓冲区仅通过指针连接。

/* allocation */
int** array = malloc(sizeof(int*) * height)
for (int y = 0; y < height; y ++)
{
   array[i] = malloc(sizeof(int) * width);
}
/* indexing */
int item = array[y][x];

方法2（单缓冲，连续的）

另一种分配2D数组的方法是使用单个缓冲区，然后基于2D坐标进行索引。例如 8 * 8 = 64。分配一个单独的64字节缓冲区并进行索引= x + y * 8。该方法将数据存储在连续的位置上，它比方法1更容易分配和释放。

/* allocation */
int* array = malloc(sizeof(int) * width * height)
/* indexing */
int item = array[x + y * width];

- Justin Meiners

---

我一直认为连续的数组对计算机来说更容易（因此更快）进行分析，这个理解正确吗？我知道对于小数据集来说，这并没有太大区别，但是我猜对于大数据集（比如大图像）会有影响。我的理解正确吗？ - makhlaghi

@astroboy 连续的数据布局对于迭代和随机访问小到大的数据集来说更加缓存友好。我想除了最小的数据集以外，速度明显更快。它也更容易进行malloc和free操作。 - Justin Meiners

Answer 3

我认为你是正确的。但是如果您真的想让数组连续，您可以使用malloc申请一个一维数组，并像使用二维数组一样使用它，例如：

int* oneDArray = (int*)malloc(sizeof(int)*10*10);
int a = oneDArray[i*10+j];     //which equals to twoDArray[i][j]

- Manas