C ++ unordered_map przy użyciu niestandardowego typu klasy jako klucza

285

Usiłuję użyć niestandardowej klasy jako klucza do unordered_map, jak poniżej:

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

class node;
class Solution;

class Node {
public:
    int a;
    int b; 
    int c;
    Node(){}
    Node(vector<int> v) {
        sort(v.begin(), v.end());
        a = v[0];       
        b = v[1];       
        c = v[2];       
    }

    bool operator==(Node i) {
        if ( i.a==this->a && i.b==this->b &&i.c==this->c ) {
            return true;
        } else {
            return false;
        }
    }
};

int main() {
    unordered_map<Node, int> m;    

    vector<int> v;
    v.push_back(3);
    v.push_back(8);
    v.push_back(9);
    Node n(v);

    m[n] = 0;

    return 0;
}

Jednak g ++ daje mi następujący błąd:

In file included from /usr/include/c++/4.6/string:50:0,
                 from /usr/include/c++/4.6/bits/locale_classes.h:42,
                 from /usr/include/c++/4.6/bits/ios_base.h:43,
                 from /usr/include/c++/4.6/ios:43,
                 from /usr/include/c++/4.6/ostream:40,
                 from /usr/include/c++/4.6/iostream:40,
                 from 3sum.cpp:4:
/usr/include/c++/4.6/bits/stl_function.h: In member function bool std::equal_to<_Tp>::operator()(const _Tp&, const _Tp&) const [with _Tp = Node]’:
/usr/include/c++/4.6/bits/hashtable_policy.h:768:48:   instantiated from bool std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_M_compare(const _Key&, std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_Hash_code_type, std::__detail::_Hash_node<_Value, false>*) const [with _Key = Node, _Value = std::pair<const Node, int>, _ExtractKey = std::_Select1st<std::pair<const Node, int> >, _Equal = std::equal_to<Node>, _H1 = std::hash<Node>, _H2 = std::__detail::_Mod_range_hashing, std::__detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, std::__detail::_Default_ranged_hash, false>::_Hash_code_type = long unsigned int]’
/usr/include/c++/4.6/bits/hashtable.h:897:2:   instantiated from std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Node* std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_M_find_node(std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Node*, const key_type&, typename std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Hash_code_type) const [with _Key = Node, _Value = std::pair<const Node, int>, _Allocator = std::allocator<std::pair<const Node, int> >, _ExtractKey = std::_Select1st<std::pair<const Node, int> >, _Equal = std::equal_to<Node>, _H1 = std::hash<Node>, _H2 = std::__detail::_Mod_range_hashing, _Hash = std::__detail::_Default_ranged_hash, _RehashPolicy = std::__detail::_Prime_rehash_policy, bool __cache_hash_code = false, bool __constant_iterators = false, bool __unique_keys = true, std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Node = std::__detail::_Hash_node<std::pair<const Node, int>, false>, std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::key_type = Node, typename std::_Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys>::_Hash_code_type = long unsigned int]’
/usr/include/c++/4.6/bits/hashtable_policy.h:546:53:   instantiated from std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::mapped_type& std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::operator[](const _Key&) [with _Key = Node, _Pair = std::pair<const Node, int>, _Hashtable = std::_Hashtable<Node, std::pair<const Node, int>, std::allocator<std::pair<const Node, int> >, std::_Select1st<std::pair<const Node, int> >, std::equal_to<Node>, std::hash<Node>, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, false, false, true>, std::__detail::_Map_base<_Key, _Pair, std::_Select1st<_Pair>, true, _Hashtable>::mapped_type = int]’
3sum.cpp:149:5:   instantiated from here
/usr/include/c++/4.6/bits/stl_function.h:209:23: error: passing const Node as this argument of bool Node::operator==(Node)’ discards qualifiers [-fpermissive]
make: *** [threeSum] Error 1

Chyba potrzebuję powiedzieć C ++, jak haszować klasę Node, jednak nie jestem do końca pewien, jak to zrobić. Jak mogę wykonać te zadania?

Alfred Zhong
źródło
2
Trzeci argument szablonu jest funkcja hash trzeba dostarczyć.
chrisaycock
3
cppreference ma prosty i praktyczny przykład jak to zrobić: en.cppreference.com/w/cpp/container/unordered_map/unordered_map
jogojapan

Odpowiedzi:

486

