二叉搜索樹（如何檢查插入時是否內存不足）

Question

我已經創建了一個binarysearchtree，並有一個問題，關於如何檢查是否有沒有足夠的內存來創建新節點。我知道它與調用構造函數有關，但我並不真正瞭解如何或與內存有什麼關係。任何幫助或指導都將非常感激。

bool BinarySearchTree::treeInsert(string firstname, string lastname, string phonenumber) 
{ 
//code to check if memory is full (what i need help on) 
//code to insert 
} 

Answer 1

這裏的假設是您要編寫的程序不會導致使用比系統可用的資源更多的資源。每次向樹中添加節點時（如果您計劃內存問題時聽起來很多，聽起來很像），請不要進行必要的系統調用來檢查資源，請考慮您可以採取哪些其他方法來防止發生這種情況。

評論中建議的異常處理是一個不錯的選擇。這裏是一個鏈接描述是：

How can I check if there is enough heap memory available?

如果你一定要，你可以使用的sysconf如下圖所示，但我會避免每次都做，也許做每1000次添加，並保持局部結果以便在您開始接近時參考並做出反應。

這裏是一個開始你想找的：

#include <unistd> 

size_t getTotalSystemMemory() 
{ 
    long pages = sysconf(_SC_PHYS_PAGES); 
    long page_size = sysconf(_SC_PAGE_SIZE); 
    return pages * page_size; 
} 

Answer 2

要回答你的問題在一個通用的方法，你會做的分配和做任何函數調用可能throw之前的任何突變或改變在你的數據結構：

例如：

bool BinarySearchTree::treeInsert(string firstname, string lastname, string phonenumber) 
{ 
    TreeNode* newNode = new TreeNode(); 
    // any other functions that may throw 
    //... 
    // now do housekeeping to update tree 
} 

所以，換句話說，確保你有你的所有數據已經在之前設置您更新您的樹。這是非常安全的，因爲拋出的異常不會損害現有的樹。您可以有一個簡單的try/catch確認如果拋出異常，則無法創建該節點。

的錯誤（或更多累贅的）方式是這樣的：

bool BinarySearchTree::treeInsert(string firstname, string lastname, string phonenumber) 
{ 
    // code that changes the internals of BinarySearchTree 
    // ... 
    // now create the node 
    TreeNode* newNode = new TreeNode(); 
} 

除非你有一個try/catch，做的樹所做的更改回滾，你最終會破壞使用這種方法，如果樹new或其他某些函數會引發異常。