(Geschwindigkeits-)Problem mit ADT Liste



  • Hallo und ohje,

    im Folgendem habe ich die perfekt funktionierende ADT-Liste und danach die modifizierte Version, welche eigentlich den Speicherplatz von den zu löschenden Elementen wieder freigeben sollte - dies tut sie; jedoch nur bei einer geringen Anzahl (Viele zu löschende Einträge = Crash) und ist zudem hierbei unglaublich langsam (mir ist bewusst, dass delete nicht schnell ist, hier ist es aber gerade zu astronomisch wie lange der Befehl braucht). Hat wer eine Idee wo der Haas im Pfeffer liegt? 😕

    /*
     * You're not allowed to make any changes to any of this files or share them as well.
     * For more information please contact me.
     * All rights reserved.
     */
    
    /* 
     * File:   main.cpp
     * Author: Simon Beginn
     *
     * Created on 3. März 2017, 19:18
     */
    
    #include <cstdlib>
    #include <iostream>
    
    using namespace std;
    
    template <typename Datatype>
    class ADT_List {
    public:
    
        struct Entry {
            Datatype *content; //Content to save
            Entry *next; //Pointer to next entry
    
            Entry() {
                this->next = NULL;
                this->content = NULL;
            }
    
            ~Entry() {
                //nothing
            }
        };
    
        Entry Anf; //Create startentry
        Entry *Pos; //Create active position
    
        ADT_List() { //Constructor for List
            //Anf = new Entry();  //Create startentry
            this->Pos = &this->Anf; //Set active position to the first entry
            this->Anf.next = NULL; //Set next entry to NOT defined
        }
    
        bool isEmpty() {
            if (this->Anf.next == NULL) { //Is the "first" entry empty?
                return true;
            } else {
                return false;
            }
        }
    
        void gotofirst() {
            this->Pos = &this->Anf; //Set active position to the start
        }
    
        void gotonext() {
            if (!this->isLast()) {
                this->Pos = this->Pos->next; //Set active position to the next
            } else {
                cout << "Error. This is already the last entry." << endl;
            }
        }
    
        void insert(Datatype *x) {
            Entry *newEntry = new Entry(); //Prepare new entry
            newEntry->content = &*x; //Insert content for new entry
            newEntry->next = this->Pos->next; //Set next pointer of the new entry to the next entry of the active position
            this->Pos->next = newEntry; //Insert the new entry now
        }
    
        bool isLast() {
            return (this->Pos->next == NULL);
        }
    
        Datatype* getcontent() {
            return this->Pos->next->content;
        }
    
        void print() {
            cout << "Content of the ADT list:" << endl;
            while (!this->isLast()) {
                cout << "Entry: " << &this->Pos->next;
                cout << "       Next is: " << this->Pos->next << endl;
                gotonext();
            }
            this->gotofirst();
            cout << "End." << endl;
        }
    
        void delEntry() {
            this->Pos->next = this->Pos->next->next;
        }
    };
    
    int main(int argc, char** argv) {
    
        ADT_List<int> *testlist = new ADT_List<int>;
    
        int i = 55;
    
        cout << "Create list..." << endl;
    
        for(int r = 0; r < 30000000; r++) {
           testlist->insert(&r); 
        }
        //testlist->print();
        testlist->gotofirst();
        cout << "List created" << endl;
        string s;
        cin >> s;
        cout << "Cleaning list..." << endl;
        while(!testlist->isLast()) {
            testlist->delEntry();
        }
        //cout << *testlist->getcontent() << endl;
        cout << "List cleared" << endl;
        cin >> s;
    
        return 0;
    }
    

    Und hier Version 2:

    /*
     * You're not allowed to make any changes to any of this files or share them as well.
     * For more information please contact me.
     * All rights reserved.
     */
    
    /* 
     * File:   main.cpp
     * Author: Simon Beginn
     *
     * Created on 3. März 2017, 19:18
     */
    
    #include <cstdlib>
    #include <iostream>
    
    using namespace std;
    
    template <typename Datatype>
    class ADT_List {
    public:
    
        struct Entry {
            Datatype *content; //Content to save
            Entry *next; //Pointer to next entry
    
            Entry() {
                this->next = NULL;
                this->content = NULL;
            }
    
            ~Entry() {
                delete content;
            }
        };
    
        Entry Anf; //Create startentry
        Entry *Pos; //Create active position
    
        ADT_List() { //Constructor for List
            //Anf = new Entry();  //Create startentry
            this->Pos = &this->Anf; //Set active position to the first entry
            this->Anf.next = NULL; //Set next entry to NOT defined
        }
    
        bool isEmpty() {
            if (this->Anf.next == NULL) { //Is the "first" entry empty?
                return true;
            } else {
                return false;
            }
        }
    
        void gotofirst() {
            this->Pos = &this->Anf; //Set active position to the start
        }
    
        void gotonext() {
            if (!this->isLast()) {
                this->Pos = this->Pos->next; //Set active position to the next
            } else {
                cout << "Error. This is already the last entry." << endl;
            }
        }
    
        void insert(Datatype *x) {
            Entry *newEntry = new Entry(); //Prepare new entry
            newEntry->content = &*x; //Insert content for new entry
            newEntry->next = this->Pos->next; //Set next pointer of the new entry to the next entry of the active position
            this->Pos->next = newEntry; //Insert the new entry now
        }
    
        bool isLast() {
            return (this->Pos->next == NULL);
        }
    
        Datatype* getcontent() {
            return this->Pos->next->content;
        }
    
        void print() {
            cout << "Content of the ADT list:" << endl;
            while (!this->isLast()) {
                cout << "Entry: " << &this->Pos->next;
                cout << "       Next is: " << this->Pos->next << endl;
                gotonext();
            }
            this->gotofirst();
            cout << "End." << endl;
        }
    
        void delEntry() {
            Entry *temp = this->Pos->next;
            this->Pos->next = this->Pos->next->next;
            delete temp;
        }
    };
    
    int main(int argc, char** argv) {
    
        ADT_List<int> *testlist = new ADT_List<int>;
    
        int i = 55;
    
        cout << "Create list..." << endl;
    
        for(int r = 0; r < 30000000; r++) {
           testlist->insert(&r); 
        }
        //testlist->print();
        testlist->gotofirst();
        cout << "List created" << endl;
        string s;
        cin >> s;
        cout << "Cleaning list..." << endl;
        while(!testlist->isLast()) {
            testlist->delEntry();
        }
        //cout << *testlist->getcontent() << endl;
        cout << "List cleared" << endl;
        cin >> s;
    
        return 0;
    }
    


  • Du nimmst die Adresse einer lokalen Variablen, fügst sie in die Liste ein und rufst am Schluss noch delete auf diese Adresse auf.


  • Mod

    Wie sollen wir dir helfen, wenn wir dabei deine tolle Lizenz verletzen würden?

    Allgemein fällt auf, dass du sämtliche Regeln der Ressourcenverwaltung in C++ verletzt, z.B. die Regel der großen Drei/Fünf. Für eine detailliertere Analyse müsste ich aber deinen Code modifizieren und würde es auch nur machen, wenn ich das Ergebnis auch hier veröffentlichen darf.


  • Mod

    SeppJ schrieb:

    Wie sollen wir dir helfen, wenn wir dabei deine tolle Lizenz verletzen würden?

    Ich gehe jetzt mal davon aus, dass der Poster der Autor ist, und die Aufforderung zur Hilfe eine entsprechende Lizenzerweiterung darstellt. Aber schon wahr...

    Ich habe mal die erste Variante fürs Erste mit ein paar Kommentaren versehen. Wenn die verstanden wurden, sollte klar sein, was im zweiten Fall schief läuft.

    template <typename Datatype>
    class ADT_List {
    public:
    
        struct Entry {
            Datatype *content;		// Wieso nicht:  Datatype content;     ?
            Entry *next;
    
            Entry() {			// In Hinblick auf die Nutzung der Klasse dürfte dieser Konstruktor überflüssig sein...
                this->next = NULL;		// modernes C++: nullptr
                this->content = NULL;
            }
    
            ~Entry() {			// ... und der Destruktor sowieso
                //nothing
            }
        };
    
        Entry Anf;				// Anf enthält einen content-Zeiger der nie verwendet wird - das kann man besser machen
        Entry *Pos;				// etwas unüblich: Position ist ein Konzept, das unabhängig von einer konkreten Liste gedacht werden kann,
    					// und man kann ja auch innerhalb einer Liste mehrere Postionen gleichzeitig verwalten wollen
    
        ADT_List() {
            this->Pos = &this->Anf;
            this->Anf.next = NULL;		// im Prinzip überflüssig, wegen Entry-Konstruktor
        }
    
        bool isEmpty() {
            if (this->Anf.next == NULL) {	// if (c) return true; else false; ==> return c;
                return true;
            } else {
                return false;
            }
        }
    
        void gotofirst() {
            this->Pos = &this->Anf;
        }
    
        void gotonext() {
            if (!this->isLast()) {
                this->Pos = this->Pos->next;
            } else {			// wenn wir hier landen, ist das Programm fehlerhaft. Für derartige Prüfungen ist ggf. assert order ein direketer Aufruf von abort angebracht.
    					// Einfach weitermachen hilft bei der Fehlersuche meist nicht.
                cout << "Error. This is already the last entry." << endl;
            }
        }
    
        void insert(Datatype *x) {
            Entry *newEntry = new Entry();	// Und hier wäre es schön einen richtigen Konstruktor mit Parametern zu haben. Sonst kann man ja gleich alles in C machen.
            newEntry->content = &*x;	// ***** Hier wird nicht kopiert. Das Idiom &*x auf Pointer angewandt bewrikt gar nichts.
            newEntry->next = this->Pos->next;
            this->Pos->next = newEntry;
        }
    
        bool isLast() {
            return (this->Pos->next == NULL);
        }
    
        Datatype* getcontent() {
            return this->Pos->next->content;
        }
    
        void print() {
            cout << "Content of the ADT list:" << endl;
            while (!this->isLast()) {
                cout << "Entry: " << &this->Pos->next;
                cout << "       Next is: " << this->Pos->next << endl;
                gotonext();
            }
            this->gotofirst();		// Sollte das nicht am Anfang der Ausgabe stehen?
            cout << "End." << endl;
        }
    
        void delEntry() {
            this->Pos->next = this->Pos->next->next;
        }
    };
    
    int main(int argc, char** argv) {
    
        ADT_List<int> *testlist = new ADT_List<int>;
    
        int i = 55;
    
        cout << "Create list..." << endl;
    
        for(int r = 0; r < 30000000; r++) {
           testlist->insert(&r);		// *** r wird nicht kopiert, weshalb
        }
        //testlist->print();		// *** hier bereits alle Einträge in der Liste ungültig sind
        testlist->gotofirst();
        cout << "List created" << endl;
        string s;
        cin >> s;
        cout << "Cleaning list..." << endl;
        while(!testlist->isLast()) {
            testlist->delEntry();
        }
        //cout << *testlist->getcontent() << endl;
        cout << "List cleared" << endl;
        cin >> s;
    
        return 0;
    }
    


  • Hallo SeppJ; Hallo liebes Forum,

    natürlich bin ich der Inhaber des Codes 🙄 - ich hatte vergessen den Lizenztext zu entfernen (oder zumindest abzuändern). Im Folgendem ist nun der Code mit sowohl deinen Änderungen, als auch den notwendigen Änderungen, welche die Geschwindigkeit erheblich erhöhen. 😉 Ich muss allerdings anmerken, dass die Änderungen in der main()-Methode nicht vollständig von mir stammen, so wurden diese von einem Informatik Professor getätigt. Dieser hatte jedoch den cygwin-Kompiler ⚠ genutzt, welcher anscheinend Abstürtze bei zu großer Speicherbelegung verhindert. Ich habe zum schlussendlichen Test dieser Implementation den MinGW-w64 Kompiler genutzt.

    Dennoch danke für alle eure Mühen und bis balde!

    Simonmicro

    /* 
     * File:   main.cpp
     * Author: Simon Beginn
     *
     * Created on 5. April 2017, 16:23
     */
    
    #include <cstdlib>
    #include <iostream>
    
    #include <time.h>
    
    using namespace std;
    
    template <typename Datatype>
    class ADT_List {
    public:
    
        struct Entry {
            Datatype content; //Content to save
            Entry *next; //Pointer to next entry
    
            Entry() {
                this->next = nullptr;
            }
    
            ~Entry() {
                //nothing...
            }
        };
    
        Entry Anf; //Create startentry
        Entry *Pos; //Create active position
    
        ADT_List() { //Constructor for List
            //Anf = new Entry();  //Create startentry
            this->Pos = &this->Anf; //Set active position to the first entry
            this->Anf.next = nullptr; //Set next entry to NOT defined
        }
    
        bool isEmpty() {
            return this->Anf.next == nullptr;
        }
    
        void gotofirst() {
            this->Pos = &this->Anf; //Set active position to the start
        }
    
        void gotonext() {
            if (!this->isLast()) {
                this->Pos = this->Pos->next; //Set active position to the next
            } else {
                cout << "Error. This is already the last entry." << endl;
                exit(1);
            }
        }
    
        void insert(Datatype x) {
            Entry *newEntry = new Entry(); //Prepare new entry
            newEntry->content = x; //Insert content for new entry
            newEntry->next = this->Pos->next; //Set next pointer of the new entry to the next entry of the active position
            this->Pos->next = newEntry; //Insert the new entry now
        }
    
        bool isLast() {
            return (this->Pos->next == nullptr);
        }
    
        Datatype* getcontent() {
            return this->Pos->next->content;
        }
    
        void print() {
            cout << "Content of the ADT list:" << endl;
            this->gotofirst();
            while (!this->isLast()) {
                cout << "Entry: " << &this->Pos->next;
                cout << "       Next is: " << this->Pos->next << endl;
                gotonext();
            }
            cout << "End." << endl;
        }
    
        void delEntry() {
            Entry *temp = this->Pos->next;
            this->Pos->next = this->Pos->next->next;
            delete temp;
        }
    
        ~ADT_List() {
            this->gotofirst();
            while(this->isLast()) {
                this->delEntry(); //Okay, lets cleanup the memory...
            }
        }
    };
    
    int main(int argc, char** argv) {
    
        ADT_List<int> *testlist = new ADT_List<int>;
    
        int i = 55;
    
        cout << "Create list..." << endl;
        char s[1];
        cout << "Hit key to continue.\n";
        cin.getline(s, 1);
    
        clock_t t1 = clock();
        int lsize = 120000000;
        for (int r = 0; r < lsize; r++) {
            testlist->insert(i);
        }
        clock_t t2 = clock();
        int time = ((t2 - t1) * 1000) / CLOCKS_PER_SEC;
        cout <<  time << " ms" << endl;
    
        //testlist->print();
        testlist->gotofirst();
        cout << "List created" << endl;
        cout << "Cleaning list..." << endl;
        cout << "Hit key to continue.\n";
        cin.getline(s, 1);
    
        t1 = clock();
        int step_size = 1000000;
        int step = 0;
        while (!testlist->isLast()) {
            if (step++ % step_size == 0)
                cout << ".";
            testlist->delEntry();
        }
        t2 = clock();
    
        cout << "\nList cleared" << endl;
        time = ((t2 - t1) * 1000) / CLOCKS_PER_SEC;
        cout <<  time << " ms" << endl;
        cout << "Hit key to finish.\n";
        cin.getline(s, 1);
    
        return 0;
    }
    


  • Das Programm hat ein Memory-Leak.



  • @theta

    Könntest du hierzu bitte noch etwas genauer werden??

    Danke.



  • Simonmicro schrieb:

    @theta

    Könntest du hierzu bitte noch etwas genauer werden??

    Danke.

    testlist wird nicht ordentlich gelöscht - allerdings wäre es besser, gleich eine automatische Variable dafür zu benutzen.


  • Mod

    Simonmicro schrieb:

    @theta

    Könntest du hierzu bitte noch etwas genauer werden??

    Danke.

    So ungefähr überall. Bitte Basics anlesen. "Regel der großen Drei" wurde schon genannt, besser auch gleich noch "RAII", um mal allgemein die Philosophie zu verstehen, wie man Ressourcen fehlerfrei und narrensicher verwaltet, noch dazu mit viel weniger Aufwand als du es gerade betreibst.



  • Hallo nochmal,

    ich werde mir diese Konzepte versuchen aneignen, schließlich bin ich kein C++-Profi, und eventuell dann nochmal eine Version hier hochstellen.

    Bis dann!

    Simonmicro



  • Mir war ein wenig langweilig und deshalb hab ich zu erst mal versucht, das ganze so hinzubiegen, dass es korrekt ist. aber da hatte ich nach wenigen minuten schon zu viele baustellen gefunden und dachte, es geht schneller, das ganze neu zu bauen und dir da zu zeigen, wie man es richtig macht. (dass das genau so lang gedauert hat, ist mir erst beim ersten mal auf-die-uhr-gucken aufgefallen :/)

    klammern hab ich mal anders gesetzt, weil ich deine variante nicht mag; was aber nicht heißt, dass sie falsch ist

    ich nehm einfach mal das ganze zeug, was design-technisch keine funktionen der liste sein darf (getcontent, positionen, ...)

    template <typename Datatype>
    struct ADT_List
    {
      bool isEmpty();
      void insert(Datatype x);
      void print();
    
      void delEntry();
    private:
      struct Entry
      {
        Datatype content;
        Entry *next;
    
        Entry()
        {
          next = nullptr;
        }
      };
    
      Entry start_entry;
    };
    

    jetzt machen wir uns erst mal über grundsätzliche dinge gedanken:
    wir haben immer ein item in der liste "start_entry". wie behandeln wir das? wir brauchen trotzdem ne leere liste, also ignorieren wir start_entry.content einfach immer und degradieren es zum dummy.
    damit wissen wir jetzt, wie isEmpty aussieht: return start_entry.next == nullptr;

    außerdem kennen wir jetzt schon das grundgerüst von print:
    die ausgabe an sich habe ich mal nur mit print_zeugs angedeutet:

    {
      Entry* pos = &start_entry;
    
      pos = pos->next;
      while(pos != nullptr)
      {
        print_zeugs( pos );
        pos = pos->next;
      };
    }
    

    das kann man etwas schöner schreiben:

    {
      for( Entry* pos = start_entry.next; pos != nullptr; pos = pos->next )
      {
        print_zeugs( pos );
      }
    }
    

    also sieht unsere liste nun erst mal so aus:

    template <typename Datatype>
    struct ADT_List
    {
      bool isEmpty()
      {
        return start_entry.next == nullptr;
      }
    
      void insert(Datatype x);
      void print()
      {
        for( Entry* pos = start_entry.next; pos != nullptr; pos = pos->next )
        {
          print_zeugs( pos );
        }
      }
    
      void delEntry();
    
    private:
      struct Entry
      {
        Datatype content;
        Entry *next;
    
        Entry()
        {
          next = nullptr;
        }
      };
    
      Entry start_entry;
    };
    

    hier fällt schon auf, dass start_entry / Anf / startentry kein schöner name ist, weil nicht ersichtlich ist, dass es nur ein dummy ist.
    da mir die ausführungen hier dann doch zu lang sind, wie man da schön abhilfe schaffen kann, leben wir aber damit.

    nun, da ich dein positions-merker in ner liste falsch finde (womit ich nicht allein stehen sollte), bau ich mal nur nen push_back(also item am ende einfügen) statt richtigem insert

    void push_back(Datatype to_add)
    {
      Entry* last = /*darum kümmern wir uns später*/;
    
      last->next = new Entry();
      last->next->content = to_add;
    }
    

    und ein pop_back(also letztes item löschen) statt delEntry:

    void pop_back()
    {
      Entry* one_before_last = /*dito*/;
    
      delete one_before_last->next;
      one_before_last->next = nullptr;
    }
    

    jetzt fällt im push_back schon mal auf, dass in den beiden wesentlichen zeilen folgendes passiert:

    last->next = new Entry();
      //last->next = 0x123;
      //last->next->content = Datatype();
      //last->next->next = nullptr;
    
      last->next->content = to_add;
      //last->next = 0x123;
      //last->next->content = to_add;
      //last->next->next = nullptr;
    

    sieht irgendwie so aus, als ob man die zweite zeile auch in der ersten machen könnte, indem wir Entry nen zusätzlichen (oder besser gleich anderen) Konstruktor verpassen:

    struct Entry
      {
        Datatype content;
        Entry *next;
    
        Entry(Datatype value)
        {
          next = nullptr;
          content = value;
        }
      };
    

    [Anmerkung: Hier geschieht (im Prinzip) leider noch immer genau das gleiche, wie oben: für content wirst erst der Standard-Konstruktur aufgerufen und danach wird der Zuweisungsoperator aufgerufen. Wenn du das besser machen möchtest, google nach "C++ Initialisierungsliste"]

    Damit sieht unser push_back jetzt so aus:

    {
      Entry* last = /*...*/;
      last->next = new Entry( to_add );
    }
    

    Einziges Problem:
    ADT_list besitzt einen Member vom Typ Entry . Es existiert aber kein parameterloser Konstruktor mehr für Entry.
    Also entweder brauchen wir einen eigenen Konstruktor für die Liste, der start_entry = Entry( irgendwas ) setzt (wieder: -> Initialisierungsliste; diesmal ist diese zwingend notwendig.) oder der einfache Weg: default-Argument für Entry::Entry

    struct Entry
      {
        Datatype content;
        Entry *next;
    
        Entry(Datatype value = Datatype())
        {
          next = nullptr;
          content = value;
        }
      };
    

    mittlerweile haben wir ne ziemlich lauffähige liste, die aber leider bisher ziemlich eingeschränkten zugriff von außen hat:

    template <typename Datatype>
    struct ADT_List
    {
      bool isEmpty()
      {
        return start_entry.next == nullptr;
      }
    
      void push_back(Datatype x)
      {
        Entry* last = /* TODO */;
        last->next = new Entry( to_add );
      }
    
      void pop_back()
      {
        Entry* one_before_last = /* TODO */;
    
        delete one_before_last->next;
        one_before_last->next = nullptr;
      }
    
      void print()
      {
        for( Entry* pos = start_entry.next; pos != nullptr; pos = pos->next )
        {
          //print_zeugs( pos );
        }
      }
    
    private:
      struct Entry
      {
        Datatype content;
        Entry *next;
    
        Entry(Datatype value = Datatype())
        {
          next = nullptr;
          content = value;
        }
      };
    
      Entry start_entry;
    };
    

    jetzt muss man sich langsam entscheiden, wie gründlich man das ganze machen möchte, um herauszufinden, wie wir weiter vorgehen wollen.
    wir entscheiden uns mal dafür, Entry doch (wieder) public zu machen, und auch außerhalb damit zu arbeiten (-> google "Iterator" ggf. mit "Konzept")

    Wenn wir außerhalb auch Zugriff auf einzelne Elemente haben möchten, brauchen wir also insbesondere einen Weg, einen Verweis auf das erste sowie letzte Item zurückzugeben.
    Da in der Praxis das letzte Element einer Spanne schwieriger zu behandeln ist als das erste nach der dieser Spanne, entscheiden wir uns gleich dazu, nicht das letzte sondern das erste nicht mehr gültige Item (bzw einen Verweis darauf) nach außen zu geben.

    also haben wir zwei weitere Funktionen, die wir begin und end nennen werden.
    damit sieht unsere Liste jetzt so aus:

    template <typename Datatype>
    struct ADT_List
    {
      bool isEmpty()
      {
    /*ist zwar weiterhin korrekt:
        return start_entry.next == nullptr;
      aber nicht so aussagekräftig, wie:
    */
        return begin() == end();
      }
    
      void push_back(Datatype x)
      {
    //  Entry* last = /* TODO */;
    //wird erst mal zu:
    //->
        Entry* last = &start_entry;
    
        while( last->next != nullptr )
          last = last->next;
    //<-
    
        last->next = new Entry( to_add );
      }
    
      void pop_back()
      {
    //  Entry* one_before_last = /* TODO */;
    //wird erst mal (!) zu:
    //->
        Entry* one_before_last = &start_entry;
        while( one_before_last->next->next != nullptr )
          one_before_last = one_before_last->next;
    //<-
    
        delete one_before_last->next;
        one_before_last->next = nullptr;
      }
    
      void print()
      {
    //  for( Entry* pos = start_entry.next; pos != nullptr; pos = pos->next )
    //können wir mit unserer range viel schöner schreiben:
        for( Entry* pos = begin(); pos != end(); pos = pos->next )
        {
          //print_zeugs( pos );
        }
      }
    
      struct Entry
      {
        Datatype content;
        Entry *next;
    
        Entry(Datatype value = Datatype())
        {
          next = nullptr;
          content = value;
        }
      };
    
      Entry* begin()
      {
        return start_entry.next;
      }
    
      Entry* end()
      {
    //logisch:
    //->
        Entry* last = begin();
    
        while(last->next != nullptr)
          last = last->next;
    
        return last->next;
    //<-
    //wird zu
        return nullptr;
      }
    
    private:
      Entry start_entry;
    };
    

    machen wir uns mal ein paar gedanken:
    isEmpty(): wenn das erste item der liste gleich das erste item nach der liste ist, ist die liste leer. gut, ist also richtig. [Anmerkung: Die Liste wird mit dieser Funktion nicht verändert. -> google "const correctness"]

    zu push_back(): kann man natürlich auch wieder schöner schreiben:

    Entry* last;
        for( last = &start_entry; last->next != end(); last = last->next )
          ;
    
    //...
    

    das &start_entry stört (mich) zwar ein wenig, aber begin() können wir hier nicht verwenden (!leere liste!).

    beim pop_back fällt sofort auf, dass dort X->next->next steht ohne das wir zuvor jemals X->next auf 0 getestet haben.
    ist ja auch klar: eine liste, aus der das letzte element entfernt werden soll, braucht mindestens ein (X->next) element.
    [für das abfragen solcher logikfehler wird normalerweise assert() genutzt -> "C++ assertion"]

    unser print gibt natürlich noch immer nichts aus, weil der körper der for-schleife leer ist.
    aber das bekommst du schon hin.
    [man könnte jetzt hinterfragen, ob die print-funktion wirklich member-funktion der Liste sein muss]

    begin() ist auch klar und end() wird durch die kommentare klar.

    also alles bestens abgesehen davon, dass unsere liste den speicher nicht allein wieder frei gibt (-> "memory leak").
    Wir brauchen also einen Destruktor. Der ist selbsterklärend und im nächsten Stück Code dabei.

    (merkt, dass er sich verzettelt hat, weil zu gründlich erklärt^^)

    ich hab mal noch weitestgehend kommentarlos deine main-funktion angepasst und eine erase-funktion (analog zu deiner delEntry) spendiert, damit dein bsp funktioniert:

    #include <cassert>
    
    template <typename Datatype>
    struct ADT_List
    {
    	struct Entry;
    
    	bool isEmpty()
    	{
    		return begin() == end();
    	}
    
    	void push_back(Datatype to_add)
    	{
    		Entry* last = &start_entry;
    		{
    			for (; last->next != end(); last = last->next)
    				;
    		}
    
    		last->next = new Entry(to_add);
    	}
    
    	void pop_back()
    	{
    		assert(!isEmpty());
    		Entry* one_before_last = &start_entry;
    		{
    			for (; one_before_last->next->next != nullptr; one_before_last = one_before_last->next)
    				;
    		}
    
    		delete one_before_last->next;
    		one_before_last->next = nullptr;
    	}
    
    	Entry* /*next*/ erase(Entry* del_me)
    	{
    		assert(del_me != nullptr);
    
    		Entry* before_del = &start_entry;
    		{
    			for (; before_del->next != del_me; before_del = before_del->next)
    				assert(before_del != nullptr);
    		}
    
    		before_del->next = del_me->next;
    		delete del_me;
    
    		return before_del->next;
    	}
    
    	struct Entry
    	{
    		Datatype content;
    		Entry *next;
    
    		Entry(Datatype value = Datatype())
    		{
    			next = nullptr;
    			content = value;
    		}
    	};
    
    	Entry* begin()
    	{
    		return start_entry.next;
    	}
    
    	Entry* end()
    	{
    		return nullptr;
    	}
    
    	void clear()
    	{
    		while (!isEmpty())
    			pop_back();
    	}
    
    	~ADT_List()
    	{
    		clear();
    	}
    
    private:
    	Entry start_entry;
    };
    
    #include <iostream>
    #include <ctime>
    
    template<class T>
    void print_list( /*const*/ ADT_List<T>& the_list )
    {
    #if 1
    	the_list;
    #else
    	for (auto i(the_list.begin()), e(the_list.end()); i != e; i = i->next)
    		std::cout << i << "[ " << i->content << ", -> " << i->next << " ]\n";
    	std::cout << '\n';
    #endif
    }
    
    int main()
    {
    	int lsize = 50*1000;
    	int step_size = 1000;
    
    	using namespace std;
    
    	ADT_List<int> testlist;
    
    	cout << "Create list..." << endl;
    	clock_t t1 = clock();
    	for (int r = 0; r < lsize; r++)
    		testlist.push_back(r);
    	clock_t t2 = clock();
    	print_list(testlist);
    	int time = ((t2 - t1) * 1000) / CLOCKS_PER_SEC;
    	cout << time << " ms" << endl;
    
    	cout << "Edit list..." << endl;
    	t1 = clock();
    	int step = 0;
    	for (auto i(begin(testlist)), e(end(testlist)); i != e; )
    	{
    		if (++step % step_size == 0)
    			i = testlist.erase(i);
    		else
    			i = i->next;
    	}
    
    	t2 = clock();
    	print_list(testlist);
    	time = ((t2 - t1) * 1000) / CLOCKS_PER_SEC;
    	cout << time << " ms" << endl;
    
    	cout << "Clear list..." << endl;
    	t1 = clock();
    	testlist.clear();
    	t2 = clock();
    	print_list(testlist);
    	time = ((t2 - t1) * 1000) / CLOCKS_PER_SEC;
    	cout << time << " ms" << endl;
    
    	cout << "cu\n";
    	cin.get();
    }
    

    compiler nickt es auch ab und es tut das, was es soll.

    push_back in O(n) ist zwar kacke, aber ansonsten tut es auch das, was man von einer liste erwartet.

    bb

    EDIT: bugfix in main-fkt.


  • Mod

    Da sind aber auch massive Fehler drin, sowohl vom Design her als auch von der technischen Umsetzung. Mach mal ein einfaches:

    ADT_List<int> testlist2 = testlist;
    

    rein, mach irgendwas damit, und siehe, wie das Kartenhaus zusammen bricht.



  • SeppJ schrieb:

    Da sind aber auch massive Fehler drin, sowohl vom Design her als auch von der technischen Umsetzung. Mach mal ein einfaches:

    ADT_List<int> testlist2 = testlist;
    

    rein, mach irgendwas damit, und siehe, wie das Kartenhaus zusammen bricht.

    copyctor sowie op= gabs auch zuvor nicht.
    Soll ich nen
    Entry(const Entry&) = delete; und
    Entry& operator=(const Entry&) = delete;

    reineditieren? 😛

    edit: op= rieneditiert, damit du nicht wieder kritisierst, ich hätte nur die hälfte gemacht.



  • Schau dir einfach mal std::unique_ptr an, dann hast du schon mindestens die Hälfte aller Fehler beseitigt.


  • Mod

    unskilled schrieb:

    copyctor sowie op= gabs auch zuvor nicht.

    Und das war falsch, dass es die nicht gab! Dein Code soll doch zeigen, wie es richtig geht, oder?

    Das entschuldigt aber immer noch nicht das leere Dummy-Element; die vielen Methoden mit linearer Laufzeit wo konstant ginge; quadratische Laufzeiten, wo auch linear ginge; und bestimmt noch viel mehr, denn so genau mag ich gar nicht mehr gucken.



  • Das entschuldigt aber immer noch nicht das leere Dummy-Element; die vielen Methoden mit linearer Laufzeit wo konstant ginge; quadratische Laufzeiten, wo auch linear ginge; und bestimmt noch viel mehr, denn so genau mag ich gar nicht mehr gucken.

    hindert dich doch keiner dran, das selbst zu tun.

    sind alles nur noch kleine ergänzungen; ich hatte aber keine zeit mehr und nicht das gefühl, dass es mit dem kenntnissstand des TOs vereinbar ist.



  • Fängt doch alles schon mit der Designentscheidung an, bei einer einfach verketteten Liste push_back und pop_back anzubieten statt der Funktionen push_front und pop_front, die beide O(1) wären.

    Nächste merkwürdige Design-Entscheidung: die erase-Funktion. Sie nimmt als Parameter und gibt als Returntyp ein Entry*. Entry ist aber ein Implementierungsdetail, warum soll man das außen kennen?

    Und push_back macht eine Kopie durch call by value und dann eine weitere beim Speichern?

    Nenene, das ist auch keine empfehlenswerte Lösung.


  • Mod

    unskilled schrieb:

    Das entschuldigt aber immer noch nicht das leere Dummy-Element; die vielen Methoden mit linearer Laufzeit wo konstant ginge; quadratische Laufzeiten, wo auch linear ginge; und bestimmt noch viel mehr, denn so genau mag ich gar nicht mehr gucken.

    hindert dich doch keiner dran, das selbst zu tun.

    Ja, die Tage mal, wenn ich Zeit habe. Irgendwas Schickes mit unique Pointern, das sich ganz von alleine verwaltet und man programmiert nur die Struktur 😋


  • Mod

    Irgendwie sieht das Ganze immer gleich aus...

    #include <utility>
    
    template <typename T>
    class adt_list {
    	struct node {
    		node* next;
    	};
    	struct data_node {
    		template <typename... U>
    		data_node(node* next, U&&... args) noexcept(noexcept(T{std::forward<U>(args)...}))
    			: base{next}, data(std::forward<U>(args)...)
    		{}
    		node base;
    		T data;
    	};
    	static T& data(node* p) noexcept { return reinterpret_cast<data_node*>(p)->data; }
    
    public:
    	// types
    	class iterator;
    	class const_iterator;
    	friend class iterator;
    	friend class const_iterator;
    	class iterator {
    		friend class adt_list;
    		friend class const_iterator;
    		explicit iterator(node* elem) noexcept : elem(elem) {}
    	public:
    		T& operator*() const noexcept { return data(elem); }
    		T* operator->() const noexcept { return &data(elem); }
    		iterator& operator++() noexcept { elem = elem->next; return *this; }
    		iterator operator++(int) noexcept { auto i = *this; ++*this; return i; }
    		friend bool operator==(iterator lhs, iterator rhs) noexcept { return lhs.elem == rhs.elem; }
    		friend bool operator!=(iterator lhs, iterator rhs) noexcept { return lhs.elem != rhs.elem; }
    	private:
    		node* elem;
    	};
    
    	class const_iterator {
    		friend class adt_list;
    		explicit const_iterator(node* elem) noexcept : elem(elem) {}
    	public:
    		const_iterator(iterator other) noexcept : elem(other.elem) {}
    		const T& operator*() const noexcept { return data(elem); }
    		const T* operator->() const noexcept { return &data(elem); }
    		const_iterator& operator++() noexcept { elem = elem->next; return *this; }
    		const_iterator operator++(int) noexcept { auto i = *this; ++*this; return i; }
    		friend bool operator==(const_iterator lhs, const_iterator rhs) noexcept { return lhs.elem == rhs.elem; }
    		friend bool operator!=(const_iterator lhs, const_iterator rhs) noexcept { return lhs.elem != rhs.elem; }
    	private:
    		node* elem;
    	};
    
    	// construct/copy/destroy
    	adt_list() noexcept : elems{nullptr} {}
    	adt_list(const adt_list& other);
    	adt_list(adt_list&& other) noexcept : elems(other.elems) { other.elems = nullptr; }
    	adt_list& operator=(adt_list rhs) noexcept { swap( rhs ); }
    	~adt_list() noexcept { clear(); }
    
    	void clear() noexcept {
    		while ( !empty() )
    			pop_front();
    	}
    	void swap(adt_list& other) noexcept { std::swap( elems, other.elems ); }
    	friend void swap(adt_list& lhs, adt_list& rhs) noexcept { lhs.swap( rhs ); }
    
    	// iterators
    	iterator begin() noexcept { return iterator{ elems.next }; }
    	const_iterator begin() const noexcept { return const_iterator{ elems.next }; }
    	const_iterator cbegin() const noexcept { return const_iterator{ elems.next }; }
    	iterator before_begin() noexcept { return iterator{ &elems }; }
    	const_iterator before_begin() const noexcept { return const_iterator{ &elems }; }
    	const_iterator cbefore_begin() const noexcept { return const_iterator{ &elems }; }
    	iterator end() noexcept { return iterator{ nullptr }; }
    	const_iterator end() const noexcept { return const_iterator{ nullptr }; }
    	const_iterator cend() const noexcept { return const_iterator{ nullptr }; }
    
    	// capacity
    	bool empty() const noexcept { return elems != nullptr; }
    	std::size_t size() const noexcept {
    		std::size_t res = 0;
    		auto p = elems.next;
    		while ( p ) {
    			++res;
    			p = p->next;
    		}
    		return res;
    	}
    
    	// access
    	T& front() noexcept { return *begin(); }
    	const T& front() const noexcept { return *begin(); }
    
    	// modifiers
    	template <typename... U>
    	iterator insert_after(const_iterator pos, U&&... args) {
    		return iterator{ pos.elem->next = &( new data_node{ pos.elem->next, std::forward<U>( args )... } )->base };
    	}
    	iterator erase_after(const_iterator pos) noexcept {
    		data_node* p = reinterpret_cast<data_node*>(pos.elem->next);
    		pos.elem->next = pos.elem->next->next;
    		delete p;
    		return iterator{ pos.elem };
    	}
    	template <typename... U>
    	void push_front(U&&... args) {
    		insert_after( before_begin(), std::forward<U>( args )... );
    	}
    	void pop_front() noexcept {
    		erase_after( before_begin() );
    	}
    private:
    	node elems;
    };
    
    #include <iostream>
    #include <ctime>
    
    template<class T>
    void print_list( const adt_list<T>& l )
    {
    #if 0
    	for ( auto i = l.begin(), end = l.end(); i != end; ) {
    		auto next = i;
    		std::cout << &*i << "[ " << *i << ", -> " << (++next==end?nullptr:&*next) << " ]\n";
    		i = next;
    	}
        std::cout << '\n';
    #endif
    }
    
    int main()
    {
    	int lsize = 100000000;
    	int step_size = 4;
    
    	using namespace std;
    
    	adt_list<int> testlist;
    
    	{
    		cout << "Create list..." << endl;
    		clock_t t1 = clock();
    
    		auto pos = testlist.before_begin();
    		for (int r = 0; r < lsize; r++) {
    			pos = testlist.insert_after( pos, r );
    		}
    		clock_t t2 = clock();
    		//print_list( testlist );
    		std::cout << "size: " << testlist.size() << '\n';
    		int time = ((t2 - t1) * 1000) / CLOCKS_PER_SEC;
    		cout << time << " ms" << endl;
    	}
    
    	{
    		cout << "Edit list..." << endl;
    		clock_t t1 = clock();
    		int step = 0;
    		auto i = testlist.before_begin(), n = begin( testlist ), e = end( testlist );
    		//std::cout << &*i << "[ " << *i << ", -> " << (++n==e?nullptr:&*n) << " ]\n";
    		for ( ; n != e;  )
    		{
    			if ( ++step % step_size == 0 )
    				n = testlist.erase_after( i );
    			i = n++;
    		}
    		clock_t t2 = clock();
    		print_list( testlist );
    		std::cout << "size: " << testlist.size() << '\n';
    		int time = ((t2 - t1) * 1000) / CLOCKS_PER_SEC;
    		cout << time << " ms" << endl;
    	}
    
    	{
    		cout << "Clear list..." << endl;
    		clock_t t1 = clock();
    		testlist.clear();
    		clock_t t2 = clock();
    		print_list( testlist );
    		std::cout << "size: " << testlist.size() << '\n';
    		int time = ((t2 - t1) * 1000) / CLOCKS_PER_SEC;
    		cout << time << " ms" << endl;
    	}
    
    	cout << "cu\n";
    	cin.get();
    }
    

    SeppJ schrieb:

    Irgendwas Schickes mit unique Pointern, das sich ganz von alleine verwaltet und man programmiert nur die Struktur 😋

    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.



  • 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?
    Ich habe unlängst einen rudimentären Binärbaum basierend auf Unique_ptr implementiert. Ok, der wird nie "groß" werden, aber wenn ich da ein Problem übersehen haben sollte, würde mich das interessieren.

    Was mich schon seit dem ersten Entwurf vom TE stört, ist dieses Dummy Element. Warum nicht ein (unique_ptr) auf das erste Element der Liste?


Log in to reply