dynamisch wachsendes Array selbst bauen



  • Hallo zusammen,

    ich habe zu Übungszwecken versucht Teile der Vector-Klasse aus C++ nachzubauen. Löschen und einiges weiter fehlt, mir gings aber hauptsächlich darum, ein internes Array zu bauen, das bei Kapazitätsüberschreitung automatisch mitwächst und das eine Möglichkeit hat minimiert zu werden.
    Würde mal jemand drüberschauen ob ich auch niergends ein memory leak gebastelt habe, das Umkopieren beim Vergrößern oder Verkleinern des internen Vectors erscheinen mir irgendwie recht kompliziert und nicht effizient.
    Und wenn man Speicher auf dem Heap mittels delete wieder freigibt, kann man dies nur ganz oder garnicht machen, aber es gibt keine Möglichkeit von einem Array auf dem Heap nur einen Anteil an nicht benötigen Elementen zu löschen und den vom Zeiger allokierten Speicher zu reduzieren statt gänzlich freizugeben? Vllt ist die Frage ja doof, aber das Thema wurde nur relativ kurz erklärt. Es gibt keine Möglichkeit wenn man Speicher für z.B. 16 Intwerte als Array allokiert hat, davon nur die Hälfte freizugeben statt alles?

    Und wenn ich unzulässige Indexzugriffe abfangen möchte, wie mache ich das am Besten, mit Exceptions?

    #include <iostream>
    
    using namespace std;
    
    template<typename T>
    struct Vector
    {
        size_t capacity;        // Anzahl Speicherplaetze
        size_t size;            // Anzahl aktuell gespeicherter Elemente  size [0,..., capacity-1]
        T* array = nullptr;
    
        /* Constructor */
        Vector(size_t initial_size = 0, T initial_value = 0): capacity(initial_size), size(initial_size)
        {
            array = new T[capacity];
            for(unsigned int i = 0; i < size; i++)
            {
                array[i] = initial_value;
            }
        }
    
        /* Copy Constructor */
        Vector(Vector const &otherVector): capacity(otherVector.capacity), size(otherVector.size)
        {
            array = new T[otherVector.capacity];
    
            for(unsigned int i = 0; i < otherVector.size; i++)
            {
                array[i] = otherVector.array[i];
            }
        }
    
    
        /* Move Constructor */
        Vector(Vector &&otherVector): capacity(otherVector.capacity) , size(otherVector.size), array(otherVector.array)
        {
            otherVector.array = nullptr;
        }
    
    
        /* Assignment operator */
        Vector& operator=(Vector const &otherVector)
        {
            if(&otherVector == this)
                return *this;
            else
            {
                if(otherVector.capacity != this->capacity)
                {
                    delete [] array;
                    capacity = otherVector.capacity;
                    array = new T[capacity];
                }
    
                size = otherVector.size;
    
                for(unsigned int i = 0; i < otherVector.size; i++)
                {
                    array[i] = otherVector.array[i];
                }
                return *this;
            }
    
        }
    
        /* Move assignment operator */
        Vector& operator=(Vector &&otherVector)
        {
            if(&otherVector == this)
                return *this;
            delete [] array;
            array = otherVector.array;
            otherVector.array = nullptr;
            return *this;
        }
    
        /* Destructor */
        ~Vector()
        {
            delete [] array;
        }
    
        T& operator[](size_t index) const
        {    
            return array[index];
        }
    
        size_t getSize() const
        {
            return size;
        }
    
        size_t getCapacity() const
        {
            return capacity;
        }
    
        void setValue(unsigned int index, T value)
        {
            array[index] = value;
        }
    
        /* Fuegt Element value ans Ende des Arrays an */
        void push_back(T value)
        {
            if(size < capacity)
            {
                array[size] = value;
                size++;
            }
            else    // size == capacity -> Array voll -> capacity verdoppeln
            {
                reserve(2 * size);
                array[size] = value;
                size++;
            }
        }
    
        void insert(size_t index, T value)
        {
            if(size == capacity)
            {
                T* newarray = new T[capacity + 1];
    
                for(size_t i = 0; i < index; i++)
                {
                    newarray[i] = array[i];
                }
    
                newarray[index] = value;
    
                for(size_t i = index; i < capacity ; i++)
                {
                    newarray[i+1] = array[i];
                }
                size++;
                capacity++;
                delete [] array;
                array = newarray;
                newarray = nullptr;
    
            }else{  //size < capacity
    
                for (size_t e = size; e > index; e--) {
                    array[e] = array[e-1];
                }
                array[index] = value;
                size++;
            }
        }
    
        /* Vergroessere Speicherplatz */
        void reserve(size_t newsize)
        {
            T* new_array = new T[newsize];
    
            for(unsigned int i = 0; i < size; i++)
            {
                new_array[i] = array[i];
            }
    
            delete [] array;
            capacity = newsize;
            array = new_array;
            new_array = nullptr;
        }
    
        /* Entferne ueberzaehlige leere Speicherplaetze */
        void shrink_to_fit()
        {
            if(size < capacity)
            {
                T* new_array = new T[size];
                for(unsigned int i = 0; i < size; i++)
                {
                    new_array[i] = array[i];
                }
    
                delete [] array;
                capacity = size;
                array = new_array;
                new_array = nullptr;
            }
        }
    
    };
    

  • Mod

    Ohne es mit valgrind (was ein Tool zum Finden von Speicherfehlern ist) oder ähnlichem durchlaufen zu lassen: Beim ersten Durchlesen sieht das erst einmal halbwegs korrekt aus, stellenweise aber etwas ungeschickt.

    Was ganz allgemein auffällt: Du wiederholst dich oft. Du solltest deine eigenen Funktionen auch selber nutzen! Und wenn du immer noch Codedoppelungen hast, dann ist das ein Indiz, dass da noch eine Funktion fehlt.

    Im Speziellen noch Tipps:

    • Bei manchen deiner Funktionen hast du Speicherlöcher, falls in der Funktion Exceptions geworfen werden (z.B. kann eine Zuweisung eines komplexen Datentyps potentiell etwas werfen). Dann gibst du deinen Speicher nämlich nicht mehr frei, weil die Exception an deinem delete vorbei fliegt. Tipp: Es ist quasi immer falsch, in ein und derselben Funktion das delete zu einem vorherigen new zu haben. Eine Ressource gehört immer an einen Handler gebunden, der diese auch wieder automatisch frei gibt. Zum Glück hast du hier selber solch einen Handler programmiert, daher zur Wiederholung: Nutze deine eigenen Funktionen! Anstatt von Hand die Attribute eines Container zu definieren und sie dann später deinem Container zuzuweisen, erstell eine neue Instanz deines Containers und tausch am Ende den neuen Container gegen den alten.
    • Noch etwas spezieller: Guck dir mal den Begriff "Copy&Swap Idiom" an! Das ist das, was ich im vorherigen Punkt gesagt habe, speziell auf den Zuweisungsoperator angewandt. Das gleiche Muster kannst du dann aber auch anderswo anwenden, wenn du das Prinzip verstanden hast.

    Das sind erst einmal drei sehr wichtige Punkte, wenn du das verinnerlicht hast, kann man weiter gucken.

    Zu deinen Fragen:

    • Indexüberschreitungen: Ignorieren oder per Exception. Im Zweifelsfall sollte man bei Designüberlegungen die Standardbibliothek zum Vorbild nehmen, die das genauso macht.
    • Teilweise Speicherfreigaben: Gibt es nicht, weil das eine recht seltene Anforderung ist und komische Auswirkungen auf die unterliegende Speicherverwaltung hätte (die sich wahrscheinlich gar nicht über die steigende Fragmentierung freut). Wenn jemand doch mal die Notwendigkeit eines wild wachsenden und schrumpfenden Containers hat, würde er kein dynamisches Array dafür nehmen, sondern eher so etwas wie eine deque, die intern dafür optimiert ist (auch wenn sie extern fast das gleiche Interface hat).


  • Danke für die Infos ich werde mal versuchen es weiter zu optimieren und Code zu ersetzen/automatisieren und suche mal nach dem Begriff "Copy&Swap Idiom".



  • Genau, und der weitere Punkt, auf den @SeppJ hingewiesen hat, ist der hier: https://en.wikipedia.org/wiki/Exception_safety (Wikipedia ist vielleicht nicht unbedingt die beste Quelle, aber sollte nebst dem dort verlinkten Stackoverflow-Artikel erstmal reichen)



  • @Tamoko
    Meine Empfehlung: Kapsel deine Resourcen erstmal auf unterster Ebene. Du machst da mit dynamisch angeforderten Arrays rum, also kapsel diese erstmal als solche. Ohne den ganzen "dynamisch wachsen" oder "initial value" Schnickschnack.

    So einfach wie möglich und so mächtig wie nötig. (D.h. du wirst vermutlich einen korrekten Konstruktor und Destruktor brauchen, vermutlich noch eine Swap Funktion und evtl. noch einen Move-Konstruktor und Move-Assignment. Aber nicht mehr.)

    Und mit Hilfe dieser Hilfsklasse kannst du dann deinen Vector implementieren.
    Dadurch wird der Code nicht nur übersichtlicher, sondern an vielen Stellen auch automatisch Thread-Safe.
    z.B. hast du im Konstruktor ein Problem wo du die array[i] = initial_value; Zuweisung machst. Je nach T kann dabei gerne eine Exception fliegen. Und wenn das passiert, dann wird das Array nicht wieder freigegeben. (Falls du dich fragst warum: Wenn ein Konstruktor durch werfen einer Exception verlassen wird, dann gilt das Objekt nicht als vollständig konstruiert, und wird daher nicht zerstört! Vollständig konstruierte Unterobjekte wie z.B. Member oder Basisklassen werden allerdings zerstört.)

    Wenn dein Array aber von einer Hilfsklasse verwaltet wird die im Konstruktor nichts tut ausser es zu erzeugen und die es im Destruktor wieder zerstört, dann kannst die nicht in dieser Art leaken. Diese Hilfsklasse verwendest du dann als Member in Vector. Und da sie dann ein Member ist, und vollständig konstruierte Member zerstört werden wenn im Konstruktor von Vector eine Exception fliegt, wird das Array dann trotzdem korrekt freigegeben.


Log in to reply