Was ist der beste Weg, um eine HashMap in C ++ zu verwenden?

Ich weiß, dass STL eine HashMap-API hat, aber ich kann keine gute und gründliche Dokumentation mit guten Beispielen dafür finden.

Alle guten Beispiele werden geschätzt.

Die Standardbibliothek enthält die geordneten und die ungeordneten Kartencontainer ( std::mapund std::unordered_map). In einer geordneten Karte werden die Elemente nach dem Schlüssel sortiert, einfügen und der Zugriff erfolgt in O (log n) . Normalerweise verwendet die Standardbibliothek intern rot-schwarze Bäume für geordnete Karten. Dies ist jedoch nur ein Implementierungsdetail. In einer ungeordneten Karte ist das Einfügen und der Zugriff in O (1). Es ist nur ein anderer Name für eine Hashtabelle.

Ein Beispiel mit (bestellt) std::map:

#include <map>
#include <iostream>
#include <cassert>

int main(int argc, char **argv)
{
  std::map<std::string, int> m;
  m["hello"] = 23;
  // check if key is present
  if (m.find("world") != m.end())
    std::cout << "map contains key world!\n";
  // retrieve
  std::cout << m["hello"] << '\n';
  std::map<std::string, int>::iterator i = m.find("hello");
  assert(i != m.end());
  std::cout << "Key: " << i->first << " Value: " << i->second << '\n';
  return 0;
}

Ausgabe:

23
Schlüssel: Hallo Wert: 23

Wenn Sie in Ihrem Container bestellen müssen und mit der O (log n) -Laufzeit zufrieden sind, verwenden Sie einfach std::map.

Andernfalls, wenn Sie wirklich eine Hash-Tabelle (O (1) insert / Zugang) benötigen, überprüfen std::unordered_map, die ein ähnliches hat std::mapAPI (zB in dem obigen Beispiel müssen Sie nur noch das Suchen und Ersetzen mapmit unordered_map).

Der unordered_mapContainer wurde mit der C ++ 11-Standardversion eingeführt . Abhängig von Ihrem Compiler müssen Sie daher C ++ 11-Funktionen aktivieren (z. B. wenn Sie GCC 4.8 verwenden, müssen Sie diese zu -std=c++11CXXFLAGS hinzufügen ).

Noch vor der Veröffentlichung von C ++ 11 wurde GCC unterstützt unordered_map- im Namespace std::tr1. Daher können Sie für alte GCC-Compiler versuchen, es wie folgt zu verwenden:

#include <tr1/unordered_map>

std::tr1::unordered_map<std::string, int> m;

Es ist auch Teil von Boost, dh Sie können den entsprechenden Boost-Header für eine bessere Portabilität verwenden.

A hash_mapist eine ältere, nicht standardisierte Version dessen, was zu Standardisierungszwecken als a bezeichnet wird unordered_map(ursprünglich in TR1 und seit C ++ 11 im Standard enthalten). Wie der Name schon sagt, unterscheidet es sich std::maphauptsächlich davon, ungeordnet zu sein. Wenn Sie beispielsweise eine Karte von begin()bis durchlaufen end(), erhalten Sie Elemente in der Reihenfolge nach Schlüssel ¹ , aber wenn Sie durch ein unordered_mapvon begin()bis iterieren end(), erhalten Sie Elemente in a mehr oder weniger willkürliche Reihenfolge.

Es unordered_mapwird normalerweise eine konstante Komplexität von A erwartet. Das heißt, das Einfügen, Nachschlagen usw. dauert normalerweise im Wesentlichen eine feste Zeit, unabhängig davon, wie viele Elemente in der Tabelle enthalten sind. A std::maphat eine Komplexität, die logarithmisch in Bezug auf die Anzahl der gespeicherten Elemente ist. Dies bedeutet, dass die Zeit zum Einfügen oder Abrufen eines Elements mit zunehmender Größe der Karte langsam ansteigt. Wenn zum Beispiel 1 Mikrosekunde benötigt wird, um eines von 1 Million Elementen zu suchen, können Sie damit rechnen, dass es ungefähr 2 Mikrosekunden dauert, um eines von 2 Millionen Elementen zu suchen, 3 Mikrosekunden für eines von 4 Millionen Elementen, 4 Mikrosekunden für eines von 8 Millionen Gegenstände usw.

Aus praktischer Sicht ist das jedoch nicht die ganze Geschichte. Eine einfache Hash-Tabelle hat von Natur aus eine feste Größe. Die Anpassung an die Anforderungen variabler Größe für einen Allzweckcontainer ist nicht trivial. Infolgedessen sind Operationen, die die Tabelle (möglicherweise) vergrößern (z. B. Einfügen), möglicherweise relativ langsam (das heißt, die meisten sind ziemlich schnell, aber in regelmäßigen Abständen ist eine viel langsamer). Suchvorgänge, bei denen die Größe der Tabelle nicht geändert werden kann, sind im Allgemeinen viel schneller. Infolgedessen sind die meisten Hash-basierten Tabellen in der Regel am besten, wenn Sie im Vergleich zur Anzahl der Einfügungen viele Suchvorgänge durchführen. In Situationen, in denen Sie viele Daten einfügen, durchlaufen Sie die Tabelle einmal, um die Ergebnisse abzurufen (z. B. die Anzahl der eindeutigen Wörter in einer Datei zu zählen)std::map wird genauso schnell und möglicherweise sogar noch schneller sein (aber auch hier ist die Rechenkomplexität unterschiedlich, so dass dies auch von der Anzahl der eindeutigen Wörter in der Datei abhängen kann).

