función hash unordered_map c++

unordered-map hash-function

Question

Necesito definir un mapa de orden no ordenado como este: unordered_map<pair<int, int>, *Foo> , ¿cuál es la sintaxis para definir y pasar un hash y funciones equal a este mapa?

He intentado pasarle este objeto:

class pairHash{
public:
    long operator()(const pair<int, int> &k) const{
        return k.first * 100 + k.second;
    }
};

y sin suerte

unordered_map<pair<int, int>, int> map = unordered_map<pair<int, int>, int>(1,
*(new pairHash()));

No tengo idea de lo que significa size_type_Buskets significa, así que le di 1 . ¿Cuál es la forma correcta de hacerlo? Gracias.

Answer 1

El tipo de retorno de la función hash debe ser size_t , no long (aunque esta no es la causa del error). La sintaxis que has mostrado para proporcionar una función hash personalizada es incorrecta.

También deberá proporcionar un predicado igual para que el trabajo anterior funcione correctamente.

#include <unordered_map>
#include <utility>

using namespace std;

class pairHash{
public:
    size_t operator()(const pair<int, int> &k) const{
        return k.first * 100 + k.second;
    }
};

struct pairEquals : binary_function<const pair<int,int>&, const pair<int,int>&, bool> {
  result_type operator()( first_argument_type lhs, second_argument_type rhs ) const
  {
    return (lhs.first == rhs.first) && (lhs.second == rhs.second);
  }
};     

int main()
{
  unordered_map<pair<int, int>, int, pairHash, pairEquals> myMap;

  myMap[make_pair(10,20)] = 100;
  myMap.insert( make_pair(make_pair(100,200), 1000) );
}

EDITAR:
No es necesario definir el predicado igual ya que el operator== está definido para std::pair y hace exactamente lo que he hecho en pairEquals . Solo necesitará la definición pairEquals si espera que la comparación se realice de manera diferente.

Answer 2

Esta es una omisión desafortunada en C ++ 11; Boost tiene la respuesta en términos de hash_combine . ¡Siéntete libre de solo pegarlo de ellos! Aquí es cómo hash pares:

template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
  std::hash<T> hasher;
  seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

namespace std
{
  template<typename S, typename T> struct hash<pair<S, T>>
  {
    inline size_t operator()(const pair<S, T> & v) const
    {
      size_t seed = 0;
      ::hash_combine(seed, v.first);
      ::hash_combine(seed, v.second);
      return seed;
    }
  };
}

Puede usar hash_combine como la base de muchas otras cosas, como tuplas y rangos, por lo que podría contener un contenedor completo (ordenado), por ejemplo, siempre que cada miembro sea hashable individualmente.

Ahora solo puedes declarar un nuevo mapa:

std::unordered_map<std::pair<int, int>, my_mapped_type> mymap;

Si desea utilizar su máquina homebrew (que no tiene buenas propiedades estadísticas), debe especificar explícitamente los parámetros de la plantilla:

std::unordered_map<std::pair<int,int>, int, pairHash> yourmap;

Tenga en cuenta que no es necesario especificar una copia de un objeto hasher, ya que el valor predeterminado es construir una predeterminada para usted.

Answer 3

Si no está de acuerdo con el uso de Boost, una solución más limpia es confiar en la implementación de la función hash de Boost para pares (que de hecho hace exactamente lo que explica kerrek-sb en su respuesta). Por lo tanto todo lo que tienes que hacer es:

#include <unordered_map>
#include <boost/functional/hash.hpp>

using namespace std;
using namespace boost;

unordered_map<pair<int, int>, int, hash<pair<int, int>>> table;