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 回答