正确分配多维数组

Question

这个问题的目的是提供一个关于如何在C中动态正确分配多维数组的参考.这是一个经常被误解的主题,即使在一些C编程书籍中也很难解释.因此,即使是经验丰富的C程序员也很难做到正确.

---

我从编程教师/书籍/教程中了解到,动态分配多维数组的正确方法是使用指针指针.

然而,SO上的几个高代表用户现在告诉我这是错误和不好的做法.他们说指针到指针不是数组,我实际上并没有分配数组,而且我的代码不必要地慢.

这就是我教我分配多维数组的方法:

#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类型中找到.

数组类型描述了具有特定成员对象类型的连续分配的非空对象集,称为元素类型.

在简单的英语中,数组是在相邻的存储器单元中连续分配的相同类型的项的集合.

例如,一个包含3个整数的数组int arr[3] = {1,2,3};将在内存中分配如下:

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

那么多维数组的形式定义呢？实际上,它与上面引用的定义完全相同.它递归应用.

如果我们要分配一个2D数组,int arr[2][3] = { {1,2,3}, {1,2,3} };它将在内存中分配如下:

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

我们在这个例子中实际上是一个数组数组.一个包含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
}

再次出现阵列衰变.arr类型的变量int [2][3]衰减为指向第一个元素的指针.第一个元素是a,int [3]并且指向这样一个元素的指针被声明为int(*)[3]- 一个数组指针.

理解数组指针和数组衰减是必要的,以便使用多维数组.

在更多情况下,数组的行为就像常规变量一样.sizeof对于(非VLA)数组,运算符与常规变量的运算方式相同.32位系统的示例:

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个整数的数组.

这被称为查找表,它是一种抽象数据类型(ADT),它与普通数组的低级概念不同.主要区别在于如何分配查找表:

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

此示例中的32位地址已组成.该0x12340000框表示指向指针的指针.它包含0x12340000指针数组中第一项的地址.依次包含该数组中的每个指针,包含指向整数数组中第一项的地址.

这就是问题的起点.

查找表版本的问题

查找表分散在堆内存中.它不是在相邻小区中连续分配的内存,因为每次调用malloc()都会给出一个新的内存区域,不一定与其他区域相邻.这反过来给我们带来了很多问题:

• 我们不能按预期使用指针算法.虽然我们可以使用指针算法的形式来索引和访问查找表中的项,但我们不能使用数组指针.

• 我们不能使用sizeof运算符.在指向指针的指针上,它会给我们一个指向指针的大小.用于指向的第一个项目,它会给我们一个指针的大小.它们都不是数组的大小.

• 我们不能使用标准库函数节选数组类型(memcpy,memset,strcpy,bsearch,qsort等等).所有这些函数都假设将数组作为输入,并且数据是连续分配的.使用我们的查找表作为参数调用它们会导致未定义的行为错误,例如程序崩溃.

• 重复调用malloc分配多个段会导致堆碎片,从而导致RAM内存使用不当.

• 由于存储器是分散的,因此在迭代查找表时CPU不能利用高速缓冲存储器.有效使用数据高速缓存需要一个连续的内存块,从上到下进行迭代.这意味着按设计,查找表的访问时间明显慢于真实的多维数组.

• 对于每次调用malloc(),管理堆的库代码必须计算有空闲空间的位置.类似地,对于每次调用free(),都存在必须执行的开销代码.因此,为了性能,通常优选尽可能少地调用这些功能.

查找表都不好吗？

我们可以看到,基于指针的查找表存在很多问题.但它们并非都是坏事,它是一种与其他工具一样的工具.它只需用于正确的目的.如果您正在寻找一个应该用作数组的多维数组,那么查找表显然是错误的工具.但它们可以用于其他目的.

当您需要所有尺寸单独具有完全可变尺寸时,查找表是正确的选择.例如,当创建C字符串列表时,这样的容器可以很方便.然后经常有理由采取上述执行速度性能损失以节省存储器.

此外,查找表的优点是您可以在运行时重新分配表的一部分,而无需重新分配整个多维数组.如果这是需要经常进行的事情,则查找表甚至可能在执行速度方面优于多维数组.例如,在实现链式哈希表时可以使用类似的查找表.

如何动态正确分配多维数组呢？

现代C中最简单的形式是简单地使用可变长度数组(VLA).int array[x][y];其中x和y是变量在运行时,先前的数组声明中给定值.但是,VLA具有本地范围,并且在整个程序期间不会持续存在 - 它们具有自动存储持续时间.因此,虽然VLA可能方便快捷地用于临时阵列,但它不是问题中查找表的通用替代品.

要动态分配多维数组,以便分配存储持续时间,我们必须使用malloc()/ calloc()/ realloc().我将在下面给出一个例子.

在现代C中,您将使用指向VLA的数组指针.即使程序中没有实际的VLA,也可以使用这样的指针.他们使用了一个普通的好处type*或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;
}

现在这是一个难以理解的"三星级节目".甚至不要考虑4个维度......

使用真正的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;
}