C ++ unordered_map usando um tipo de class personalizado como chave

Eu estou tentando usar uma class personalizada como chave para unordered_map, como o seguinte,

#include  #include  #include  //#include  using namespace std; class node; class Solution; class Node { public: int a; int b; int c; Node(){} Node(vector v) { sort(v.begin(), v.end()); a = v[0]; b = v[1]; c = v[2]; } bool operator==(Node i) { if ( ia==this->a && ib==this->b &&i.c==this->c ) { return true; } else { return false; } } }; int main() { unordered_map m; vector v; v.push_back(3); v.push_back(8); v.push_back(9); Node n(v); m[n] = 0; return 0; } 

Eu acho que eu preciso dizer ao C ++ como hash class Node, no entanto, não tenho certeza como fazê-lo. Existe algum exemplo para esse tipo de tarefa?

O seguinte é o erro do g + +:

 In file included from /usr/include/c++/4.6/string:50:0, from /usr/include/c++/4.6/bits/locale_classs.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::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::_M_compare(const _Key&, std::__detail::_Hash_code_base::_Hash_code_type, std::__detail::_Hash_node*) const [with _Key = Node, _Value = std::pair, _ExtractKey = std::_Select1st<std::pair >, _Equal = std::equal_to, _H1 = std::hash, _H2 = std::__detail::_Mod_range_hashing, std::__detail::_Hash_code_base::_Hash_code_type = long unsigned int]' /usr/include/c++/4.6/bits/hashtable.h:897:2: instantiated from 'std::_Hashtable::_Node* std::_Hashtable::_M_find_node(std::_Hashtable::_Node*, const key_type&, typename std::_Hashtable::_Hash_code_type) const [with _Key = Node, _Value = std::pair, _Allocator = std::allocator<std::pair >, _ExtractKey = std::_Select1st<std::pair >, _Equal = std::equal_to, _H1 = std::hash, _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::_Node = std::__detail::_Hash_node<std::pair, false>, std::_Hashtable::key_type = Node, typename std::_Hashtable::_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, true, _Hashtable>::mapped_type& std::__detail::_Map_base<_Key, _Pair, std::_Select1st, true, _Hashtable>::operator[](const _Key&) [with _Key = Node, _Pair = std::pair, _Hashtable = std::_Hashtable<Node, std::pair, std::allocator<std::pair >, std::_Select1st<std::pair >, std::equal_to, std::hash, 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, 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 

    Para poder usar std::unordered_map (ou um dos outros contêineres associativos não-ordenados) com um tipo de chave definido pelo usuário, você precisa definir duas coisas:

    1. Uma function hash ; essa deve ser uma class que substitui operator() e calcula o valor de hash dado a um object do tipo de chave. Uma maneira particularmente direta de fazer isso é especializar o modelo std::hash para o tipo de chave.

    2. Uma function de comparação para igualdade ; isso é necessário porque o hash não pode confiar no fato de que a function hash sempre fornecerá um valor de hash exclusivo para cada chave distinta (ou seja, ele precisa ser capaz de lidar com colisões), portanto, precisa de uma maneira de comparar duas chaves dadas para uma correspondência exata. Você pode implementar isto como uma class que substitui operator() , ou como uma especialização de std::equal , ou – o mais fácil de tudo – sobrecarregando o operator==() para o seu tipo de chave (como você já fez).

    A dificuldade com a function hash é que se o seu tipo de chave consistir em vários membros, você normalmente terá a function hash para calcular os valores de hash dos membros individuais e, de alguma forma, combiná-los em um valor de hash para o object inteiro. Para um bom desempenho (ou seja, poucas colisões), você deve pensar cuidadosamente sobre como combinar os valores de hash individuais para garantir que você evite obter a mesma saída para objects diferentes com muita frequência.

    Um ponto de partida bastante bom para uma function hash é aquele que usa o deslocamento de bit e o XOR bit a bit para combinar os valores de hash individuais. Por exemplo, assumindo um tipo de chave como este:

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

    Aqui está uma function hash simples (adaptada daquela usada no exemplo de cppreference para funções hash definidas pelo usuário ):

     namespace std { template <> struct hash { 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()(k.first) ^ (hash()(k.second) < < 1)) >> 1) ^ (hash()(k.third) < < 1); } }; } 

    Com isso, você pode instanciar um std::unordered_map para o tipo de chave:

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

    Ele usará automaticamente std::hash como definido acima para os cálculos de valor de hash e o operator== definido como function de membro de Key for equality checks.

    Se você não quiser especializar o template dentro do namespace std (embora seja perfeitamente legal neste caso), você pode definir a function hash como uma class separada e adicioná-la à lista de argumentos do template para o mapa:

     struct KeyHasher { std::size_t operator()(const Key& k) const { using std::size_t; using std::hash; using std::string; return ((hash()(k.first) ^ (hash()(k.second) < < 1)) >> 1) ^ (hash()(k.third) < < 1); } }; int main() { std::unordered_map m6 = { { {"John", "Doe", 12}, "example"}, { {"Mary", "Sue", 21}, "another"} }; } 

    Como definir uma melhor function hash? Como dito acima, definir uma boa function hash é importante para evitar colisões e obter um bom desempenho. Para um bem real, você precisa levar em conta a distribuição de valores possíveis de todos os campos e definir uma function hash que projeta essa distribuição para um espaço de resultados possíveis tão amplo e uniformemente distribuído quanto possível.

    Isso pode ser difícil; o método XOR / bit-shifting acima provavelmente não é um mau começo. Para um início um pouco melhor, você pode usar o modelo de function hash_combine e hash_combine da biblioteca Boost. O primeiro age de maneira semelhante ao std::hash para tipos padrão (incluindo também tuplas e outros tipos de padrões úteis); o último ajuda a combinar valores de hash individuais em um. Aqui está uma reescrita da function hash que usa as funções auxiliares do Boost:

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

    E aqui está uma reescrita que não usa boost, mas usa um bom método de combinar os hashes:

     namespace std { template <> struct hash { 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()( k.first ); res = res * 31 + hash()( k.second ); res = res * 31 + hash()( k.third ); return res; } }; }