Iteratoren mit Zeigern in dynamische Datenstrukturen

Wenn wir mit Iteratoren und dynamischen Datenstrukturen operieren, müssen wir festlegen, was mit Iteratoren geschieht, wenn die referenzierte Datenstruktur abgebaut wird. Theoretisch wäre es denkbar, die Datenstruktur dann weiterzubestehen lassen. Dies würde aber eine weitere Indirektion kosten, da dann die gesamte Datenstruktur hinter einen weiteren std::shared_ptr versteckt werden müsste, auf den der Iterator zeigt. Normalerweise wird aber (wie in der STL) davon ausgegangen, dass den Iteratoren die dynamischen Datenstrukturen nicht gehören.

Fragen und Aufgabe

• Was muss die Datenstruktur eines Iterators für eine Hash-Tabelle umfassen, damit wir die Hash-Tabelle vorwärts durchlaufen können?

• Wie verweisen wir am besten auf den gesamten Inhalt der Hash-Tabelle? Hat das Konsequenzen für die Datentypen der Hash-Tabelle selbst?

• Wie können Sie den Ende-Iterator repräsentieren?

• Wie können Sie sicherstellen, dass Iteratoren (wie bei Forward-Iteratoren üblich) Zuweisungen unterstützen?

Aufgabe

• Implementieren Sie einen Forward-Iterator für die Hash-Tabelle mit den zugehörigen Operationen begin und end.

• Für den Forward-Iterator benötigen Sie folgende Methoden:

  • Einen default constructor, der einen am Ende stehenden Iterator liefert,

  • einen Konstruktor, der den Iterator an den Anfang einer Hash-Tabelle setzt,

  • einen Operator für die Dereferenzierung,

  • einen Operator für das Inkrement (auf das Post-Inkrement können Sie verzichten) und

  • den Operator != (ggf. gleich in Kombination mit ==).

• Ersetzen Sie im Testprogramm den Aufruf der for_each-Methode durch eine for-Schleife, die durch alle Elemente durchiteriert.

Vorlage

#ifndef HASH_HPP
#define HASH_HPP

#include <cstdlib>
#include <functional>
#include <memory>
#include <utility>

template<typename Key, typename Value>
class Hash {
   public:
      using Object = std::pair<const Key, Value>;
      Hash(std::size_t dim) :
	 dim(dim), bucket(std::make_unique<NodePtr[]>(dim)) {
      }
      bool insert(Object object) {
	 auto index = hash(object.first) % dim;
	 auto ptr = bucket[index];
	 while (ptr && ptr->object.first != object.first) {
	    ptr = ptr->next;
	 }
	 if (ptr) return false;
	 bucket[index] = std::make_shared<Node>(std::move(object),
	    bucket[index]);
	 return true;
      }
      template<typename F>
      void for_each(F&& f) {
	 for (std::size_t index = 0; index < dim; ++index) {
	    auto ptr = bucket[index];
	    while (ptr) {
	       f(ptr->object);
	       ptr = ptr->next;
	    }
	 }
      }
   private:
      struct Node;
      using NodePtr = std::shared_ptr<Node>;
      struct Node {
	 Node(Object object) : object(std::move(object)) {
	 }
	 Node(Object object, NodePtr next) :
	    object(std::move(object)), next(next) {
	 }
	 Object object;
	 NodePtr next;
      };
      const std::size_t dim;
      std::unique_ptr<NodePtr[]> bucket;
      std::hash<Key> hash;
};

#endif

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

View document source

© Andreas F. Borchert