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

⏰ 14 minutos de lectura

C unordered map usando un tipo de clase personalizado como
Alfredo Zhong

Estoy tratando de usar una clase personalizada como clave para un unordered_mapcomo 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 de clase Node, sin embargo, no estoy muy seguro de cómo hacerlo. ¿Cómo puedo realizar estas tareas?

1647563412 941 C unordered map usando un tipo de clase personalizado como
jogojapan

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

  1. A 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 hacer esto es especializar el std::hash plantilla para su tipo de clave.

  2. A 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 poder manejar 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 de std::equalo, lo más fácil de todo, sobrecargando operator==() para 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, normalmente hará que la función hash calcule los valores hash para los miembros individuales y luego los combine de alguna manera en un valor hash para todo el objeto. Para un buen rendimiento (es decir, pocas colisiones), debe pensar detenidamente en cómo combinar los valores hash individuales para asegurarse de evitar obtener el mismo resultado para diferentes objetos con demasiada frecuencia.

Un punto de partida bastante bueno para una función hash es uno que utiliza el 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 de 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 instanciar un std::unordered_map para 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 el operator== definida como función miembro de Key para comprobaciones de igualdad.

Si no desea especializar la plantilla dentro de la std espacio 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, definir una buena función hash es importante para evitar colisiones y obtener un buen rendimiento. Para uno 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/bit-shifting anterior probablemente no sea un mal comienzo. Para un comienzo un poco mejor, puede usar el hash_value y hash_combine plantilla de función de la biblioteca Boost. El primero actúa de manera similar a std::hash para tipos estándar (recientemente también incluye tuplas y otros tipos estándar útiles); este último lo ayuda a combinar valores hash individuales en uno. Aquí hay una reescritura de la función hash que usa las funciones auxiliares de 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;
        }
    };
}

  • ¿Puede explicar por qué es necesario cambiar los bits en KeyHasher ?

    – Chani

    12/08/2014 a las 17:39

  • Si no cambiara los bits y dos cadenas fueran 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

    29/08/2014 a las 15:40

  • Estoy aprendiendo C++ y una cosa con la que siempre lucho es: ¿Dónde poner el código? He escrito un especial std::hash método para mi clave como lo has hecho. Puse esto en la parte inferior de mi archivo Key.cpp pero recibo el siguiente error: 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? ¿Debería agregar algo a mi archivo Key.h?

    – ben

    7 febrero 2015 a las 17:13

  • @Ben Ponerlo en el archivo .h es correcto. std::hash no es en realidad 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 lo necesite. Las plantillas siempre deben ir en los archivos de encabezado. Consulte también stackoverflow.com/questions/495021/…

    – jogojapan

    8 de febrero de 2015 a las 1:02

  • @Furia Nocturna find() devuelve un iterador, y ese iterador apunta a una “entrada” del mapa. Una entrada es un std::pair que consta de clave y valor. entonces si lo haces auto iter = m6.find({"John","Doe",12});obtendrás la llave iter->first y el valor (es decir, la cadena "example") en iter->second. Si desea la cadena directamente, puede usar m6.at({"John","Doe",12}) (que lanzará una excepción si la clave no sale), o m6[{"John","Doe",12}] (eso creará un valor vacío si la clave no existe).

    – jogojapan

    21 de abril de 2015 a las 8:12

Creo, 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 para un unordered_map por separado, 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 Node objetos entre s, sino slo algunos miembros especficos como clave de un unordered_map.
  2. También puedes usar expresiones lambda en lugar de definir las funciones hash y de comparación.

En definitiva, para su Node clase, 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 hash al final de la respuesta de jogojapan, pero puede encontrar la idea de una solución más general aquí (si no desea usar Boost).
  • Mi código es quizás un poco demasiado minimizado. Para una versión un poco más legible, por favor vea este código en Ideone.

  • ¿De dónde vino el 8 y qué significa?

    – Andi Chin

    14 de febrero de 2020 a las 22:42

  • @WhalalalalalalaCHen: Por favor, eche un vistazo a la documentación de la unordered_map constructor. los 8 representa el llamado “recuento de cubos”. Un cubo es una ranura en la tabla hash interna del contenedor, consulte, por ejemplo unordered_map::bucket_count para más información.

    – tocar la bocina

    15 de febrero de 2020 a las 8:23

  • @WhalalalalalalaCHen: Elegí 8 al azar. Dependiendo del contenido que desee almacenar en su unordered_mapel recuento de cubos puede afectar el rendimiento del contenedor.

    – tocar la bocina

    15 de febrero de 2020 a las 8:27

El ejemplo ejecutable completo de copiar/pegar más básico posible del uso de una clase personalizada como clave para un unordered_map (implementación básica de una matriz dispersa):

// UnorderedMapObjectAsKey.cpp

#include <iostream>
#include <vector>
#include <unordered_map>

struct Pos
{
  int row;
  int col;

  Pos() { }
  Pos(int row, int col)
  {
    this->row = row;
    this->col = col;
  }

  bool operator==(const Pos& otherPos) const
  {
    if (this->row == otherPos.row && this->col == otherPos.col) return true;
    else return false;
  }

  struct HashFunction
  {
    size_t operator()(const Pos& pos) const
    {
      size_t rowHash = std::hash<int>()(pos.row);
      size_t colHash = std::hash<int>()(pos.col) << 1;
      return rowHash ^ colHash;
    }
  };
};

int main(void)
{
  std::unordered_map<Pos, int, Pos::HashFunction> umap;

  // at row 1, col 2, set value to 5
  umap[Pos(1, 2)] = 5;

  // at row 3, col 4, set value to 10
  umap[Pos(3, 4)] = 10;

  // print the umap
  std::cout << "\n";
  for (auto& element : umap)
  {
    std::cout << "( " << element.first.row << ", " << element.first.col << " ) = " << element.second << "\n";
  }
  std::cout << "\n";

  return 0;
}

Para el tipo de enumeración, creo que esta es una forma adecuada, y la diferencia entre clases es cómo calcular el valor hash.

template <typename T>
struct EnumTypeHash {
  std::size_t operator()(const T& type) const {
    return static_cast<std::size_t>(type);
  }
};

enum MyEnum {};
class MyValue {};

std::unordered_map<MyEnum, MyValue, EnumTypeHash<MyEnum>> map_;

STL No proporciona función hash para pares. Debe implementarlo usted mismo y especificarlo como parámetro de plantilla o colocarlo en el espacio de nombres estándar, desde donde se recogerá automáticamente. Siguiente https://github.com/HowardHinnant/hash_append/blob/master/n3876.h es muy útil para implementar funciones hash personalizadas para estructuras. Más detalles están bien explicados en las otras respuestas a esta pregunta, por lo que no repetiré eso. También hay algo similar (hash_combine) en el Impulso.

1647563413 577 C unordered map usando un tipo de clase personalizado como
ReyEze

consulta el siguiente enlace https://www.geeksforgeeks.org/how-to-create-an-unordered_map-of-user-defined-class-in-cpp/ para más detalles.

  • la clase personalizada debe implementar el operador ==
  • debe crear una función hash para la clase (para tipos primitivos como int y también tipos como string, la función hash está predefinida)

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad