使用元组作为键构建无序映射
-
26-09-2019 - |
题
在带有 Boost 的 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;
}
可以缩短吗?
解决方案
你需要一点 头条新闻. 。由于底层的实现 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;
其他提示
实际上,你可以完美地定义一个通用的哈希函数 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;
}
} }
笔记:我只是证明了它是正确的,我还没有测试过。
这一切都在文档中......
- 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;
Boost 文档给出了 所需接口. 。如果不了解更多所涉及的价值观,就很难说更多。给定一个关键对象作为输入,它必须产生一个确定性的 size_t ——即,它是一个纯函数,其结果仅取决于输入值,因此给出相同的输入将始终产生相同的哈希码。
这段代码来自 unordered_map / unordered_set 中元组的通用哈希 为标准哈希类型(字符串、整数等)的所有 c++11 元组提供神奇的支持。
毫不奇怪,它看起来非常像上面 Matthieu M. 的解决方案,但没有 boost 依赖性。
将代码放入头文件中并包含它,无序的元组集将开箱即用:
#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;
}
};
}
不隶属于 StackOverflow