Как 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

Поместите хэш-функцию в усиление пространства имен.

#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

Лучшее (и более общее решение для любого кортежа), опубликованное Стивеном Ватанабе: «[tuple] [hash] Хэширование вопроса о кортеже» » 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

Этот код из Общий хэш для кортежей в 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;                                 
        }                                              

    };
}