如何在 C 中為無序集合中的元組實現通用雜湊函數？

無序集合中元組的通用雜湊

在C 標準庫領域，元組的概念及其作為無序集合（如std::unordered_map ）中鍵的用法std::unordered_set 可能會帶來挑戰。預設情況下，元組沒有定義通用雜湊函數，這使得開發人員需要手動定義一個繁瑣的任務。

需要通用解決方案

為元組定義自訂雜湊函數可以很麻煩且容易出錯。為了解決這個問題，開發人員經常尋求一種更通用的解決方案來自動化流程。

符合標準的方法

雖然標準沒有明確為元組提供通用雜湊函數，但標準- 可以使用合規方法。透過將程式碼移動到自訂命名空間中，可以避免與專門化 std 命名空間相關的未定義行為。

在這種方法中，使用自己的雜湊函數實作建立自訂命名空間 hash_tuple 。此實作將非元組類型分派給 std::hash 函式。

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

遞歸模板程式碼已修改為使用hash_tuple::hash 而不是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);
        }
    }
}

最後，std 模板特化被放置在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;                                 
        }                                              
    };
}

要使用此方法，使用者必須在其無序集合聲明中指定hash_tuple 命名空間：

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

雖然此解決方案符合標準，但它需要為每個無序集合聲明指定命名空間。

非標準方法

另一種不符合 C 標準的方法是將通用雜湊函數程式碼放置在 std 命名空間中。這允許參數相關查找（ADL）自動找到正確的雜湊實作。

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;                                 
        }                                              

    };
}

透過這種方法，無序集合語法仍然更簡單：

unordered_set<tuple<double, int> > test_set;

但是，這種技術攜帶由於std 命名空間中的專門化，存在未定義行為的風險。

結論

無序集合中元組的通用雜湊是一個不平凡的問題，可能需要自訂實作。本文中概述的符合標準和非標準的方法都提供了可行的解決方案。最終，這些方法之間的選擇取決於開發人員的要求和對潛在未定義行為的容忍度。

以上是如何在 C 中為無序集合中的元組實現通用雜湊函數？的詳細內容。更多資訊請關注PHP中文網其他相關文章！