Comment se spécialiser std::hash<Key>:: operator() pour le type défini par l’utilisateur dans des conteneurs non ordonnées ?</Key>

Question

À l'appui de touche définie par l'utilisateur des types en std::unordered_set<Key> et std::unordered_map<Key, Value> on a à offrir 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 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

• Norme C++ Projet de N3242 §20.8.12 [unord.hash] et §17.6.3.4 [hachage.exigences],
• Coup de pouce.Non ordonnée
• g++ include\c++\4.7.0\bits\functional_hash.h
• VC10 include\xfunctional
• divers liés à la questions dans le Débordement de Pile

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?

Answer 1

Vous êtes expressément autorisés et encouragés à ajouter des spécialisations à l’espace de noms `` *. La manière correcte (et fondamentalement seulement) pour ajouter une fonction de hachage est la suivante :

(Autres spécialisations populaires que vous pourriez considérer l’appui, on , et `` .)

_{*) tant que l’un des types impliqués est défini par l’utilisateur, je suppose.}

Answer 2

Mon pari serait sur l’argument de modèle de hachage pour les classes unordered_map/unorder_set /... :

Bien sûr

• hashX pourrait tout aussi bien être une fonction statique globale
• dans le second cas, vous pourriez passer que- l’objet de functor démodé ( `` )
• ``
• tout lier expression satisfaisant la signature -

Answer 3

@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 l' 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 d' 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 copie est constructible.
• H sont destructibles.
• Si h est une expression de type H ou const H, et k est une expression d'un type convertible (éventuellement const) Key, alors 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, alors h(u) est une expression valide de type size_t qui ne se modifie pas u.