erreur pour la fonction de hachage de la paire d'entiers

J'ai la classe suivante avec un unordered_map membre, et une fonction de hachage définis pour pair<int,int> 

class abc
{public :
    unordered_map < pair<int,int> , int > rules ;
    unsigned nodes;
    unsigned packet ;     
};

namespace std {
template <>
    class hash < std::pair< int,int> >{
    public :
        size_t operator()(const pair< int, int> &x ) const
        {
            size_t h =   std::hash<int>()(x.first) ^ std::hash<int>()(x.second);
            return  h ;
        }
    };
}

Mais j'obtiens les erreurs suivantes : 

error: invalid use of incomplete type ‘struct std::hash<std::pair<int, int> >

error: declaration of ‘struct std::hash<std::pair<int, int> >

error: type ‘std::__detail::_Hashtable_ebo_helper<1, std::hash<std::pair<int, int> >, true>’ is not a direct base of ‘std::__detail::_Hash_code_base<std::pair<int, int>, std::pair<const std::pair<int, int>, int>, std::__detail::_Select1st, std::hash<std::pair<int, int> >, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>’
  • Vous devez transmettre declate template<typename T> class hash;
  • Une déclaration anticipée est insuffisante. La coopérative doit définir la spécialisation avant class abc.
  • Ouais je vois que maintenant.
  • Qu'arriverait-il si deux programmeurs essayé dans les deux composantes d'un même programme?
InformationsquelleAutor Shambo | 2013-12-15
  1. 46

    Malheureusement, ce programme a un comportement indéfini. C++11 §17.6.4.2.1:

    Un programme peut ajouter une spécialisation de modèle pour toute la bibliothèque standard du modèle de l'espace de noms std seulement si la déclaration dépend d'un type défini par l'utilisateur et de la spécialisation répond à la norme de la bibliothèque exigences pour le modèle d'origine et n'est pas explicitement interdit.

    hash<pair<int,int>> dépend de primitif et de la bibliothèque standard uniquement les types de. Ceci est facilement contourné par la définition de votre classe hash à l'extérieur de l'espace de noms std, et l'utilisation de hachage explicitement dans votre carte de déclaration:

    struct pairhash {
public:
  template <typename T, typename U>
  std::size_t operator()(const std::pair<T, U> &x) const
  {
    return std::hash<T>()(x.first) ^ std::hash<U>()(x.second);
  }
};

class abc {
  std::unordered_map<std::pair<int,int>, int, pairhash> rules;
};

    EDIT: j'ai utilisé un xor pour combiner les valeurs de hachage de la paire de membres ici parce que je suis paresseux, mais pour un usage sérieux xor est assez minable de hachage combinant la fonction.

    • Ah droit, oublié.
    • (même commentaire que j'ai fait pour Jesse) std::hash<T>()(x.first) ^ std::hash<T>()(x.second); - c'est une spectaculaire collision sujettes à la façon de hachage une pair, comme chaque paire avec deux identiques valeur hachages à 0, et chaque paire {a, b} hache le même que {b, a}. Pour vaguement exigeantes, beaucoup mieux pour trouver un hash_combine de la fonction et de l'employer.
    • Attendez donc non seulement la stl ne pas mettre en œuvre std::hash pour std::pairs mais également de ne pas vous laisser mettre en œuvre vous-même? Pourquoi?
    • Vous pouvez la mettre en œuvre vous-même, mais seulement si au moins l'un des paramètres du modèle est un type défini par l'utilisateur.
    • Je ne comprends pas la raison du maintien d'une telle norme. Pouvez-vous nous expliquer la raison de cela?
    • La règle générale existe pour empêcher les utilisateurs d'interférer avec la bibliothèque des réalisateurs et/ou les modifications futures de la norme. Une mise en œuvre de bibliothèque peuvent, par exemple, fournir une spécialisation de std::hash<std::pair<T, U>> comme conforme extension. Ou C++35 peut définir une telle spécialisation. Ni serait possible, sans rupture de certains programmes - si les utilisateurs ont permis de définir de telles spécialisations eux-mêmes.
    • Ne pouvez-vous pas simplement fournir un bon hachage combinant la fonction ? :p
    • putain! C++35... Sur plus de deux décennies? C'est dur... 🙂

    InformationsquelleAutor Casey
  2. 0

    Je préfère me fier sur la norme de mise en œuvre de std::hash<uintmax_t> de mélanger les hachages des composants d'un std::pair:

    #include <functional>
#include <utility>

struct hash_pair final {
    template<class TFirst, class TSecond>
    size_t operator()(const std::pair<TFirst, TSecond>& p) const noexcept {
        uintmax_t hash = std::hash<TFirst>{}(p.first);
        hash <<= sizeof(uintmax_t) * 4;
        hash ^= std::hash<TSecond>{}(p.second);
        return std::hash<uintmax_t>{}(hash);
    }
};
    • hash <<= sizeof(uintmax_t) * 4; elle ne sera pas seulement de supprimer les de hachage en tout? E. g imaginez un uintmax de 64 bits. décalage à gauche (4*64) bits est en le poussant au-delà de sa limite.
    • sizeofdonne la taille en octets, mais << prend le nombre de bits à décaler par. en.cppreference.com/w/cpp/language/sizeof
    • Merci Vlad. J'avais oublié qu'elle a été mesurée en octets, pas de bits. Donc, le but est de déplacer le premier hachage exactement la moitié de la taille de TFirst. Ne serait-il pas préférable de faire tourner le hachage nombre de bits? Sinon, nous perdons la moitié des bits de la première de hachage.
    • Cette, (pour exemple. uintmax_t) serait de compiler rol 32: hash = (hash << (sizeof(uintmax_t) << 2)) | (hash >> (sizeof(uintmax_t)) << 2));
    InformationsquelleAutor Vladimir Reshetnikov