[Solved] Stack Container Klasse, muss pop() den Destruktor aufrufen?



  • Hallo zusammen,

    ich will eine minimale Stack klasse selbst implementieren (mithilfe eines C-Style Arrays welches ggf. dynamisch wächst).

    Ich habe nun in einem Buch über vector::pop_back() gelesen, dass hier explizit der Destruktor aufgerufen wird. Dann habe ich darüber nachgedacht, wie meine pop() Funktion momentan so aussieht:

    template<class T>
    void Stack<T>::pop()
    {
        if (!sz) throw std::out_of_range{ "Called Stack::pop() on empty stack" };
        --sz;
    }
    

    Es wird also einfach der Speicherplatz zum Überschreiben freigegeben. Jetzt habe ich aber überlegt, dass am Ende die Destruktoren der via 'pop' entfernten Elemente nicht aufgerufen werden, wenn man diese Elemente wieder via 'push' überschreibt.

    Jetzt die überlegung, wenn T selbst Ressourcen hat, welche freigegeben werden müssen, dann würde das doch leaken. Nun meine Frage: Übersehe ich etwas oder ist meine Implementierung tatsächlich total falsch? Und wenn ja, wie korrigiere ich das?

    Ich habe im Internet gesucht, aber da geht es meistens darum, ob vector<T*> delete selbst aufruft bei erase/pop_back etc.

    template<class T>
    Stack {
    // ...
    private:
        T* elem;
        std::size_t sz;
        std::size_t space;
    };
    
    template<class T>
    Stack<T>::Stack()
        :elem{}, sz{}, space{}
    {
    }
    
    template<class T>
    Stack<T>::~Stack()
    {
        delete[] elem;
    }
    
    template<class T>
    void Stack<T>::push(const T& val)
    {
        if (sz == space) reserve(sz ? 2*space : 8);
        elem[sz] = val;
        ++sz;
    }
    
    template<typename T>
    void Stack<T>::reserve(std::size_t n)
    {
        if (n <= space) return;
        auto mem = new T[n];
        for (std::size_t i = 0; i < sz; ++i)
            mem[i] = elem[i];
        delete[] elem;
        elem = mem;
        space = n;
    }
    

    Vielen Dank im Voraus.

    LG

    Edit: z.B. könnte es so aussehen?

    if (!sz) throw std::out_of_range{ "Called Stack::pop() on empty stack" };
    --sz;
    elem[sz].~T();
    


  • Bereits im reserve rufst du die Konstruktoren auf! Ist das gewollt?

    Jetzt die überlegung, wenn T selbst Ressourcen hat, welche freigegeben werden müssen, dann würde das doch leaken.

    Sehe ich nicht, denn du rufst ja am Ende, soweit ich das gerade sehe, korrekt delete[] auf. Das delete[] interessiert sich ja nicht für deine sz-Variable. Und auch "Es wird also einfach der Speicherplatz zum Überschreiben freigegeben." ist so nicht richtig, du überschreibst ja nicht den Speicherplatz brutal, sondern rufst ja bei push T.operator= auf.

    Das wirkliche Problem ist, dass du die Konstruktoren bereits alle am Anfang (nicht erst bei push) und die Destruktoren erst im Destruktor aufrufst, nicht schon bei pop. Ich denke, du wirst mit placement-new arbeiten müssen und die Destruktoren explizit aufrufen müssen.

    Was ist denn das Ziel der Übung?



  • std::string und int auf Palindrome prüfen mithilfe des Stacks... 🙄 (Darum geht es glaube nicht, es geht darum template's zu verwenden etc.)

    Da kann man nix machen, daher ist mein Ziel den minimalen Stack korrekt und ordentlich zu implementieren (ohne zu sehr zu "übertreiben", sprich mit Allokator etc. wie bei std::vector). Es heißt auch der Stack soll wieder schrumpfen können, aber damit habe ich mich noch nicht befasst.

    Also push , pop , top , size im Prinzip, mehr soll der nicht können. Ich habe auch eine Version mit einer singly linked list gemacht, es stellte sich aber beim Messen heraus, dass diese viel langsamer ist.



  • Die Destruktoren aller Elemente werden beim delete[] aufgerufen. Da leakt nichts und du darfst den Destruktor hier nicht selbst aufrufen, sonst passiert das nämlich mehrfach pro Objekt.

    Außerdem muss dir klar sein, was hier passiert:

    auto mem = new T[n];
    

    Damit erzeugst du n vollwertige Elemente, egal was dein aktuelles sz ist.
    std::vector & Co. verwenden placement new um Elemente innerhalb ihres reservierten Speicherbereichs zu erzeugen. Um solche Objekte wieder zu zerstören, kannst/musst du dann tatsächlich selbst deren Destruktor aufrufen.



  • HarteWare schrieb:

    daher ist mein Ziel den minimalen Stack korrekt und ordentlich zu implementieren

    Naja, dann musst du erstmal festlegen, was für dich korrekt ist. Ein Container, der keine Typen ohne Defaultkonstruktor beherbergen kann, wäre für mich schon mal nicht korrekt oder zumindest nicht sonderlich nützlich. Dem Professor (oder wer auch immer die Aufgabe gestellt hat) ist das dagegen wahrscheinlich egal.



  • OK soweit habe ich jetzt verstanden, dass new T[n] für alle n Objekte den default Konstruktor aufruft, was wohl eine ziemliche Verschwendung ist (und eine Limitierung, man braucht einen default ctor).

    Was ich noch nicht verstanden habe, ist warum

    push(foo);
    pop();
    push(bar)
    

    Den Destruktor von foo aufruft. Denn das delete[] ruft zwar jeden Destruktor der Array Elemente auf, aber foo wurde ja "überschrieben" sozusagen. Ich habe diese Klasse zum Test verwendet:

    struct TP {
        TP() { }
        explicit TP(bool) :ID{ id++ } { std::cerr << str(); }
    
        ~TP() { if (ID) std::cerr << "~" << str(); }
    
        TP(const TP&)
            :ID{ id++ }
        { 
            std::cerr << "copy ctor " << str(); 
        }
    
        TP& operator=(const TP&) 
        { 
            ID = id++;
            std::cerr << "copy assign " << str(); return *this; 
        }
    
        string str() const { return "TP(" + (ID ? std::to_string(ID) : "") + ")\n"; }
        static int id;
        int ID{};
    };
    
    int TP::id{ 1 };
    
    int main()
    {
        Stack<TP> s;
        s.push(TP{true});
        s.pop();
        s.push(TP{true});
    }
    

    Output (Kommentiert nach meinem Verständnis):

    TP(1)    // ctor des Parameters zu push()
    copy assign TP(2)    // das passiert bei elem[sz] = val
    ~TP(1)    // dtor des Paramters zu push() am Ende der Funktion
    
    // mit elem[sz].~T() in pop() würde hier ~TP(2) aufgerufen werden.
    
    TP(3)    // ctor des Parameters zum zweiten push()
    copy assign TP(4)    // analog
    ~TP(3)    // analog
    ~TP(4)    // dtor für das als zweites gepushte Element wird aufgerufen, ~TP(2) aber nicht
    

    Ich glaube euch schon, aber verstehen tu ich's nicht, und das bringt mir dann auch nichts.

    Was das Anfordern des Speichers ohne die Konstruktoren aufzurufen angeht, bzw. placement new/delete werde ich mal nachlesen.

    Vielen Dank.

    LG

    Edit:
    Soweit habe ich in "More Effective C++" Item4 und Item8 gelesen und bin zu folgenen Änderungen gelangt (bin mir nicht sicher ob das richtig ist):

    // elem is T*
    
    template<class T>
    Stack<T>::~Stack()
    {
        while (sz--) elem[sz].~T();
        operator delete[](elem);
    }
    
    template<class T>
    void Stack<T>::push(const T& val)
    {   // leerer stack: sz == space == 0
        if (sz == space) reserve(sz ? 2*space : 8);
        new (elem + sz) T(val);  // placement-new via copy-ctor?
        ++sz;
    }
    
    template<class T>
    void Stack<T>::pop()
    {
        if (!sz) throw std::out_of_range{ "Called Stack::pop() on empty stack" };
        --sz;
        elem[sz].~T();
    }
    
    template<typename T>
    void Stack<T>::reserve(std::size_t n)
    {
        if (n <= space) return;
        auto mem = static_cast<T*>(operator new[](n * sizeof(T)));
        for (std::size_t i = 0; i < sz; ++i)
            new (mem + i) T(elem[i]);  // anstatt mem[i] = elem[i]
        operator delete[] (elem); 
        elem = mem;
        space = n;
    }
    

    Schätze mal, std::allocator soll genau das machen, nur schön gekapselt?

    Edit2: Im Code oben stimmt die Exceptionsicherheit wohl auch nicht mehr. Aber mal davon abgesehen.



  • Vielleicht solltest du zum besseren Verständnis deines Codes (vor dem Edit) mal folgende Klasse testen:

    struct TP {
        TP() : ID(id++) {
            std::cerr << "default construct: " << str() << '\n';
        }
        explicit TP(bool) :ID { id++ } { std::cerr << "construct: " << str() << '\n'; }
    
        ~TP() {
            std::cerr << "~" << str() << '\n';
        }
    
        TP(const TP& rhs)
            :ID { id++ }
        {
            std::cerr << "copy ctor from " << rhs.str() << " to new object " << str() << '\n';
        }
    
        TP& operator=(const TP& rhs)
        {
            std::cerr << "copy assign to " << str() << "  setting value of " << rhs.str() << '\n';
            return *this;
        }
    
        std::string str() const {
            return "TP(" + std::to_string(ID) + ")";
        }
        static int id;
        int ID {};
    };
    

    Dann siehst du den Ablauf deutlich besser als bei deiner TP-Klasse, wo du ja nur teilweise siehst, wie konstruiert wird.



  • @wob vielen Dank für dein Beispiel, ich habe es ebenfalls mal laufen lassen und versucht nachzuvollziehen, aber irgendwie klickt es nicht.

    Ich mache mal ein anderes Beispiel: Die Sequenz push-pop-push sieht bei mir im Kopf so aus:

    int main()
    {
        int* front = new int{5};  // analog: push auf das 1. Element vom Stack
    
        front = new int{10};  // analog: pop und push auf das 1. Element vom Stack
    
        delete front;  // analog: Aufruf des Destruktors des 1. Elements vom Stack
        // int{5} leaked
    }
    

    Stack erstellt beim pushen ja eine Kopie des Arguments (elem[sz] = val) und ist somit für das Objekt verantwortlich (ownership). Jetzt kommt pop() und tut einfach so, als wäre das Element garnicht da (--sz). Und beim nächsten push() wird das Element durch ein anderes ersetzt, ohne aber dass der Destruktor des ursprünglichen Elements aufgerufen wird. Am Ende des Tages ruft Stack zwar die Destruktoren jedes einzelnen Elements in elem auf, aber wie soll Stack den Destruktor des ursprünglich ersten Elements aufrufen, wenn dort nun ein anderes Element steht.



  • HarteWare schrieb:

    Stack erstellt beim pushen ja eine Kopie des Arguments (elem[sz] = val) und ist somit für das Objekt verantwortlich (ownership). Jetzt kommt pop() und tut einfach so, als wäre das Element garnicht da (--sz). Und beim nächsten push() wird das Element durch ein anderes ersetzt, ohne aber dass der Destruktor des ursprünglichen Elements aufgerufen wird. Am Ende des Tages ruft Stack zwar die Destruktoren jedes einzelnen Elements in elem auf, aber wie soll Stack den Destruktor des ursprünglich ersten Elements aufrufen, wenn dort nun ein anderes Element steht.

    Nein, beim push() wird nichts kopiert und auch kein Objekt erzeugt, es wird lediglich operator= des bereits vorhandenen Objekts aufgerufen.
    In deinem vorigen Beispiel sind 2 und 4 dasselbe Objekt, deswegen siehst du auch kein ~TP(2). Beim zweiten push wird dem Objekt mit der ID 2 eine neue ID 4 zugewiesen, aber es ist trotzdem noch dasselbe Objekt.



  • Die Ausgabe, die du mit meiner geänderten Klasse siehst, ist wie folgt. Ich versuchs mal zu kommentieren.

    $ ./a.out                       
    construct: TP(1) // es wird das TP {true} (Parameter) erzeugt
    default construct: TP(2)  // nun kommt das push, das resize ruft
    default construct: TP(3)  // und deine 8 Objekte (2-9) erzeugt
    default construct: TP(4)
    default construct: TP(5)
    default construct: TP(6)
    default construct: TP(7)
    default construct: TP(8)
    default construct: TP(9)
    copy assign to TP(2)  setting value of TP(1) // hier das = im push
    ~TP(1) // nun ist der push-Befehl vorüber und das temporäte Objekt (Parameter) wird gelöscht
    construct: TP(10) // wieder Parameter erzeugen
    copy assign to TP(2)  setting value of TP(10) // wieder der operator=
    ~TP(10) // Parameter löschen
    ~TP(9) // und nun die 8 erzeugten Objekte des Stacks löschen
    ~TP(8)
    ~TP(7)
    ~TP(6)
    ~TP(5)
    ~TP(4)
    ~TP(3)
    ~TP(2)
    

    Klar soweit?



  • Achso, wenn die Klasse eine Ressource hat, muss der copy-assignment-operator ja dafür sorgen, dass die alte Ressource freigegeben wird. Da war denke ich mein Fehler, mit dem Gedanke da geht was durch "überschreiben" verloren. Ich bin etwas langsam heute, vielen Dank für Eure Hilfe/Geduld wob und ;kar! Es ergibt jetzt alles Sinn.

    Damit wäre die Frage auch (sehr ausführlich) geklärt, der ganze allocator Kram kann dann wenn schon in einen neuen Thread.

    LG



  • HarteWare schrieb:

    Achso, wenn die Klasse eine Ressource hat, muss der copy-assignment-operator ja dafür sorgen, dass die alte Ressource freigegeben wird.

    Nein. Das siehst du schon daran, dass der copy-Constructor bzw. assignment-Operator sein Argument als const& bekommt. Er gibt überhaupt nichts altes frei.

    Oder meinst du ausschließlich den operator= und die Resource des eigenen Objekts? Die muss auch nicht zwangsweise freigegeben werden, vielleicht kann sie ja einfach wiederverwendet werden?



  • Ich meinte jetzt die eigene, z.B.

    vector<int> v1, v2;
    // ...
    v1 = v2
    

    Da wird da v1 die Elemente von v2 kopieren, und dabei seinen alten Speicher freigeben.

    P.S.: Wollte mich grad beschweren, warum der primitive Stack 30% - 50% schneller läut mit push, als der vector, dann ist mir aufgefallen ich mache es mit einfachen integern^^



  • Wenn du nur ints hast, dann kannst du auch optimieren. Deine Objekte sind dann relocatable.

    Ich fand das hier ganz erhellend: https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md



  • Ich wusste nicht, dass der Faktor 2 so schlecht ist. Verstehen von dem ganzen low-level Memory Zeugs tu ich nicht so viel, aber ich fande das trotzdem interessant.


Anmelden zum Antworten