Die Implementierung eines C++ - hashtable-Klasse, die mit Vorlage

Ich versuche zu implementieren ist eine hashtable in C++, dass in der Art, wie Sie die Java-version

Ich würde es gerne, hat die form 

template <class Key, class Value> 
class hashtable {
...
}

Schon bald merke ich, dass ich brauchen, um irgendwie konvertieren Schlüssel in eine Reihe, so dass ich verwenden können, die einfache hash-Funktion 

int h(int hashkey) { 
    return hashkey%some_prime;
}

Aber die Kopfschmerzen, Schlüssel-Typ ist nur bekannt, zur Laufzeit. Ist es möglich zu überprüfen, welche Art Key ist zur Laufzeit in C++. Oder ich habe zum erstellen dieser hashtable-Klasse, die mit verschiedenen Art manuell? Das ist einfacher zu tun, aber hässlich. Weiss jemand eine elegante Lösung?

  • Haben Sie sich überlegt std::unordered_map statt?
  • Die Implementierung einer Hashtabelle ist eine gute Lernübung, aber Sie wollen, schauen Sie in die Dokumentation (und ggf. den code) für Billy ' s Vorschlag auf std::unordered_map, um Ihnen den Einstieg erleichtern.
  • Danke für die Anregung! Ich bin eigentlich eine Lern-übung, und ich darf hinzufügen möchten, in-house-Merkmal dieser Implementierung später. Eine dumme Frage, wo kann ich auf die Implementierung von std:unordered_map?
  • wie wäre hash_map?
  • Wenn Sie interessiert sind, im Blick auf die Implementierung von std::unordered_map, die auf einer linux-Maschine, es beginnt in der Regel in /usr/include/c++/<your_version>/unordered_map, und auf der Suche nach anderen header-Dateien enthalten, wie tr1_impl/hashtable. Allerdings ist es nicht trivial zu verstehen, die Umsetzung.
  • machen Sie Ihre hash-Funktion, der Dritte parameter der Vorlage.

InformationsquelleAutor Alfred Zhong | 2013-01-02
  1. 1

    Wenn Sie möchten, versuchen zur Umsetzung einer "generischen" ein, vielleicht können Sie beginnen, mit einem Skelett ähnlich wie diese: 

    template <class T, class K>
struct HashEntry {  //you would need this to deal with collision
    T curr;
    K next;
}

template <class V, size_t n>
class HashTable {
    void insert(V v)
    {
        ...
        size_t idx = v->getHashCode(n);
        ...
    }
private:
    HashEntry <V> table_[n];

}

    Ist es in der Regel instanziiert mit einigen Zeiger-Typ, um herauszufinden, wo ein Zeiger gehen sollte, erfordert es die Art implementieren member-Funktion "getHashCode" ...

    InformationsquelleAutor
  2. 3

    C++ - templates sind in der Regel Ente getippt, was bedeutet, dass man explizit casten zu einem integeral geben Sie in der Vorlage, und alle Typen, die Umsetzung der entsprechenden Umbau kann als Schlüssel verwendet. Das hat den Nachteil, dass die Klassen implementieren die Umwandlung Betreiber in der Weise, dass die hash-Funktion wird anständig sein, das ist gefragt für eine Menge.

    Könnten Sie stattdessen eine Funktion bieten, Vorlage

    template<typename T> int hash (T t);

    Zusammen mit Spezialisierungen für die eingebauten Typen, und jeder Benutzer, der will, verwenden Sie eine benutzerdefinierte Klasse als Schlüssel wird nur noch um seinen eigenen specialzation. Ich denke, das ist ein vernünftiger Ansatz.

    InformationsquelleAutor StoryTeller
  3. 2

    Sie haben anscheinend ein paar Missverständnisse. Schlüssel-Typ zur Kompilierzeit bekannt ist - das ist der springende Punkt bei der Verwendung von Vorlagen. Zweitens, es gibt wirklich keine solche Sache wie eine vollkommen generische hash-Funktion, funktioniert auf jeder Art. Sie müssen die Implementierung der verschiedenen hash-Funktionen für die verschiedenen Arten, mit überladen von Funktionen oder template-Spezialisierung. Es gibt viele gängige hash-Funktionen für strings verwendet, zum Beispiel.

    Schließlich, C++11 bietet eine standard-hash-Tabelle ( std::unordered_map ), die Sie stattdessen verwenden können von der Umsetzung Ihrer eigenen.

    • Danke, du hast Recht. Ich war mir im klaren über die Laufzeit, was am Anfang aber verwirrt nach der Suche auf der Website für eine Weile. unordered_map ist sehr ähnlich zu dem, was ich will. Wo kann ich auf der Implementierung von it?
    • so ziemlich jeder compiler unterstützt C++11 sollte Schiff mit einer Umsetzung. Ich schlage vor, dass Sie einen Blick auf die neueste Version von GCC.
    • hier die status-Seite für die Bibliothek der Umsetzung gebündelt mit GCC, siehe Eintrag 23.5.4.
    InformationsquelleAutor Charles Salvia
Schreibe einen Kommentar