0

我有以下代码：

class Node {
    public:
        int data;
        Node* parent;
        std::unique_ptr<Node> left;
        std::unique_ptr<Node> right;
    public:       
        explicit Node(int d) : data(d),
                               parent(nullptr),
                               left(nullptr),
                               right(nullptr) { }
        /*
            Some functions
        */                  
};

class dt {
    private:            
        Node* root;
    private:        
        void add_helper(Node* parent, Node* node); 
        /*
                Some helper functions
        */      
    public:
        dt() : root(nullptr) {}
        ~dt() {
            delete root;
        } 
        /*
                Some functions
        */       
        void add(int data);        
};


void dt::add(int data) {
    if(!root) {
        root = new Node(data); // 1: memory leak
        return;
    }   
    Node* node = new Node(data); // 2: memory leak
    add_helper(root, node);
}

当我扫描此代码以查找内存泄漏时，Memory 博士在上述评论中提到的行中显示错误。但它们真的是内存泄漏吗？dt有析构函数，其中根指针正在删除。当析构函数开始删除根节点时，它将递归地删除所有子节点。或者还有其他事情发生？

4

1 回答 1

1

这些行真的会导致内存泄漏吗？

在线分配的内存Node* node = new Node(data)可能会泄漏。至少该示例没有显示指针将被删除的位置。所有权可能会在 内部转移add_helper，但这已从示例中排除。

我不熟悉 Dr. Memory，但我假设它会报告泄漏内存的分配位置；不是泄露的地方。

此外，如果您复制一个dt实例，程序的行为将是不确定的，因为原始和副本都将尝试删除复制的指针。

要修复潜在的内存泄漏和潜在的 UB，请使用唯一指针。就像你用Node.

我不能将 unqiue_ptr 用于 root，因为有多个指针指向同一个节点。

通过delete root;在析构函数中进行操作，您的类将假定指针的唯一所有权。如果该假设是正确的，那么使用唯一指针就没有问题。如果假设不正确，那么析构函数可能会导致未定义的行为。使用它而不是唯一指针不是解决方案。您可能需要改用共享指针。

最后，除非你的树是平衡的，否则隐式递归析构函数会线性增加最坏情况的递归深度，这很容易导致堆栈溢出。您应该平衡树（例如使用 red-back 或 AVL 增强）或使用迭代算法来销毁孩子。

于 2019-06-16T01:11:48.723 回答