DIGITAL
Auf diesem Übungsblatt arbeiten wir drei weitere wichtige Inhalte von Lerneinheit 04 auf, Templates, Speicherverwaltung und Containerklassen.
Wir haben im Tutorium 04 und auf dem Übungsblatt 04 zwei „Orte“ zum Speichern von Daten in C++ kennen gelernt:
new
angesprochen.Das Hauptproblem von raw-Pointern ist die einfache Frage, wer sich um das Löschen der unnötigen Objekte kümmert. In Sprachen wie Python oder Java stellt sich die Frage meistens nicht. Dort kümmert sich ein Mechanismus namens Garbage Collector um das Aufräumen des Speichers.1
Auf diesem Blatt werden wir den Begriff der Speicherverwaltung (aus Vorlesung C07) aus zwei verschiedenen Sichtweisen betrachten.
Und übrigens: Die Strukturen std::tuple
und std::vector
, die auf diesem Blatt (natürlich vereinfacht) nachimplementiert werden, dürfen ab dem nächsten Übungsblatt in jeder Lösung mit verwendet werden, sofern es sich anbietet.
[1] Dabei werden periodisch alle Objekte darauf geprüft, ob es noch einen Zeiger gibt, der darauf zeigt. Alle „freistehenden“ Objekte können demnach gelöscht werden. In C++ gibt es diesen Mechanismus nicht von Haus aus.
.h
) implementiert werden. Dies liegt daran, dass Templates erst übersetzt werden, wenn man sie "instanziiert", also konkrete Werte für die Template-Argumente einsetzt. Ein typischer Nachteil davon ist, dass in großen Projekten mit vielen Templates die Compilezeit und Dateigröße der kompilierten Dateien zunimmt, da jede Datei, die ein Template instanziiert, eine Kopie des kompilierten Template-Codes enhält.
Auf Blatt 3 haben wir gesehen, wie man struct
s zur sinnvollen Gruppierung von Daten einsetzen kann. Braucht man viele solcher Gruppierungen, kann die Anzahl an struct
s schnell dazu führen, dass man die Übersicht verliert. Wir wollen jetzt mithilfe von Templates eine Alternative zu struct
s 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) {
// ...
}
first
und second
initialisiert.==
und !=
.swap
, die ein anderes pair
mit denselben Typparametern akzeptiert und jeweils first
und second
zwischen den Paaren austauscht.pair
eine freistehende Funktion flip
, die innerhalb eines Paares die Werte von first
und second
vertauscht. T
und nicht F
und S
als Templateargument?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. struct
s (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 struct
s (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";
}
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:
vector(size_t initial_size = 0, T initial_value = T())
initial_size
. Alle Werte darin werden mit initial_value
initialisiert.void reserve(size_t new_size)
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
size_t capacity() const
void push_back(const T &val)
void insert(size_t pos, const T &val)
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
operator[]
der Aufrufer der Funktion darum kümmern, dass der Index zulässig ist.void clear()
void shrink_to_fit()
vector
).~vector()
vector(const vector<T>& other)
vector
s.vector<T>& operator=(const vector<T>& other)
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;
}