Comment se spécialisent std::hash<Key>::operator() pour le type défini par l'utilisateur non ordonnée dans les conteneurs?

À l'appui de l'utilisateur a défini les principaux types de std::unordered_set<Key> et std::unordered_map<Key, Value>
on doit fournir operator==(Key, Key) et un hachage foncteur:

struct X { int id; /* ... */ };
bool operator==(X a, X b) { return a.id == b.id; }

struct MyHash {
  size_t operator()(const X& x) const { return std::hash<int>()(x.id); }
};

std::unordered_set<X, MyHash> s;

Il serait plus commode d'écrire juste std::unordered_set<X>
avec un de hachage par défaut pour le type X,
comme pour les types à venir avec le compilateur et de la bibliothèque.
Après consultation de

il semble possible de se spécialiser std::hash<X>::operator():

namespace std { //argh!
  template <>
  inline size_t 
  hash<X>::operator()(const X& x) const { return hash<int>()(x.id); } //works for MS VC10, but not for g++
  //or
  //hash<X>::operator()(X x) const { return hash<int>()(x.id); }     //works for g++ 4.7, but not for VC10 
}

Compte tenu de prise en charge du compilateur de C++11 est encore expérimental---je n'ai pas essayer Clang---, voici mes questions:

  1. Est-il légal d'ajouter une spécialisation à l'espace de noms std? J'ai des sentiments mitigés à ce sujet.

  2. Qui de la std::hash<X>::operator() versions, le cas échéant, est compatible avec le C++11?

  3. Est-il un portable moyen de le faire?

  • Avec gcc 4.7.2, j'ai dû fournir un mondial operator==(const Key, const Key)
InformationsquelleAutor René Richter | 2011-11-16
  1. 117

    Vous sont expressément autorisés et encouragés à ajouter spécialisations à l'espace de noms std*. La bonne (et, fondamentalement, la seule façon) pour ajouter une fonction de hachage est-ce:

    namespace std {
  template <> struct hash<Foo>
  {
    size_t operator()(const Foo & x) const
    {
      /* your code here, e.g. "return hash<int>()(x.value);" */
    }
  };
}

    (Parmi les plus populaires, les spécialisations que vous pourriez envisager de soutenir sont std::less, std::equal_to et std::swap.)

    *) tant que l'un des types définis par l'utilisateur, je suppose.

    • alors que cela est possible, auriez-vous recommandent en général de le faire de cette façon? Je préfère l'instanciation unorder_map<eltype, hash, equality> au lieu de cela, pour éviter de ruiner la journée de quelqu'un avec un drôle d'ADL d'affaires. (Modifier Pete Becker du conseil sur ce sujet)
    • Si vous avez une table de hachage foncteur qui traînent, c'est par défaut constructible, peut-être, mais pourquoi? (L'égalité est plus facile, puisque vous venais de mettre en œuvre des états-operator==.) Ma philosophie est que si la fonction est naturel, et essentiellement de la seule "correcte" (comme lexicographique paire de comparaison), puis-je l'ajouter à std. Si c'est quelque chose de particulier (comme la paire non ordonnée de comparaison), puis-je le faire spécifiques à un type de conteneur.
    • Devrait être size_t operator()(const Foo & x) const.
    • Il fonctionne sur les deux compilateurs lors de l'ajout d'un const modificateur de la méthode. Merci!
    • FWIW, j'ai posté mon léger, prendre sur cela (qui, soit dit en passant, n'exige nullement un objet de fonction; même si vous choisissez d'en utiliser un, il n'a pas besoin d'être par défaut constructible, AFAICT)
    • quelqu'un d'autre) je ne comprends pas le "template<> struct hachage<Foo>". Pourriez-vous expliquer ce que cela signifie et pourquoi vous ne le faites pas s'il vous plaît ? Thx
    • C'est la syntaxe du modèle de spécialisation.
    • Je ne suis pas en désaccord, mais où, à la norme sommes-nous autorisés et encouragés à ajouter des spécialisations pour les mst?
    • tous sur la place, par exemple,hash, mais aussi toutes sortes de traits... allocator_traits, pointer_traits, iterator_traits...
    • Je suis d'accord, mais je m'attendais à un chapitre et le verset de référence pour une place dans le standard. J'ai trouvé le libellé permettant l'injection au 17.6.4.2.1 où il dit qu'il n'est pas autorisé "sauf indication contraire", mais je n'ai pas été en mesure de trouver la "autrement spécifié" partie parmi les 4000+ page de cahier des charges.
    • href="http://timepp.github.io/doc/cpp14/namespace.std.html" >ici, vous pouvez lire "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.". Donc cette solution est ok.

    InformationsquelleAutor Kerrek SB
  2. 6

    Mon pari serait sur la table de Hachage argument de modèle pour la unordered_map/unorder_set/... classes:

    #include <unordered_set>