^{1 Wenn die Reihenfolge beim Erstellen der Karte std::less<T>standardmäßig durch den dritten Vorlagenparameter definiert wird .}

Hier ist ein vollständigeres und flexibleres Beispiel, bei dem die erforderlichen Includes zum Generieren von Kompilierungsfehlern nicht ausgelassen werden:

#include <iostream>
#include <unordered_map>

class Hashtable {
    std::unordered_map<const void *, const void *> htmap;

public:
    void put(const void *key, const void *value) {
            htmap[key] = value;
    }

    const void *get(const void *key) {
            return htmap[key];
    }

};

int main() {
    Hashtable ht;
    ht.put("Bob", "Dylan");
    int one = 1;
    ht.put("one", &one);
    std::cout << (char *)ht.get("Bob") << "; " << *(int *)ht.get("one");
}

Immer noch nicht besonders nützlich für Schlüssel, es sei denn, sie sind als Zeiger vordefiniert, da ein übereinstimmender Wert nicht ausreicht! (Da ich jedoch normalerweise Zeichenfolgen für Schlüssel verwende, sollte dieses Problem durch Ersetzen von "const void *" in der Schlüsseldeklaration durch "Zeichenfolge" behoben werden.)

Beweise, std::unordered_mapdie eine Hash-Map in GCC stdlibc ++ 6.4 verwenden

Dies wurde erwähnt unter: https://stackoverflow.com/a/3578247/895245, aber in der folgenden Antwort: Welche Datenstruktur befindet sich in std :: map in C ++? Ich habe weitere Beweise dafür für die Implementierung von GCC stdlibc ++ 6.4 gegeben durch:

• GDB-Schritt beim Debuggen in die Klasse
• Analyse der Leistungsmerkmale

Hier ist eine Vorschau des in dieser Antwort beschriebenen Leistungsmerkmalsdiagramms:

Verwendung einer benutzerdefinierten Klassen- und Hashfunktion mit unordered_map

Diese Antwort lautet: C ++ unordered_map mit einem benutzerdefinierten Klassentyp als Schlüssel

Auszug: Gleichheit:

struct Key
{
  std::string first;
  std::string second;
  int         third;

  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }
};

Hash-Funktion:

namespace std {

  template <>
  struct hash<Key>
  {
    std::size_t operator()(const Key& k) const
    {
      using std::size_t;
      using std::hash;
      using std::string;

      // Compute individual hash values for first,
      // second and third and combine them using XOR
      // and bit shifting:

      return ((hash<string>()(k.first)
               ^ (hash<string>()(k.second) << 1)) >> 1)
               ^ (hash<int>()(k.third) << 1);
    }
  };

}

Für diejenigen von uns, die versuchen, herauszufinden, wie sie ihre eigenen Klassen hashen können, während sie noch die Standardvorlage verwenden, gibt es eine einfache Lösung:

1. In Ihrer Klasse müssen Sie eine Überladung des Gleichheitsoperators definieren ==. Wenn Sie nicht wissen, wie das geht, bietet GeeksforGeeks ein großartiges Tutorial: https://www.geeksforgeeks.org/operator-overloading-c/

2. Deklarieren Sie unter dem Standard-Namespace eine Vorlagenstruktur namens Hash mit Ihrem Klassennamen als Typ (siehe unten). Ich habe einen großartigen Blogpost gefunden, der auch ein Beispiel für die Berechnung von Hashes mit XOR und Bitshifting zeigt, aber das liegt außerhalb des Rahmens dieser Frage, enthält aber auch detaillierte Anweisungen zur Verwendung von Hash-Funktionen sowie https://prateekvjoshi.com/ 2014/06/05 / using-hash-function-in-c-for-user-defined-classes /

namespace std {

  template<>
  struct hash<my_type> {
    size_t operator()(const my_type& k) {
      // Do your hash function here
      ...
    }
  };

}

3. Um eine Hashtabelle mit Ihrer neuen Hash-Funktion zu implementieren, müssen Sie nur eine erstellen std::mapoder std::unordered_mapwie gewohnt und my_typeals Schlüssel verwenden. Die Standardbibliothek verwendet automatisch die zuvor definierte Hash-Funktion (in Schritt 2) für Hash deine Schlüssel.

#include <unordered_map>

int main() {
  std::unordered_map<my_type, other_type> my_map;
}