c++ - 在这段代码引起麻烦之前，调用堆栈可以有多大？

Question

我像这样优化了链表析构函数：

template <class T>
class LinkedList
{
    /* snip */
    T* pData;
    LinkedList* pNext;
};

template <class T>
LinkedList<T>::~LinkedList()
{
    delete pData;
    delete pNext;
}

现在我有点担心它可能会给大型列表带来麻烦。此代码会导致堆栈溢出吗？如果是这样，有多大的名单？

Answer 1

堆栈的大小由许多因素决定，例如系统上的操作系统/编译器/配置设置。

我绝对不会使用递归方法来删除列表中的元素，因为你可能会溢出堆栈 - 你可以通过创建一个包含 X 元素的列表来尝试这个，如果可行，加倍 X，直到你达到堆栈溢出- 我几乎可以保证它发生在几千个元素内（可能是 10-100k，但肯定不会更多）。

用于删除二叉树等的递归函数更容易接受，因为（假设合理平衡）递归级别的数量是log2(n)，而不是n，因此在堆栈溢出之前您可以拥有大量元素。

我参加了您的课程并对其进行了扩展以使其“工作”（这可能与您使用它的方式完全不同，但它可以解释问题）：

#include <iostream>

using namespace std;

template <class T>
class LinkedList
{
public:
    LinkedList() : pNext(0), pData(0) {};
    LinkedList(T e) : pNext(0) { pData = new T(e); }
    LinkedList(LinkedList* l, T e) : LinkedList(e) { pNext = l;}

    LinkedList *AppendFirst(LinkedList *l) { l->pNext = this ; return l; }

    LinkedList *Next() { return pNext; }

    T Data() { return *pData; }

    ~LinkedList();
private:
    T* pData;
    LinkedList* pNext;
};

#if 0
template <class T>
LinkedList<T>::~LinkedList()
{
    delete pData;
    delete pNext;
};
#else
template <class T>
LinkedList<T>::~LinkedList()
{
    LinkedList<T>* p;
    LinkedList<T>* q;
    p = pNext;
    while(p)
    {
        q = p->pNext;   // Save next link. 
        p->pNext = NULL;   // Break the link. 
        delete p->pData;
        p->pData = NULL;
        delete p;
        p = q;
    }

    delete pData;
};
#endif


typedef LinkedList<int> IntList;

int main()
{
    for(int x = 0; x < 30; x++)
    {
        cout << "Trying " << (1 << x) << " elements" << endl;
        IntList *head = new IntList(-1);
        for(int i = 0; i < (1 << x); i++)
        {
            head = head->AppendFirst(new IntList(i));
        }
        cout << "Now destroying " << (1 << x) << " elements" << endl;
        delete head;
    }
}

如果我更改#if 0为#if 1（或其他具有该效果的东西），它适用于 128K 元素并在 256K 时崩溃。如果我在 中使用迭代方法，#else当它达到 268435456（256M 条目）时，我不得不停止它，因为我的机器没有足够的内存，并且开始严重交换（我只有 16GB 的 RAM，而且它不只是在做那）。