C/C++多维数组内部

Question

我有一个关于C/C++如何在内部存储使用符号声明的多维数组的问题foo[m][n].我不是在质疑指针的纯指针等等......因为速度原因,我在问...

如果我错了,请纠正我,但语法上foo是一个指针数组,它们本身指向一个数组

int foo[5][4]
*(foo + i)           // returns a memory address
*( *(foo + i) + j)    // returns an int

我从很多地方听说过C/C++编译器foo[m][n]在幕后转换为一维数组(计算所需的一维索引i * width + j).但是如果这是真的那么以下就可以了

*(foo + 1)          // should return element foo[0][1]

因此我的问题foo[m][n]是:(总是吗？)存储在内存中作为平面一维数组是真的吗？如果是这样,为什么上面的代码如图所示.

Answer 1

是的,C/C++将多维(矩形)数组存储为连续的内存区域.但是,您的语法不正确.要修改元素foo[0][1],以下代码将起作用:

*((int *)foo+1)=5;

显式类型转换是必要的,因为foo+1,是一样的&foo[1]它是不是在所有的同样的事情foo[0][1].*(foo+1)是指向平坦存储区中第五个元素的指针.换句话说,*(foo+1)基本上是foo[1]和**(foo+1)是foo[1][0].以下是一些二维数组的内存布局:

Answer 2

二维数组:

int foo[5][4];

不过是一个数组数组:

typedef int row[4];   /* type "row" is an array of 4 ints */
row foo[5];           /* the object "foo" is an array of 5 rows */

这里没有指针对象,无论是显式还是隐式.

数组不是指针.指针不是数组.

经常引起混淆的是,在大多数情况下,数组表达式被隐式转换为指向其第一个元素的指针.(并且一个单独的规则说看起来像数组参数声明实际上是一个指针声明,但这不适用于此示例.)数组对象是一个数组对象; 声明这样的对象不会创建任何指针对象.引用数组对象可以创建指针值(数组的第一个元素的地址),但是没有指针对象存储在内存中.

数组对象foo作为5个连续元素存储在内存中,其中每个元素本身是由4个连续int元素组成的数组; 因此,整个事物被存储为20个连续的int对象.

索引运算符是根据指针算法定义的; x[y]相当于*(x + y).通常,左操作数将是指针表达式或数组表达式; 如果它是一个数组表达式,则该数组被隐式转换为指针.

所以foo[x][y]相当于*(foo[x] + y),而这相当于*(*(foo + x) + y).(请注意,不需要强制转换.)幸运的是,您不必以这种方式编写它,并且foo[x][y]更容易理解.

请注意,您可以创建一个可以使用相同foo[x][y]语法访问的数据结构,但foo实际上是指向int的指针.(在这种情况下,每个[]运算符的前缀已经是一个指针表达式,并且不需要转换.)但要做到这一点,你必须声明foo为指向指针的指针:

int **foo;

然后分配并初始化所有必要的内存.这比int foo[5][4]以前更灵活,因为您可以动态地确定每行的行数和大小(甚至存在).

comp.lang.c FAQ的第6节很好地解释了这一点.

编辑:

在回应Arrakis的评论时,重要的是要记住类型和表示之间的区别.

例如,这两种类型:

struct pair { int x; int y;};
typedef int arr2[2];

很可能在内存中有相同的表示(两个连续的int对象),但访问元素的语法是完全不同的.

类似地,类型int[5][4]和int[20]具有相同的内存布局(20个连续int对象),但访问元素的语法是不同的.

您可以访问foo[2][2]为((int*)foo)[10](将二维数组视为一维数组).有时这样做很有用,但严格来说,这种行为是不确定的.您可能会逃脱它,因为大多数C实现不进行数组边界检查.另一方面,优化编译器可以假定您的代码的行为已定义,如果不是,则生成任意代码.

Answer 3

C数组 - 甚至是多维数组 - 是连续的,即类型数组在int [4][5]结构上等同于类型数组int [20].

但是,根据C语言语义,这些类型仍然不兼容.特别是,以下代码违反了C标准:

int foo[4][5] = { { 0 } };
int *p = &foo[0][0];
int x = p[12]; // undefined behaviour - can't treat foo as int [20]

这样做的原因是C标准(可能是故意的)措辞使得边界检查实现成为可能:从p派生出来foo[0],有类型int [5],有效索引必须在范围内0..5(0..4如果实际访问元素,则相应) ).

许多其他编程语言(Java,Perl,Python,JavaScript,...)使用锯齿状数组来实现多维数组.通过使用指针数组,这在C中也是可能的:

int *bar[4] = { NULL };
bar[0] = (int [3]){ 0 };
bar[1] = (int [5]){ 1, 2, 3, 4 };
int y = bar[1][2]; // y == 3

但是,锯齿状数组不是连续的,并且指向数组不需要具有统一的大小.

由于将数组表达式隐式转换为指针表达式,索引锯齿状和非锯齿状数组看起来完全相同,但实际的地址计算将完全不同:

&foo[1]    == (int (*)[5])((char *)&foo + 1 * sizeof (int [5]))

&bar[1]    == (int **)((char *)&bar + 1 * sizeof (int *))

&foo[1][2] == (int *)((char *)&foo[1] + 2 * sizeof (int))
           == (int *)((char *)&foo + 1 * sizeof (int [5]) + 2 * sizeof (int))

&bar[1][2] == (int *)((char *)bar[1] + 2 * sizeof (int)) // no & before bar!
           == (int *)((char *)*(int **)((char *)&bar + 1 * sizeof (int *))
                      + 2 * sizeof (int))