24

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?

6 Answers 6

12

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.

3
  • For boost 1.60.0, the "namespace tuple" should be "namespace tuples" to make it work.
    – Val
    Mar 14, 2016 at 15:51
  • @Val: I think it was the case with all previous versions too actually; thanks :) Mar 14, 2016 at 15:52
  • "I have only proved it correct, I haven't tested it." <-- that is also my preferred way to develop code :-) Apr 3, 2017 at 1:05
10

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

It's all in the docs...

You'd need something like:

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

... and then you can define:

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

... actually this is default, so it should work without explicit hash definition now:

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

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

Unsurprisingly it looks very much like Matthieu M.'s solution above but with 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;                                 
        }                                              

    };
}
1

Have you tried using this:

#include "boost/functional/hash.hpp"
#include <unordered_map>
#include <tuple>

using Edge = std::tuple<double, double, double, double>;

struct KeyHash {
    std::size_t operator()(const Edge & key) const {
        return boost::hash_value(key);
    }
};

using EdgeMap = std::unordered_map<Edge, int, KeyHash>;

please notice I am using std for tuple and unordered_map.

You can see full code with using even lambda on this Compiler Explorer link.

0

The Boost documentation gives the required interface. Without knowing more about the values involved, it's hard to say a lot more. Given a key object as input, it has to produce a size_t that's deterministic -- i.e., it's a pure function, where the result depends solely on the input value, so giving the same input will always produce the same hash code.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.