mapa - unordered_map c++ example

¿Por qué no puedo compilar un mapa_desordenado con un par como clave?

Question

Estoy tratando de crear un unordered_map para asignar pares con enteros:

#include <unordered_map>

using namespace std;
using Vote = pair<string, string>;
using Unordered_map = unordered_map<Vote, int>;

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

Sin embargo, recibo el siguiente error cuando intento compilarlo:

/Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/include/c++/v1/type_traits:948:38: instanciación implícita de la plantilla indefinida ''std :: __ 1 :: hash, std :: __ 1: : basic_string>> ''

No obtengo este error si uso un mapa regular como map<pair<string, string>, int> lugar de unordered_map .

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

Answer 1

Como indica su error de compilación, no hay una instancia válida de std::hash<std::pair<std::string, std::string>> en su espacio de nombres std.

De acuerdo con mi compilador:

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

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

#include <string>
#include <unordered_map>
#include <functional>

using namespace std;
using Vote = pair<string, string>;
using Unordered_map = unordered_map<Vote, int>;

namespace std
{
    template<>
    struct hash<Vote>
    {
        size_t operator()(Vote const& v) const
        {
            // ... hash function here ...
        }
    };
}

int main()
{
    Unordered_map m;
}

Answer 2

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

#include <unordered_map>
#include <functional>
#include <string>
#include <utility>

// 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 <class T1, class T2>
    std::size_t operator () (const std::pair<T1,T2> &p) const {
        auto h1 = std::hash<T1>{}(p.first);
        auto h2 = std::hash<T2>{}(p.second);

        // Mainly for demonstration purposes, i.e. works but is overly simple
        // In the real world, use sth. like boost.hash_combine
        return h1 ^ h2;  
    }
};

using Vote = std::pair<std::string, std::string>;
using Unordered_map = std::unordered_map<Vote, int, pair_hash>;

int main() {
    Unordered_map um;
}

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

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á un hash a 0 y los pares que difieran solo por permutación tendrán el mismo hash. Esto probablemente esté bien para su ejercicio de programación, pero podría afectar seriamente el rendimiento del código del mundo real.

Answer 3

En los comentarios sobre la answer de Baum mit Augen , el usuario Joe Black pidió un ejemplo sobre el uso de expresiones lambda en lugar de definir una función hash. Estoy de acuerdo con la opinion de Baum mit Augen , de que esto podría perjudicar la legibilidad, especialmente si desea implementar una solución más universal. Por lo tanto, me gustaría mantener mi ejemplo breve centrándome en una solución específica para std::pair<std::string, std::string> , tal como lo presenta el OP. El ejemplo también utiliza una combinación handcrafted de llamadas de función std::hash<std::string> :

using Vote = std::pair<std::string, std::string>;
auto hash = [](const Vote& v){
    return std::hash<std::string>()(v.first) * 31 + std::hash<std::string>()(v.second);
};
using Unordered_map = std::unordered_map<Vote, int, decltype(hash)>;
Unordered_map um(8, hash);

Código de Ideone

Answer 4

Mi forma preferida de resolver este problema es definir una función key que transforme su par en un número entero único (o cualquier tipo de datos hashaable). Esta clave no es la clave hash. Es la ID única del par de datos que luego será desmejorada óptimamente por el unordered_map . Por ejemplo, desea definir un unordered_map del tipo

  unordered_map<pair<int,int>,double> Map;

Y desea utilizar Map[make_pair(i,j)]=value o Map.find(make_pair(i,j)) para operar en el mapa. Luego tendrá que decirle al sistema cómo make_pair(i,j) 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<size_t,double> 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 la función de key línea.

Este método garantiza que la clave tendrá un hash óptimo, porque ahora el sistema realiza la parte de hashing, que siempre elegirá el tamaño interno de la tabla de hash para que sea primordial y garantizar que cada depósito sea igualmente probable. Pero debe asegurarse al 100% 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.

Answer 5

Para la clave de par, podemos utilizar la función hash de par de refuerzo:

#include <iostream>
#include <boost/functional/hash.hpp>
#include <unordered_map>
using namespace std;

int main() {
  unordered_map<pair<string, string>, int, boost::hash<pair<string, string>>> m;

  m[make_pair("123", "456")] = 1;
  cout << m[make_pair("123", "456")] << endl;
  return 0;
}

Del mismo modo, podemos usar hash de impulso para vectores,

#include <iostream>
#include <boost/functional/hash.hpp>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
  unordered_map<vector<string>, int, boost::hash<vector<string>>> m;
  vector<string> a({"123", "456"});

  m[a] = 1;
  cout << m[a] << endl;
  return 0;
}

Answer 6

Sé que esta es una implementación demasiado ingenua en comparación con otras respuestas, pero hay una solución alternativa.

Si está tomando la entrada de pares, simplemente divida el par con otro entero en un desordenado_hash mientras toma la entrada y luego use este valor integral indirectamente para dividir el par, es decir

unordered_hash<int, Vote> h;
using Unordered_map = unordered_map<i, int>; // i is corresponding value to pair

Answer 7

Si usar pair no es un requisito estricto, simplemente puede usar el mapa dos veces.

#include <unordered_map>

using namespace std;
using Unordered_map = unordered_map<string, unordered_map<string, int>>;

Unordered_map um;
um["Region1"]["Candidate1"] = 10;
cout << um["Region1"]["Candidate1"];    // 10