(Geschwindigkeits-)Problem mit ADT Liste



  • Schlangenmensch schrieb:

    camper schrieb:

    std::unique_ptr als Strukturelemente einer verketteten Liste sind wahrscheinlich keine so gute Idee. Es dürfte schwierig sein, Stacküberläufe beim Löschen großer Listen zu vermeiden.

    Warum?

    Stell dir vor, du hast eine einfach verkettete Liste mit 100k Elementen. Nun lasse diese Liste out of scope gehen. Der Destruktor wird aufgerufen. Der Unique-ptr-Destruktor muss nun den Destruktor des Elementes rufen, aus das er zeigt. Dies ist aber wieder eine Node, die zum Zerstören erst einmal die Nachfolger deleten muss. Und so weiter. D.h. du hast dann 100k Destruktor-Calls auf dem Stack und BOOOM.

    Wenn du einen Binärbaum hattest, wird der nicht besonders tief gewesen sein. Denn die Tiefe ist hier das Problem, nicht die Gesamtanzahl Elemente.



  • jo; klasse - der TO wird anhand einer fertigen liste bestimmt gut lernen, es selbst zu bauen.
    wenn das ein wettbewerb im weitpinkeln ist, hättet ihr davor bescheid sagen müssen, dann hätte ich auch nur ne fertige liste hier rein copy&pasted...

    merkt ihr nicht, dass es bei jedem anfänger-thread am ende nur noch darum geht, die c++igste lösung zu posten und der TO jedes mal nach 5-6 beiträgen aufhören kann(sollte!) zu lesen?



  • wob schrieb:

    Stell dir vor, du hast eine einfach verkettete Liste mit 100k Elementen. Nun lasse diese Liste out of scope gehen. Der Destruktor wird aufgerufen. Der Unique-ptr-Destruktor muss nun den Destruktor des Elementes rufen, aus das er zeigt. Dies ist aber wieder eine Node, die zum Zerstören erst einmal die Nachfolger deleten muss. Und so weiter. D.h. du hast dann 100k Destruktor-Calls auf dem Stack und BOOOM.

    Klingt logisch. Aber das sollte man doch umgehen können, wenn ein roher "nicht besitzender" Zeiger auf das nächste Element zeigt und die "besitzenden" Unique_Ptr in einem vector speichert.



  • Bei der Regel der großen 3/5 kann man sich etwas Arbeit sparen durch die Benutzung von unique_ptr. Im Destruktor kann man die Rekursion auflösen, indem man die unique_ptr manuell löscht.

    ~adt_list()
    {
       while( head_ )
       {
          auto& tmp = head_->next;
    // Fix dank theta
    //      head_.release();
          head_.reset( nullptr );
          head_ = tmp;
       }
    }
    

    Ansonsten @camper 👍 👍 👍



  • DocShoe schrieb:

    Beim ser Regel der großen 3/5 kann man sich etwas Arbeit sparen durch die Benutzung von unique_ptr. Im Destruktor kann man die Rekursion auflösen, indem man die unique_ptr manuell löscht.

    ~adt_list()
    {
       while( head_ )
       {
          auto& tmp = head_->next;
          head_.release();
          head_ = tmp;
       }
    }
    

    Ansonsten @camper 👍 👍 👍

    Hier wird aber nicht gelöscht. 🙄



  • Ouch, ja. Ich benutze std::unique_ptr nicht, sondern die boost smart_ptr. Hab mich dann bei der Auswahl der Methode vergriffen 😉


  • Mod

    Schlangenmensch schrieb:

    Klingt logisch. Aber das sollte man doch umgehen können, wenn ein roher "nicht besitzender" Zeiger auf das nächste Element zeigt und die "besitzenden" Unique_Ptr in einem vector speichert.

    Dann löst du das durch den unique_ptr verursachte Problem¹ aber durch mehr Code und mehr Verwaltung, anstatt die wesentlich einfachere Lösung zu nehmen, keinen uniqu_ptr zu benutzen.

    ¹: Danke camper, dass er daran gedacht hat!


Anmelden zum Antworten