Jaki jest najlepszy sposób używania HashMap w C ++?

Wiem, że STL ma HashMap API, ale nie mogę znaleźć dobrej i dokładnej dokumentacji z dobrymi przykładami na ten temat.

Wszelkie dobre przykłady będą mile widziane.

Biblioteka standardowa zawiera uporządkowane i nieuporządkowane kontenery map ( std::mapi std::unordered_map). W uporządkowanej mapie elementy są sortowane według klucza, wstawianie i dostęp odbywa się w O (log n) . Zwykle standardowa biblioteka wewnętrznie używa czerwonych czarnych drzew do uporządkowanych map. Ale to tylko szczegół implementacji. W nieuporządkowanej mapie wstawianie i dostęp jest w O (1). To po prostu inna nazwa tablicy haszującej.

Przykład z (zamówione) 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;
}

Wynik:

23
Klucz: witaj Wartość: 23

Jeśli potrzebujesz zamówienia w swoim kontenerze i nie przeszkadza Ci środowisko uruchomieniowe O (log n), po prostu użyj std::map.

W przeciwnym razie, jeśli naprawdę potrzebujesz hash-table (O (1) Wstawić / Access), sprawdź std::unordered_map, który ma podobny do std::mapinterfejsu API (np w powyższym przykładzie po prostu trzeba wyszukać i zamienić mapz unordered_map).

unordered_mapPojemnik z wprowadzonym C ++ 11 standardowej wersji. Tak więc, w zależności od kompilatora, musisz włączyć funkcje C ++ 11 (np. Używając GCC 4.8 musisz dodać -std=c++11do CXXFLAGS).

Nawet przed wydaniem C ++ 11 obsługiwane GCC unordered_map- w przestrzeni nazw std::tr1. Dlatego w przypadku starych kompilatorów GCC możesz spróbować użyć tego w następujący sposób:

#include <tr1/unordered_map>

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

Jest to również część wzmocnienia, tzn. Możesz użyć odpowiedniego nagłówka zwiększającego dla lepszej przenośności.

A hash_mapjest starszą, niestandaryzowaną wersją tego, co dla celów standaryzacji nazywa się an unordered_map(pierwotnie w TR1 i uwzględnione w standardzie od C ++ 11). Jak sama nazwa wskazuje, różni się od std::mapprzede wszystkim nieuporządkowaniem - jeśli na przykład iterujesz po mapie od begin()do end(), otrzymujesz przedmioty w kolejności według klawisza ¹ , ale jeśli przechodzisz przez unordered_mapod begin()do end(), otrzymujesz przedmioty w mniej lub bardziej arbitralna kolejność.

unordered_mapOczekuje się normalnie mieć stałą złożoność. Oznacza to, że wstawianie, wyszukiwanie itp. Zwykle zajmuje w zasadzie stałą ilość czasu, niezależnie od liczby elementów w tabeli. std::mapMa złożoność logarytmiczną na który jest liczba elementów są przechowywane - co oznacza, że czas, aby wstawić lub pobrać element rośnie, ale bardzo powoli , jak mapa rozrasta. Na przykład, jeśli wyszukanie jednego z 1 miliona elementów zajmuje 1 mikrosekundę, możesz oczekiwać, że wyszukanie jednego z 2 milionów elementów zajmie około 2 mikrosekund, 3 mikrosekundy dla jednego z 4 milionów elementów, 4 mikrosekundy dla jednego z 8 milionów elementów przedmioty itp.

Z praktycznego punktu widzenia to jednak nie wszystko. Z natury prosta tabela skrótów ma stały rozmiar. Dostosowanie go do wymagań o zmiennej wielkości dla kontenera ogólnego przeznaczenia jest nieco nietrywialne. W rezultacie operacje, które (potencjalnie) powiększają tabelę (np. Wstawianie) są potencjalnie stosunkowo wolne (to znaczy większość jest dość szybka, ale okresowo jedna będzie znacznie wolniejsza). Wyszukiwania, które nie mogą zmienić rozmiaru tabeli, są na ogół znacznie szybsze. W rezultacie większość tabel opartych na skrótach zwykle działa najlepiej, gdy wykonujesz wiele wyszukiwań w porównaniu z liczbą wstawień. W sytuacjach, w których wstawiasz dużo danych, powtórz raz tabelę, aby pobrać wyniki (np. Licząc liczbę unikalnych słów w pliku), istnieje prawdopodobieństwo, żestd::map będzie równie szybki, a być może nawet szybszy (ale znowu złożoność obliczeniowa jest inna, więc może to również zależeć od liczby unikalnych słów w pliku).

^{1 Gdzie kolejność jest definiowana std::less<T>domyślnie przez trzeci parametr szablonu podczas tworzenia mapy .}

Oto bardziej kompletny i elastyczny przykład, który nie pomija niezbędnych elementów do generowania błędów kompilacji:

#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");
}

Nadal nie jest szczególnie przydatne w przypadku kluczy, chyba że są one wstępnie zdefiniowane jako wskaźniki, ponieważ pasująca wartość nie wystarczy! (Ponieważ jednak zwykle używam ciągów znaków jako kluczy, zastąpienie „string” zamiast „const void *” w deklaracji klucza powinno rozwiązać ten problem).

Dowody, które std::unordered_mapużywają mapy skrótów w GCC stdlibc ++ 6.4

Wspomniano o tym na: https://stackoverflow.com/a/3578247/895245, ale w następującej odpowiedzi: Jaka struktura danych znajduje się w std :: map w C ++? Podałem dalsze dowody na to dla implementacji GCC stdlibc ++ 6.4 przez:

• Debugowanie krokowe GDB w klasie
• analiza charakterystyk wydajności

Oto podgląd wykresu charakterystyki wydajności opisanego w tej odpowiedzi:

Jak używać niestandardowej klasy i funkcji skrótu w programie unordered_map

Ta odpowiedź oznacza: C ++ unordered_map używając niestandardowego typu klasy jako klucza

Fragment: równość:

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);
  }
};

Funkcja skrótu:

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);
    }
  };

}

Dla tych z nas, którzy próbują dowiedzieć się, jak haszować własne klasy, nadal używając standardowego szablonu, istnieje proste rozwiązanie:

1. W swojej klasie musisz zdefiniować przeciążenie operatora równości ==. Jeśli nie wiesz, jak to zrobić, GeeksforGeeks ma świetny samouczek https://www.geeksforgeeks.org/operator-overloading-c/

2. W standardowej przestrzeni nazw zadeklaruj strukturę szablonu o nazwie hash z nazwą klasy jako typem (patrz poniżej). Znalazłem świetny post na blogu, który pokazuje również przykład obliczania hashów za pomocą XOR i bitshiftingu, ale to wykracza poza zakres tego pytania, ale zawiera również szczegółowe instrukcje, jak korzystać z funkcji skrótu, a także https://prateekvjoshi.com/ 2014/06/05 / using-hash-function-in-c-for-user-specified-classes /

namespace std {

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

}

3. Zatem aby zaimplementować tablicę haszującą za pomocą nowej funkcji skrótu, wystarczy utworzyć std::maplub std::unordered_maptak jak zwykle robisz i używać my_typejako klucza, biblioteka standardowa automatycznie użyje funkcji skrótu, którą zdefiniowałeś wcześniej (w kroku 2) do hashowania Twoje klucze.

#include <unordered_map>

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