时间戳

首页 > 解决方案 > 使用callstack在C中实现栈数据结构？

c - 使用callstack在C中实现栈数据结构？

问题描述

我对 C 下的内存结构的理解是程序的内存与堆栈和堆分开，每个都从块的两端增长，可以想象分配所有 ram，但显然抽象为某种 OS 内存片段管理器。
堆栈设计用于处理局部变量（自动存储）和堆用于内存分配（动态存储）。

（编者注：在某些 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块。

考虑到这一点，这就是我正在寻找的东西，但我看不到自己编写 asm 版本，除非它非常简单，而且我认为编写或维护并不容易，尽管它在我的脑海中看起来更简单。显然它不能跨 ISA 移植。

我不知道我是否忽略了某些功能，或者我是否需要寻找另一种语言，或者我是否应该重新考虑我的生活选择。一切都可能是真的……我希望这只是第一个。

我不反对使用一些图书馆。有没有，如果有，它是如何工作的？我在搜索中没有找到任何东西。

我最近了解了可变长度数组，但我真的不明白为什么不能将它们用作增加堆栈引用的一种方式，但我也无法想象它们以这种方式工作。

标签： cassemblystackcallstackstack-memory

解决方案

tl; 博士：使用std::vector或等效。

（已编辑）

关于你的开场白：分段的日子已经结束。这些天来，进程有多个堆栈（每个线程一个），但都共享一个堆。

关于选项 1：与其编写和维护堆栈并猜测其大小，不如直接使用std::vector，或围绕它的 C 包装器，或它的 C 克隆 - 在任何情况下，使用“向量”数据结构。

Vector的算法通常非常有效。不完美，但通常对许多现实世界的用例都有好处。

关于选项 2：您是对的，至少只要讨论仅限于 C。在 C 中，递归既浪费又不可扩展。在其他一些语言中，特别是在函数式语言中，递归是表达这些算法的方式，尾调用优化是语言定义的一部分。

关于选项 3：最接近您正在寻找的 C 的东西是alloca()。它允许您增加堆栈帧，如果堆栈没有足够的内存，操作系统将分配它。realloca()但是，正如@Peter Cordes 指出的那样，围绕它构建一个堆栈对象将非常困难，因为没有.

另一个缺点是堆栈仍然有限。在 Linux 上，堆栈通常限制为 8 MB。这与递归的可伸缩性限制相同。

关于可变长度数组：VLA 基本上是语法糖，表示方便。除了语法之外，它们还具有与数组完全相同的功能（实际上，甚至更少，即sizeof()不起作用），更不用说std::vector.

推荐阅读