c++ - BST のデストラクタ

Question

独自の二分探索木を実装する必要があります。私の知る限り、デストラクタを除いて、すべて正常に動作します。ここにいくつかのコードがあります(すべてのデストラクタとコンストラクタ)

Node(){
        val = T();
        parent=nullptr;
        lChild = nullptr;
        rChild = nullptr;
    }
    Node(T &valx){
        val=valx;
        parent=nullptr;
        lChild = nullptr;
        rChild = nullptr;
    }
    Node(const Node &other){
        val = other.val;
        if(other.lChild!=nullptr){
            lChild = new Node(*other.lChild);
            lChild->parent=this;
        }
        else
            lChild=nullptr;
        if(other.rChild!=nullptr){
            rChild= new Node(*other.rChild);
            rChild->parent=this;
        }
        else
            rChild=nullptr;
    }
    ~Node(){
        if(lChild!=nullptr){
            delete lChild; 
            lChild=nullptr; 
        }
        if(rChild!=nullptr){
            delete rChild; 
            rChild=nullptr; 
        }
    }

と

Set(){
    root = nullptr;
    sizeOfTree=0;
}
Set(const Set &other){
    if(other.root!=nullptr){
        root = new Node(*other.root);
        root->parent=nullptr;
    }
    else
        root=nullptr;
    sizeOfTree=other.sizeOfTree;
}
~Set()
{
    if(root!=nullptr){
        delete root;
        //root->~Node();
        root=nullptr;
    }
}

最も単純なテストでは、valgrind は 272 個のエラーを示します。手伝ってくれてありがとう

@edit: valgrind 出力の一部:

