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

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?

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

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 .