Institut für Informatik

Michael Wand
Christian Ali Mehmeti-Göpel

Wintersemester 2020/21 • DIGITAL

Aufgabe Vector

Mit std::vector haben Sie bereits auf vergangenen Blättern gearbeitet. std::vector ist ein sehr effektiver Weg, um manuelle Speicherverwaltung mittels new[] and delete[] zu umgehen. Generell sollten Sie in allen folgenden Aufgabenblättern std::vector verwenden, anstatt Speicher für Arrays selbst zu verwalten. Eine vollständige Liste der unterstützten Operationen von std::vector erhalten Sie auf https://en.cppreference.com/w/cpp/container/vector .

In dieser Aufgabe wollen wir std::vector teilweise nachimplementieren, um die internen Mechanismen zu verstehen. Es geht hier also explizit darum, den Speicher manuell zu verwalten. Denken Sie bei manueller Speicherverwaltung immer an die rule of three!

Ein std::vector<T> speichert intern einen Pointer auf ein C-Array vom Typ T. Der std::vector ist dabei der "Owner" des C-Arrays, das heißt, dass der std::vector das Array selbst anlegt und am Ende seiner Lebenszeit das C-Array eigenständig löscht. Sie können C-Arrays eines Typs T mittels new T[n] dynamisch allokieren, dabei ist n die Größe des Arrays. Arrays lassen sich nicht nachträglich vergrößern oder verkleinern. Falls also eine Operation ein größeres C-Array benötigen würde (z.B. push_back), erzeugen wir ein neues C-Array mit doppelter Länge (oder Länge 8, falls das Array zu Beginn leer war) und kopieren alle Werte vom alten C-Array in das neue C-Array um. Intern müssen wir uns also nicht nur merken, wie groß das C-Array ist ("Kapazität"), sondern auch, wie viele Elemente wir darin gespeichert haben ("Größe"). Achten Sie darauf, das alte C-Array zu löschen, falls Sie es gegen ein neues ersetzen.

Weil wir mit Templates arbeiten, muss vector vollständig im Header implementiert werden.

Implementieren Sie folgende Funktionen:

• Einen Konstruktor vector(size_t initial_size = 0, T initial_value = T())
  Erstellt intern ein Array der Größe initial_size. Alle Werte darin werden mit initial_value initialisiert.
• void reserve(size_t new_size)
  Stellt sicher, dass das Array mindestens Größe new_size bereitstellt. Diese Operation macht vor allem dann Sinn, wenn wir vorher wissen, wie viele Elemente wir später einfügen wollen.
• size_t size() const
  Ermittelt die Anzahl der gespeicherten Elemente (nicht des internen C-Arrays).
• size_t capacity() const
  Ermittelt die Kapazität des internen C-Arrays.
• void push_back(const T &val)
  Fügt ein neues Element hinter den bereits gespeicherten Elementen ein.
• void insert(size_t pos, const T &val)
  Setzt ein neues Element an der Position pos ein. Alle nachfolgenden Elemente werden ohne Datenverlust um eine Position verschoben.
• T& operator[](size_t pos) und const T& operator[](size_t pos) const
  Gibt das Element an der angegebenen Position zurück. Wie auch auf einem vergangenen Blatt gesagt, muss sich bei operator[] der Aufrufer der Funktion darum kümmern, dass der Index zulässig ist.
• void clear()
  Löscht den Inhalt des Arrays.
• void shrink_to_fit()
  Garantiert, dass das interne Array nach dem Aufruf die kleinste mögliche Größe hat (also die Anzahl der Elemente im vector).
• Der Destruktor ~vector()
  Gibt das interne C-Array frei.
• Der Copy-Konstruktor vector(const vector<T>& other)
  Erstellt eine Kopie eines anderen vectors.
• Der Copy-Assignment-Operator vector<T>& operator=(const vector<T>& other)
  Überschreibt den Inhalt von diesem vector mit dem von other.

Natürlich dürfen Sie auch Hilfsfunktionen nach eigenem Ermessen hinzufügen, um die Implementierung übersichtlicher zu halten.

#include <iostream>

int main(){
    vector<int32_t> myvec;

    for(int32_t i = 0; i < 200; i++)
        myvec.push_back(i);

    // 200
    std::cout << myvec.size() << std::endl;
    // 256
    std::cout << myvec.capacity() << std::endl;

    myvec.shrink_to_fit();

    // 200
    std::cout << myvec.size() << std::endl;
    // 200
    std::cout << myvec.capacity() << std::endl;

    for(size_t i = 0; i < myvec.size(); ++i)
        std::cout << myvec[i] << "   ";
    std::cout << std::endl;
}