Building an unordered map with tuples as keys

Question

In a C++ program with Boost, I am trying to build an unordered map whose keys are tuples of doubles:

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

Initializing the map completes OK, however, when I try to populate it with keys and values

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

I encounter the following error message:

/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>&)’ 

I presume this is because I need to specify a hash function for the tuple keys. How can I do that?

EDIT:

Following the suggestions below, I wrote the following implementation:

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

Is it possible to shorten it?

Answer 1

Actually, you could perfectly define a general hash function for boost::tuple. The only requirement is that it lives within the same namespace so that it is picked up by ADL.

I am actually surprised that they did not already write one.

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

Note: I have only proved it correct, I haven't tested it.

Answer 2

You need a bit of front matter. Because of the underlying implementation of boost::tuples::tuple, make Edge a structure to allow the overloads to resolve correctly. Otherwise, you'll get no matches for

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

Code below:

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;