Aby móc używać std::unordered_map(lub jednego z innych nieuporządkowanych kontenerów asocjacyjnych) z kluczem zdefiniowanym przez użytkownika, musisz zdefiniować dwie rzeczy:

  1. Funkcja skrótu ; musi to być klasa, która zastępuje operator()i oblicza wartość skrótu, biorąc pod uwagę obiekt typu klucza. Jednym szczególnie prostym sposobem na to jest specjalizacja std::hashszablonu dla twojego typu klucza.

  2. Funkcja porównania dla równości ; jest to wymagane, ponieważ skrót nie może polegać na tym, że funkcja skrótu zawsze zapewnia unikalną wartość skrótu dla każdego odrębnego klucza (tj. musi być w stanie poradzić sobie z kolizjami), więc musi mieć sposób na porównanie dwóch podanych kluczy dla dokładnego dopasowania. Możesz to zaimplementować albo jako klasę, która zastępuje operator(), albo specjalizację std::equal, albo - najłatwiej ze wszystkich - przez przeciążenie operator==()dla twojego typu klucza (jak to już zrobiłeś).

Trudność związana z funkcją skrótu polega na tym, że jeśli typ klucza składa się z kilku elementów, zazwyczaj funkcja skrótu oblicza wartości skrótu dla poszczególnych elementów, a następnie łączy je w jedną wartość skrótu dla całego obiektu. Aby uzyskać dobrą wydajność (tj. Kilka kolizji), powinieneś dokładnie przemyśleć, jak łączyć poszczególne wartości skrótu, aby uniknąć zbyt częstego uzyskiwania tego samego wyniku dla różnych obiektów.

Dość dobrym punktem wyjścia dla funkcji skrótu jest taki, który wykorzystuje przesunięcie bitów i bitowe XOR do łączenia poszczególnych wartości skrótu. Na przykład zakładając taki typ klucza:

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

Oto prosta funkcja skrótu (dostosowana z funkcji użytej w przykładzie cppreference dla funkcji skrótu zdefiniowanych przez użytkownika ):

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

}

Dzięki temu możesz utworzyć instancję std::unordered_mapdla typu klucza:

int main()
{
  std::unordered_map<Key,std::string> m6 = {
    { {"John", "Doe", 12}, "example"},
    { {"Mary", "Sue", 21}, "another"}
  };
}

Będzie automatycznie używał, std::hash<Key>jak zdefiniowano powyżej, do obliczeń wartości skrótu i operator==zdefiniowanej jako funkcja elementu Keydla kontroli równości.

Jeśli nie chcesz specjalizować szablonu w stdprzestrzeni nazw (chociaż w tym przypadku jest to całkowicie legalne), możesz zdefiniować funkcję skrótu jako oddzielną klasę i dodać ją do listy argumentów szablonu dla mapy:

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

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

int main()
{
  std::unordered_map<Key,std::string,KeyHasher> m6 = {
    { {"John", "Doe", 12}, "example"},
    { {"Mary", "Sue", 21}, "another"}
  };
}

Jak zdefiniować lepszą funkcję skrótu? Jak wspomniano powyżej, zdefiniowanie dobrej funkcji skrótu jest ważne, aby uniknąć kolizji i uzyskać dobrą wydajność. Dla prawdziwego dobra należy wziąć pod uwagę rozkład możliwych wartości wszystkich pól i zdefiniować funkcję skrótu, która rzutuje tę dystrybucję na przestrzeń możliwych wyników tak szeroką i równomiernie rozłożoną, jak to możliwe.

To może być trudne; powyższa metoda zmiany bitów / XOR prawdopodobnie nie jest zła. Aby nieco lepiej zacząć, możesz użyć szablonu hash_valuei hash_combinefunkcji z biblioteki Boost. Ten pierwszy działa w podobny sposób, jak w std::hashprzypadku standardowych typów (ostatnio także krotek i innych przydatnych standardowych typów); ten ostatni pomaga łączyć poszczególne wartości skrótu w jedną. Oto przepis funkcji haszującej, która korzysta z funkcji pomocniczych Boost:

#include <boost/functional/hash.hpp>

struct KeyHasher
{
  std::size_t operator()(const Key& k) const
  {
      using boost::hash_value;
      using boost::hash_combine;

      // Start with a hash value of 0    .
      std::size_t seed = 0;

      // Modify 'seed' by XORing and bit-shifting in
      // one member of 'Key' after the other:
      hash_combine(seed,hash_value(k.first));
      hash_combine(seed,hash_value(k.second));
      hash_combine(seed,hash_value(k.third));

      // Return the result.
      return seed;
  }
};

A oto przepisanie, które nie używa wzmocnienia, ale używa dobrej metody łączenia skrótów:

