一维访问多维数组：这是良定义的行为吗？

Question

我想我们都同意，以一维形式解引用（可能有偏移的）指向多维数组第一个元素的指针是C语言中被视为习惯用法的。例如：

void clearBottomRightElement(int *array, int M, int N)
{
    array[M*N-1] = 0;  // Pretend the array is one-dimensional
}


int mtx[5][3];
...
clearBottomRightElement(&mtx[0][0], 5, 3);

然而，我这个语言律师需要被说服这实际上是明确定义的C语言！特别是：

1. Does the standard guarantee that the compiler won't put padding in-between e.g. mtx[0][2] and mtx[1][0]?

2. Normally, indexing off the end of an array (other than one-past the end) is undefined (C99, 6.5.6/8). So the following is clearly undefined:

   struct {
       int row[3];           // The object in question is an int[3]
       int other[10];
   } foo;
   int *p = &foo.row[7];     // ERROR: A crude attempt to get &foo.other[4];
   

   So by the same rule, one would expect the following to be undefined:

   int mtx[5][3];
   int (*row)[3] = &mtx[0];  // The object in question is still an int[3]
   int *p = &(*row)[7];      // Why is this any better?
   

   So why should this be defined?

   int mtx[5][3];
   int *p = &(&mtx[0][0])[7];
   

那么C标准的哪一部分明确允许这样做呢？（为了讨论的方便，我们假设c99。）

编辑

请注意，我毫不怀疑这在所有编译器中都可以正常工作。我所质疑的是是否标准明确允许这样做。

- Oliver Charlesworth

---

由于不确定，我将此作为评论发布。据我所知，数组在内存中保证是连续的，而结构体之间可能存在填充。如果您查看数组访问的汇编代码，您应该能够看到对[][]访问执行的操作与*(array + x * index + y)相同。 - RedX

我不是语言专家，所以我不会给出答案，但这正是光栅成像的工作原理。基本上，你只有字节，并且你知道每行有多少个字节。要进入下一行，你必须用行数*宽度来偏移原始指针。因此，在数据定义良好的情况下，我认为这是完全可以接受的编码方式。 - Wouter Simons

@Wouter：哦，我毫不怀疑这很好！我每天都使用这个原则，其他人也是如此。我只是从语言法律专家的角度纠结地问一下！ - Oliver Charlesworth

@Oli：律师是可怕的开发人员。在内存中，数组没有填充，因此将多维数组作为单个维度进行索引始终有效。您的指针增量是根据基本数组指针确定的，因此arr[10]必须是arr + 10 * sizeof（arr），我确定这是规格说明中提到的。这意味着具有第二维始终为5的arr [1] [5]为： arr + 1 * 5 * sizeof（arrType）+ 5 * sizeof（arrType）... - Wouter Simons

我没有时间写出来，但是C99 6.5.2.1的第3和第4段似乎使这个定义明确了。 - Hasturkun

Answer 1

所有的数组（包括多维数组）都是无填充的。即使从未明确提到，也可以从 sizeof 规则中推导出这一点。

现在，数组订阅是指针算术的一个特殊情况，C99 第6.5.6节第8条清楚地规定，只有当指针操作数和结果指针位于同一数组（或一个元素之后）时，行为才被定义，这使得实现 C 语言的边界检查成为可能。

这意味着您的示例实际上是未定义的行为。但是，由于大多数 C 实现不检查边界，它将按预期工作 - 大多数编译器像处理未定义的指针表达式一样处理它。

mtx[0] + 5 

与明确定义的类似，

(int *)((char *)mtx + 5 * sizeof (int))

这是可以明确定义的，因为任何对象（包括整个二维数组）都可以被视为类型为char的一维数组。

---

进一步思考6.5.6节用语时，将越界访问分割为看似可以明确定义的子表达式，例如：

(mtx[0] + 3) + 2

