使用灵活的数组成员实现栈

Question

使用这个结构：

typedef struct MyStack {
    size_t     size;      // current size of stack
    size_t     max;       // max size of stack
    Item*      data[];
} MyStack;

如何正确地 malloc 然后 realloc ？例如，如果我这样做：

MyStack* stack = malloc(sizeof(MyStack));
stack->data  = malloc(size * sizeof(Item*));
// ... and later on...
stack->data = realloc(stack->data, new_stack_size);

我收到以下错误：

error: invalid use of flexible array member
error: invalid use of flexible array member (one error for each item above)

那么正确的做法是什么？使用 Item** data 而不是 Item data[] 会更简单吗？

Answer 1

不，您不想为此使用灵活的数组成员（即 data[];）。 Item *data[] 的分配是在 相同的 操作中完成的，该操作分配整个 MyStack，因为 Item *data[] 将位于它的末尾。

但是这永远不会对您的堆栈起作用，因为大概您希望在别处保存指向堆栈对象的指针。当你 realloc 然后 all 指向之前 stack 的指针将变得无效（准确地说不确定）。否则，所有更改 stack 的函数必须始终将 MyStack **stack 指向指针的指针作为参数，并且您只能直接引用它。

因此灵活的数组成员不是您想要在这里使用的。所以是的，如果数据项是 contained[=38=，那么只使用 Item **data 甚至 Item *data 会 mostly 更简单] 在栈里面。这将意味着如上所述的双重间接寻址，但在这种情况下处理起来会简单得多，您可以将 MyStack *stack 传递给任何修改堆栈的函数。

P.S。总是通过 factor 而不是常数来扩展分配，这样每个插入操作的摊销插入成本是 O(1) 而不是 O(n)，即 new_stack_size = new_stack_size * 5 / 4 + 1 或其他...

使用灵活的数组成员实现栈

Using flexible array member to implement a stack

c

malloc