C ++ unordered_map usando un tipo de clase personalizado como clave

285

Estoy tratando de usar una clase personalizada como clave para un unordered_map , como el siguiente:

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

Sin embargo, g ++ me da el siguiente error:

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

Supongo que necesito decirle a C ++ cómo hacer hash class Node, sin embargo, no estoy muy seguro de cómo hacerlo. ¿Cómo puedo realizar esta tarea?

Alfred Zhong
fuente
2
El tercer argumento de plantilla es la función hash que necesita proporcionar.
chrisaycock
3
cppreference tiene un ejemplo simple y práctico de cómo hacer esto: en.cppreference.com/w/cpp/container/unordered_map/unordered_map
jogojapan

Respuestas:

485

Para poder usar std::unordered_map(o uno de los otros contenedores asociativos no ordenados) con un tipo de clave definido por el usuario, debe definir dos cosas:

  1. Una función hash ; esta debe ser una clase que anula operator()y calcula el valor hash dado un objeto del tipo clave. Una forma particularmente directa de hacerlo es especializar la std::hashplantilla para su tipo de clave.

  2. Una función de comparación para la igualdad ; esto es necesario porque el hash no puede confiar en el hecho de que la función hash siempre proporcionará un valor hash único para cada clave distinta (es decir, debe ser capaz de lidiar con colisiones), por lo que necesita una forma de comparar dos claves dadas para una coincidencia exacta Puede implementar esto como una clase que anula operator(), o como una especialización std::equalo, lo más fácil de todo, al sobrecargar operator==()su tipo de clave (como ya lo hizo).

La dificultad con la función hash es que si su tipo de clave consta de varios miembros, generalmente tendrá la función hash para calcular valores hash para los miembros individuales y luego, de alguna manera, combinarlos en un valor hash para todo el objeto. Para un buen rendimiento (es decir, pocas colisiones), debe pensar cuidadosamente sobre cómo combinar los valores hash individuales para asegurarse de evitar obtener la misma salida para diferentes objetos con demasiada frecuencia.

Un punto de partida bastante bueno para una función hash es aquel que utiliza desplazamiento de bits y XOR bit a bit para combinar los valores hash individuales. Por ejemplo, suponiendo un tipo de clave 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);
  }
};

Aquí hay una función hash simple (adaptada de la utilizada en el ejemplo cppreference para funciones hash definidas por el usuario ):

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

}

Con esto en su lugar, puede crear una instancia std::unordered_mappara el tipo de clave:

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

Se usará automáticamente std::hash<Key>como se definió anteriormente para los cálculos del valor hash y la función operator==definida como miembro deKey las comprobaciones de igualdad.

Si no desea especializar la plantilla dentro del stdespacio de nombres (aunque es perfectamente legal en este caso), puede definir la función hash como una clase separada y agregarla a la lista de argumentos de la plantilla para el mapa:

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

¿Cómo definir una mejor función hash? Como se dijo anteriormente, es importante definir una buena función hash para evitar colisiones y obtener un buen rendimiento. Para que sea realmente bueno, debe tener en cuenta la distribución de los posibles valores de todos los campos y definir una función hash que proyecte esa distribución en un espacio de posibles resultados lo más amplio y uniformemente distribuido posible.

Esto puede ser difícil; El método XOR / desplazamiento de bits anterior probablemente no sea un mal comienzo. Para comenzar un poco mejor, puede usar la plantilla hash_valuey la hash_combinefunción de la biblioteca Boost. El primero actúa de manera similar std::hasha los tipos estándar (recientemente también incluye tuplas y otros tipos estándar útiles); este último te ayuda a combinar valores hash individuales en uno. Aquí hay una reescritura de la función hash que usa las funciones auxiliares 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;
  }
};

Y aquí hay una reescritura que no usa impulso, pero usa un buen método para combinar los hashes:

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
fuente
11
¿Puede explicar por qué es necesario cambiar los bits KeyHasher?
Chani
45
Si no movió los bits y dos cadenas eran iguales, el xor haría que se cancelaran entre sí. Entonces hash ("a", "a", 1) sería lo mismo que hash ("b", "b", 1). Además, el orden no importaría, por lo que hash ("a", "b", 1) sería lo mismo que hash ("b", "a", 1).
Buge
1
Solo estoy aprendiendo C ++ y una cosa con la que siempre lucho es: ¿Dónde poner el código? He escrito un std::hashmétodo especializado para mi clave como lo ha hecho. Pongo esto en la parte inferior de mi archivo Key.cpp pero estoy consiguiendo el error siguiente: 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. ¿Supongo que el compilador no encuentra mi método hash? ¿Debo agregar algo a mi archivo Key.h?
Ben
44
@Ben Ponerlo en el archivo .h es correcto. std::hashen realidad no es una estructura, sino una plantilla (especialización) para una estructura . Por lo tanto, no es una implementación: se convertirá en una implementación cuando el compilador la necesite. Las plantillas siempre deben ir a los archivos de encabezado. Ver también stackoverflow.com/questions/495021/…
jogojapan
3
@nightfury find()devuelve un iterador, y ese iterador apunta a una "entrada" del mapa. Una entrada std::pairconsiste en una clave y un valor. Entonces, si lo hace auto iter = m6.find({"John","Doe",12});, obtendrá la clave iter->firsty el valor (es decir, la cadena "example") iter->second. Si desea la cadena directamente, puede usar m6.at({"John","Doe",12})(que arrojará una excepción si la clave no sale) o m6[{"John","Doe",12}](que creará un valor vacío si la clave no existe).
jogojapan
16

Creo que jogojapan dio una respuesta muy buena y exhaustiva . Definitivamente deberías echarle un vistazo antes de leer mi publicación. Sin embargo, me gustaría agregar lo siguiente:

  1. Puede definir una función de comparación por unordered_mapseparado, en lugar de utilizar el operador de comparación de igualdad ( operator==). Esto podría ser útil, por ejemplo, si desea utilizar este último para comparar todos los miembros de dos Nodeobjetos entre sí, pero solo algunos miembros específicos como clave de un unordered_map.
  2. También puede usar expresiones lambda en lugar de definir las funciones hash y de comparación.

En general, para su Nodeclase, el código podría escribirse de la siguiente manera:

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

Notas:

  • Acabo de reutilizar el método de hash al final de la respuesta de jogojapan, pero puedes encontrar la idea de una solución más general aquí (si no quieres usar Boost).
  • Mi código está quizás demasiado minimizado. Para una versión un poco más legible, consulte este código en Ideone .
bocinazo
fuente
¿De dónde vino el 8 y qué significa?
AndiChin
@WhalalalalalalaCHen: Por favor, eche un vistazo a la documentación del unordered_mapconstructor . El 8representa el llamado "conteo de cubos". Un cubo es una ranura en la tabla hash interna del contenedor; consulte, por ejemplo, unordered_map::bucket_countpara obtener más información.
tocar la bocina
@WhalalalalalalaCHen: elegí 8al azar. Dependiendo del contenido que desee almacenar en su unordered_map, el recuento de depósitos puede afectar el rendimiento del contenedor.
tocar la bocina