代码之家 › 专栏 › 技术社区 › Stef1611

灵活的数组成员和指针成员:优缺点?

Stef1611 · 技术社区 · 6 年前

使用灵活数组成员(fam)或指针成员有什么区别?在这两种情况下,必须逐个执行malloc和affectation元素。但是对于FAM,对整个结构进行内存分配,对于ptr成员,只对ptr成员进行内存分配(参见代码)。这两种方法的优点和缺点是什么?

#include <stdio.h>
#include <stdlib.h>

typedef struct farr_mb {
    int lg;
    int arr[];
} Farr_mb;

typedef struct ptr_mb {
    int lg;
    int * ptr;
} Ptr_mb;

 int main() {

    int lg=5;

    Farr_mb *a=malloc(sizeof(Farr_mb)+lg*sizeof(int));
    Ptr_mb b; b.ptr=malloc(lg*sizeof(int));

    for (int i=0;i<lg;i++) (a->arr)[i]=i;
    for (int i=0;i<lg;i++) (b.ptr)[i]=i;

    for (int i=0;i<lg;i++) printf("%d \t",(a->arr)[i]=i);
    printf("\n");
    for (int i=0;i<lg;i++) printf("%d \t",(b.ptr)[i]=i);

    return 0;
}

1 回复 | 直到 6 年前

Nominal Animal 6 年前

在讨论优缺点之前,让我们先看看一些实际的例子。

假设我们希望实现一个哈希表,其中每个条目都是一个动态管理的 element S:

struct hash_entry {
    size_t              allocated;
    size_t              used;
    element             array[];
};

struct hash_table {
    size_t              size;
    struct hash_entry **entry;
};
#define HASH_TABLE_INITIALIZER { 0, NULL }

这实际上是用来 二者都 . 哈希表本身是一个包含两个成员的结构。这个 size 成员指示哈希表的大小,以及 entry 成员是指向哈希表项指针数组的指针。这样,每个未使用的条目都只是 NULL 指针。向哈希表条目添加元素时,整个 struct entry 可重新分配(用于 sizeof (struct entry) + allocates * sizeof (element) 或释放,只要在 进入 成员在 struct hash_table 相应更新。

如果我们使用 element *array 相反,我们需要使用 struct hash_entry *entry: 在 结构哈希表 或分配 struct hash_entry 与数组分开;或同时分配两者 结构哈希项 并在单个块中数组, array 指针指向相同的后面 结构哈希项 .

那要另外两个费用 size_t 用于每个未使用的哈希表槽的内存值,以及访问时额外的指针取消引用。 要素 S.(或者,为了得到数组的地址,两个连续的指针解引用,而不是一个指针解引用加上偏移量。)如果这是一个在实现中大量使用的键结构,那么在配置文件中该开销是可见的,并且会对缓存性能产生负面影响。对于随机访问,元素越大 数组 是, 较少的 但是,两者之间存在差异;当 数组 s很小,与 allocated 和 used 成员。

我们通常不想 进入 成员在 结构哈希表 一个灵活的数组成员,因为这意味着您不再可以使用静态声明哈希表。 struct hash_table my_table = HASH_TABLE_INITIALIZER; ;需要使用指向表的指针和初始值设定项函数: struct hash_table *my_table; my_table = hash_table_init(); 或类似的。

我确实有 another example 使用指针成员和灵活数组成员的相关数据结构。它允许使用类型的变量 matrix 表示任意二维矩阵 double 条目,即使矩阵是另一个视图(例如转置、块、行或列向量,甚至对角线向量);这些视图都是相等的(不同于GNU科学库,其中矩阵视图由单独的数据类型表示)。这种矩阵表示方法使得编写健壮的数字线性代数代码变得容易,并且随后的代码比使用GSL或BLAS+LAPACK时更易于阅读。在我看来,就是这样。

那么,让我们从如何选择使用哪种方法的角度来看利弊。(因此,我不会将任何特性指定为“pro”或“con”,因为决定取决于上下文和每个特定用例。)

具有灵活数组成员的结构不能静态初始化。只能通过指针引用它们。

可以使用指针成员声明和初始化结构。如上面的示例所示,使用预处理器初始值设定项宏可能意味着您不需要初始值设定项函数。例如,函数接受 struct hash_table *table 参数始终可以使用 realloc(table->entry, newsize * sizeof table->entry[0]) ,甚至当 table->entry 是空的。这减少了所需的函数数量,并简化了它们的实现。
通过指针成员访问数组可能需要额外的指针取消引用。

如果我们将静态初始化结构中对数组的访问与指向数组的指针进行比较,将对具有通过静态指针引用的灵活数组成员的结构进行比较,则会进行相同数量的取消引用。

如果我们有一个函数获取结构的地址作为参数,那么通过指针成员访问数组元素需要两个指针解引用,而访问灵活的数组元素只需要一个指针解引用和一个偏移量。如果数组元素足够小,并且数组索引足够小,以便被访问的数组元素位于同一缓存线中,那么灵活的数组成员访问通常会更快。对于较大的阵列,性能差异往往是微不足道的。然而,这在硬件体系结构之间是不同的。
通过指针成员重新分配数组会隐藏将结构用作不透明变量的复杂性。

这意味着,如果我们有一个函数接收一个指向结构的指针作为参数,并且该结构有一个指向动态分配的数组的指针,则该函数可以重新分配该数组,而调用方不会看到结构地址本身的任何变化(仅限于结构内容改变。

但是,如果我们有一个函数接收一个指向具有灵活数组成员的结构的指针,那么重新分配数组就意味着重新分配整个结构。这可能会修改结构的地址。因为指针是通过值传递的,所以调用方看不到修改。因此,可以调整可变数组成员大小的函数必须接收指向具有可变数组成员的结构的指针的指针。

如果函数只检查具有灵活数组成员的结构的内容,比如统计满足某些条件的元素的数量,那么指向该结构的指针就足够了;并且可以标记指针和指向数据 const .这可能有助于编译器生成更好的代码。此外,所有访问的数据在内存中都是线性的,这有助于更复杂的处理器更高效地管理缓存。(要对具有指针成员的数组执行同样的操作,需要将指针传递给数组,以及至少作为计数函数参数的大小字段,而不是指向包含这些值的结构的指针。)
具有灵活数组成员的未使用/空结构可以用空指针(指向此类结构)表示。当您有一个数组时,这一点很重要。

对于具有灵活数组成员的结构,外部数组只是指针数组。对于具有指针成员的结构,外部数组可以是结构数组,也可以是指向结构的指针数组。

如果结构作为第一个成员具有公共类型标记,并且使用这些结构的联合,则这两种类型都可以支持不同类型的子数组。(不幸的是,在这种情况下,“使用”的含义是有争议的。有人声称您需要通过联合访问数组,我声称这种联合的可见性是足够的,因为任何其他东西都会破坏大量现有的POSIX C代码;基本上所有服务器端C代码都使用套接字。)

这些是我现在能想到的主要的。这两种形式在我自己的代码中随处可见,我对它们都没有任何问题。(特别是,我更喜欢使用一个无结构助手函数,该函数对结构进行毒物处理,以帮助检测在早期测试中释放错误后的使用情况;而且我的程序通常不存在任何与内存相关的问题。)

我会编辑上面的列表,如果我发现我错过了重要的方面。因此,如果您有任何建议或认为我忽略了上述内容,请在评论中告诉我,以便我可以根据需要进行验证和编辑。