«двойное освобождение или повреждение» shared_ptr в двоичном дереве

Question

Я пишу коды о двоичном дереве, используя умный указатель, но с деструктором что-то не так.Я не знаю, где просачивается Момери.Но когда я удаляю все компоненты с указателем parent в BinNode, он работает без ошибок.

Заголовочный файл отображается следующим образом:

#ifndef BINARY_H
#define BINARY_H

#include <memory>
#include <iostream>

#ifndef RANK_DEFINED
#define RANK_DEFINED
typedef int64_t Rank;
#endif

template <typename T> class BinaryTree;
typedef enum {RB_RED, RB_BLACK} RBColor;

template <typename T>
class BinNode {
public:
    friend class BinaryTree<T>;
    BinNode() = default;
    BinNode(const T& data, std::shared_ptr<BinNode> pare = nullptr, std::shared_ptr<BinNode> left = nullptr, std::shared_ptr<BinNode> right = nullptr,
        int h = 1) : _data(data), left_child(left), right_child(right), parent(pare), height(h){}
    ~BinNode() = default;

    std::shared_ptr<BinNode> insertAsLeft(const T& e) {
        left_child = std::make_shared<BinNode>(e);
        left_child->parent = std::shared_ptr<BinNode>(this);
        return left_child;
    }
    std::shared_ptr<BinNode> insertAsRight(const T& e) {
        right_child = std::make_shared<BinNode>(e, this);
        return right_child;
    }
    int size() const;

    std::shared_ptr<BinNode> succ();
    template <typename VST> void travelLevel(VST (*f)());
    template <typename VST> void travelPre(VST (*f)());
    template <typename VST> void travelIn(VST&);
    template <typename VST> void travelPost(VST&);

    bool operator<(BinNode const& bn) { return _data < bn._data; }
    bool operator==(BinNode const& bn) { return _data == bn._data; }

    bool isRoot() { return !(parent); }
    bool isLChild() { return !isRoot() && this == parent->left_child; }
    bool isRChild() { return !isRoot() && this == parent->right_child; }
    bool hasParent() { return !isRoot(); }
    bool hasLChild() { return !left_child; }
    bool hasRChild() { return !right_child; }
    bool hasChild() { return hasLChild() || hasRChild(); }
    bool hasBothChild() { return hasLChild() && hasRChild(); }
    bool isLeaf() { return !hasChild(); }

    std::shared_ptr<BinNode> sibling() const {
        return (isLChild() ? parent->right_child : parent->left_child);
    }
    std::shared_ptr<BinNode> uncle() const {
        return parent->sibling();
    }
private:
    T _data;
    std::shared_ptr<BinNode<T>> left_child = nullptr;
    std::shared_ptr<BinNode<T>> right_child = nullptr;
    std::shared_ptr<BinNode<T>> parent = nullptr;
    int height = 1;
};


// Binary Tree Defination
template <typename T>
class BinaryTree
{
    using BN = BinNode<T>;
public:
    BinaryTree(): _size(0), _root(nullptr) {}
    ~BinaryTree() = default;

    int size() const { return _size; }
    bool empty() const { return !_root; }
    std::shared_ptr<BN> root() const { return _root; }
    std::shared_ptr<BN> insertAsRoot(const T& e);
    std::shared_ptr<BN> insertAsLC(std::shared_ptr<BN> pare, const T& e);
    std::shared_ptr<BN> insertAsRC(std::shared_ptr<BN> pare, const T& e);
    std::shared_ptr<BN> insertAsLC(std::shared_ptr<BN> pare, BinaryTree<T> bt);
    std::shared_ptr<BN> insertAsRC(std::shared_ptr<BN> pare, BinaryTree<T> bt);

    int remove(std::shared_ptr<BN>);
    BinaryTree* secede(std::shared_ptr<BN>);

    template <typename VST>
    void travelLevel(VST& visit) { if (_root) _root->travelLevel(visit); }
    template <typename VST>
    void travelPre(VST& visit) { if (_root) _root->travelPre(visit); }
    template <typename VST>
    void travelIn(VST& visit) { if (_root) _root->travelIn(visit); }
    template <typename VST>
    void travelPost(VST& visit) { if (_root) _root->travelPost(visit); }

protected:
    Rank _size;
    std::shared_ptr<BN> _root;
    virtual int updateHeight(std::shared_ptr<BN>);
    void updateHeightAbove(std::shared_ptr<BN>);
    void delTree(std::shared_ptr<BN>);
};

template <typename T>
std::shared_ptr<BinNode<T>> BinaryTree<T>::insertAsRoot(const T& e)
{
    _root = std::make_shared<BN>(e);
    _size = 1;
    return _root;
}

template <typename T>
std::shared_ptr<BinNode<T>> BinaryTree<T>::insertAsLC(std::shared_ptr<BN> pare, const T& e)
{
    auto newNode = pare->insertAsLeft(e);
    _size++;
    updateHeightAbove(newNode);
    return pare->left_child;
}

template <typename T>
std::shared_ptr<BinNode<T>> BinaryTree<T>::insertAsRC(std::shared_ptr<BN> pare, const T& e)
{
}

template <typename T>
void BinaryTree<T>::updateHeightAbove(std::shared_ptr<BN> x)
{
    while(x)
    {
        updateHeight(x);
        x = x->parent;
    }
}

template <typename T>
int BinaryTree<T>::updateHeight(std::shared_ptr<BN> x)
{
    Rank lh = 1, rh = 1;
    if (x->left_child)
        lh = x->left_child->height;
    if (x->right_child)
        rh = x->right_child->height;
    x->height = (lh > rh) ? lh : rh;
    return x->height;
}

#endif

, а основная функция:

int main()
{
    BinaryTree<int> bt;
    bt.insertAsRoot(1);
    bt.insertAsLC(bt.root(), 2);
    cout << bt.size() << endl;

    return 0;
}

Результат double free or corruption (out).

Answer 1

Есть две проблемы с вашими parent ссылками:

• И нисходящий, и восходящий указатели std::shared_ptr. Это называется справочным циклом и запрещает уничтожение вашего дерева должным образом. Распространенное решение состоит в том, чтобы сделать указатель parent std::weak_ptr таким образом, чтобы он не учитывался в отношении поддержки родителя.

• Вторая проблема скрыта в вашем insertAsLeft: std::shared_ptr<BinNode>(this) создаст new shared_ptr с refcount 1. Это означает, что у вас есть несколько shared_ptr s, указывающих на тот же блок памяти и первый, который падает на счет 0, освобождает блок, оставляя вас с висящими указателями. К счастью для вас, C ++ имеет готовое решение. Просто наследуйте от std::enable_shared_from_this и используйте вместо него left_child->parent = shared_from_this();. В двух словах, эта конструкция позволяет BinNode отслеживать, кому shared_ptr принадлежит.