> 백엔드 개발 > C++ > 본문

사용자 정의 해시 함수를 작성하지 않고 정렬되지 않은 맵에서 튜플을 키로 어떻게 사용할 수 있습니까?

Linda Hamilton
풀어 주다: 2024-11-08 06:29:02
원래의
722명이 탐색했습니다.

How can I use tuples as keys in unordered maps without writing a custom hash function?

사용자 지정 해시 함수 없이 순서가 지정되지 않은 맵에서 튜플 사용

std::unordered_map이 즉시 튜플 키를 사용하여 쉽게 작동할 것으로 기대할 수 있습니다. 그러나 아래와 같이 튜플에 대한 해시 함수를 정의해야 합니다.

template<> struct do_hash<tuple<int, int>> {
    size_t operator()(std::tuple<int, int> const& tt) const {...}
};
로그인 후 복사

이 프로세스는 지루할 수 있으므로 가변 템플릿을 사용하지 않고 C 0x 튜플에 대해 자동화해야 하는 문제로 이어질 수 있습니다.

다음 접근 방식을 사용하면 표준 해시 가능 유형을 포함하는 모든 C 0x 튜플이 unordered_map의 일부가 되고 추가 노력 없이 unordered_set:

#include <tuple>
namespace std {
    namespace {
        template <class T>
        inline void hash_combine(std::size_t& seed, T const& v) {
            // Modified from Boost
            seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
        }

        // Recursive template for hashing tuples
        template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
        struct HashValueImpl {
            static void apply(size_t& seed, Tuple const& 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& seed, Tuple const& tuple) {
                hash_combine(seed, std::get<0>(tuple));
            }
        };
    }

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

std 네임스페이스에 함수를 배치하면 인수 종속 이름 조회(ADL)를 통해 액세스할 수 있습니다.

표준 준수 코드

std 네임스페이스의 개체를 특수화하는 것은 정의되지 않은 동작입니다. 따라서 표준을 준수하는 솔루션의 경우 코드를 별도의 네임스페이스로 이동하고 ADL의 편리함을 포기하세요.

namespace hash_tuple {

// Forward non-tuple types to std::hash
template <class TT>
struct hash {
    size_t
    operator()(TT const& tt) const {
        return std::hash<TT>()(tt);
    }
};

// Hash function combining values in a tuple
template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
struct HashValueImpl {
    static void apply(size_t& seed, Tuple const& 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& seed, Tuple const& tuple) {
        hash_combine(seed, std::get<0>(tuple));
    }
};

// Hash function for tuples
template <typename... TT>
struct hash<std::tuple<TT...>> {
    size_t
    operator()(std::tuple<TT...> const& tt) const {
        size_t seed = 0;
        HashValueImpl<std::tuple<TT...>>::apply(seed, tt);
        return seed;
    }
};
} // namespace hash_tuple
로그인 후 복사

tuple이 아닌 모든 유형을 std로 전달하려면 hash_tuple 네임스페이스 내에서 해시 구현을 선언하세요. :hash std::hash 대신 hash_tuple::hash를 사용하도록 hash_combine을 수정합니다. 나머지 코드는 hash_tuple 네임스페이스 안에 배치합니다.

이 솔루션을 사용하려면 ADL의 편의성을 포기하는 다음 코드를 포함해야 합니다.

unordered_set<tuple<double, int>, hash_tuple::hash<tuple<double, int>>> test2;
로그인 후 복사

위 내용은 사용자 정의 해시 함수를 작성하지 않고 정렬되지 않은 맵에서 튜플을 키로 어떻게 사용할 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
저자별 최신 기사
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