Antworten und Beispiellösung
Content |
Zu den Fragen
-
Wir benötigen Zugang zur Bucket-Table mitsamt deren Dimensionierung, einen laufenden Index für die Bucket-Table und einen Zeiger auf das aktuelle Objekt.
-
Wenn wir eine Referenz auf die Hash-Tabelle verwenden würden, dann haben wir keine Unterstützung für Zuweisungen. Wir könnten zwar einen Zuweisungs-Operator definieren, hätten dann aber ein Problem, wenn die Referenzen nicht übereinstimmen würden. Daher ist am besten, einen std::weak_ptr auf die Bucket-Tabelle zu haben mitsamt einer lokalen Kopie der Dimensionierung. Alternativ könnten wir auch mit einer weiteren Indirektion dies vereinfachen.
Die Konsequenz ist, dass wir für die Bucket-Table nicht mehr std::unique_ptr nehmen können, sondern std::shared_ptr benötigen. (Dies geht ab C++17.)
-
Den Ende-Iterator repräsentieren wir mit einem Index, der den Wert der Dimensionierung der Bucket-Table erreicht hat und einem Objekt-Zeiger, der null ist.
Beispiellösung
#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
#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; } } for (auto& object: hash) { std::cout << object.first << " " << object.second << std::endl; } }
theon$ g++ -std=c++17 -Wall -o testit testit.cpp theon$ valgrind ./testit==3139== Memcheck, a memory error detector ==3139== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==3139== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info ==3139== Command: ./testit ==3139== Freiburg 227590 Konstanz 83789 Karlsruhe 309999 Stuttgart 628032 Mannheim 304781 Ulm 123953 Tübingen 88347 Heidelberg 159914 ==3139== ==3139== HEAP SUMMARY: ==3139== in use at exit: 5,648 bytes in 2 blocks ==3139== total heap usage: 13 allocs, 11 frees, 79,472 bytes allocated ==3139== ==3139== LEAK SUMMARY: ==3139== definitely lost: 0 bytes in 0 blocks ==3139== indirectly lost: 0 bytes in 0 blocks ==3139== possibly lost: 5,648 bytes in 2 blocks ==3139== still reachable: 0 bytes in 0 blocks ==3139== suppressed: 0 bytes in 0 blocks ==3139== Rerun with --leak-check=full to see details of leaked memory ==3139== ==3139== For counts of detected and suppressed errors, rerun with: -v ==3139== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) theon$