Operator kopiujący powoduje naruszenie ochrony pamięci

0

Dzień dobry. Na podstawie drzewa BST postanowiłem stworzyć implementację zbioru. Problem polega na tym, że metoda pomocnicza (copyTree()) operatora kopiującego powoduje naruszenie ochrony pamięci. Szukałem przyczyny i dotarłem do tego, że pomimo prawidłowego zakończenia metody dla liści, wykonywany jest w pewnym momencie krok dalej. Co ciekawe, ta sama metoda wywołana dla drzewa (zarówno w konstruktorze, jak i w operatorze) działa prawidłowo. Mógłby mi ktoś pomóc, wyjaśnić w czym może tkwić problem?

gdb zwraca coś takiego:

7
kolejny krok: 0x55555556ae70
kolejny krok: 0x55555556aef0
kolejny krok: 0x55555556af30
kolejny krok: 0 nullptr
kolejny krok: 0 nullptr
kolejny krok: 0x55555556af10
kolejny krok: 0 nullptr
kolejny krok: 0 nullptr
kolejny krok: 0x55555556ae90
kolejny krok: 0x55555556aed0
kolejny krok: 0 nullptr
kolejny krok: 0 nullptr
kolejny krok: 0x55555556aeb0
kolejny krok: 0 nullptr
kolejny krok: 0 nullptr
kolejny krok: 0xffffffffffffff90

Program received signal SIGSEGV, Segmentation fault.
0x00005555555559fe in BST<int>::copyTree (this=0x7fffffffdda0, copyTo=@0x7fffffffddb0: 0x55555556af30, copyFrom=0xffffffffffffff90) at bst.hpp:71
71 copyTo->key=copyFrom->key;

Kod mojego programu wygląda następująco:
bst.hpp

#ifndef BST_HPP
#define BST_HPP

#include <iostream>
#include <cstddef>


template <typename E>
class BST {
    
    protected:
    struct node
    {
        E key;  //klucz
        node* right;    //prawe dziecko
        node* left;     //lewe dziecko
    };

    protected:
    node* root;   //korzeń
    size_t numberOfNodes;   //liczba elementów drzewa
    
    void copyTree(node*& copyTo, const node* copyFrom);

    public:
    BST();  //konstruktor
    BST(const BST<E>& source);  //konstruktor (nie)kopiujący
    node* getMin() const;
    node* getMax() const;
    node* insert(E x);
    bool remove(E x);
    node* find(E x) const;
    size_t size() const;
    void inOrder(node* e) const;
    void preOrder(node* e) const;
    void postOrder(node* e) const;
    node* getTreeRoot() const;
    BST<E>& operator=(const BST<E>& source);

};

/*----------------------------------------------------------------------------------*/

template <typename E>
BST<E>::BST() : root(nullptr), numberOfNodes(0) {

}

template <typename E>
BST<E>::BST(const BST<E>& source) : root(nullptr), numberOfNodes(source.numberOfNodes) {
    copyTree(root, source.root);
}

template <typename E>
void BST<E>::copyTree(node*& copyTo, const node* copyFrom) {
    std::cout<<"kolejny krok:   ";
    std::cout<<copyFrom<<"  ";

    if(copyFrom==nullptr) {
        std::cout<<"nullptr"<<std::endl;
        copyTo=nullptr;
        return;
    }

    //std::cout<<copyFrom->key<<"  "<<copyFrom->left<<"    "<<copyFrom->right<<std::endl;

    copyTo=new node;
    /*std::cout<<"value:  "<<std::endl;
    std::cout<<copyFrom->key<<"  "<<copyFrom<<" "<<copyFrom->left<<"    "<<copyFrom->right;*/
    std::cout<<std::endl;
    copyTo->key=copyFrom->key;
    
    copyTree(copyTo->right, copyFrom->right);
    copyTree(copyTo->left, copyFrom->left);

}

template <typename E>
BST<E>& BST<E>::operator=(const BST<E>& source) {
    if(&source==this) {
        return *this;
    }
    this->numberOfNodes=source.numberOfNodes;

    std::cout<<"tree c-op="<<std::endl;

    copyTree(root, source.root);
    return *this;
}

