2017-08-22 16 views
7

Ich habe einen Hash-Prozess implementiert mit Howard Hinnant's method (generische Hash basierend auf hash_append Überladungen).Hashing polymorphen Typ der richtige Weg

Der Zweck dieser Methode besteht darin, einen Hash der Klassen zu erstellen, um das Ergebnis der Berechnungen zu "memoisieren" (siehe Ende dieser Antwort), so dass mir ein Problem bevorsteht. Insbesondere sollten Sie die folgenden möglichen Input Klasse, die gehasht werden muss:

struct A { 
    virtual int do_stuff() const = 0; 
    virtual ~A(); 
}; 
struct B: A { 
    int do_stuff() const override { return 0; } 
}; 
struct C: A { 
    const int u; 
    int do_stuff() const override { return u; } 
}; 

struct Input { 
    A const& a; // store a reference to an instance of B or C 
}; 

Nun, wenn ich Input Hash will, muss ich so etwas wie:

template <class HashAlgorithm> 
void hash_append(HashAlgorithm& h, Input const& input) { 
    hash_append(h, typeid(input)); 
    hash_append(h, typeid(input.a)); 
} 

Also muss ich eine Überlastung von hash_append für A:

template <class HashAlgorithm> 
void hash_append(HashAlgorithm& h, A const& a) { 
    hash_append(h, typeid(a)); 
} 

Das hier Problem ist, dass auf dem Laufzeittyp vonje, würde ich zusätzliche Informationen zu dem Hash hinzufügen müssen, z. für C würde ich u hinzufügen müssen.

Ich dachte an die folgenden Lösungen (und Nachteile):

  1. eine virtuelle Methode zu A hinzufügen, die einen bestimmten Wert zurückgibt, der zu dem typeid() Hash hinzugefügt werden können, aber:

    • das bedeutet, eine Methode innerhalb von A hinzuzufügen, die nicht mit dem Zweck von A zusammenhängt, daher mag ich diese Idee nicht wirklich (insbesondere weil ich mehrere A-ähnliche Klassen habe);
    • dies bricht das Konzept von hash_append, da die Methode einen eindeutigen Rückgabetyp für alle erbenden Klassen haben wird.
  2. tun ein Bündel von dynamic_cast innen hash_append:

    • Das fand ich ziemlich hässlich ... insbesondere, wenn ich mehrere Klassen ähnlich wie A haben;
    • Dies ist fehleranfällig: wenn jemand eine neue Kinder von A hinzufügt und keine dynamische_cast innerhalb hash_append hinzufügen.

Gibt es eine Möglichkeit, einen polymorphen Typ Hash, ohne dass der Typ selbst oder stützen sich auf eine Reihe von dynamic_cast ändern?


Das Endziel dieser ist in der Lage sein, die Ergebnisse einiger Schwer Funktionen memoize. Lassen Sie uns die Grundstruktur meiner Anwendung skizzieren: mit Hash Input s

struct Input { }; 
struct Result { }; 

Result solve(Input const&); 

Die solve Funktion ist rechenlastig, so möchte ich die Ergebnisse der vorherigen Berechnung in der Datei speichern, z.B.so etwas wie:

// depends on hash_append 
std::string hash(Input const&); 

Result load_or_solve(Input const& input) { 
    auto h = hash(input); 
    Result result; 
    if (exists(h)) { // if result exists, load it 
     result = load(h); 
    } 
    else { // otherwize, solve + store 
     result = solve(input); 
     store(h, result); 
    } 
    return result; 
} 

Die load und store Methoden würden laden und zu speichern Ergebnisse von Dateien ist das Ziel, Lösungen zwischen verschiedenen Läufen memoize.

Wenn Sie einen Vorschlag haben, wie Sie diese Ergebnisse notieren können, ohne sich mit den oben genannten Problemen zu befassen, werde ich mich freuen, sie zu lesen.

+1

Sie doppelte Dispatching können innerhalb der 'hash_append' Version von' A' und versenden die Anfrage an die entsprechenden Versionen für 'B' und 'C 'wenn du den Typ zurückbekommst, aber ich denke nicht, dass du genau das suchst. Hast du darüber nachgedacht? Der Nachteil ist, dass Sie diesen Klassen einen Text hinzufügen müssen, um einen Besucher zu akzeptieren. Wenn es für Sie arbeiten kann, kann ich den Kommentar in eine detailliertere Antwort setzen. – skypjack

