如何unordered_set <tuple <int,int>>？

Question

我在構建unordeed_set<tuple<int,int>>時遇到了奇怪的問題。我曾試過VC++ 8，gcc3.2，gcc4.3，都有相同的結果。我不知道什麼是錯的代碼，以下是我的代碼：

#include <boost/unordered_set.hpp> 
#include <boost/tuple/tuple.hpp> 
// For unordered container, the declaration of operator== 
#include <boost/tuple/tuple_comparison.hpp> 

using namespace std ; 
using namespace boost ; 

// define of the hash_value funciton for tuple<int, int> 
size_t hash_value(tuple<int, int> const& t) { 
    return get<0>(t) * 10 + get<1>(t) ; 
} 

int main() { 
    unordered_set<tuple<int, int>> s ; 
    tuple<int, int> t ; 
    s.insert(t) ; 
} 

以下是編譯錯誤消息：

1>c:\libs\boost_1_37_0\boost\functional\hash\extensions.hpp(72) : error C2665: 'boost::hash_value' : none of the 16 overloads could convert all the argument types 
1>  c:\libs\boost_1_37_0\boost\functional\hash\hash.hpp(33): could be 'size_t boost::hash_value(bool)' 
1>  c:\libs\boost_1_37_0\boost\functional\hash\hash.hpp(34): or  'size_t boost::hash_value(char)' 
1>  c:\libs\boost_1_37_0\boost\functional\hash\hash.hpp(35): or  'size_t boost::hash_value(unsigned char)' 
.... 

看來編譯器看不到的hash_value(tuple<int, int>)定義。但是，如果我將tuple<int, int>替換爲其他數據類型，如struct F{int a, b;}並且它可以工作。這真的很奇怪。我錯過了什麼嗎？非常感謝你。

Answer 1

將哈希函數放入命名空間boost中。

#include <boost/unordered_set.hpp> 
#include <boost/tuple/tuple.hpp> 
#include <boost/tuple/tuple_comparison.hpp> 

using namespace std; 
using namespace boost; 

namespace boost { 
    size_t hash_value(tuple<int, int> const & t) { 
     return get<0>(t) * 10 + get<1>(t) ; 
    } 
} 

int main() { 
    unordered_set< tuple<int, int> > s ; 
    tuple<int, int> t ; 
    s.insert(t) ; 
} 

Answer 2

更好的（和任何元組更通用的解決方案）公佈由史蒂芬渡邊： '[元組] [散列]哈希元組提問「' http://lists.boost.org/boost-users/2008/06/37643.php

他的解決方案：

#include <boost/functional/hash.hpp> 
#include <boost/fusion/algorithm/iteration/fold.hpp> 
#include <boost/fusion/adapted/boost_tuple.hpp> 
#include <boost/tuple/tuple.hpp> 

namespace stlex 
{ 
    struct tuple_fusion_hash 
    { 
     typedef size_t result_type; 

     template <typename T> 
#if BOOST_VERSION >= 104300 
     //NOTE: order changed in Boost 1.43 
     std::size_t operator()(std::size_t nSeed, const T& crArg) const 
#else 
     std::size_t operator()(const T& crArg, std::size_t nSeed) const 
#endif 
     { 
     boost::hash_combine(nSeed, crArg); 
     return nSeed; 
     } 
    }; 


    struct tuple_hash 
    { 
     template <typename Tuple> 
     std::size_t operator()(const Tuple& cr) const 
     { 
     return boost::fusion::fold(cr, 0, tuple_fusion_hash()); 
     } 
    }; 

} //end namespace stlex 


namespace boost 
{ 
    //---------------------------------------------------------------------------- 
    // template struct tuple_hash 
    //---------------------------------------------------------------------------- 
    // Description: hash function for tuples 
    // Note  : must be declared in namespace boost due to ADL 
    //---------------------------------------------------------------------------- 
    template <class T0, class T1, class T2, class T3, class T4, class T5, class T6, class T7, class T8, class T9> 
    std::size_t hash_value(const boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9>& cr) 
    { 
     const stlex::tuple_hash hsh; 
     return hsh(cr); 
    } 
} 

Answer 3

Generic hash for tuples in unordered_map/unordered_set這段代碼爲標準可哈希類型（字符串，整數等）的所有C++ 0x元組提供了神奇的支持。

這非常像史蒂文渡邊，但與提升魔術解壓和沒有提升依賴。

將代碼放在一個頭文件，包括它和無序集的元組將工作開箱：

#include <tuple> 
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: 
     //  https://stackoverflow.com/questions/4948780 

     template <class T> 
     inline void hash_combine(std::size_t& seed, T const& v) 
     { 
      seed ^= 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& seed, Tuple const& tuple) 
      { 
      HashValueImpl<Tuple, Index-1>::apply(seed, tuple); 
      hash_combine(seed, get<Index>(tuple)); 
      } 
     }; 

     template <class Tuple> 
     struct HashValueImpl<Tuple,0> 
     { 
      static void apply(size_t& seed, Tuple const& tuple) 
      { 
      hash_combine(seed, 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;         
     }            

    }; 
}