Modern C++ Linkedlist Memorymanagement

TheCrazyDev64

Moin,
ich bin gerade dabei C++ zu lernen und bin dabei eine LinkedList in C++ zu programmieren. Dabei stoß ich auf ein paar Probleme. Bisher hab ich eher in C mit normalen Pointern gearbeitet und diese soll man ja oftmals eher meiden hab ich gelesen. Genauso hab ich gelesen, dass man für Datenstrukturen sowas eher weniger verwendet.

Derzeit hab ich folgende Klasse für mein Node:

template<class T>
class DoubleLinkedNode {
private:
    std::shared_ptr<T> item_;
    DoubleLinkedNode<T> *next_;
    DoubleLinkedNode<T> *prev_;

public:
    explicit DoubleLinkedNode(std::unique_ptr<T> item) : item_(item), next_(nullptr), prev_(nullptr) {}

    DoubleLinkedNode(std::unique_ptr<T> item, DoubleLinkedNode<T> *next, DoubleLinkedNode<T> *prev) : item_(item),
                                                                                                      next_(next),
                                                                                                      prev_(prev) {
        item_ = std::move(item);
    }


    std::unique_ptr<T> getItem() { return item_; }

    DoubleLinkedNode<T> *getNext() { return next_; }

    DoubleLinkedNode<T> *getPrev() { return prev_; }

    void setNext(DoubleLinkedNode<T> *next) { next_ = next; }

    void setPrev(DoubleLinkedNode<T> *prev) { prev_ = prev; }

    DoubleLinkedNode *operator=(DoubleLinkedNode<T> *other) {
        std::shared_ptr<T> item = new T(*other->getItem());
        return new DoubleLinkedNode<T>(item, other->getNext(), other->getPrev());
    }

    ~DoubleLinkedNode() {
        item_ = nullptr;
        next_ = nullptr;
        prev_ = nullptr;
    }
};

Wie man erkennen kann nutze ich Raw pointer für die Node Verknüpfung, sowie ein Smart pointer für das Item.
Meine Idee des Smartpointers in der Liste ist, dass man sich nicht um das Löschen des Items kümmern muss, sondern das automatisch passiert.
Ist der Ansatz gut? Und gibt es weitere Verbesserungen (wenn ja, warum?) Die einfache Theorie (zumindest shared und unique) versteh ich, aber wie man die nun Optimal anwendet bisher nicht ganz.

Wo wir bereits dabei sind. Beim implementieren der Linkedlist fiel mir auf, dass ich beim Implementieren in der .cpp bei der ersten Methodendeklaration keine Template angeben musste, bei allen anderen schon. Was läuft da schief?

Jockelx

Hi,

erstmal Dauem hoch für deinen ersten Beitrag! So ordentlich kriegen das viele nach 50 Beiträgen nicht hin!

@TheCrazyDev64 sagte in Modern C++ Linkedlist Memorymanagement:

Bisher hab ich eher in C mit normalen Pointern gearbeitet und diese soll man ja oftmals eher meiden hab ich gelesen.

Man soll raw--owning-pointer vermeiden, d.h. "normale" Pointer, die Resourcen "besitzen" (also z.B. explizit mit "new" gesetzt werden). Für besitzende Zeiger bieten sich unique_ptr an. Den Besitz kann man auch übertragen, wie dein Konstruktor z.B. gut und richtig andeutet: unique_ptr als Parameter heisst: Ich will das Ding besitzen - kein Anderer.
Andererseits heißt unique_ptr als Rückgabewert einer Funktion (bei dir "getItem") , dass man nicht mehr Besitzer sein will.
Das ist so sicherlich nicht gewollt und lässt sich sowieso nicht kompilieren, weil item_ ein shared_ptr ist, was ich auch nicht verstehe, warum. getItem sollte also einen normalen Pointer zurückgeben.

