代码之家 › 专栏 › 技术社区 › yoco

如何无序设置<tuple<int,int>>?

boost c++

yoco · 技术社区 · 15 年前

我在构造一个模型时遇到了一个奇怪的问题 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;} 它是有效的。真奇怪。我错过什么了吗?非常感谢你。

3 回复 | 直到 15 年前

Bill Lynch 15 年前

将哈希函数放在名称空间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) ;
}

gast128 12 年前

史蒂文·渡边捷夫(Steven Watanabe)发布了更好的(对任何元组都更通用的解决方案):““[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);
   }
}

Community CDub 8 年前

此代码来自 Generic hash for tuples in unordered_map / unordered_set

这很像渡边捷文,但没有增压魔法和增压依赖。

将代码放在头文件中并包含它,无序的元组集将开箱即用:

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

    };
}