认为 mtx[0] + 3 是指向 mtx[0] 结尾后的一个元素的指针(使得第一次加法是有定义的)，同时也是指向 mtx[1] 的第一个元素的指针(使得第二次加法是有定义的)是不正确的:

尽管保证了 mtx[0] + 3 和 mtx[1] + 0 相等(见第6.5.9, §6节)，但它们在语义上是不同的。例如前者无法进行解引用，因此不指向 mtx[1] 的任何元素。

- Christoph

---

我同意你所说的大部分内容。但我不确定我能同意(mtx[0] + 3) + 2)是有效的这一观点，因为所有越界指针加法都可以递归地表示为(((p+1)+1)+1)等等。如果以这种方式明确定义它们是有意义的，那么6.5.6/8还有什么意义呢？ - Oliver Charlesworth

@Oli：C语言算术运算不是结合律——(a+b)+c不一定等于a+(b+c)；问题的关键在于，在多维数组的情况下，指针可以同时“属于”两个数组，并且指针算术运算不会跟踪原始数组，因此您只需要验证每个子表达式；据我所知，确实可以通过单步增量迭代多维数组。 - Christoph

@Christoph：我同意你关于结合性的观点。我想唯一剩下的问题就是，是否将对象与指向前一个对象的超出末尾元素的指针别名化是有效的。例如，在我的结构示例中，如果实现保证row和other之间没有填充，那么行为是否定义良好？ - Oliver Charlesworth

是的，指针加法可能会有问题。请注意，如果基本类型是char类型，则不会出现问题，因为任何指向它的指针也都是指向representation数组的指针，该数组的类型是unsigned char [整个多维数组的大小]，因此所有的算术运算都是有效的。 - R.. GitHub STOP HELPING ICE

我不确定(int *)((char *)mtx + 5 * sizeof (int))是否被定义。mtx将是一个指向包含3个整数的数组的指针，该数组将被+5*...溢出。更好的表达方式应该是(int *)((char *)&mtx + 5 * sizeof (int))。 - tstanisl

Answer 2

您想要访问的唯一障碍是类型为int [5][3]和int [15] 的对象不允许互相别名。 因此，如果编译器意识到指向前者int [3]数组之一的int *指针，则它可能会强制执行数组边界限制，以防止访问int [3]数组之外的任何内容。

您可能可以通过将所有内容放在包含int [5][3]数组和int [15]数组的联合体中来解决此问题，但我真的不清楚人们用于 type-punning 的联合体 hack 是否是明确定义的。 由于您只会进行数组逻辑的类型转换而不是单个单元格的类型转换，因此这种情况可能会稍微不那么棘手，但我仍然不确定。

应该注意的一个特殊情况： 如果您的类型是unsigned char（或任何char类型），则将多维数组作为一维数组访问是完全明确定义的。 这是因为与之重叠的unsigned char的一维数组是标准明确定义的对象的“表示”，因此本质上被允许别名。

- R.. GitHub STOP HELPING ICE

---

通过联合体进行类型转换并不比通过指针强制转换更加定义明确，但是GCC的文档超出了前者的标准，并保证程序将执行程序员所期望的操作。 "即使使用-fstrict-aliasing，只要通过联合类型访问内存，就允许进行类型转换。" http://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html - Pascal Cuoq

@Pascal：C99允许通过联合进行类型切换-这在脚注82（第73页）中明确提到，该脚注是通过TC3添加的。 - Christoph

我意外地再次发现了这篇答案。如果您能回复我的先前评论，或者至少说一下您不想回复的话，我会非常感激。谢谢。 - 2501

@2501：这是类型表示（重叠的unsigned char [sizeof T]）和指针在表示、结构体和结构体成员之间的等价性/可转换性应用的结果。简而言之，同一个unsigned char *合法地指向整个结构体的表示数组中的元素和结构体内部成员数组中的元素。由于前者的存在，更广泛的算术范围是有效的。 - R.. GitHub STOP HELPING ICE