template<typename E>
typename BST<E>::node* BST<E>::getMax() const {
    node* temp=root;

    if(temp==nullptr) {
        return nullptr;
    }

    while(temp->right!=nullptr) {
        temp=temp->right;
    }

    return temp;
}

template <typename E>
typename BST<E>::node* BST<E>::getMin() const {
    node* temp=root;

    if(temp==nullptr) {
        return nullptr;
    }

    while(temp->left!=nullptr) {
        temp=temp->left;
    }

    return temp;
}

template <typename E>
typename BST<E>::node* BST<E>::insert(E x) {
    node* current=root;
    node* previous=nullptr;

    while(current!=nullptr) {
        previous=current;

        if(x < current->key) {
            current=current->left;
        }
        else {
            current=current->right;
        }
    }

    node* nEl=new node;
    nEl->right=nullptr;
    nEl->left=nullptr;
    nEl->key=x;

    if(previous!=nullptr) {
        if(x < previous->key) {
            previous->left=nEl;
        }
        else {
            previous->right=nEl;
        }
    }
    else {
        root=nEl;
    }

    ++numberOfNodes;

    return nEl;
}

template <typename E>
bool BST<E>::remove(E x) {
    auto temp=root;
    node* parent=nullptr;

    while(temp!=nullptr && temp->key!=x) {
        parent=temp;

        if(x < temp->key) {
            temp=temp->left;
        }
        else {
            temp=temp->right;
        }
    }

    if(temp==nullptr) {
        return false;
    }

    auto toRemove=temp;
    if(temp->right==nullptr) {
        if(parent!=nullptr) {
            if(parent->left==temp) {
                parent->left=temp->left;
            }
            else {
                parent->right=temp->left;
            }
        }
        else {
            root=temp->left;
        }
    }
    else if(temp->left==nullptr) {
        if(parent!=nullptr) {
            if(parent->left==temp) {
                parent->left=temp->right;
            }
            else {
                parent->right=temp->right;
            }
        }
        else {
            root=temp->right;
        }
    }
    else {
        auto e=temp->left;
        parent=temp;

        if(e->right==nullptr) {
            temp->key=e->key;
            parent->left=e->left;
        }
        else {
            while(e->right!=nullptr) {
                parent=e;
                e=e->right;
            }

            temp->key=e->key;
            parent->right=e->left;
        }
        
        toRemove=e;
    }

    delete toRemove;
    --numberOfNodes;

    return true;
}

template <typename E>
typename BST<E>::node* BST<E>::find(E x) const {
    auto temp=root;

    while(temp!=nullptr && temp->key!=x) {
        if(x < temp->key) {
            temp=temp->left;
        }
        else {
            temp=temp->right;
        }
    }

    return temp;
}

template <typename E>
size_t BST<E>::size() const {
    return numberOfNodes;
}

template <typename E>
void BST<E>::inOrder(node* e) const {
    if(e==nullptr) {
        return;
    }

    inOrder(e->left);
    std::cout<<e->key<<" ";
    inOrder(e->right);
}

template <typename E>
void BST<E>::postOrder(node* e) const {
    if(e==nullptr) {
        return;
    }

    postOrder(e->left);
    postOrder(e->right);
    std::cout<<e->key<<" ";
}

template <typename E>
void BST<E>::preOrder(node* e) const {
    if(e==nullptr) {
        return;
    }

    std::cout<<e->key<<" ";
    preOrder(e->left);
    preOrder(e->right);
}

template <typename E>
typename BST<E>::node* BST<E>::getTreeRoot() const {
    return root;
}


#endif  //BST_HPP

set.hpp:

#ifndef SET_HPP
#define SET_HPP

#include "bst.hpp"
//#include <stack>

template <typename E>
class Set : public BST<E> {
    typename BST<E>::node* root;
    size_t numberOfNodes;

