为了回答这个问题,我们首先需要澄清一些概念。什么是数组?它如何使用?那么问题中的代码又是什么呢,难道不是一个数组吗?
什么是数组?
数组的正式定义可以在C标准中找到,ISO 9899:2011 6.2.5/20 Types。
数组类型描述了一组连续分配的非空对象,这些对象具有特定的成员对象类型,称为元素类型。
简单来说,数组是同一类型的项目集合,以相邻的内存单元连续分配。
例如,一个包含3个整数的数组 int arr[3] = {1,2,3};
将在内存中分配如下:
+
| | | |
| 1 | 2 | 3 |
| | | |
+
所以多维数组的正式定义是什么?实际上,它与上面引用的定义完全相同。它递归地应用。如果我们要分配一个二维数组,
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;
for(size_t i=0; i<3; i++)
{
printf("%d ", *ptr);
ptr++;
}
这是通过"数组衰减"实现的。当在表达式中使用
arr
时,它会"衰减"为指向第一个元素的指针。
同样地,我们可以使用相同类型的指针算术来迭代数组中的数组,通过使用一个
数组指针:
int arr[2][3] = { {1,2,3}, {1,2,3} };
int (*ptr)[3] = arr;
for(size_t i=0; i<2; i++)
{
printf("%d %d %d\n", (*ptr)[0], (*ptr)[1], (*ptr)[2]);
ptr++;
}
再次出现了数组衰变。类型为int [2][3]
的变量arr
衰变成了指向第一个元素的指针。第一个元素是int [3]
,指向这样一个元素的指针被声明为int(*)[3]
- 一个数组指针。
理解数组指针和数组衰变对于处理多维数组是必要的。
有更多情况下数组表现得就像普通变量一样。对于非VLA数组,sizeof
运算符的工作方式与普通变量完全相同。以下是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));
Contiguous allocation是其他类似标准库函数(如memset、strcpy、bsearch和qsort)能够工作的原因。它们被设计为在连续分配的数组上运行。因此,如果您有一个多维数组,可以使用bsearch和qsort高效地搜索和排序它,省去了自己实现二分查找和快速排序的麻烦,从而避免了为每个项目重新发明轮子。
所有上述数组与其他类型之间的一致性都是我们想要利用的非常好的事情,特别是在进行通用编程时。
如果不是数组,指针指向指针是什么意思?
现在回到问题中的代码,它使用了一个指向指针的不同语法。这并没有什么神秘的地方。它只是一个指向类型的指针,没有多余的东西。它不是一个数组,也不是一个二维数组。严格来说,它不能用于指向一个数组,也不能用于指向一个二维数组。
然而,指向指针的指针可以用来指向指针数组的第一个元素,而不是整个数组。这就是它在问题中的使用方式——作为“模拟”数组指针的一种方式。在问题中,它被用来指向一个由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
是在运行时给定值的变量,在数组声明之前。但是,VLAs具有局部作用域,并且在程序运行期间不会持续存在 - 它们具有自动存储期。因此,虽然VLAs可能方便快捷地用于临时数组,但它们并不能普遍替代问题中的查找表。
为了真正动态分配多维数组,使其获得分配的存储期,我们必须使用malloc()
/calloc()
/realloc()
。下面我将给出一个示例。
在现代C语言中,您可以使用指向VLA的数组指针。即使在程序中没有实际的VLA,您也可以使用这些指针。使用指向VLA的指针的好处是增加了类型安全性。使用指向VLA的指针还允许您将数组维度作为参数传递给使用数组的函数,使其同时具有可变性和类型安全性。
很遗憾,为了使用指向可变长度数组的指针的好处,我们不能将该指针作为函数结果返回。因此,如果我们需要将指向数组的指针返回给调用者,则必须将其作为参数传递(原因在仅在函数内部工作的动态内存访问中描述)。这在C语言中是可以接受的做法,但使代码难以阅读。它看起来会像这样:
void arr_alloc (size_t x, size_t y, int(**aptr)[x][y])
{
*aptr = malloc( sizeof(int[x][y]) );
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]) );
assert(*aptr != NULL);
}
现在将该代码与添加一个维度到查找表版本的代码进行比较:
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个维度了...
使用真正的二维数组的完整代码
#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]) );
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);
return 0;
}
bsearch/qsort
?它们的意图是用于单一维度操作。如果你将它们用于对 p2p 数组第一维的指针排序,只要用户定义适当的比较函数并给出有效参数,它就能像对 2D 数组的行进行排序一样正常工作。 - user694733*aptr = malloc(sizeof **aptr)
作为*aptr = malloc(sizeof(int[x][y]))
的替代方案,这样可以符合惯用法的正确性,即pointer = malloc(sizeof *pointer)
。请注意,这两者的意思相同且不含解释。 - chux - Reinstate Monicamalloc
函数以分配多个内存段会导致堆(heap)碎片化,从而导致RAM内存使用不佳。通过仅调用N+1次malloc()
函数,可以几乎毫不费力地动态分配N维“数组”,而仅使用一次调用来分配一个N维“数组”则是可能的,但并不容易实现。 - Andrew Henle