Comment se spécialiser std:: hash: operator() pour le type défini par l'utilisateur dans les conteneurs non classés?

pour prendre en charge les types de clés définis par l'utilisateur dans std::unordered_set<Key> et std::unordered_map<Key, Value> on doit fournir operator==(Key, Key) et un foncteur de hachage: 

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 venant avec le compilateur et la bibliothèque. Après consultation

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 
}

donné le support du compilateur pour C++11 est encore expérimental- - - Je n'ai pas essayé Clang - - -, ce sont mes questions:

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

  2. laquelle des versions std::hash<X>::operator() , le cas échéant, est conforme à la norme C++11?

  3. y a-t-il un moyen portable de le faire?

89
demandé sur Community 2011-11-17 00:05:42

3 réponses

vous êtes expressément autorisé et encouragé à ajouter spécialisations à l'espace de noms std *. La façon correcte (et essentiellement seulement) d'ajouter une fonction de hachage est la suivante: 

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

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

*) aussi longtemps que l'un des types impliqués est défini par l'utilisateur, je suppose.

110
répondu Kerrek SB 2011-11-16 20:14:14

mon pari serait sur l'argument Hash template pour 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 une fonction statique globale
  • dans le second cas, vous pouvez passer que
    • l'ancien foncteur de l'objet ( struct Xhasher { size_t operator(const X&) const; }; )
    • std::hash<X>()
    • toute expression contraignante satisfaisant aux signature -
6
répondu sehe 2011-11-16 20:36:29

@Kerrek SB a couvert 1) et 3).

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

la norme ne spécifie pas les membres de std::hash<T> . Il dit simplement que chaque telle spécialisation doit satisfaire les mêmes exigences "Hash" nécessaires pour le 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 du type H ou const H , et k est une expression d'un type convertible en (éventuellement const ) Key , alors h(k) est une expression valide avec type size_t .
  • si h est une expression du type H ou const H , et u est une valeur l du type Key , alors h(u) est une expression valide avec le type size_t qui ne modifie pas u .
4
répondu aschepler 2011-11-16 20:24:50