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

재귀 템플릿 코드는 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);
        }
    }
}

대신 hash_tuple::hash를 활용하도록 수정되었습니다. 🎜>마지막으로 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!