我对 C 下内存结构的理解是，程序的内存与堆栈和堆分开，每个堆栈和堆都从块的两端生长，可以想象分配所有 RAM，但显然抽象为某种操作系统内存片段管理器。
堆栈设计用于处理局部变量（自动存储），堆设计用于内存分配（动态存储）。
（编者注：有一些 C 实现，其中自动存储不使用“调用堆栈”，但这个问题假设在普通 CPU 上有一个正常的现代 C 实现，其中局部变量如果不能只存在于寄存器中，则确实使用调用堆栈。 ）
假设我想为某些数据解析算法实现堆栈数据结构。它的生命周期和范围仅限于一个函数。
我可以想到 3 种方法来做这样的事情，但在我看来，考虑到这种情况，它们都不是最干净的方法。
我的第一个想法是在堆中构造一个堆栈，就像 C++ 一样std::vector:
Some algorithm(Some data)
{
Label *stack = new_stack(stack_size_estimate(data));
Iterator i = some_iterator(data);
while(i)
{
Label label = some_label(some_iterator_at(i));
if (label_type_a(label))
{
push_stack(stack,label);
}
else if(label_type_b(label))
{
some_process(&data,label,pop_stack(stack));
}
i = some_iterator_next(i);
}
some_stack_cleanup(&data,stack);
delete_stack(stack);
return data;
}
这个方法没问题，但是很浪费，因为堆栈大小是一个猜测，并且随时都会发生。push_stack可能会调用一些内部 malloc 或 realloc 并导致不规则的速度减慢。对于该算法来说，这些都不是问题，但这种构造似乎更适合必须跨多个上下文维护堆栈的应用程序。这里的情况并非如此；堆栈是该函数私有的，并且在退出之前被删除，就像自动存储类一样。
我的下一个想法是递归。因为递归使用内置堆栈，这似乎更接近我想要的。
Some algorithm(Some data)
{
Iterator i = some_iterator(data);
return some_extra(algorithm_helper(extra_from_some(data),&i);
}
Extra algorithm_helper(Extra thing, Iterator* i)
{
if(!*i)
{return thing;}
{
Label label = some_label(some_iterator_at(i));
if (label_type_a(label))
{
*i = some_iterator_next(*i);
return algorithm_helper
( extra_process( algorithm_helper(thing,i), label), i );
}
else if(label_type_b(label))
{
*i = some_iterator_next(*i);
return extra_attach(thing,label);
}
}
}
这种方法使我免于编写和维护堆栈。对我来说，代码似乎更难遵循，但这对我来说并不重要。
我的主要问题是这使用了更多的空间。
堆栈帧保存此副本Extra构造（基本上包含Some data加上想要保存在堆栈中的实际位）以及每个帧中完全相同的迭代器指针的不必要副本：因为它比引用一些静态全局更“安全”（而且我不知道如何不这样做） 。如果编译器做了一些聪明的尾递归之类的事情，这不会成为问题，但我不知道我是否喜欢交叉手指并希望我的编译器很棒。
我能想到的第三种方法涉及某种可以在堆栈上增长的动态数组，这是使用某种我不知道的 C 语言编写的最后一个东西。
或者是外来的asm block.
考虑到这一点，这就是我正在寻找的东西，但我不认为自己会编写一个汇编版本，除非它非常简单，而且我不认为它更容易编写或维护，尽管它在我的脑海中看起来更简单。显然它不能跨 ISA 移植。
我不知道我是否忽略了某些功能，或者我是否需要寻找另一种语言，或者我是否应该重新考虑我的生活选择。一切都可能是真的……我希望这只是第一个。
我不反对使用一些图书馆。有吗？如果有，它是如何运作的？我在搜索中没有找到任何东西。
我最近了解了可变长度数组，我真的不明白为什么不能利用它们作为增长堆栈引用的方式，但我也无法想象它们以这种方式工作。
