建設有元組作爲鍵

Question

與升壓C++程序無序的地圖，我想建立一個無序的地圖，它的鍵是雙打的元組：

typedef boost::tuples::tuple<double, double, double, double> Edge; 
typedef boost::unordered_map< Edge, int > EdgeMap; 

初始化地圖完成後確定，但是，當我試着用鑰匙來填充它和值

EdgeMap map; 
Edge key (0.0, 0.1, 1.1, 1.1); 
map[key] = 1; 

我遇到以下錯誤消息：

/usr/include/boost/functional/hash/extensions.hpp:176: error: no matching function for call to ‘hash_value(const boost::tuples::tuple<double, double, double, double, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type, boost::tuples::null_type>&)’ 

我認爲這是因爲我需要指定元組鍵的哈希函數。我怎樣才能做到這一點？

編輯：

按照下面的建議，我寫了下面的實現：

#include <boost/tuple/tuple.hpp> 
#include <boost/unordered_map.hpp> 

typedef boost::tuples::tuple<double, double, double, double> Edge; 

struct ihash 
    : std::unary_function<Edge, std::size_t> 
{ 
    std::size_t operator()(Edge const& e) const 
    { 
     std::size_t seed = 0; 
     boost::hash_combine(seed, e.get<0>()); 
     boost::hash_combine(seed, e.get<1>()); 
     boost::hash_combine(seed, e.get<2>()); 
     boost::hash_combine(seed, e.get<3>()); 
     return seed; 
    } 
}; 

struct iequal_to 
    : std::binary_function<Edge, Edge, bool> 
{ 
    bool operator()(Edge const& x, Edge const& y) const 
    { 
     return (x.get<0>()==y.get<0>() && 
       x.get<1>()==y.get<1>() && 
       x.get<2>()==y.get<2>() && 
       x.get<3>()==y.get<3>()); 
    } 
}; 

typedef boost::unordered_map< Edge, int, ihash, iequal_to > EdgeMap; 

int main() { 

    EdgeMap map; 
    Edge key (0.0, 0.1, 1.1, 1.1); 
    map[key] = 1; 

    return 0; 
} 

是否有可能縮短呢？

Answer 1

你需要一點front matter。由於boost::tuples::tuple的底層實現，因此使Edge成爲允許重載正確解析的結構。否則，你會得到不匹配下面

• boost::hash_value(const Edge &)
• operator==(const Edge &, const Edge &)

代碼：

struct Edge { 
    Edge(double x1, double x2, double x3, double x4) 
    : tuple(x1,x2,x3,x4) {} 
    boost::tuples::tuple<double, double, double, double> tuple; 
}; 

// XXX: less than ideal implementation! 
bool operator==(const Edge &a, const Edge &b) 
{ 
    return a.tuple.get<0>() == b.tuple.get<0>() && 
     a.tuple.get<1>() == b.tuple.get<1>() && 
     a.tuple.get<2>() == b.tuple.get<2>() && 
     a.tuple.get<3>() == b.tuple.get<3>(); 
} 

// XXX: me too! 
std::size_t hash_value(const Edge &e) 
{ 
    std::size_t seed = 0; 
    boost::hash_combine(seed, e.tuple.get<0>()); 
    boost::hash_combine(seed, e.tuple.get<1>()); 
    boost::hash_combine(seed, e.tuple.get<2>()); 
    boost::hash_combine(seed, e.tuple.get<3>()); 
    return seed; 
} 

typedef boost::unordered_map< Edge, int > EdgeMap; 

Answer 2

這一切都在文檔...

• http://www.boost.org/doc/libs/1_38_0/doc/html/hash/custom.html
• http://www.boost.org/doc/libs/1_38_0/doc/html/hash/combine.html

你會需要像：

std::size_t hash_value(Edge const& e) 
{ 
    std::size_t seed = 0; 
    boost::hash_combine(seed, e.get<0>()); 
    boost::hash_combine(seed, e.get<1>()); 
    boost::hash_combine(seed, e.get<2>()); 
    boost::hash_combine(seed, e.get<3>()); 
    return seed; 
} 

...然後你可以定義：

boost::unordered_map< Edge, int, boost::hash<Edge> > EdgeMap; 

...其實這是默認的，所以應該沒有明確的定義哈希現在的工作：

boost::unordered_map< Edge, int > EdgeMap; 

Answer 3

Boost文檔給出了required interface。在不瞭解涉及的價值的情況下，很難說更多。給定一個關鍵對象作爲輸入，它必須產生一個確定性的size_t，即它是一個純函數，結果只依賴於輸入值，因此給定相同的輸入將始終產生相同的散列碼。

Answer 4

其實，你完全可以定義一個通用哈希函數boost::tuple。唯一的要求是它存在於相同的命名空間中，以便ADL獲取它。

我真的很驚訝，他們沒有寫過一個。

namespace boost { namespace tuples { 

    namespace detail { 

    template <class Tuple, size_t Index = length<Tuple>::value - 1> 
    struct HashValueImpl 
    { 
     static void apply(size_t& seed, Tuple const& tuple) 
     { 
     HashValueImpl<Tuple, Index-1>::apply(seed, tuple); 
     boost::hash_combine(seed, tuple.get<Index>()); 
     } 
    }; 

    template <class Tuple> 
    struct HashValueImpl<Tuple,0> 
    { 
     static void apply(size_t& seed, Tuple const& tuple) 
     { 
     boost::hash_combine(seed, tuple.get<0>()); 
     } 
    }; 
    } // namespace detail 

    template <class Tuple> 
    size_t hash_value(Tuple const& tuple) 
    { 
    size_t seed = 0; 
    detail::HashValueImpl<Tuple>::apply(seed, tuple); 
    return seed; 
    } 

} } 

注：我只證明它是正確的，我沒有測試它。

Answer 5

Generic hash for tuples in unordered_map/unordered_set這段代碼爲所有標準可散列類型（字符串，整數等）的11個元組提供了神奇的支持。不出所料，它看起來非常像Matthieu M.的解決方案，但沒有提升依賴關係。

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

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

    }; 
}