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

Hachage générique pour les tuples dans les collections non ordonnées

Dans le domaine des bibliothèques standard C, le concept des tuples et leur utilisation comme clés dans les collections non ordonnées comme std::unordered_map et std::unordered_set peut poser un défi. Par défaut, les tuples n'ont pas de fonction de hachage générique définie, laissant aux développeurs la tâche fastidieuse d'en définir une manuellement.

Le besoin d'une solution générique

Définir une fonction de hachage personnalisée pour les tuples peut être fastidieux et sujet aux erreurs. Pour résoudre ce problème, les développeurs recherchent souvent une solution plus générique qui automatise le processus.

Une approche conforme aux normes

Bien que la norme ne fournisse pas explicitement de fonction de hachage générique pour les tuples, une norme -une approche conforme est disponible. En déplaçant le code dans un espace de noms personnalisé, il est possible d'éviter un comportement indéfini associé à la spécialisation dans l'espace de noms std.

Dans cette approche, un espace de noms personnalisé, hash_tuple, est créé avec sa propre implémentation de la fonction de hachage. . Cette implémentation distribue des types non-tuple à la fonction std::hash.

namespace hash_tuple{
template <typename TT>
struct hash
{
    size_t
    operator()(TT const&amp; tt) const
    {                                              
        return std::hash<TT>()(tt);                                 
    }                                              
};
}

Le code du modèle récursif est modifié pour utiliser hash_tuple::hash au lieu de std::hash:

namespace hash_tuple{
    namespace
    {
        template <class T>
        inline void hash_combine(std::size_t&amp; seed, T const&amp; v)
        {
            seed ^= hash_tuple::hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }
    }
}

Enfin, la spécialisation du modèle std est placée dans l'espace de noms hash_tuple :

namespace hash_tuple{
    template <typename ... TT>
    struct hash<std::tuple<TT...>> 
    {
        size_t
        operator()(std::tuple<TT...> const&amp; tt) const
        {                                              
            size_t seed = 0;                             
            HashValueImpl<std::tuple<TT...> >::apply(seed, tt);    
            return seed;                                 
        }                                              
    };
}

Pour utiliser cette approche, les utilisateurs doivent spécifier l'espace de noms hash_tuple dans leurs déclarations de collection non ordonnées :

unordered_set<tuple<double, int>, hash_tuple::hash<tuple<double, int>>> test2;

Bien que cette solution soit conforme aux standards, elle nécessite de spécifier l'espace de noms pour chaque déclaration de collection non ordonnée.

Une approche non standard

Une approche alternative, qui n'est pas conforme à la norme C, est pour placer le code de la fonction de hachage générique dans l'espace de noms std. Cela permet à la recherche dépendante de l'argument (ADL) de trouver automatiquement l'implémentation de hachage correcte.

namespace std{
    namespace
    {
        // Code from boost
        // Reciprocal of the golden ratio helps spread entropy
        //     and handles duplicates.
        // See Mike Seymour in magic-numbers-in-boosthash-combine:
        //     http://stackoverflow.com/questions/4948780

        template <class T>
        inline void hash_combine(std::size_t&amp; seed, T const&amp; v)
        {
            seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }

        // Recursive template code derived from Matthieu M.
        template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
        struct HashValueImpl
        {
          static void apply(size_t&amp; seed, Tuple const&amp; tuple)
          {
            HashValueImpl<Tuple, Index-1>::apply(seed, tuple);
            hash_combine(seed, std::get<Index>(tuple));
          }
        };

        template <class Tuple>
        struct HashValueImpl<Tuple,0>
        {
          static void apply(size_t&amp; seed, Tuple const&amp; tuple)
          {
            hash_combine(seed, std::get<0>(tuple));
          }
        };
    }

    template <typename ... TT>
    struct hash<std::tuple<TT...>> 
    {
        size_t
        operator()(std::tuple<TT...> const&amp; tt) const
        {                                              
            size_t seed = 0;                             
            HashValueImpl<std::tuple<TT...> >::apply(seed, tt);    
            return seed;                                 
        }                                              

    };
}

Avec cette approche, la syntaxe de collection non ordonnée reste plus simple :

unordered_set<tuple<double, int> > test_set;

Cependant, cette technique comporte le risque de comportement indéfini dû à la spécialisation dans l'espace de noms std.

Conclusion

Le hachage générique de tuples dans des collections non ordonnées est un problème non trivial qui peut nécessiter une implémentation personnalisée. Les approches conformes aux normes et non standard décrites dans cet article fournissent des solutions viables. En fin de compte, le choix entre ces approches dépend des exigences du développeur et de sa tolérance à l'égard d'un comportement potentiel indéfini.

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!