Dann noch: Destruktoren lässt man weg, wenn nicht gebraucht und irgendwas auf nullptr im Destruktor setzen erst recht.
Das "move" im Konstruktor macht keinen Sinn - du initiaisierst doch schon in der Initiaisierungsliste.
Soweit erstmal als Diskussionsgrundlage.

Ergänzung: "dass ich beim Implementieren in der .cpp"
Du musst template Klassen/Funktionen im header definieren!

TheCrazyDev64

@Jockelx vielen Dank für deine Antwort!

Also verstehe ich das richtig, dass die Smartpointer dazu gedacht sind Objekt an sich zu verwalten und wenn es nicht mehr gebraucht wird zu löschen? Das klingt Logisch und sinnvoll ^^

Macht es sinn, dass die LL das Item als unique_ptr speicher , oder wäre ein Sharedpointer dort sinnvoller? Macht in meinem Fall weniger Sinn, da ich diese Sicherheit nicht brauch, dass man in der Liste was ändert, aber eventuell gibt es ja noch andere Argumente

Die Template hab ich in der .h Datei natürlich angelegt und die Methoden auch per Template deklariert.

Aber wenn ich diese nun Implementieren will, hab ich das Problem, dass ich die erneut angeben muss. Beispiel:

template<typename T>
void LinkedList<T>::add(T item){...}

wob

@TheCrazyDev64 sagte in Modern C++ Linkedlist Memorymanagement:

Macht es sinn, dass die LL das Item als unique_ptr speicher , oder wäre ein Sharedpointer dort sinnvoller? Macht in meinem Fall weniger Sinn, da ich diese Sicherheit nicht brauch, dass man in der Liste was ändert, aber eventuell gibt es ja noch andere Argumente

Nein, normalerweise speichern die Container einfach T, also direkt das Objekt, nicht einen Pointer auf irgendwas. Nimm mal als usecase einfach eine Liste von int. Du willst da den int direkt speichern, nicht einen Pointer auf int. Wenn der Anwender deiner Klasse Pointer will, muss er halt einfach DoubleLinkedNode<int*> nehmen - oder was auch immer. Jedenfalls speichern std::vector, std::list etc. einfach direkt die Objekte, keine Pointer.

hustbaer

@TheCrazyDev64 sagte in Modern C++ Linkedlist Memorymanagement:

Macht es sinn, dass die LL das Item als unique_ptr speicher

unique_ptr würde schon Sinn machen mMn. Die einzige Gefahr dabei ist dass du nen Stack-Overflow bekommst wenn eine grosse Liste gelöscht wird. Weil dann immer der Destruktor eines Knoten den eigenen unique_ptr zerstört, der dann den nächsten Knoten zerstört, der dann wieder seinen unique_ptr zerstört usw.

wob

@hustbaer sagte in Modern C++ Linkedlist Memorymanagement:

unique_ptr würde schon Sinn machen mMn.

Ich will nur sichergehen: die Frage war hier nach dem Item, also den Daten selbst. Es gibt keine Rekursion in Listenlänge, die die next- und prev-Pointer ja keine unique_ptr sind.

hustbaer

Upps.
Beim Item macht unique_ptr mMn. keinen Sinn. Das sollte man wohl doch eher direkt in die Node reinlegen. Also direkt T statt xyz_ptr<T>.

Jockelx

@hustbaer
Als prev/next Zeiger macht ein unique_ptr aber noch weniger Sinn. Zumindest einer (prev oder next) darf kein unique_ptr sein.

hustbaer

@Jockelx Richtig. Ich hab einfach nicht aufgepasst. Also überhaupt nicht. Bin von einer einfach verketteten Liste ausgegangen. Obwohl eh klar dasteht/zu sehen ist dass es ne doppelt verkettete Liste ist. Nur dazu hätte ich halt mehr als bloss nen halben Satz lesen müssen

TheCrazyDev64

Okay danke Jungs, dann hab ich eine grobe Idee bekommen wie man die Smartpointer verwendet