0

我最近一直在写 SEC 算法（比如这里http://18.7.29.232/bitstream/handle/1721.1/4015/HPCES024.pdf?sequence=2）。起初是递归版本，它似乎抛出“堆栈溢出”异常超过 200000 点。直到我把它写在我自己的堆栈上（使用迭代而不是递归）我才知道为什么，它在 1000000 点上工作得很好。

我相信当我调用函数时，处理器和变量的指令会被复制到一些“随机”分配的内存中。我还认为，当我有一个类向量的全局变量时，它需要有一些紧凑的内存（如表）。

问题是当我有大量的函数调用时（例如在某些递归算法中），因为（在我看来）当内存被分成小部分时，向量不能“放大”并引发“堆栈溢出”异常。

所以我认为我可以以某种方式说服 c++ 应该在哪里存储函数实例内存。就像这里http://www.parashift.com/c++-faq-lite/placement-new.html制作一些“函数实例”表，所以它不会弄乱内存。

可能吗？

4

1 回答 1

0

从来不是vector谁给出堆栈溢出错误。vector在堆上分配它的内存，它可以和你的总内存（包括虚拟内存）一样大。

另一方面，堆栈是（相当）一小块内存，您的程序在其中存储函数局部变量以及其他内容。

当你调用一个函数时，这些是写入堆栈的一些数据：

  • 可能是一些寄存器
  • 堆栈指针
  • 可能有一些空间用于返回值
  • 函数参数（如果有）
  • 基指针
  • 新函数的局部变量

根据架构/编译器，可能还有其他数据。

因此，即使是最简单的函数也会在堆栈上占用最少的内存才能被调用。幸运的是，当函数返回时，这些内存再次可用。然而，虽然这个函数没有返回，但这些数据仍然存在。因此，如果您一遍又一遍地递归调用一个函数，所有这些数据就会相互堆积。如果你没有尽快结束你的递归函数，你将耗尽内存并且你会得到一个堆栈溢出错误。

如果你很好奇，你可以在你的函数中添加额外的变量（确保它们不会被优化），并看到你得到这个错误的点数较少。

您的解决方案，其他人在评论中说过因此是使用迭代方法，std::stack例如基本上模拟调用堆栈。

于 2012-09-01T10:47:42.713 回答