正确分配多维数组

Question

这个问题的目的是为如何正确地在C语言中动态地分配多维数组提供一个参考。这是一个经常被误解的话题，甚至在一些C语言编程书籍中也没有得到很好的解释。因此，即使是经验丰富的C程序员也很难正确地完成它。

我从我的编程老师/书/教程中学到，动态分配多维数组的正确方法是使用指针到指针。

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

int** arr_alloc (size_t x, size_t y)
{
  int** pp = malloc(sizeof(*pp) * x);
  assert(pp != NULL);
  for(size_t i=0; i<x; i++)
  {
    pp[i] = malloc(sizeof(**pp) * y);
    assert(pp[i] != NULL);
  }

  return pp;
}

int** arr_fill (int** pp, size_t x, size_t y)
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      pp[i][j] = (int)j + 1;
    }
  }

  return pp;
}

void arr_print (int** pp, size_t x, size_t y)
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      printf("%d ", pp[i][j]);
    }
    printf("\n");
  }
}

void arr_free (int** pp, size_t x, size_t y)
{
  (void) y;

  for(size_t i=0; i<x; i++)
  {
    free(pp[i]);
    pp[i] = NULL;
  }
  free(pp);
  pp = NULL;
}


int main (void)
{
  size_t x = 2;
  size_t y = 3;
  int** pp;

  pp = arr_alloc(x, y);
  pp = arr_fill(pp, x, y);
  arr_print(pp, x, y);
  arr_free(pp, x, y);

  return 0;
}

1 2 3
1 2 3

Answer 1

为了回答这个问题，我们首先要弄清楚一些概念。什么是数组，如何使用数组？问题中的代码是什么，如果不是数组的话？

什么是数组？

数组的正式定义见于C标准ISO 9899：2011 6.2.5/20 Types。

+-------+-------+-------+
|       |       |       |
|   1   |   2   |   3   |
|       |       |       |
+-------+-------+-------+

+-------+-------+-------+-------+-------+-------+
|       |       |       |       |       |       |
|   1   |   2   |   3   |   1   |   2   |   3   |
|       |       |       |       |       |       |
+-------+-------+-------+-------+-------+-------+

C中的数组通常遵循与常规变量相同的类型系统。如上所示，您可以拥有数组数组，就像您可以拥有任何其他类型的数组一样。

您还可以对n维数组应用与普通一维数组相同的指针算术。对于常规的一维数组，应用指针算术应该很简单：

int arr[3] = {1,2,3};
int* ptr = arr; // integer pointer to the first element.

for(size_t i=0; i<3; i++)
{
  printf("%d ", *ptr); // print contents.
  ptr++; // set pointer to point at the next element.
}

这是通过“阵列衰变”而成为可能的。当在表达式中使用arr时，它“衰减”为指向第一个元素的指针。

int arr[2][3] = { {1,2,3}, {1,2,3} };
int (*ptr)[3] = arr; // int array pointer to the first element, which is an int[3] array.

for(size_t i=0; i<2; i++)
{
  printf("%d %d %d\n", (*ptr)[0], (*ptr)[1], (*ptr)[2]); // print contents
  ptr++; // set pointer to point at the next element
}

int x；printf（“%zu”,sizeof(x))；打印4.
int arr[3]={1,2,3}；printf（“%zu”,sizeof（arr））；打印12(3*4=12)
int arr[2][3]={{1,2,3},{1,2,3}}；printf（“%zu”,sizeof（arr））；打印24(2*3*4=24)

与任何其他类型一样，数组可以与库函数和泛型API一起使用。由于数组满足连续分配的要求，例如，我们可以使用memcpy安全地复制它们：

int arr_a[3] = {1,2,3};
int arr_b[3];
memcpy(arr_b, arr_a, sizeof(arr_a));

连续分配也是其他类似的标准库函数如memset、strcpy、bsearch和qsort工作的原因。它们被设计用来处理连续分配的数组。因此，如果您有一个多维数组，您可以使用bsearch和qsort高效地搜索它并对其进行排序，从而省去了自己实现二进制搜索和快速排序的麻烦，从而为每个项目重新发明轮子。

指针到指针的东西是什么，如果不是数组的话？