+0

@skypjack Es tut mir leid, ich verstehe nicht ganz, was du meinst - könntest du ein kleines Beispiel schreiben, um deine Bedeutung zu verdeutlichen? – Holt

+1

Ich meine etwas [in dieser Zeile] (http://coliru.stacked-crooked.com/a/c1b5c249535f7590). Das ist kein funktionierendes Beispiel, aber Sie sollten auf die Idee kommen. Leider fehlt Ihrem Beispielcode viel Code, um ein konkretes Beispiel zu packen, tut mir leid. Und natürlich kann 'HashVisitor' _simplified_ sein (zumindest so entworfen, dass Sie es nicht jedes Mal ändern müssen, wenn Sie einen neuen Typ definieren), indem Sie variadische Vorlagen und direkte Vererbung verwenden, aber die Art, wie ich es definiert habe, sollte einfacher sein verstehen. – skypjack

Antwort

4

können Sie doppelten Dispatching zum Einsatz innerhalb der hash_append Version von A und die Anforderung an die richtigen Version weiterleiten (dh derjenige ist entweder für B oder C). Der Nachteil ist, dass Sie diesen Klassen einen Text hinzufügen müssen, um einen Besucher zu akzeptieren, und ich kann nicht sagen, ob es für Sie akzeptabel ist.
Hier ist ein Bündel von Code, der die Idee veranschaulichen soll:

struct B; 
struct C; 

struct Visitor { 
    virtual void visit(const B &) = 0; 
    virtual void visit(const C &) = 0; 
}; 

template<typename T, typename... O> 
struct HashVisitor: T, HashVisitor<O...> { 
    template<typename U> 
    std::enable_if_t<std::is_same<T, U>::value> tryVisit(const U &u) { 
     T::operator()(u); 
    } 

    template<typename U> 
    std::enable_if_t<not std::is_same<T, U>::value> tryVisit(const U &u) { 
     HashVisitor<O...>::visit(u); 
    } 

    void visit(const B &b) override { tryVisit<B>(b); } 
    void visit(const C &c) override { tryVisit<C>(c); } 
}; 

template<> 
struct HashVisitor<>: Visitor {}; 

template<typename... F 
auto factory(F&&... f) { 
    return HashVisitor<std::decay_t<F>>{std::forward<F>(f)...}; 
} 

struct A { 
    virtual void accept(Visitor &) = 0; 
    virtual int do_stuff() const = 0; 
    virtual ~A(); 
}; 

struct B: A { 
    void accept(Visitor &v) override { v.visit(*this); } 
    int do_stuff() const override { return 0; } 
}; 

struct C: A { 
    const int u; 
    void accept(Visitor &v) override { v.visit(*this); } 
    int do_stuff() const override { return u; } 
}; 

template <class HashAlgorithm> 
void hash_append(HashAlgorithm &, const B &) { 
    // do something 
} 

template <class HashAlgorithm> 
void hash_append(HashAlgorithm &, const C &) { 
    // do something 
} 

template <class HashAlgorithm> 
void hash_append(HashAlgorithm &h, const A &a) { 
    auto vis = factory(
     [&h](const B &b){ hash_append(h, b); }, 
     [&h](const C &c){ hash_append(h, c); } 
    ); 

    a.accept(vis); 
} 
+0

Danke für die Antwort - ich denke, das ist die beste Antwort, wenn ich Robustheit möchte, d. H. Keinen Typ mit einer nicht implementierten Hash-Methode. Leider muss ich die umgekehrte Richtung wählen, dh eine weniger robuste Methode (zur Kompilierzeit), aber mit weniger Einschränkungen: normalerweise kann ich die Klassen nicht vor dem Besucher weiterleiten, und ich möchte den Hashing-Prozess immer noch von der trennen Klasse sich selbst. Ich versuche etwas zu implementieren, das mir erlaubt, benutzerdefinierte Runtime-Dispatch nach Deklaration der Klassen hinzuzufügen (Ich bin ein bisschen fest zu der Zeit, könnte eine andere Frage bald eröffnen ...). – Holt

+0

Lassen Sie es mich wissen und ich werde versuchen, Ihnen eine Antwort zu geben, wenn möglich. – skypjack

+0

Es ist hier - https://stackoverflow.com/questions/45837117/storing-various-tuples-and-applyping-templated-functor-on-them – Holt

Verwandte Themen