C++析构函数，EXC_BAD_ACCESS，无法访问内存。

Question

C++析构函数，EXC_BAD_ACCESS，无法访问内存。

3

我打算使用有序数组来构建平衡二叉搜索树。一切进行得很顺利，直到程序结束。似乎二叉搜索树的析构函数出了一些问题。

错误信息：

程序收到EXC_BAD_ACCESS信号，无法访问内存。原因：KERN_PROTECTION_FAILURE，地址为0x00007fff5f3ffff8 0x0000000100002857在BST_Node.h:18中的~BST_Node（this=0x100100920）中 ~BST_Node() {delete parent; delete left; delete right;}

#ifndef BST_NODE_H
#define BST_NODE_H

#include <cstddef>

class BST_Node {
    public:
        BST_Node(int k) : key(k), parent(NULL), left(NULL), right(NULL) {}
        ~BST_Node() {if (parent!=NULL) delete parent;if (left!=NULL) delete left;if (right!=NULL) delete right;}
        // data member
        int key;
        BST_Node* parent;
        BST_Node* left;
        BST_Node* right;
};

#endif

#include <iostream>
#include <vector>
#include "BST_Tree.h"
#include "BST_Node.h"

using namespace std;

// use recursion to construct the tree. Find the mid of the array to be the root of the subtree. Use left part of the array to construct the left subtree and right part to construct the right subtree.
BST_Node* CreateTree(vector<int> &a, int start, int end) {
    if (end<start) {
        return NULL;
    } else {
        int mid = (start+end+1)/2;
        BST_Node* p = new BST_Node(a[mid]);
        BST_Node* l_tmp = CreateTree(a, start, mid-1);
        if (l_tmp)
            l_tmp->parent = p;
        p->left = l_tmp;
        BST_Node* r_tmp = CreateTree(a, mid+1, end);
        if (r_tmp)
            r_tmp->parent = p;
        p->right = r_tmp;
        return p;
    }
}

int main() {
    vector<int> a;
    a.push_back(0);
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);
    a.push_back(4);
    a.push_back(5);
    a.push_back(6);
    BST_Tree t;
    t.root = CreateTree(a, 0, 6);
    t.InOrderWalk(t.root);
    return 0;
}

非常感谢！

- randomp

1

你考虑过使用智能指针吗？这正是它们旨在解决的问题类型。 - Andy Prowl

移除 delete parent。这不是递归调用的正确方式。 - Dan

所以你正在删除父节点，这将运行父节点的析构函数，它将删除其左右子节点，每个子节点都将删除其父节点。这将是一个问题。 - nos

你正在尝试对“parent”进行两次析构，或者尝试访问已经被析构的“parent”的成员。BST_Tree的析构函数是如何工作的？ - qPCR4vir

@Andy Prowl：这里的关键问题是要看到parent是一个非拥有指针。盲目地用智能指针替换每个指针将导致相同的问题（使用unique_ptr<>）或内存泄漏（使用shared_ptr<>）。对于父指针使用weak_ptr<>是过度设计：树不变量（x->left->parent == x等）保证了parent始终有效。 - JoergB

@JoergB：我并没有建议“盲目替换”它们。我建议使用“智能指针”，这意味着对于拥有引用，使用shared_ptr，而对于非拥有引用，使用weak_ptr（或常规指针，如果悬空引用不是问题）。 - Andy Prowl

2个回答

0

我只是在运行代码时发现这个部分有问题

    if (l_tmp)
        l_tmp->parent = p;
    p->left = l_tmp;
    BST_Node* r_tmp = CreateTree(a, mid+1, end);
    if (r_tmp)
        r_tmp->parent = p;
    p->right = r_tmp;

l_tmp->parent和r_tmp->parent都指向同一个节点p。因此，在调用l_tmp的析构函数和r_tmp的析构函数时，会对节点p进行两次删除。这可能是您看到错误的原因。正如Andy在评论中建议的那样，这似乎是使用智能指针的好场景。

- Raam

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- JoergB · Accepted Answer

任何所有权关系（其中一个对象在不再需要另一个对象时负责删除它）都不能有循环。在您的情况下，父节点拥有其子节点，反之亦然。

当根节点被删除时，它的构造函数将首先删除左子节点。子节点的析构函数将删除正在被删除的父节点。

树中的典型所有权关系是父节点拥有其子节点。子节点具有指向不带所有权的父节点的指针。该指针的有效期与子节点的生命周期相同，因为子节点将作为父节点的一部分被删除。

因此，您的析构函数应该简单地执行以下操作：

BST_Node::~BST_Node() {
   delete left;
   delete right;
}

额外的注意事项：

你不需要检查NULL指针——删除一个空指针是安全的，什么也不会发生。
应该防止BST_Node对象的复制。隐式定义的复制构造函数和复制赋值运算符将创建另一个拥有相同子节点的对象，也会导致对象被重复删除。

表达指针所有权语义的最佳方式是使用适当的智能指针类。在您的情况下，最合适的声明是具有

class BST_Node {
    public:
        ~BST_Node() = default; // you can simply omit this completely

        // other things

        BST_Node* parent; // no ownership
        std::unique_ptr<BST_Node> left;  // exclusive ownership
        std::unique_ptr<BST_Node> right;
};

作为这种方法的有用附带效果，隐式生成的复制操作将被禁止，因为 std::unique_ptr<T> 不可复制。