C语言 正确分配多维数组

ubof19bj  于 2022-12-03  发布在  其他
关注(0)|答案(2)|浏览(110)
  • 这个问题的目的是提供一个关于如何在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;
}

输出量
这段代码运行得很好!怎么会出错呢?

yebdmbv4

yebdmbv41#

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

什么是数组?

数组的正式定义可在C语言标准 ISO 9899:2011 6.2.5/20 Types 中找到。
数组型别描述具有特定成员对象型别(称为元素型别)的连续配置非空白对象集。
简单英语,数组是在相邻的存储单元中连续分配的相同类型的项的集合。
例如,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时,它“衰减”为指向第一个元素的指针。
类似地,我们可以使用非常类似的指针算法,通过使用一个 array pointer 来迭代数组的数组:

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 [2][3]类型的变量arr衰退为指向第一个元素的指针,第一个元素是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(34=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));

连续分配也是其他类似的标准库函数(如memsetstrcpybsearchqsort)工作的原因。它们被设计为在连续分配的数组上工作。因此,如果你有一个多维数组,你可以高效地搜索它,并使用bsearchqsort对其排序。从而为每个项目重新发明轮子。
数组和其他类型之间的所有上述一致性都是我们希望利用的一件非常好的事情,特别是在进行泛型编程时。

如果不是数组,指针到指针是什么?

现在回到问题中的代码,它使用了不同的语法,使用了指针到指针。这并不神秘。它是一个指针到类型的指针,不多不少。它不是数组。它不是二维数组。严格地说,它不能用来指向数组,也不能用来指向二维数组。
然而,指针到指针可以用来指向指针数组的第一个元素,而不是指向整个数组。这就是它在问题中的用法--作为一种“模拟”数组指针的方式。在问题中,它被用来指向一个2个指针的数组。然后,2个指针中的每一个都被用来指向一个3个整数的数组。
这就是所谓的查找表,它是一种抽象数据类型(ADT),与普通数组的低级概念有所不同。主要区别在于查找表是如何分配的:

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

这个例子中的32位地址是虚构的。0x12340000框表示指针到指针。它包含指向指针数组中第一项的地址0x12340000。该数组中的每个指针依次包含指向整数数组中第一项的地址。
问题就从这里开始。

查找表版本有问题

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

  • 我们不能像预期的那样使用指针算法。虽然我们可以使用指针算法的一种形式来索引和访问查找表中的项,但我们不能使用数组指针来这样做。

  • 我们不能使用sizeof运算符。如果用在指针到指针的位置,它会给予指针到指针的大小。如果用在第一个指向的项,它会给出指针的大小。它们都不是数组的大小。

  • 我们不能使用数组类型以外的标准库函数(memcpymemsetstrcpybsearchqsort等)。所有这些函数都假定以数组作为输入,数据是连续分配的。用我们的查找表作为参数调用它们会导致未定义的行为错误,比如程序崩溃。

  • 重复调用malloc以分配多个段会导致堆fragmentation,这反过来又会导致RAM内存的使用率低下。

  • 由于内存是分散的,CPU在遍历查找表时无法利用高速缓存。有效使用数据高速缓存需要连续的内存块,从上到下遍历。这意味着,根据设计,查找表的访问时间比真实的多维数组慢得多。

  • 对于每次调用malloc(),管理堆的库代码必须计算哪里有空闲空间。同样,对于每次调用free(),都有必须执行的开销代码。因此,出于性能考虑,尽可能少地调用这些函数通常是更可取的。
    查找表都是坏的吗?

正如我们所看到的,基于指针的查找表有很多问题。但它们并不都是坏的,它是一个和其他工具一样的工具。它只需要用于正确的目的。如果你正在寻找一个多维数组,它应该被用作数组,查找表显然是错误的工具。但它们可以用于其他目的。
当你需要所有维度的大小都完全可变时,查找表是正确的选择。这样的容器在创建C字符串列表时非常方便。然后,为了保存内存,通常需要考虑上述的执行速度和性能损失。
另外,查找表的优点是,您可以在运行时重新分配表的一部分,而不需要重新分配整个多维数组。如果这是需要经常做的事情,查找表甚至可能在执行速度方面优于多维数组。例如,在实现链接哈希表时可以使用类似的查找表。

如何正确地动态分配多维数组?

现代C语言中最简单的形式就是使用可变长度数组(VLA). int array[x][y];其中xy是在运行时给定值的变量,在数组声明之前。但是,VLA具有局部作用域,并且不会在整个程序期间持续存在-它们具有自动存储持续时间。因此,尽管VLA用于临时数组可能方便快捷,它不是问题中查找表的通用替代。
要真正动态地分配多维数组,使其获得 * 分配的存储持续时间 *,我们必须使用malloc()/calloc()/realloc()
在现代C语言中,你可以使用指向VLA的数组指针。即使程序中没有实际的VLA,你也可以使用这样的指针。使用它们比使用普通的type*void*的好处是增加了类型安全。使用指向VLA的指针还允许你将数组维数作为参数传递给使用数组的函数,使它同时具有变量和类型安全。
不幸的是,为了利用VLA指针的好处,我们不能将指针作为函数结果返回。因此,如果我们需要将数组指针返回给调用者,它必须作为参数传递(原因在Dynamic memory access only works inside function中描述)。这在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);
}

虽然这个语法带有 a pointer to a array pointer,看起来可能有点奇怪和吓人,但即使我们添加更多的维度,它也不会变得比这更复杂:

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;
}
os8fio9y

os8fio9y2#

C没有多维数组(作为一种 primitive 数据类型)。但是你可以有数组的数组(或者其他聚合的数组)和指针数组。

一种可能的方法是用一些abstract data type(也许使用flexible array members,这是一种实现技巧,您可以使用其他方法)进行推理,如this answer
我们不能建议任何抽象数据类型,因为这取决于你的家庭作业,我们没有。你需要设计你的抽象数据类型(在一张纸上),然后实现它。
一旦您(在纸上或白板上)列出ADT所需的所有操作,就可以直接实现它们。
这段代码运行得很好!怎么会出错呢?
那句话前后矛盾(错误的w.r.t.什么规格?)...
我建议编译时使用所有警告和调试信息(例如withgcc -Wall -Wextra -g with GCC),以改进代码直到没有警告,使用调试器gdb(了解程序中发生了什么)和其他工具(如valgrind)。

相关问题