c++ - Compruebe si el tipo es hashable

c++11 sfinae

Question

Me gustaría hacer un rasgo de tipo para verificar si un tipo particular es hashable usando las instancias predeterminadas de los contenedores desordenados de la biblioteca estándar, por lo tanto, si tiene una especialización válida para std::hash . Creo que esta sería una característica muy útil (por ejemplo, para usar std::set como failafe para std::unordered_set en código genérico). Entonces, pensando que std::hash no está definido para cada tipo, comencé a hacer la siguiente solución SFINAE:

template<typename T> std::true_type hashable_helper(
    const T&, const typename std::hash<T>::argument_type* = nullptr);

template<typename T> std::false_type hashable_helper(...);

//It won''t let me derive from decltype directly, why?
template<typename T> struct is_hashable 
    : std::is_same<decltype(hashable_helper<T>(std::declval<T>())),
                   std::true_type> {};

(Perdone mis modestas habilidades de SFINAE si esta no es la mejor solución o si está mal).

Pero luego aprendí que tanto gcc 4.7 como VC ++ 2012 definen std::hash para cualquier tipo T , solo static_assert ing en la versión no especializada. Pero en lugar de compilar de forma condicional, ellos (y también clang 3.1 usando libstdc ++ de gcc 4.7 ) fallan la afirmación, lo que resulta en un error de compilación. Esto parece razonable, ya que creo que static_assert s no son manejados por SFINAE (¿verdad?), Por lo que parece que una solución SFINAE no es posible en absoluto. Es aún peor para gcc 4.6 que ni siquiera tiene static_assert en la plantilla general std::hash pero simplemente no define su operador () , lo que genera un error de vinculador al intentar usarlo (que siempre es peor que un compile error y no puedo imaginar ninguna forma de transformar un error de vinculador en un error de compilación).

Entonces, ¿hay alguna forma compatible y estándar de definir un rasgo de tipo que devuelva si un tipo tiene una especialización estándar std::hash , o quizás al menos para las bibliotecas static_assert ing en la plantilla general (de alguna manera transformando el error static_assert en un SFINAE sin error)?

Answer 1

Aquí hay una solución MUY sucia para su problema: funciona para GCC 4.7 (y no 4.6, debido a la función que falta en C ++ 11: sobrecarga de manipulación)

// is_hashable.h
namespace std {
    template <class T>
    struct hash {
        typedef int not_hashable;
    };

}

#define hash hash_
#define _Hash_impl _Hash_impl_
#include<functional>
#undef hash
#undef _Hash_impl

namespace std {
    struct _Hash_impl: public std::_Hash_impl_{
        template <typename... Args>
            static auto hash(Args&&... args) 
                -> decltype(hash_(std::forward<Args>(args)...)) {
             return hash_(std::forward<Args>(args)...);
        }
    };
    template<> struct hash<bool>: public hash_<bool> {};
    // do this exhaustively for all the hashed standard types listed in:
    // http://en.cppreference.com/w/cpp/utility/hash
}

template <typename T>
class is_hashable
{
    typedef char one;
    typedef long two;

    template <typename C> static one test( typename std::hash<C>::not_hashable ) ;
    template <typename C> static two test(...);


public:
    enum { value = sizeof(test<T>(0)) == sizeof(long) };
};


// main.cpp
// #include "is_hashable.h"
#include<iostream>
#include<unordered_set>

class C {};

class D {
public:
    bool operator== (const D & other) const {return true;}
};

namespace std {
    template <> struct hash<D> {
        size_t operator()(const D & d) const { return 0;}
    };
}

int main() {
    std::unordered_set<bool> boolset; 
    boolset.insert(true);
    std::unordered_set<D> dset; 
    dset.insert(D());// so the hash table functions
    std::cout<<is_hashable<bool>::value<<", ";
    std::cout<<is_hashable<C>::value << ", ";
    std::cout<<is_hashable<D>::value << "/n";
}

Y la salida es:

1, 0, 1

Básicamente, "secuestramos" el símbolo de hash e inyectamos un poco de typedef auxiliar en él. Tendrá que modificarlo para VC ++, en particular, la solución para _Hash_impl::hash() ya que es un detalle de implementación.

Si te aseguras de que la sección etiquetada como is_hashable.h esté incluida como la primera, este truco sucio debería funcionar ...

Answer 2

Desde C ++ 17 ahora es posible hacerlo de una manera más elegante. De cppreference sobre std :: hash:

Cada especialización de esta plantilla está habilitada ("no contaminada") o deshabilitada ("envenenada"). Para cada tipo de clave para la cual ni la biblioteca ni el usuario proporcionan una especialización habilitada std :: hash, esa especialización existe y está deshabilitada. Las especializaciones deshabilitadas no satisfacen Hash, no satisfacen FunctionObject, y std :: is_default_constructible_v, std :: is_copy_constructible_v, std :: is_move_constructible_v, std :: is_copy_assignable_v, std :: is_move_assignable_v son todas falsas. En otras palabras, existen, pero no se pueden utilizar.

