How to unordered_set<tuple<int,int>>?

Question

I had encountered strange problem while construct a unordeed_set<tuple<int,int>>. I had tried VC++8, gcc3.2, gcc4.3, all have the same result. I have no idea what's wrong with the code, following is my code:

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

Here is the compile error message:

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)'
....

It seems the compiler can not see the definition of hash_value(tuple<int, int>). But if I replace the tuple<int, int> to other data type like struct F{int a, b;} and it works. That's really strange. Do I miss anything? Thank you very much.

Answer 1

This code from Generic hash for tuples in unordered_map / unordered_set provides magical support for all c++0x tuples of standard hashable types (strings, ints etc).

This is very much like Steven Watanabe but with the boost magic unpacked and no boost dependencies.

Put the code in a header file and include it and unordered sets of tuples will work out of the box:

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

    };
}

Answer 2

Better (and more general solution for any tuple) posted by Steven Watanabe: '"[tuple][hash] Hashing a tuple question"' http://lists.boost.org/boost-users/2008/06/37643.php

His solution:

#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

Put the hash function in namespace 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) ;
}