现在回到问题中的代码，它使用了不同的语法，指针指向指针。这没什么神秘的。它是一个指针指向类型的指针，不多不少。它不是数组。它不是2D数组。严格地说，它不能用来指向一个数组，也不能用来指向一个2D数组。

但是，指针指向指针可以用于指向指针数组的第一个元素，而不是指向整个数组。这就是它在问题中的用法--作为“模拟”数组指针的一种方式。在问题中，它被用来指向一个由2个指针组成的数组。然后用这两个指针中的每一个指向一个3个整数的数组。

+------------+
|            |
| 0x12340000 |
|            |
+------------+
      |
      |
      v
+------------+     +-------+-------+-------+
|            |     |       |       |       |
| 0x22223333 |---->|   1   |   2   |   3   |
|            |     |       |       |       |
+------------+     +-------+-------+-------+
|            | 
| 0xAAAABBBB |--+
|            |  | 
+------------+  |  
                |
                |  +-------+-------+-------+
                |  |       |       |       |
                +->|   1   |   2   |   3   |
                   |       |       |       |
                   +-------+-------+-------+

我们不能使用异常数组类型的标准库函数(memcpy、memset、strcpy、bsearch、qsort等等）。所有这样的函数都假定以连续分配数据的方式获取数组作为输入。用我们的查找表作为参数调用它们会导致未定义的行为错误，如程序崩溃。

重复调用malloc来分配几个段会导致堆碎片，进而导致RAM内存使用不良。

由于内存是分散的，CPU在遍历查找表时不能利用高速缓冲存储器。有效地使用数据缓存需要从上到下迭代的连续内存块。这意味着，根据设计，查找表的访问时间比真正的多维数组要慢得多。

要真正动态地分配一个多维数组，以便它得到分配的存储持续时间，我们必须使用malloc()/calloc()/realloc()。下面我举一个例子。

在现代C语言中，您将使用数组指针指向VLA。即使在程序中没有实际的VLA时，也可以使用这样的指针。与普通类型*或void*相比，使用它们的好处是增加了类型安全性。使用指向VLA的指针还可以将数组维度作为参数传递给使用数组的函数，使其同时具有变量和类型安全。

不幸的是，为了使用指向VLA的指针的好处，我们不能将该指针作为函数结果返回。因此，如果我们需要向调用方返回一个指向数组的指针，它必须作为参数传递（由于动态内存访问中描述的原因，它只在函数内部工作）。这在C语言中是很好的做法，但使代码有点难读。它看起来如下所示：

void arr_alloc (size_t x, size_t y, int(**aptr)[x][y])
{
  *aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array
  assert(*aptr != NULL);
}

void arr_alloc (size_t x, size_t y, size_t z, int(**aptr)[x][y][z])
{
  *aptr = malloc( sizeof(int[x][y][z]) ); // allocate a true 3D array
  assert(*aptr != NULL);
}

/* Bad. Don't write code like this! */
int*** arr_alloc (size_t x, size_t y, size_t z)
{
  int*** ppp = malloc(sizeof(*ppp) * x);
  assert(ppp != NULL);
  for(size_t i=0; i<x; i++)
  {
    ppp[i] = malloc(sizeof(**ppp) * y);
    assert(ppp[i] != NULL);
    for(size_t j=0; j<y; j++)
    {
      ppp[i][j] = malloc(sizeof(***ppp) * z);
      assert(ppp[i][j] != NULL);
    }
  }

  return ppp;
}

使用真2D数组的版本的完整代码

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

void arr_alloc (size_t x, size_t y, int(**aptr)[x][y])
{
  *aptr = malloc( sizeof(int[x][y]) ); // allocate a true 2D array
  assert(*aptr != NULL);
}

void arr_fill (size_t x, size_t y, int array[x][y])
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      array[i][j] = (int)j + 1;
    }
  }
}

void arr_print (size_t x, size_t y, int array[x][y])
{
  for(size_t i=0; i<x; i++)
  {
    for(size_t j=0; j<y; j++)
    {
      printf("%d ", array[i][j]);
    }
    printf("\n");
  }
}

int main (void)
{
  size_t x = 2;
  size_t y = 3;
  int (*aptr)[x][y];

  arr_alloc(x, y, &aptr);
  arr_fill(x, y, *aptr);
  arr_print(x, y, *aptr);
  free(aptr); // free the whole 2D array

  return 0;
}