Esto significaba que la STL tenía que eliminar el static_assert en C ++ 17. Aquí hay una solución de trabajo con ''Clang-6.0.0 -std = c ++ 17'':

#include <functional>
#include <ios>
#include <iostream>
#include <type_traits>

template <typename T, typename = std::void_t<>>
struct is_std_hashable : std::false_type { };

template <typename T>
struct is_std_hashable<T, std::void_t<decltype(std::declval<std::hash<T>>()(std::declval<T>()))>> : std::true_type { };

template <typename T>
constexpr bool is_std_hashable_v = is_std_hashable<T>::value; 

struct NotHashable {};

int main()
{
    std::cout << std::boolalpha;
    std::cout << is_hashable_v<int> << std::endl;
    std::cout << is_hashable_v<NotHashable> << std::endl;
    return 0;
}

Esto, por ejemplo, puede ser útil cuando usa boost::hash_combine o boost::hash_range . Si incluye un encabezado que contiene el siguiente ejemplo de código, ya no necesita definir los hashes de refuerzo para tipos específicos.

#include <boost/functional/hash_fwd.hpp>

template <typename T, typename = std::void_t<>>
struct is_boost_hashable : std::false_type { };

template <typename T>
struct is_boost_hashable<T, std::void_t<decltype(boost::hash_value(std::declval<T>()))>> : std::true_type { };

template <typename T>
constexpr bool is_boost_hashable_v = is_boost_hashable<T>::value;  

namespace boost
{
    template <typename T>
    auto hash_value(const T &arg) -> std::enable_if_t<is_std_hashable_v<T> &&
                                                      !is_boost_hashable_v<T>, std::size_t>
    {
        return std::hash<T>{}(arg);
    }
}

Tenga en cuenta que is_boost_hashable_v , esto es necesario para evitar la ambigüedad, ya que el impulso ya proporciona hashes para muchos hashes.

Answer 3

Golpeé esto también. Probé algunas soluciones y fui con un filtro de lista blanca para std::hash<> . La lista blanca no es agradable de mantener, pero es segura y funciona.

Intenté esto en VS 2013, 2015, clang y gcc.

#include <iostream>
#include <type_traits>

// based on Walter Brown''s void_t proposal
// http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3911.pdf
namespace detail {
    template<class... TN> struct void_t {typedef void type;};
}
template<class... TN>
struct void_t {typedef typename detail::void_t<TN...>::type type;};

// extensible whitelist for std::hash<>
template <class T, typename = void> 
struct filtered_hash;
template <class T> 
struct filtered_hash<T, 
    typename std::enable_if<std::is_enum<T>::value>::type> 
    : std::hash<T> {
};
template <class T> 
struct filtered_hash<T, 
    typename std::enable_if<std::is_integral<T>::value>::type> 
    : std::hash<T> {
};
template <class T> 
struct filtered_hash<T, 
    typename std::enable_if<std::is_pointer<T>::value>::type> 
    : std::hash<T> {
};

template<typename, typename = void>
struct is_hashable
    : std::false_type {};

template<typename T>
struct is_hashable<T, 
    typename void_t<
        typename filtered_hash<T>::result_type, 
        typename filtered_hash<T>::argument_type, 
        typename std::result_of<filtered_hash<T>(T)>::type>::type>
    : std::true_type {};

// try it out..
struct NotHashable {};

static_assert(is_hashable<int>::value, "int not hashable?!");
static_assert(!is_hashable<NotHashable>::value, "NotHashable hashable?!");

int main()
{
    std::cout << "Hello, world!/n";
}

Answer 4

Parece que tenemos dos requisitos conflictivos:

1. El objetivo de SFINAE es evitar cualquier creación de instancias de una plantilla si la instanciación puede fallar y eliminar la función correspondiente del conjunto de sobrecarga.
2. static_assert() está destinado a crear un error, por ejemplo, durante la creación de instancias de una plantilla.

En mi opinión, 1. claramente triunfa sobre 2. Es decir, su SFINA debería funcionar. Desde el aspecto de dos proveedores de compiladores separados no están de acuerdo, desafortunadamente no entre ellos sino conmigo. El estándar no parece especificar cómo se ve la definición predeterminada de std::hash<T> y parece imponer restricciones solo para los casos en que std::hash<T> está especializado para un tipo T

Creo que los rasgos de tipo propuestos son una idea razonable y deberían apoyarse. Sin embargo, parece que el estándar no garantiza que se pueda implementar. Puede valer la pena mencionar esto a los proveedores del compilador y / o presentar un informe de defectos para el estándar: la especificación actual no proporciona una guía clara de lo que debería suceder, por lo que puedo decir. ... y si la especificación actualmente exige que un tipo de características como la anterior falla, puede ser un error de diseño que debe corregirse.