Comment implémenter une fonction de hachage générique pour les tuples dans les collections non ordonnées ?

Fonction de hachage générique pour les tuples dans les collections non ordonnées

Les conteneurs std::unordered_map et std::unordered_set permettent une recherche et une insertion efficaces d'éléments en fonction de leurs valeurs hachées. Cependant, utiliser des tuples comme clés dans ces collections sans définir de fonction de hachage personnalisée peut entraîner un comportement inattendu.

Pour remédier à ce problème, une approche consiste à définir manuellement une fonction de hachage pour le type de tuple spécifique, telle que :

template<>
struct std::hash<std::tuple<int, int>> {
  size_t operator()(std::tuple<int, int> const& tuple) const { ... }
};

Bien que cette approche fonctionne, il peut être fastidieux de définir des fonctions de hachage pour chaque type de tuple utilisé. Pour automatiser cela, une fonction de hachage générique peut être implémentée comme suit :

#include <tuple>

namespace std {
  namespace {

    // Code derived from Boost
    template<class T>
    inline void hash_combine(std::size_t& seed, T const& v) { ... }

    // Recursive template code from Matthieu M.
    template<class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
    struct HashValueImpl { ... };

  }

  template<typename... TT>
  struct hash<std::tuple<TT...>> {
    size_t operator()(std::tuple<TT...> const& tuple) const { ... }
  };
}

Cette fonction exploite la recherche de nom dépendante de l'argument (ADL) pour permettre au compilateur de sélectionner automatiquement l'implémentation de hachage correcte en fonction du type de tuple. .

Solution conforme à la norme

Il convient de noter que la définition de fonctions non standard dans l'espace de noms std est un comportement indéfini. Pour une solution conforme aux normes, un espace de noms personnalisé peut être créé et utilisé pour définir la fonction de hachage :

namespace my_hash {

  // Forward non-tuple types to the std::hash
  template<typename TT>
  struct hash { ... };

  // Provide the optimized hash for tuples
  template<typename... TT>
  struct hash<std::tuple<TT...>> { ... };

}

Lors de l'utilisation de cette solution, la collection non ordonnée doit explicitement référencer l'implémentation de hachage personnalisée comme suit :

unordered_set<
  std::tuple<double, int>,
  std::hash<std::tuple<double, int>>,
  std::equal_to<std::tuple<double, int>>
> test;  

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!