    public:
    Set();
    Set(const Set<E>& source);
    typename BST<E>::node* find(E x) const;
    typename BST<E>::node* insert(E x);
    void inOrder(typename BST<E>::node* e) const;
    bool remove(E x);
    typename BST<E>::node* getTreeRoot() const;
    Set<E>& operator=(const Set<E>& source);
};

template <typename E>
Set<E>::Set() : BST<E>() {
}

template <typename E>
Set<E>::Set(const Set<E>& source) : BST<E>(source) {

}

template <typename E>
typename BST<E>::node* Set<E>::insert(E x) {
    if(find(x)!=nullptr) {  //znaleziono taki element
        return nullptr;
    }

    return BST<E>::insert(x);
}

template <typename E>
typename BST<E>::node* Set<E>::find(E x) const {
    return BST<E>::find(x);
}

template <typename E>
void Set<E>::inOrder(typename BST<E>::node* e) const {
    return BST<E>::inOrder(e);
}

template <typename E>
typename BST<E>::node* Set<E>::getTreeRoot() const {
    return BST<E>::getTreeRoot();
}

template <typename E>
bool Set<E>::remove(E x) {
    return BST<E>::remove(x);
}

template <typename E>
Set<E>& Set<E>::operator=(const Set<E>& source) {
    
    if(&source==this) {
        return *this;
    }

    this->numberOfNodes=source.numberOfNodes;
    BST<E>::copyTree(root, source.root);
    std::cout<<"skopiowane"<<std::endl;

    return *this;
}


#endif //SET_HPP

test4.cpp:

#include "set.hpp"

int main() {
    Set<int> tree;

    tree.insert(8);
    tree.insert(2);
    tree.insert(1);
    tree.insert(3);
    tree.insert(10);
    tree.insert(9);
    tree.insert(11);
    tree.insert(11);

    std::cout<<tree.size()<<std::endl;
    /*tree.inOrder(tree.getTreeRoot());
    std::cout<<std::endl;*/


    auto tree2=tree;

    /*tree.inOrder(tree.getTreeRoot());
    std::cout<<std::endl;*/

    tree.remove(2);
    tree.remove(2);
    tree.remove(11);

    Set<int> tree3;
    tree3=tree;

    tree.inOrder(tree.getTreeRoot());
    std::cout<<std::endl;

    tree2.inOrder(tree2.getTreeRoot());
    std::cout<<std::endl;
    //std::cout<<tree2.getTreeRoot()->key<<std::endl;

    //std::cout<<tree.size()<<std::endl;

    std::cout<<tree.size()<<std::endl;
    std::cout<<tree2.size()<<std::endl;
    std::cout<<tree3.size()<<std::endl;
}
3 
template <typename E>
class BST {
    // ...
    node* root;   //korzeń
    // ...
};

template <typename E>
class Set : public BST<E> {
    typename BST<E>::node* root;
    // ...
};

Bezpośrednim powodem jest fakt, że przesłaniasz zmienną BST<T>::root zmienną Set<T>::root, a tej wartości nigdzie nie ustalasz. Czyli klasyczne UB.

Usunięcie tej zmiennej i poprawa kompilacji powoduje, że program się wykonuje:

    BST<E>::copyTree(this->root, source.root);
                     ^^^^^^

Przy czym nie podoba mi się użycie tutaj dziedziczenia. Set powinien enkapsulować swoją implementację, a nie ją uwypuklać.

0

Dziękuję za pomoc :)
Jeśli dobrze rozumiem, chodziło o to, że konstrukcję zbioru zaczynałem od przesłoniętego root, do niego też wszystko "podłączałem", a kopiowanie zaczynałem od root przesłaniającego. I z tego samego powodu moja wcześniejsza implementacja konstruktora kopiującego (korzystająca z copyTree) powodowała Segmentation fault.

W kwestii implementacji - podejrzewam, że chodzi Ci o to, by stworzyć całkowicie oddzielną klasę Set, która posiadałaby wewnątrz własny obiekt BST i na nim operowała. Nie wiem dlaczego, ale na początku uznałem dziedziczenie za prostsze rozwiązanie.

1 użytkowników online, w tym zalogowanych: 0, gości: 1