#include <functional>

struct X 
{
    int x, y;
    std::size_t gethash() const { return (x*39)^y; }
};

typedef std::unordered_set<X, std::size_t(*)(const X&)> Xunset;
typedef std::unordered_set<X, std::function<std::size_t(const X&)> > Xunset2;

int main()
{
    auto hashX = [](const X&x) { return x.gethash(); };

    Xunset  my_set (0, hashX);
    Xunset2 my_set2(0, hashX); //if you prefer a more flexible set typedef
}

    Bien sûr

    • hashX pourrait tout aussi bien être un global statique de la fonction de
    • dans le second cas, vous pourriez passer que
      • l'ancien foncteur objet (struct Xhasher { size_t operator(const X&) const; };)
      • std::hash<X>()
      • tout lier l'expression de la satisfaction de la signature
        -
    • J'apprécie que vous pouvez écrire quelque chose qui n'a pas de constructeur par défaut, mais j'ai toujours trouver qu'en exigeant que chaque construction de la carte à retenir l'argument est un peu un fardeau -- tout à fait un peu un fardeau trop lourd à mon goût. Je suis OK avec explicitement un argument de modèle, bien que spécialisée std::hash est toujours la plus belle façon de sortir 🙂
    • défini par l'utilisateur types à la rescousse 🙂 Plus sérieusement, j'espère que nous avions gifle sur les poignets, déjà au stade où leur classe contient une char*!
    • Hmm... vous avez un exemple de la façon dont un hash spécialisation interfère via ADL? Je veux dire, c'est tout à fait plausible, mais j'ai un moment difficile à venir avec un problème de cas.
    • laissez-nous continuer cette discussion dans le chat
    • C'est tous les amusement et jeux jusqu'à ce que vous avez besoin d'un std::unordered_map<Whatever, Xunset> et il ne fonctionne pas parce que votre Xunset hasher type n'est pas par défaut constructible.
    InformationsquelleAutor sehe
  3. 4

    @Kerrek SB a couvert 1) et 3).

    2) Même si g++ et VC10 déclarer std::hash<T>::operator() avec des signatures différentes, les deux implémentations de la bibliothèque sont conformes à la Norme.

    La Norme ne précise pas les membres de std::hash<T>. Il dit seulement que chaque spécialisation doit respecter les mêmes "Hash" les exigences requises pour la deuxième argument de modèle de std::unordered_set et ainsi de suite. À savoir:

    • Type de hachage H est un objet de fonction, avec au moins un type d'argument Key.
    • H la copie est constructible.
    • H est destructible.
    • Si h est une expression de type H ou const H, et k est une expression d'un type convertible (éventuellement const) Key, puis h(k) est une expression valide de type size_t.
    • Si h est une expression de type H ou const H, et u est une lvalue de type Key, puis h(u) est une expression valide de type size_t qui ne modifie pas u.
    • Non, ni la mise en œuvre est conforme à la norme, car ils tentent de se spécialiser std::hash<X>::operator() plutôt que std::hash<X> dans son ensemble, et la signature de std::hash<T>::operator() la mise en œuvre est définie.
    • Précisé - je parlais de la bibliothèque implémentations, pas la tentative de spécialisations. Vous ne savez pas lequel exactement l'OP voulais dire.
    InformationsquelleAutor aschepler