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?

Matthieu M. · Answer 1 · 2016-03-14T16:17:17.933

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.

For boost 1.60.0, the "namespace tuple" should be "namespace tuples" to make it work. — Val, Mar 14 '16 at 15:51
@Val: I think it was the case with all previous versions too actually; thanks :) — Matthieu M., Mar 14 '16 at 15:52
"I have only proved it correct, I haven't tested it." <-- that is also my preferred way to develop code :-) — Chris Jones, Apr 03 '17 at 01:05

score 10 · Accepted Answer · answered Aug 31 '10 at 19:00

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;

score 1 · Answer 3 · edited May 23 '17 at 12:24

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

    };
}

Kornel Kisielewicz · Answer 4 · 2010-08-31T18:31:38.460

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;

Daniel · Answer 5 · 2020-10-07T13:17:37.830

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.

score 0 · Answer 6 · answered Aug 31 '10 at 18:26

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.

Building an unordered map with tuples as keys

6 Answers6

Linked