Weiterer Ausbau der Hash-Tabelle

Content

Dynamische Datenstrukturen mit intelligenten Zeigern
Antworten und Beispiell�sung
Iteratoren mit Zeigern in dynamische Datenstrukturen
Antworten und Beispiell�sung
Weiterer Ausbau der Hash-Tabelle
- Aufgabe
- Vorlage
Beispiell�sung
Anwendung: Topologisches Sortieren
Beispiell�sung
Verbesserte Beispiell�sung

Es ist naheliegend, noch einige Anpassungen und Ergänzungen vorzunehmen:

Die Methode insert sollte wie die Originale der STL ein std::pair bestehend aus einem Iterator und einem bool-Wert zurückgeben, wobei der bool-Wert angibt, ob eingefügt wurde und der Iterator entweder auf das bereits vorhandene oder eben neu eingefügte Objekt verweist.
Die entsprechenden Klassen der STL bieten auch eine erase-Methode an, bei der ein Iterator angegeben wird und dann das entsprechende Element aus der Datenstruktur gelöscht wird.

Wie kann das mit konstantem Aufwand umgesetzt werden? Ist es dazu notwendig, die eigentliche Datenstruktur dazu zu verändern oder reicht es aus, dem Iterator-Objekt mehr Informationen hierzu zu geben.

Wenn erase (also eine Methode von Hash) auf Interna der Iterator-Klasse zugreifen möchte, ist eine friend Hash-Deklaration innerhalb der Iterator-Klasse notwendig.
Die Container-Klassen der STL bieten eine Methode size an, mit der die Zahl der Elemente zurückgegeben wird. Auch dies kann mit konstantem Aufwand erreicht werden.
Bei der Verwendung unserer Iteratoren-Klasse ist zwar (*it).member zulässig, aber nicht it->member. Letzteres wird nur möglich, wenn ein operator-> deklariert wird, der einen Zeiger auf das Objekt zurückgibt.

Aufgabe

Setzen Sie die obigen Erweiterungen sukzessive um und testen Sie diese.

Vorlage

#ifndef HASH_HPP
#define HASH_HPP

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

template<typename Key, typename Value>
class Hash {
   public:
      using Object = std::pair<const Key, Value>;
   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::shared_ptr<NodePtr[]> bucket;
      std::hash<Key> hash;
   public:

      class Iterator {
	 public:
	    Iterator() : dim(0), index(0) {
	    }
	    Iterator(Hash& hash) :
		  dim(hash.dim), bucket(hash.bucket), index(0) {
	       advance();
	    }
	    Iterator(Hash& hash, std::size_t index, NodePtr node) :
		  dim(hash.dim), bucket(hash.bucket), index(index), node(node) {
	       assert(node && index < dim);
	    }
	    Object& operator*() {
	       return node.lock()->object;
	    }
	    Iterator& operator++() {
	       advance();
	       return *this;
	    }
	    bool operator==(const Iterator& other) {
	       bool end1 = index >= dim;
	       bool end2 = other.index >= other.dim;
	       if (end1 && end2) return true;
	       if (end1 || end2) return false;
	       return
		  bucket.lock() == other.bucket.lock() &&
		  index == other.index &&
		  node.lock() == other.node.lock();
	    }
	    bool operator!=(const Iterator& other) {
	       return !(*this == other);
	    }
	 private:
	    void advance() {
	       /* move to next object */
	       auto b = bucket.lock();
	       if (b) {
		  auto n = node.lock();
		  if (n) {
		     node = n->next;
		     n = node.lock();
		     if (!n) ++index;
		  }
		  if (!n) {
		     while (index < dim && !b[index]) {
			++index;
		     }
		     if (index < dim) {
			node = b[index];
		     }
		  }
	       } else {
		  node = NodePtr(); index = dim;
	       }
	    }
	    std::size_t dim;
	    std::weak_ptr<NodePtr[]> bucket;
	    std::size_t index; /* current location in bucket table */
	    std::weak_ptr<Node> node; /* current object at bucket[index] */
      };

      Hash(std::size_t dim) :
	 // dim(dim), bucket(std::make_shared<NodePtr[]>(dim)) {
	 dim(dim), bucket(new 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;
	    }
	 }
      }
      Iterator begin() {
	 return Iterator(*this);
      }
      Iterator end() {
	 return Iterator();
      }
};

#endif