unordered_map con par como clave – no comstackndo

Estoy tratando de crear un mapa sin ordenar para mapear pares con números enteros.

#include  using namespace std; using Vote = pair; using Unordered_map = unordered_map; 

Tengo una clase donde he declarado un Unordered_map como un miembro privado.

Sin embargo, recibo este error cuando bash comstackr:

 /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/type_traits:948:38: Implicit instantiation of undefined template 'std::__1::hash<std::__1::pair<std::__1::basic_string, std::__1::basic_string > >' 

No obtengo este error si utilizo un mapa normal como map<pair, int> lugar de un unordered_map.

¿No es posible usar el pair como clave en los mapas desordenados?

Debe proporcionar una función hash adecuada para su tipo de clave. Un simple ejemplo:

 #include  #include  #include  #include  // Only for pairs of std::hash-able types for simplicity. // You can of course template this struct to allow other hash functions struct pair_hash { template  std::size_t operator () (const std::pair &p) const { auto h1 = std::hash{}(p.first); auto h2 = std::hash{}(p.second); // Mainly for demonstration purposes, ie works but is overly simple // In the real world, use sth. like boost.hash_combine return h1 ^ h2; } }; using Vote = std::pair; using Unordered_map = std::unordered_map; int main() { Unordered_map um; } 

Esto funcionará, pero no tendrá las mejores propiedades de hash . Es posible que desee echar un vistazo a algo como boost.hash_combine para obtener resultados de mayor calidad al combinar los boost.hash_combine hash.

Para uso en el mundo real: Boost también proporciona el conjunto de funciones hash_value que ya proporciona una función hash para std::pair , así como std::tuple y la mayoría de los contenedores estándar.


Más precisamente, producirá demasiadas colisiones. Por ejemplo, cada par simétrico tendrá hash a 0 y los pares que difieren solo por permutación tendrán el mismo hash. Esto probablemente esté bien para su ejercicio de progtwigción, pero podría dañar seriamente el rendimiento del código del mundo real.

Mi forma preferida de resolver este problema es definir una función de key que transforma su par en un entero único (o cualquier tipo de datos con capacidad de lectura). Esta clave no es la tecla hash. Es el ID único del par de datos que será correlacionado de manera óptima por el unordered_map . Por ejemplo, quería definir un unordered_map del tipo

  unordered_map,double> Map; 

Y desea usar Map[make_pair(i,j)]=value o Map.find(make_pair(i,j)) para operar en el mapa. Luego tendrás que decirle al sistema cómo hash un par de enteros make_pair(i,j) . En lugar de eso, podemos definir

  inline size_t key(int i,int j) {return (size_t) i << 32 | (unsigned int) j;} 

y luego cambia el tipo de mapa a

  unordered_map Map; 

Ahora podemos usar Map[key(i,j)]=value o Map.find(key(i,j)) para operar en el mapa. Cada make_pair ahora se convierte en llamar a la función de key línea.

Este método garantiza que la clave será hasheada de manera óptima, porque ahora la parte de hash es realizada por el sistema, que siempre seleccionará el tamaño de la tabla de hash interna para ser primordial para asegurarse de que cada cubeta sea igualmente probable. Pero tienes que estar 100% seguro de que la key es única para cada par, es decir, no hay dos pares distintos que puedan tener la misma clave, o puede haber errores muy difíciles de encontrar.

Como indica su error de comstackción, no hay una instanciación válida de std::hash> en su espacio de nombres std.

De acuerdo con mi comstackdor:

Error C2338 El estándar de C ++ no proporciona un hash para este tipo. c: \ archivos de progtwig (x86) \ microsoft visual studio 14.0 \ vc \ include \ xstddef 381

Puede proporcionar su propia especialización para std::hash siguiente manera:

 #include  #include  #include  using namespace std; using Vote = pair; using Unordered_map = unordered_map; namespace std { template<> struct hash { size_t operator()(Vote const& v) const { // ... hash function here ... } }; } int main() { Unordered_map m; } 

Para la clave de par, podemos usar la función hash boost pair:

 #include  #include  #include  using namespace std; int main() { unordered_map, int, boost::hash>> m; m[make_pair("123", "456")] = 1; cout << m[make_pair("123", "456")] << endl; return 0; } 

Del mismo modo, podemos usar boost hash para vectores,

 #include  #include  #include  #include  using namespace std; int main() { unordered_map, int, boost::hash>> m; vector a({"123", "456"}); m[a] = 1; cout << m[a] << endl; return 0; }