namespace std
{
    template <>
    struct hash<Key>
    {
        size_t operator()( const Key& k ) const
        {
            // Compute individual hash values for first, second and third
            // http://stackoverflow.com/a/1646913/126995
            size_t res = 17;
            res = res * 31 + hash<string>()( k.first );
            res = res * 31 + hash<string>()( k.second );
            res = res * 31 + hash<int>()( k.third );
            return res;
        }
    };
}
jogojapan
źródło
11
Czy możesz wyjaśnić, dlaczego konieczne jest przesunięcie bitów KeyHasher?
Chani,
45
Jeśli nie przesuniesz bitów, a dwa ciągi będą takie same, xor spowoduje, że się skasują. Tak więc hash („a”, „a”, 1) będzie taki sam jak hash („b”, „b”, 1). Również kolejność nie ma znaczenia, więc skrót („a”, „b”, 1) byłby taki sam jak skrót („b”, „a”, 1).
Buge
1
Uczę się tylko C ++ i zawsze mam problem: gdzie umieścić kod? Tak jak ty, napisałem specjalizującą się std::hashmetodę dla mojego klucza. Ja to w dolnej części mojego pliku Key.cpp ale otrzymuję następujący błąd: Error 57 error C2440: 'type cast' : cannot convert from 'const Key' to 'size_t' c:\program files (x86)\microsoft visual studio 10.0\vc\include\xfunctional. Zgaduję, że kompilator nie znajduje mojej metody mieszania? Czy powinienem coś dodawać do mojego pliku Key.h?
Ben,
4
@Ben Umieszczenie go w pliku .h jest poprawne. std::hashnie jest w rzeczywistości struct, ale szablonem (specjalizacją) dla struct . Więc to nie jest implementacja - zostanie przekształcona w implementację, gdy kompilator będzie jej potrzebował. Szablony powinny zawsze wchodzić do plików nagłówkowych. Zobacz także stackoverflow.com/questions/495021/…
jogojapan
3
@nightfury find()zwraca iterator, który wskazuje na „wejście” mapy. Wpis std::pairskłada się z klucza i wartości. Więc jeśli to zrobisz auto iter = m6.find({"John","Doe",12});, dostaniesz klucz iter->firsti wartość (tj. Ciąg "example") w iter->second. Jeśli chcesz bezpośrednio napisu, możesz użyć m6.at({"John","Doe",12})(spowoduje to wyjątek, jeśli klucz nie wyjdzie) lub m6[{"John","Doe",12}](utworzy pustą wartość, jeśli klucz nie istnieje).
jogojapan
16

Myślę, że jogojapan udzielił bardzo dobrej i wyczerpującej odpowiedzi . Zdecydowanie powinieneś rzucić na to okiem, zanim przeczytasz mój post. Chciałbym jednak dodać następujące:

  1. Możesz zdefiniować funkcję porównania unordered_maposobno, zamiast używać operatora porównania równości ( operator==). Może to być pomocne, na przykład, jeśli chcesz użyć tego ostatniego do porównania wszystkich członków dwóch Nodeobiektów ze sobą, ale tylko niektórych określonych członków jako klucza an unordered_map.
  2. Możesz także użyć wyrażeń lambda zamiast definiować funkcje skrótu i ​​porównania.

Podsumowując, dla twojej Nodeklasy kod można zapisać w następujący sposób:

using h = std::hash<int>;
auto hash = [](const Node& n){return ((17 * 31 + h()(n.a)) * 31 + h()(n.b)) * 31 + h()(n.c);};
auto equal = [](const Node& l, const Node& r){return l.a == r.a && l.b == r.b && l.c == r.c;};
std::unordered_map<Node, int, decltype(hash), decltype(equal)> m(8, hash, equal);

Uwagi:

  • Właśnie ponownie wykorzystane metody haszowania na końcu odpowiedź jogojapan, ale można znaleźć pomysł na bardziej ogólne rozwiązanie tutaj (jeśli nie chcesz używać Boost).
  • Mój kod jest może trochę zbyt mały. Aby uzyskać nieco bardziej czytelną wersję, zobacz ten kod w Ideone .
dźwięk klaksonu
źródło
skąd pochodzi 8 i co to oznacza?
AndiChin
@WhalalalalalalaCHen: Proszę spojrzeć na dokumentację unordered_mapkonstruktora . 8Reprezentuje tzw „Count wiadro”. Wiadro to miejsce w wewnętrznej tabeli mieszającej kontenera, patrz np. unordered_map::bucket_countWięcej informacji.
honk
@WhalalalalalalaCHen: Wybrałem 8losowo. W zależności od zawartości, którą chcesz przechowywać unordered_map, liczba segmentów może wpływać na wydajność kontenera.
honk