Institut für Informatik

Michael Wand
Christian Ali Mehmeti-Göpel

Wintersemester 2020/21 • DIGITAL

Aufgabe Tupel

Auf Blatt 3 haben wir gesehen, wie man structs zur sinnvollen Gruppierung von Daten einsetzen kann. Braucht man viele solcher Gruppierungen, kann die Anzahl an structs schnell dazu führen, dass man die Übersicht verliert. Wir wollen jetzt mithilfe von Templates eine Alternative zu structs implementieren und deren Tradeoffs diskutieren. Als Basis verwenden wir folgende Deklaration:

template <typename F, typename S>
struct pair {
    F first;
    S second;

    void swap(pair<F, S>& other) {
        // ...
    }
};

template <typename F, typename S> inline
bool operator ==(const pair<F, S>& lhs, const pair<F, S>& rhs) {
    // ...
}

template <typename F, typename S> inline
bool operator !=(const pair<F, S>& lhs, const pair<F, S>& rhs) {
    // ...
}

template <typename T> inline
void flip(pair<T, T> &p) {
    // ...
}

1. Ergänzen Sie einen passenden Konstruktor, der zwei Argumente nimmt und damit first und second initialisiert.
2. Implementieren Sie die Vergleichsoperatoren == und !=.
3. Implementieren Sie die oben angedeutete Funktion swap, die ein anderes pair mit denselben Typparametern akzeptiert und jeweils first und second zwischen den Paaren austauscht.
4. Implementieren Sie außerhalb von pair eine freistehende Funktion flip, die innerhalb eines Paares die Werte von first und second vertauscht.
   Warum haben wir nur T und nicht F und S als Templateargument?
5. Betrachten Sie den untenstehenden Codeauszug. Durch unglückliche Variablenbenennung und exzessize Benutzung von pair ist dem Programmierer des Codes der Fehler unterlaufen, dass ein 2D-Punkt an eine Funktion übergeben wird, die eigentlich einen Bruch kürzen soll. Der Compiler kann diesen Fehler nicht erkennen, da für ihn beide Paare dieselbe Bedeutung haben.
   Schreiben Sie den Codeauszug unter Verwendung von zwei unterschiedlichen structs (eins für Punkte, eins für Brüche) so um, dass dieser Fehler zur Compilezeit gefunden wird. Überlegen Sie sich gleichzeitig sinnvolle Namen für die Membervariablen Ihrer structs (nicht first und second!)
   
   

   #include <cstdint>
   #include <numeric>
   
   pair<int64_t, int64_t> project_point_onto_second_axis(const pair<int64_t, int64_t> &p) {
       return pair<int64_t, int64_t>(p.first, 0);
   }
   
   pair<int64_t, int64_t> cancel_fraction(const pair<int64_t, int64_t> &p) {
       // find greatest common divisor (c++17 and later)
       int64_t gcd = std::gcd(p.first, p.second);
       return pair<int64_t, int64_t>(p.first / gcd, p.second / gcd);
   }
   
   int main() {
       // this is a fraction
       pair<int64_t, int64_t> a(10, 4);
       // this is a 2D point on an integer grid
       pair<int64_t, int64_t> p(-2, 3);
   
       pair<int64_t, int64_t> b = project_point_onto_second_axis(p);
       pair<int64_t, int64_t> c = cancel_fraction(b);
   
       std::cout << c.first << " " << c.second << "\n";
   }
   

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;
}