Obiekt ze wskaznikami, tablica wskaznikow na obiekty

Witajcie. Na ile poniższy kod jest poprawny? Czy w dobry sposob deklaruję tablicę wskazników na obiekty dynamiczne?
Czy dodając element klasy Element do kolejki/listy muszę mieć napisany konstruktor kopiujacy, czy jesli zależy mi na tym, aby w kolejce były trzymane tylko wskazniki, to taki jest mi niepotrzebny?
W podobnym kodzie, tylko duzo bardziej rozbudowanym mam błąd w programie "Double free or corrupt (out)".

Drugie pytanie z innej beczki, to czy w Element wskazniki mogę zamienić na referencję, i to będzie działać tak samo ?

#include <iostream>
#include <list>

using namespace std;

struct Element{
    Element* parent;
    list<Element*> children;
    int value;
    Element(Element* parent, int value)
        : parent(parent)
        , value(value){}

};

void deleteElement(Element *el){
    for(Element* child : el->children){
        deleteElement(child);
    }

    cout << "USUWAM " << el->value << endl;
    delete el;
}

int main() {

    int n = 3;
    Element** pointersToElements = new Element*[n+1];

    Element* el1 = new Element(nullptr, 1);
    Element* el2 = new Element(el1, 2);
    el1->children.push_back(el2);

    Element* el3 = new Element(el2, 3);
    el2->children.push_back(el3);

    pointersToElements[el1->value] = el1;
    pointersToElements[el2->value] = el2;
    pointersToElements[el3->value] = el3;

    pointersToElements[el2->value]->children.push_back(new Element(el2, 7));
    delete [] pointersToElements; // co własciwie sie stanie ? Znsizcze tablice wskaznikow, czy takze obiekty na ktore wskazuja wskazniki zostana zmienione

    deleteElement(el1);

    return 0;
}

    for(Element* child : el->children){
        if (child != nullptr) {
            deleteElement(child);
        }
    }

Dlaczego przy deklaracji tego typu

Element** pointersToElements = new Element*[n+1];

mam problem przy niszczeniu elementów "double free or corruption" , a kiedy uzywam automatycznej tablicy wskaznikow to zadnych problemow z obiektami typu element nie ma.

Element* pointersToElements[someConstSize];

Czy w 1 sposobie dzieje się coś szczególnego? Jakieś przesuniecia wskaznikow, czy cos?

piotreekk napisał(a):

Witajcie. Na ile poniższy kod jest poprawny? Czy w dobry sposob deklaruję tablicę wskazników na obiekty dynamiczne?

Teoretycznie tak, ale nie widzę sensu w tworzeniu takiej tablicy. Czasem życia każdego(oprócz tzw. root) obiektu zarządza jego rodzic, więc trzymanie dodatkowo wszystkich wskaźników gdzieś indziej skomplikuje tylko sprawę(synchronizacja).

Czy dodając element klasy Element do kolejki/listy muszę mieć napisany konstruktor kopiujacy, czy jesli zależy mi na tym, aby w kolejce były trzymane tylko wskazniki, to taki jest mi niepotrzebny?

Jeśli jest to kontener wskaźników to konstruktor/operator kopiujący nie ma tutaj nic do tego. Kopiowany jest wyłącznie wskaźnik na obiekt a nie sam obiekt.

Drugie pytanie z innej beczki, to czy w Element wskazniki mogę zamienić na referencję, i to będzie działać tak samo ?

Nie bardzo. Referencja nie może być nullem. Czym zainicjujesz składową parent dla obiektu nie mającego rodzica?

    delete [] pointersToElements; // co własciwie sie stanie ? Znsizcze tablice wskaznikow, czy takze obiekty na ktore wskazuja wskazniki zostana zmienione

Jeśli masz na kartce listę książek znajdujących się na półce to czy wyrzucenie tej kartki do kosza oznacza wyrzucenie też książek? No nie.

piotreekk napisał(a):

Dlaczego przy deklaracji tego typu

Element** pointersToElements = new Element*[n+1];

mam problem przy niszczeniu elementów "double free or corruption" , a kiedy uzywam automatycznej tablicy wskaznikow to zadnych problemow z obiektami typu element nie ma.

Komunikat wydaje się w miarę jasny. Próbujesz usunąć coś, co zostało już wcześniej usunięte.

BTW dlaczego wybrałeś list zamiast vector?

Dziękuję za odpowiedz na każde z pytań. ;) List użyłem jakoś z automatu, bo pomyslałem sobie że muszę trzymać listę wskazników na dzieci, więc wpisałem "std::list", ale z tego co wiem, to z zewnątrz nie widać różnicy w korzystaniu z list i vector (może kilkoma operacjami się różnią, które w jednym kontenerze są a w innym ich nie ma).

tajny_agent napisał(a):

piotreekk napisał(a):

Dlaczego przy deklaracji tego typu

Element** pointersToElements = new Element*[n+1];

mam problem przy niszczeniu elementów "double free or corruption" , a kiedy uzywam automatycznej tablicy wskaznikow to zadnych problemow z obiektami typu element nie ma.

