unión - ¿Cómo hacer un conjunto desordenado de pares de enteros en C++?

teoria de conjuntos python

Question

El programa no compila un conjunto desordenado de pares de enteros, pero lo hace para los enteros. ¿Se puede usar unordered_set y sus funciones miembro en tipos definidos por el usuario, y cómo puedo definirlo?

#include <unordered_set>
...

class A{
...
private: 
std::unordered_set< std::pair<int, int> > u_edge_;
};

error: no matching function for call to ''std::unordered_set<std::pair<unsigned int, unsigned int> >::unordered_set()''

Answer 1

Debe proporcionar una especialización para std::hash<> que funcione con std::pair<int, int> . Aquí hay un ejemplo muy simple de cómo podría definir la especialización:

#include <utility>
#include <unordered_set>

namespace std
{
    template<>
    struct hash<std::pair<int, int>>
    {
        size_t operator () (std::pair<int, int> const& p)
        {
            // A bad example of computing the hash, 
            // rather replace with something more clever
            return (std::hash<int>()(p.first) + std::hash<int>()(p.second));
        }
    };
}

class A
{
private:
    // This won''t give you problems anymore
    std::unordered_set< std::pair<int, int> > u_edge_;
};

Answer 2

El problema es que std::unordered_set usa la plantilla std::hash para calcular los hashes para sus entradas y no hay especialización std::hash para los pares. Entonces deberás hacer dos cosas:

1. Decide qué función hash quieres usar.
2. Especialice std::hash para su tipo de clave ( std::pair<int, int> ) utilizando esa función.

Aquí hay un ejemplo simple:

#include <unordered_set>

namespace std {
template <> struct hash<std::pair<int, int>> {
    inline size_t operator()(const std::pair<int, int> &v) const {
        std::hash<int> int_hasher;
        return int_hasher(v.first) ^ int_hasher(v.second);
    }
};

}

int main()
{
    std::unordered_set< std::pair<int, int> > edge;
}

Answer 3

Falta una función hash para std::pair<int, int>> . Por ejemplo,

struct bad_hash
{
  std::size_t operator()(const std::pair<int,int>& p) const
  {
    return 42;
  }
};

....

std::unordered_set< std::pair<int, int>, bad_hash> u_edge_;

También puede especializar std::hash<T> para std::hash<std::pair<int,int>> , en cuyo caso puede omitir el segundo parámetro de plantilla.

Answer 4

Las otras respuestas aquí sugieren que se cree una función hash que de alguna manera combine sus dos enteros.

Esto funcionará, pero produce hashes no únicos. Aunque esto está bien para el uso de unordered_set , para algunas aplicaciones puede ser inaceptable. En su caso, si elige una función hash incorrecta, puede provocar muchas colisiones innecesarias.

¡Pero puedes producir hashes únicos!

int es generalmente 4 bytes. Puedes hacer esto explícito usando int32_t .

El tipo de datos del hash es std::size_t . En la mayoría de las máquinas, esto es de 8 bytes. Puede verificar esto en la compilación.

Como un par consta de dos tipos int32_t , puede poner ambos números en std::size_t para crear un hash único.

Esto se parece a esto (no puedo recordar cómo obligar al compilador a tratar un valor firmado como si no hubiera sido firmado para la manipulación de bits, así que escribí lo siguiente para uint32_t ):

#include <cassert>
#include <cstdint>
#include <unordered_set>
#include <utility>


struct IntPairHash {
  std::size_t operator()(const std::pair<uint32_t, uint32_t> &p) const {
    assert(sizeof(std::size_t)>=8);  //Ensure that std::size_t, the type of the hash, is large enough
    //Shift first integer over to make room for the second integer. The two are
    //then packed side by side.
    return (((uint64_t)p.first)<<32) | ((uint64_t)p.second);
  }
};

int main(){
  std::unordered_set< std::pair<uint32_t, uint32_t>, IntPairHash> uset;
  uset.emplace(10,20);
  uset.emplace(20,30);
  uset.emplace(10,20);
  assert(uset.size()==2);
}

Answer 5

No hay una forma estándar de calcular un hash en un par. Agregue esta definición a su archivo:

struct pair_hash {
    inline std::size_t operator()(const std::pair<int,int> & v) const {
        return v.first*31+v.second;
    }
};

Ahora puedes usarlo así:

std::unordered_set< std::pair<int, int>,  pair_hash> u_edge_;

Esto funciona, porque el pair<T1,T2> define la igualdad. Para las clases personalizadas que no proporcionan una forma de probar la igualdad, es posible que deba proporcionar una función separada para probar si dos instancias son iguales entre sí.

Por supuesto, esta solución está limitada a un par de dos enteros. Aquí hay un enlace a una respuesta que lo ayuda a definir una forma más general de hacer hash para múltiples objetos.

Answer 6

Su código se compila en VS2010 SP1 (VC10), pero no compila con GCC g ++ 4.7.2.

Sin embargo, es posible que desee considerar boost::hash de Boost.Functional para hash a std::pair (con esta adición, su código se compila también con g ++).

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

class A
{
private: 
    std::unordered_set< 
        std::pair<int, int>, 
        boost::hash< std::pair<int, int> > 
    > u_edge_;
};