c++ - 构建以元组为键的无序映射

Question

在带有 Boost 的 C++ 程序中，我正在尝试构建一个无序映射，其键是 double 元组:

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

初始化 map 可以完成，但是，当我尝试用键和值填充它时

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

实际上，您可以完美地为 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;
  }

} }

注意:我只是证明它是正确的，我没有测试过。