我猜你的意思是说这个问题的唯一原因是别名。如果是这样，那么使用void指针来规避别名规则怎么样？将(void *)&a[0][0]（假设a是int a[10][10]）传递给一个接收void指针作为参数的函数，然后将其强制转换为int *并将2D数组作为1D访问，这样做是否合法？我之所以问这个问题，是因为我相信必须有一种方法使1D访问合法，因为C标准保证多维数组是连续的。 - cesss

Answer 3

1. 数组元素之间肯定没有填充。

2. 有提供比完整地址空间更小的地址计算功能。例如，在8086的巨型模式下，如果编译器知道您不能跨越段边界，则可以使用此功能，以便不必始终更新段部分。(对于我来说，这太久远了，无法回忆起我使用的编译器是否从中受益)。

根据我的内部模型——我不确定它是否完全与标准模型相同，而且检查起来太麻烦了，因为信息分散在各个地方——

• clearBottomRightElement 中的操作是有效的。

• int *p = &foo.row[7]; 是未定义的。

• int i = mtx[0][5]; 是未定义的。

• int *p = &row[7]; 无法编译（gcc 同意我的观点）。

• int *p = &(&mtx[0][0])[7]; 处于灰色地带（上次我详细检查类似这样的东西时，最终认为它是无效的 C90 和有效的 C99，这可能也是本例的情况，或者我可能错过了什么）。

- AProgrammer

---

你说得对，我在 int *p = &row[7] 的语法上出了错。我会编辑我的问题。 - Oliver Charlesworth

我真正需要的是基于标准措辞的论据... - Oliver Charlesworth

Answer 4

我对C99标准的理解是，多维数组不一定要按照内存中连续的顺序排列。根据标准中唯一相关的信息（每个维度都保证是连续的）。

如果您想使用x [COLS * r + c]访问，请坚持使用单维数组。

数组下标

连续的下标运算符指定了多维数组对象的一个元素。 如果E是一个n维数组（n≥2），其维数为i×j×...×k，则E（用作 除lvalue之外的其他内容）转换为指向具有（n-1）维数组的指针，其 尺寸为j×...×k。如果显式地将一元*运算符应用于此指针，或者 由于下标而隐含地应用，结果是指向（n-1）维数组， 如果用作除lvalue之外的其他内容，则本身会被转换为指针。由此可见， 数组以行优先顺序存储（最后一个下标变化最快）。

数组类型

——数组类型描述了一组具有特定成员对象类型（称为元素类型）的连续分配的非空对象集。 36） 数组类型由其元素类型和数组中元素数量来确定。如果数组类型的元素类型是T，则该数组类型被称为“T的数组”。从元素类型构造数组类型称为“数组类型派生”。

- nimrodm

---

@nimrodm：你对标准的解释基本上与我的相同。（我想这让我感到放心！） - Oliver Charlesworth

第一句话明显是错误的。内存中的布局完全由 sizeof 和指针运算的语义所决定。只是由于别名规则，这种用法才是未定义的，因此仅适用于非 char 类型。 - R.. GitHub STOP HELPING ICE

关于多维数组不需要连续的说法，我持有不同意见。一个包含3个元素的数组内嵌在另一个包含3个元素的数组中（arr[3][3]），为了匹配这样的描述，它必须是连续的，否则第二个“数组”（包含其他3个数组的那个）将无法称其自身为数组，因为它的布局不是连续的。其中的“内部”数组（arr[3]）具有X大小的数组，而“外部”数组是一个X[sizeof("内部数组")]的数组。 - RedX

@R.. - 不，我明白了 - 星号表示“指向”，也就是说，我的问题是外部数组是否实际上被实现为指向每个内部数组开头的指针数组，还是作为整个int[3]对象的数组。 - detly

这是后者 - 一个由 int [3] 对象组成的数组。 - R.. GitHub STOP HELPING ICE