這段代碼引起麻煩之前可以調用多大堆棧？

Question

我優化鏈表的析構函數是這樣的：

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

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

現在我有點擔心它可能會導致大名單的麻煩。此代碼是否會導致堆棧溢出？如果是這樣，列表有多大？

Answer 1

堆棧的大小由許多因素決定，例如系統上的OS /編譯器/配置設置。

我絕對不會使用遞歸方法來刪除列表中的元素，因爲您可能會溢出堆棧 - 您可以通過創建帶有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，並且不是JUST這樣做）。