二叉搜索树（如何检查插入时是否内存不足）

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或其他某些函数会引发异常。