==6981== Invalid read of size 8
==6981==    at 0x405C29: Set<Pionek>::Node::~Node() (JakbyGomoku4.cpp:53)
==6981==    by 0x4049EA: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x404790: Plansza::~Plansza() (in /media/Dokumenty/Workspace/JakbyGomoku4/Debug/JakbyGomoku4)
==6981==    by 0x4015F0: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:718)
==6981==    by 0x401746: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:745)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981==  Address 0x4c34468 is 24 bytes inside a block of size 40 free'd
==6981==    at 0x4A073CC: operator delete(void*) (vg_replace_malloc.c:480)
==6981==    by 0x4049F2: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x401E27: Plansza::Plansza(Plansza const&) (JakbyGomoku4.cpp:315)
==6981==    by 0x4015A6: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:718)
==6981==    by 0x401746: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:745)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981== 
==6981== Invalid read of size 8
==6981==    at 0x405C5F: Set<Pionek>::Node::~Node() (JakbyGomoku4.cpp:57)
==6981==    by 0x4049EA: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x404790: Plansza::~Plansza() (in /media/Dokumenty/Workspace/JakbyGomoku4/Debug/JakbyGomoku4)
==6981==    by 0x4015F0: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:718)
==6981==    by 0x401746: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:745)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981==  Address 0x4c34470 is 32 bytes inside a block of size 40 free'd
==6981==    at 0x4A073CC: operator delete(void*) (vg_replace_malloc.c:480)
==6981==    by 0x4049F2: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x401E27: Plansza::Plansza(Plansza const&) (JakbyGomoku4.cpp:315)
==6981==    by 0x4015A6: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:718)
==6981==    by 0x401746: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:745)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981== 
==6981== Invalid free() / delete / delete[] / realloc()
==6981==    at 0x4A073CC: operator delete(void*) (vg_replace_malloc.c:480)
==6981==    by 0x4049F2: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x404790: Plansza::~Plansza() (in /media/Dokumenty/Workspace/JakbyGomoku4/Debug/JakbyGomoku4)
==6981==    by 0x4015F0: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:718)
==6981==    by 0x401746: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:745)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981==  Address 0x4c34450 is 0 bytes inside a block of size 40 free'd
==6981==    at 0x4A073CC: operator delete(void*) (vg_replace_malloc.c:480)
==6981==    by 0x4049F2: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x401E27: Plansza::Plansza(Plansza const&) (JakbyGomoku4.cpp:315)
==6981==    by 0x4015A6: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:718)
==6981==    by 0x401746: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:745)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981== 
==6981== Invalid read of size 8
==6981==    at 0x405C6C: Set<Pionek>::Node::~Node() (JakbyGomoku4.cpp:58)
==6981==    by 0x4049EA: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x4057AF: Set<Pionek>::clear() (JakbyGomoku4.cpp:222)
==6981==    by 0x40160B: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:731)
==6981==    by 0x401746: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:745)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981==  Address 0x4c334c0 is 32 bytes inside a block of size 40 free'd
==6981==    at 0x4A073CC: operator delete(void*) (vg_replace_malloc.c:480)
==6981==    by 0x4049F2: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x401E27: Plansza::Plansza(Plansza const&) (JakbyGomoku4.cpp:315)
==6981==    by 0x4016DE: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:742)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981== 
==6981== Invalid write of size 8
==6981==    at 0x405C89: Set<Pionek>::Node::~Node() (JakbyGomoku4.cpp:59)
==6981==    by 0x4049EA: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x4057AF: Set<Pionek>::clear() (JakbyGomoku4.cpp:222)
==6981==    by 0x40160B: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:731)
==6981==    by 0x401746: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:745)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981==  Address 0x4c334c0 is 32 bytes inside a block of size 40 free'd
==6981==    at 0x4A073CC: operator delete(void*) (vg_replace_malloc.c:480)
==6981==    by 0x4049F2: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x401E27: Plansza::Plansza(Plansza const&) (JakbyGomoku4.cpp:315)
==6981==    by 0x4016DE: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:742)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981== 
==6981== Invalid read of size 8
==6981==    at 0x405C36: Set<Pionek>::Node::~Node() (JakbyGomoku4.cpp:54)
==6981==    by 0x4049EA: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x40479C: Plansza::~Plansza() (in /media/Dokumenty/Workspace/JakbyGomoku4/Debug/JakbyGomoku4)
==6981==    by 0x401755: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:748)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981==  Address 0x4c33448 is 24 bytes inside a block of size 40 free'd
==6981==    at 0x4A073CC: operator delete(void*) (vg_replace_malloc.c:480)
==6981==    by 0x4049F2: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x401DF0: Plansza::Plansza(Plansza const&) (JakbyGomoku4.cpp:314)
==6981==    by 0x4016DE: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:742)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981== 
==6981== Invalid write of size 8
==6981==    at 0x405C53: Set<Pionek>::Node::~Node() (JakbyGomoku4.cpp:55)
==6981==    by 0x4049EA: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x40479C: Plansza::~Plansza() (in /media/Dokumenty/Workspace/JakbyGomoku4/Debug/JakbyGomoku4)
==6981==    by 0x401755: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:748)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)
==6981==  Address 0x4c33448 is 24 bytes inside a block of size 40 free'd
==6981==    at 0x4A073CC: operator delete(void*) (vg_replace_malloc.c:480)
==6981==    by 0x4049F2: Set<Pionek>::~Set() (JakbyGomoku4.cpp:152)
==6981==    by 0x401DF0: Plansza::Plansza(Plansza const&) (JakbyGomoku4.cpp:314)
==6981==    by 0x4016DE: generujPlansze(Plansza&, int, bool, Set<Plansza>&) (JakbyGomoku4.cpp:742)
==6981==    by 0x4019D5: main (JakbyGomoku4.cpp:792)

score 1 · Accepted Answer

ここでコピー ctor とデストラクタチェックに加えて operator=
がありません。また、デストラクタで nullptr をチェックする必要はありません。 nullptr を削除しても問題ありません。
次のようなものを検討してください

Node n1;
//set children for n1
{
Node n2;
//set children for n2
n1 = n2;//Now both n1 and n2 points same children, and initial children of n1 becomes mem leak
}//n2 destructor deletes its children leaving n1 pointing to the same already freed memory location

c++ - BST のデストラクタ

1 に答える 1

Related

Reference