====================================================
Dynamische Datenstrukturen mit intelligenten Zeigern    [TOC]
====================================================

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:

   ---- CODE (type=cpp) -------------------------------------------------------
   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
=======

:import: session08/step01/testit.cpp [fold]
:import: session08/step01/cities [fold]

:navigate: up   -> doc:index
           next -> doc:session08/page02