Institut für Informatik

Michael Wand
David Hartmann

Sommersemester 2020 • DIGITAL

Aufgabe 2-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 First, typename Second>
struct pair {
    First first;
    Second second;

    void swap(pair<First, Second> &other);
};

template <typename First, typename Second>
bool operator ==(const pair<First, Second> &lhs, const pair<First, Second> &rhs);

template <typename First, typename Second>
bool operator !=(const pair<First, Second> &lhs, const pair<First, Second> &rhs);

template <typename T>
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 First und Second 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 <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 << "\n";
   }
   

Aufgabe Shared Pointer

C++ liefert von daher von Haus aus die Klasse shared_ptr mit, die genau die oben genannten Anforderungen erfüllt:

1. Der Konstruktor shared_ptr(T* ptr) und der Destruktor virtual ~shared_ptr()
   übernehmen die Verantwortung dafür, das Objekt auf das ptr zeigt zu löschen, sobald es nicht mehr benötigt wird. Mit anderen Worten ruft der Destruktor von shared_ptr „delete ptr“ auf.
   Achtung: Dieser Konstruktor darf nur ein einziges Mal für ein bestehendes Objekt aufgerufen werden.

Das bedeutet, wir nutzen den Mechanismus des Stack (automatisches Aufrufen des Destruktors), um ein Objekt auf dem Heap zu löschen. Viel können wir jedoch noch nicht damit tun, daher definieren wir zusätzlich die Memberfunktionen:

1. T* operator->() und T& operator *()
   So ermöglichen wir das Arbeiten mit shared_ptr wie auch mit einem Pointer.
   (Also das Zugreifen auf die Member bzw. das Dereferenzieren.)
2. Konstruktor shared_ptr(const shared_ptr &other)
   Soll ermöglichen, dass wir mehrere Zeiger auf exakt das gleiche Objekt erstellen dürfen.
   (Beispielsweise zum Übergeben an eine andere Funktion).

Die Schwierigkeit besteht nun darin sicherzustellen, dass der Destruktor des eigentlichen Objektes nicht mehrfach aufgerufen wird. Hierzu gibt es zwei Möglichkeiten (welche Möglichkeit implementiert wird ist an dieser Stelle egal):

1. (etwas einfacher, jedoch nicht wie in offiziellen Implementierungen) Wir speichern zusätzlich zum eigentlichen Zeiger auf ein Objekt auch einen Zeiger auf einen Zähler new uint64_t[1], der somit auf dem Heap liegt. Beim Erstellen einer Kopie des shared_ptr kopieren wir nicht nur die beiden Pointer (nicht die Objekte, auf die sie zeigen), sondern inkrementieren auch den Zähler auf dem Heap. Wir müssen jetzt einzig darauf achten, dass wir im Destruktor genau dann delete ptr aufrufen, wenn der Zähler \(0\) ist.
2. (etwas realistischer) Statt das Objekt direkt zu erstellen, speichern wir ein Struct, dass das Objekt und einen Zähler direkt zusammen speichert. Was komplizierter aussieht hat den Vorteil, dass Zähler- und Objekt-Speicher physikalisch direkt nebeneinander im liegen und somit eher schneller nacheinaner zugegriffen werden können.

Aufgabe

1. Implementieren Sie die oben definierte generische Klasse shared_ptr<T>.
   T ist hierbei ein beliebiges, aber festes Struct.
2. Testen Sie ihren Code, indem Sie als erstes
   1. einen shared_ptr erstellen und initialisiern, dann
   2. das Objekt mithilfe des shared_ptr in eine Funktion übergeben, dann
   3. in der Funktion ein Attribut des Objektes verändern, und zuletzt
   4. das Objekt wieder zurückgeben und den geänderten Wert ausgeben.
3. Der folgende Code stürzt unter GCC 9.3.0 ab.
   Erklären Sie, wo das Problem liegt.

   #include "shared_ptr.h"
   
   #include <iostream>
   
   int main() {
       uint32_t *p = new uint32_t{5};
       shared_ptr<uint32_t> my_ptr(p);
       shared_ptr<uint32_t> my_ptr2(p);
   
       std::cout << *my_ptr << "\n";
   }
   

4. Bonus: Testen Sie auch die offizielle C++-Implementierung.

Aufgabe Vector

C-Arrays (solche, die beispelsweise per new int[123]; initialisiert werden) haben so ihre Probleme (sie kennen etwa ihre eigene Größe nicht direkt, die Größe wird zur Compilezeit festgelegt, ...). Ein Array, das man nachträglich vergrößern oder verkleinern kann, nennt man "dynamisches Array" (vergleichbar mit Listen in Python). Die Standardbibliothek in C++ bietet glücklicherweise eine Implementierung von dynamischen Arrays names vector<T>. T ist der Typ der gespeicherten Elemente und wird durch ein Template-Typargument festgelegt. Eine komplette Liste an Funktionen erhalten Sie auf https://en.cppreference.com/w/cpp/container/vector.

Intern wird hierbei ein C-Array als Speicher verwendet. 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 10, 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").

Wir wollen jetzt std::vector teilweise nachimplementieren. Schreiben Sie dazu folgende Funktionen. Achten Sie darauf, das alte C-Array vom Speicher zu löschen, falls Sie es gegen ein neues ersetzen.

• Einen Konstruktor vector(T initial_value, size_t initial_size = 0)
  Erstellt 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, falls wir vor einer Reihe Operation wissen, wie groß das Array danach sein wird.
• size_t size() const
  Ermittelt die Anzahl der Elemente der gespeicherten Liste (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 ans Ende des Arrays an.
• 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 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 User der Klasse 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 virtual ~vector()
  Gibt das interne C-Array frei.
• Der Konstruktor vector(const vector<T>& other)
  Erstellt eine Kopie eines anderen Arrays.
• vector<T>& operator=(const vector<T>& other)
  Überschreibt den Inhalt von diesem vector mit dem von other.

Hinweis: Viele der Methoden sollten einfache Ein-Zeiler sein. Es ist hier auch nicht nötig die „Machbarkeit“ der Funktionen (etwa a[100000]) abzufangen.

#include <iostream>

int main(){
    vector<int> myvec(0, 0);

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

    // 200
    std::cout << myvec.size() << std::endl;
    // 320
    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(int i = 0; i < myvec.size(); i++)
        std::cout << myvec[i] << "   ";
    std::cout << std::endl;
}