Antworten und Beispiellösung
Content |
Zu den Fragen
-
Für die Knoten benötigen wir std::shared_ptr. Sonst können wir nicht ohne weiteres mit einem Zeiger all die verketteten Knoten zu einem Hash-Wert durchlaufen. Aber auf die Bucket-Table können wir mit einem Array-basierten std::unique_ptr verweisen.
-
Wegen dem std::unique_ptr ist die Hash-Tabelle nicht mehr kopierkonstruierbar, wohl aber move constructible.
-
Bei einem Objekt ist darauf zu achten, dass der Schlüssel unveränderlich ist, da sich natürlich nicht der Hash-Wert eines Objekts in der Hash-Tabelle verändern darf:
using Object = std::pair<const Key, Value>;
Beispiellösung
#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
theon$ g++ -Wall -o testit testit.cpp theon$ valgrind ./testit==3115== Memcheck, a memory error detector ==3115== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==3115== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info ==3115== Command: ./testit ==3115== Freiburg 227590 Konstanz 83789 Karlsruhe 309999 Stuttgart 628032 Mannheim 304781 Ulm 123953 Tübingen 88347 Heidelberg 159914 ==3115== ==3115== HEAP SUMMARY: ==3115== in use at exit: 5,648 bytes in 2 blocks ==3115== total heap usage: 12 allocs, 10 frees, 79,448 bytes allocated ==3115== ==3115== LEAK SUMMARY: ==3115== definitely lost: 0 bytes in 0 blocks ==3115== indirectly lost: 0 bytes in 0 blocks ==3115== possibly lost: 5,648 bytes in 2 blocks ==3115== still reachable: 0 bytes in 0 blocks ==3115== suppressed: 0 bytes in 0 blocks ==3115== Rerun with --leak-check=full to see details of leaked memory ==3115== ==3115== For counts of detected and suppressed errors, rerun with: -v ==3115== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) theon$