Beispiellösung
Content |
#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; std::size_t count; public: class Iterator { public: friend Hash; 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 prev, NodePtr node) : dim(hash.dim), bucket(hash.bucket), index(index), prev(prev), node(node) { assert(node && index < dim); } Object& operator*() { return node.lock()->object; } const Object& operator*() const { return node.lock()->object; } 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> prev; /* previous object, if any in the same list */ 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]), count(0) { } std::pair<Iterator, bool> insert(Object object) { auto index = hash(object.first) % dim; auto ptr = bucket[index]; NodePtr prev; while (ptr && ptr->object.first != object.first) { prev = ptr; ptr = ptr->next; } bool inserted; if (ptr) { inserted = false; } else { ptr = std::make_shared<Node>(std::move(object), bucket[index]); bucket[index] = ptr; prev = nullptr; inserted = true; ++count; } return std::make_pair(Iterator(*this, index, prev, ptr), inserted); } Iterator find(Key key) { auto index = hash(key) % dim; auto ptr = bucket[index]; NodePtr prev; while (ptr && ptr->object.first != key) { prev = ptr; ptr = ptr->next; } if (ptr) { return Iterator(*this, index, prev, ptr); } else { return Iterator(); } } void erase(Iterator it) { if (it.bucket.lock() == bucket && it.index < dim) { auto node = it.node.lock(); auto prev = it.prev.lock(); if (node) { if (prev) { prev->next = node->next; } else { bucket[it.index] = node->next; } --count; } } } 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(); } std::size_t size() const { return count; } }; #endif
#include <iostream> #include <memory> #include <sstream> #include <string> #include "Hash.hpp" constexpr std::size_t hashdim = 32; struct Item; using ItemPtr = std::shared_ptr<Item>; using Dependencies = Hash<std::string, ItemPtr>; struct Item { Item(std::string name) : name(std::move(name)), dependencies(hashdim), reversed(hashdim) { } std::string name; Dependencies dependencies; /* this item depends on these other items */ Dependencies reversed; /* items that depend on us */ }; int main() { Hash<std::string, ItemPtr> items(hashdim); /* lookup an item by name and create it, if it does not exist yet */ auto lookup = [&items](const std::string& name) -> ItemPtr { auto it = items.find(name); if (it == items.end()) { auto item = std::make_shared<Item>(name); std::tie(it, std::ignore) = items.insert(std::make_pair(name, item)); } return it->second; }; /* build data structure */ std::string line; while (std::getline(std::cin, line)) { std::istringstream in(line); std::string name; if (!(in >> name)) continue; auto item = lookup(name); std::string depname; while (in >> depname) { auto dep = lookup(depname); item->dependencies.insert(std::make_pair(depname, dep)); dep->reversed.insert(std::make_pair(name, item)); } } /* topological sort */ while (items.size() > 0) { std::size_t removed = 0; auto it = items.begin(); while (it != items.end()) { auto next = it; ++next; auto item = it->second; if (item->dependencies.size() == 0) { /* no dependencies left for item: print it and wipe it entirely from our data structure */ std::cout << item->name << std::endl; for (auto& revdepobj: item->reversed) { auto revdep = revdepobj.second; auto it = revdep->dependencies.find(item->name); revdep->dependencies.erase(it); } items.erase(it); ++removed; } it = next; } if (removed == 0) { std::cerr << "reference cycle!" << std::endl; break; } } for (auto& object: items) { auto item = object.second; std::cout << item->name << ":"; for (auto& depobj: item->dependencies) { auto dep = depobj.second; std::cout << " " << dep->name; } std::cout << std::endl; } }
theon$ g++ -std=c++17 -Wall -o tsort tsort.cpp theon$ valgrind ./tsort==3216== Memcheck, a memory error detector ==3216== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==3216== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info ==3216== Command: ./tsort ==3216== hinfahren zur_bank_gehen pin_eingeben geldautomat_bedienen geld_abheben geld_haben tanken ware_nehmen bezahlen zurueckfahren einkauf_erledigen essen_kochen ==3216== ==3216== HEAP SUMMARY: ==3216== in use at exit: 5,648 bytes in 2 blocks ==3216== total heap usage: 167 allocs, 165 frees, 98,766 bytes allocated ==3216== ==3216== LEAK SUMMARY: ==3216== definitely lost: 0 bytes in 0 blocks ==3216== indirectly lost: 0 bytes in 0 blocks ==3216== possibly lost: 5,648 bytes in 2 blocks ==3216== still reachable: 0 bytes in 0 blocks ==3216== suppressed: 0 bytes in 0 blocks ==3216== Rerun with --leak-check=full to see details of leaked memory ==3216== ==3216== For counts of detected and suppressed errors, rerun with: -v ==3216== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) theon$
Was passiert aber, wenn in der Eingabe Referenzzyklen enthalten sind?
theon$ cat cycle a b c b d e c g e c d f g f a theon$ valgrind ./tsort==3236== Memcheck, a memory error detector ==3236== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. ==3236== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info ==3236== Command: ./tsort ==3236== g c e reference cycle! a: b f: a d: f b: d ==3236== ==3236== HEAP SUMMARY: ==3236== in use at exit: 11,152 bytes in 30 blocks ==3236== total heap usage: 65 allocs, 35 frees, 89,408 bytes allocated ==3236== ==3236== LEAK SUMMARY: ==3236== definitely lost: 128 bytes in 1 blocks ==3236== indirectly lost: 5,376 bytes in 27 blocks ==3236== possibly lost: 5,648 bytes in 2 blocks ==3236== still reachable: 0 bytes in 0 blocks ==3236== suppressed: 0 bytes in 0 blocks ==3236== Rerun with --leak-check=full to see details of leaked memory ==3236== ==3236== For counts of detected and suppressed errors, rerun with: -v ==3236== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) theon$
Ist das bei Ihnen auch der Fall? Woran liegt es? Wie kann das Problem vermieden werden?