Dynamische Datenstrukturen mit intelligenten Zeigern
Content |
Im Normalfall gibt es keinen Bedarf für ungeschützte Zeiger. Stattdessen lohnt sich der konsequente Einsatz entsprechender RAII-Klassen.
Relevant sind hier zunächst die folgenden Typen und Funktionen zum Anlegen eines Objekts mit einem entsprechenden Zeiger darauf:
|
std::unique_ptr<T> |
std::make_unique<T>(...) mit Parametern für den Konstruktor |
ab C++14 |
|
std::unique_ptr<T[]> |
std::make_unique<T[]>(size) mit der Dimensionierung des Arrays |
ab C++14 |
|
std::shared_ptr<T> |
std::make_shared<T>(...) mit Parametern für den Konstruktor |
ab C++11 |
|
std::shared_ptr<T[]> |
noch ohne zugehörige Unterstützung von std::make_shared<T[]> |
ab C++17 |
|
std::shared_ptr<T[]> |
std::make_shared<T[]>(size) mit der Dimensionierung des Arrays |
ab C++20 |
Um diese Typen und Funktionen etwas näher kennenzulernen, lohnt es sich, auch klassische Datenstrukturen vereinfacht nachzuimplementieren. Im Rahmen dieser Sitzung beschäftigen wir uns hier mit (der Einfachheit halber) Hash-Tabellen mit einer festdimensionierten Bucket-Table:
-
Beim Konstruieren der Hash-Tabelle legen wir uns fest, wie groß die Bucket-Table sein wird. Dies wird danach nicht mehr verändert. (Wir haben also kein dynamisches Hash-Verfahren.)
-
Die Klasse Hash hat zwei Template-Typparameter Key und Value, die den Schlüssel- und den Wertetyp angeben. Diese können mit Hilfe von std::pair zu einem Objekt vereinigt werden. Bei std::pair sind die beiden Komponenten dann über first und second erreichbar.
-
Für Key müssen wir in der Lage sein, einen Hash-Wert zu ermitteln. Dies geht über die Template-Klasse std::hash aus <functional>. Wenn wir den Hash-Wert eines key des Typs Key ermitteln wollen, geht dies so:
std::hash<Key> hash; std::size_t hash_value = hash(key);Der Hash-Wert ist dann natürlich noch mit Hilfe des %-Operators in einen Index der Bucket-Table abzubilden.
-
Ein Knoten in der Hash-Tabelle besteht aus einem Objekt und einem next-Zeiger auf den nächsten Knoten mit einem Objekt, das den gleichen Hash-Wert hat.
-
Die Bucket-Table ist dann ein Array von Zeigern auf Knoten.
Fragen und Aufgabe
-
Wo können Sie in der Datenstruktur für die Hash-Tabelle std::unique_ptr einsetzen, wo ist std::shared_ptr notwendig und warum?
-
Wenn Sie sich das überlegt haben, denken Sie nach, ob Ihre Hash-Tabelle kopierkonstruierbar ist.
-
Wie genau deklarieren Sie den Datentyp für ein Objekt, das mit Hilfe von std::pair ein Schlüssel/Werte-Paar repräsentiert? Denken Sie genau darüber nach, was bei einem Objekt in einer Hash-Tabelle änderbar sein darf und was nicht.
-
Implementieren Sie eine Template-Klasse Hash in der Header-Datei Hash.hpp:
-
Der Konstruktor verlangt die Dimensionierung der Bucket-Table. Einen default constructor gibt es nicht.
-
Die Methode insert sollte ein Objekt (d.h. ein std::pair) entgegennehmen. Falls der Schlüssel bereits in der Hash-Tabelle existiert, ist false zurückzuliefern. Ansonsten ist ein Knoten mit dem Objekt anzulegen und in die Tabelle einzufügen. Im Erfolgsfall ist true zurückzugeben.
-
Zu Beginn verzichten wir noch auf Iteratoren. Stattdessen soll eine void-Methode for_each angeboten werden, die ein Funktionsobjekt für jedes Objekt in der Hash-Tabelle aufruft.
-
-
Verwenden Sie das Testprogramm aus der Vorlage. Überprüfen Sie mit valgrind, ob wirklich alles ordnungsgemäß läuft.
Vorlage
#include <iostream> #include <string> #include "Hash.hpp" int main() { Hash<std::string, unsigned int> hash(32); std::string town; unsigned int population; while (std::cin >> town && std::cin >> population) { if (!hash.insert(std::make_pair(town, population))) { std::cerr << "insertion of " << town << " failed." << std::endl; } } hash.for_each([](auto& object) { std::cout << object.first << " " << object.second << std::endl; }); }
Freiburg 227590 Heidelberg 159914 Karlsruhe 309999 Konstanz 83789 Mannheim 304781 Stuttgart 628032 Tübingen 88347 Ulm 123953