奇怪的可变大小数组声明

Question

阅读这个跳表实现时，我遇到了以下代码片段：

typedef struct nodeStructure{
    keyType key;
    valueType value;
    node forward[1]; /* variable sized array of forward pointers */
    };

对我来说，forward [1] 看起来表示一个元素的数组。而注释称其为“可变大小的数组”。

我是否误解了什么，还是我正在阅读的源代码中有错误？

- ovgolovin

Answer 1

这被称为结构体技巧。它是C99引入的可变数组成员的旧形式。

过去曾经使用它来模拟结构体中最后一个成员的变量数组，但它在C中不是一个严格符合的构造。

- ouah

Answer 2

这是C语言中的一种编程范式，有时会用到。在分配结构时，你需要分配sizeof(struct nodeStructure + numNodes * sizeof(node))。

这样可以让你为结构体拥有多个前向节点，即使它只被声明为一个节点。虽然有点丑陋，但它确实可行。

通常，在这种情况下，还会有一个名为“count”或类似名称的字段，以便你知道节点后面有多少额外条目。

- samoz

---

花了几分钟尝试查找计数器，但没有找到。最终我意识到，超过numNodes的值根本不会被访问（因为指向此节点的指针的保留方式：该节点仅从具有相同数组的跳表级别中访问）。 - ovgolovin

Answer 3

这是老版本的C编译器（C99之前）常用的技巧：当forward是struct的最后一个元素时，编译器允许您解除引用超出声明长度的元素；然后，您可以像这样为额外的node元素分配足够的内存：malloc。

nodeStructure *ptr = malloc(sizeof(nodeStructure)+4*sizeof(node));
for (int i = 0 ; i != 5 ; i++) { // The fifth element is part of the struct
    ptr->forward[i] = ...
}
free(ptr);

该技巧可以让您在结构中嵌入可变大小的数组，而无需单独动态分配。另一种解决方案是声明node *forward，但这样你就需要将其与nodeStructure分别进行malloc和free，从而不必要地使malloc的数量翻倍，并可能增加内存碎片化的风险：

以下是没有该技巧时上述代码片段的示例：

typedef struct nodeStructure{
    keyType key;
    valueType value;
    node *forward;
};

nodeStructure *ptr = malloc(sizeof(nodeStructure));
ptr->forward = malloc(5*sizeof(node));
for (int i = 0 ; i != 5 ; i++) {
    ptr->forward[i] = ...
}
free(ptr->forward);
free(ptr);

编辑（回应Adam Rosenfield的评论）：C99允许您定义没有大小的数组，例如：node forward[];这被称为灵活的数组成员，它在C99标准的6.7.2.1.16节中定义。

- Sergey Kalinichenko

---

这种晦涩的语法有什么用途？它能带来任何好处吗？ - ovgolovin

C标准允许你这样做吗？我一直以为这只是一个hack，只能因为编译器安排结构体如此相似。由于forward被定义为一个1元素数组，所以forward[10]在数组之外，因此应该在技术上触发UB。 - cHao

@cHao 是的，forward[10] 在过去和现在都是未定义的行为，但九十年代曾经是如此简单的时代。 - Pascal Cuoq

值得注意的是，C99添加了一个名为灵活数组成员的特性，它非常相似，只不过你使用不确定大小来声明数组：node forward[]; - Adam Rosenfield

@AdamRosenfield 谢谢，Adam，我编辑了答案，包括了你评论中的信息。 - Sergey Kalinichenko

Answer 4

数据结构实现很可能是针对C90标准编写的，该标准没有灵活数组成员（在C99中添加）。那时，通常使用一个大小为1或甚至为0的数组放在结构体末尾，以允许动态访问其中可变数量的元素。

这个注释不应被解释为意味着C99风格的可变长度数组；此外，在C99中，成员 forward 的惯用和符合标准的定义将是 node forward [];。具有这样一个成员的类型，例如 struct nodeStructure ，则称为不完整类型。您可以定义指向它的指针，但不能定义此类型的变量或获取其大小，所有操作 node forward [0] 或 node forward [1] 都允许，尽管这些操作明显与程序员的意图不匹配。

(*) 标准禁止使用大小为0的数组，但GCC接受这些作为扩展，用于此用途。

- Pascal Cuoq