Komunikat wydaje się w miarę jasny. Próbujesz usunąć coś, co zostało już wcześniej usunięte.

Z tym że próbuję usunąć coś co zostało już usunięte, to małe prawdopodobieństwo. Ogólnie jesli nie tworzę dynamicznej tablicy wskaznikow na elementy i nie korzystam z niej to problemu z usuwaniem nie ma, wszystko ładnie się rekurencyjnie usuwa. Jeśli utworzę taką tablicę i przy jej pomocy dodaję elementy do drzewa (tablica wskaznikow, w ktorej pod indeksem element.number jest wskaznik do elementu) to napotykam ten problem z podwójnym usuwaniem :(

Pewnie gdzieś kopiujesz i masz double delete, bo nie przestrzegasz rule of three/five/zero. Dodatkowa lektura: https://dsp.krzaq.cc/post/176/ucze-sie-cxx-kiedy-uzywac-new-i-delete/

    void utworz(list<pair<int, int> > sciezki){
        korzen = new Node(nullptr, 1);

        Node* current = korzen;
        Node** pointers = new Node*[paths.size()+1];
        pointers[1] = root;
        for(pair<int, int> path : paths){
            current = pointers[path.first];
//            cout << " Adres przy tworzeniu: " << current << endl;

            Node* child = new Node(current, path.second);
            current->children.push_back(child);
            pointers[child.number] = child;
        }

        delete [] pointers;
    }

W powyższym kodzie Node to odpowiednik Element tak w wiekszym przybliżeniu. Czy taki sposób tworzenia drzewa majac okreslone sciezki(polaczenia miedzy wezlami) jest na ileś % poprawny?

Wrzucam MCVE

#include <iostream>
#include <list>

using namespace std;

class Tree{
private:
    struct Node{
        int number;
        Node* parent;
        list<Node*> children;

        Node(){}
        Node(Node* parent, int number)
            : number(number)
            , parent(parent)
        { }

        ~Node(){
            cout << "Usuwam sie " << endl;
        };

        Node(const Node &other) = delete;
        Node &operator=(const Node &other) = delete;
    };

    Node* root;
    int minPathsCount;

public:

    Tree(){}
    Tree(const Tree &other) = delete;
    Tree &operator=(const Tree &other) = delete;
    ~Tree(){
        deleteNode(root);
    }

    void setMinPathsCount(int count){
        minPathsCount = count;
    }

    void create(list<pair<int, int> > paths){
        root = new Node(nullptr, 1);
        Node* current = root;

        // wiem, ze w zadnej parze najwieksza liczba to paths.size()+1
        Node** pointers = new Node*[paths.size()+2];
        pointers[1] = root;

        for(pair<int, int> path : paths){
            current = pointers[path.first];

            Node* child = new Node(current, path.second);
            current->children.push_back(child);
            pointers[child->number] = child;
        }
        delete [] pointers;
    }

    void deleteNode(Node* node){
        for(Node* child : node->children)
            deleteNode(child);
        
        delete node;
    }

};

int main()
{
    list<pair<int, int> > paths = {{1, 2}, {2, 3}, {2, 4}, {3, 5}};
    // path.first < path.size
    // path.second <= path.size()

    Tree drzewo;
    drzewo.create(paths);

    return 0;
}

W końcu jakieś porządne MCVE.

            pointers[child->number] = child;

wartość child->number nie jest powiązana z rozmiarem tablicy i dla podanych przykładowych danych za nią wychodzi - mażesz po pamięci. https://wandbox.org/permlink/8Yf9NiRUXu1JsQCf (wypisuję info w linii 54)

Do takich problemów świetnym pomocnikiem jest debugger i address sanitizer.

Mówiliście, że zwykłych wskazników powinno się unikać, tak samo tworzenia obiektów przy pomocy new. Co byłoby rozsądne w moim przypadku?

Biorąc pod uwagę to co robisz, new może być wybaczalne (niestandardowe strategie alokacji). Ale domyślnie próbowałbym pierw zmiennych automatycznych ("zwykłych zmiennych"), a potem unique_ptr i make_unique.

Wszystko mi się już udało zrobic, działa jak powinno (przynajmniej na razie). Dziękuję Wam za pomoc.
Mam jeszcze jedno pytanie, które mnie trochę dręczy.
Jeśli pozbędę się alokacji na heapie, zmienie wszystkie obiekty na automatyczne, a przy dodawaniu nowego elemetnu do listy dzieci czy do rodzica przekazuję adres pobrany za pomocą operatora & , to nie potrzebne mi już żadne destruktory itd, bo pamięć zwolni się sama.
Ale co z konstruktorem kopiujacym i operatorem przypisania? Musialem je przywrócić zmieniając podejscie na takie, ale czy one powinny dokonywac deep copy? Wydaje mi się, że nie powinno się kopiować rodzica i dzieci w żadne inne miejsce, a jedyne deep copy, jakie mogłoby zachodzić, to w klasie zawierajacej elementy typu Element czy Node tj. Drzewo, bo kiedy skopiowalibysmy drzewo, to aby nie "psuło" nam tego starego, to wskazniki powinny wskazywac na kopie węzłów. Czy moje myslenie jest prawidłowe?