C ++:使用一对(cpp_int,int)整数作为unordered_map中的键(其中cpp_int是升压多精度整数) [英] C++: Using pair of (cpp_int, int) integers as key in unordered_map (where cpp_int are boost multiprecision integers)
问题描述
对于我的无序地图,我想用作(cpp_int, int)
的键对,其中cpp_int
是
For my unordered map I would like to use as keys pairs of (cpp_int, int)
where cpp_int
are boost multiprecision integers:
#include <boost/multiprecision/cpp_int.hpp>
#include <unordered_map>
using boost::multiprecision::cpp_int;
std::unordered_map<std::pair<cpp_int, int>, double> myMap
在此站点上搜索时,我发现了很多关于将std::pair<int,int>
的自定义哈希函数用作键的建议,但是我找不到如何处理std::pair<cpp_int, int>
的方法.
Searching on this site I have found many suggestions of using a custom hash function for std::pair<int,int>
as keys, but I couldn't found how to deal with std::pair<cpp_int, int>
.
更新:为澄清起见,我尝试了在网络上找到的哈希函数(用于(int,int):
Update: To clarify, I have tried a hash function I found on the web (for (int,int):
#include <boost/multiprecision/cpp_int.hpp>
#include <unordered_map>
using boost::multiprecision::cpp_int;
typedef std::pair<cpp_int, int> MyPair;
struct MyHash {
public:
size_t operator()(MyPair x) const throw() {
size_t h = x.first * 1 + x.second * 100000;
return h;
}
};
void function()
{
std::unordered_map<MyPair, double, MyHash> M;
}
无法编译:
error: cannot convert ‘boost::enable_if_c<true, boost::multiprecision::detail::expression<boost::multiprecision::detail::multiply_add, boost::multiprecision::detail::expression<boost::multiprecision::detail::terminal, boost::multiprecision::number<boost::multiprecision::backends::cpp_int_backend<> >, void, void, void>, boost::multiprecision::detail::expression<boost::multiprecision::detail::terminal, int, void, void, void>, int, void> >::type {aka boost::multiprecision::detail::expression<boost::multiprecision::detail::multiply_add, boost::multiprecision::detail::expression<boost::multiprecision::detail::terminal, boost::multiprecision::number<boost::multiprecision::backends::cpp_int_backend<> >, void, void, void>, boost::multiprecision::detail::expression<boost::multiprecision::detail::terminal, int, void, void, void>, int, void>}’ to ‘size_t {aka long unsigned int}’ in initialization
size_t h = x.first * 1 + x.second * 100000;
^
我的问题是:如何使用(cpp_int,int)对作为unordered_map中的键?
非常感谢您!
更新2: 感谢@sehe向我指出了他的回答(其中他为cpp_int提供了哈希函数).结合此答案(它显示了如何将两个哈希函数组合为一对),我提出了以下内容解决方案(编译正常,我需要对我的问题进行测试以查看其是否有效):
Update 2: Thanks to @sehe for pointing me to his answer (in which he provided a hash function for cpp_int). Combining with this answer (which shows how to combine two hash functions for a pair), I've come up with the following solution (it compiles fine, I'll need to test on my problem to see if it works):
#include <boost/archive/binary_oarchive.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_int/serialize.hpp>
#include <boost/iostreams/device/back_inserter.hpp>
#include <boost/iostreams/stream_buffer.hpp>
#include <boost/iostreams/stream.hpp>
#include <boost/functional/hash.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <unordered_map>
using boost::multiprecision::cpp_int;
typedef std::pair<cpp_int, int> MyPair;
namespace mp_hashing {
namespace io = boost::iostreams;
struct hash_sink {
hash_sink(size_t& seed_ref) : _ptr(&seed_ref) {}
typedef char char_type;
typedef io::sink_tag category;
std::streamsize write(const char* s, std::streamsize n) {
boost::hash_combine(*_ptr, boost::hash_range(s, s+n));
return n;
}
private:
size_t* _ptr;
};
template <typename T> struct hash_impl {
size_t operator()(T const& v) const {
using namespace boost;
size_t seed = 0;
{
iostreams::stream<hash_sink> os(seed);
archive::binary_oarchive oa(os, archive::no_header | archive::no_codecvt);
oa << v;
}
return seed;
}
};
}
namespace std {
template <typename backend>
struct hash<boost::multiprecision::number<backend> >
: mp_hashing::hash_impl<boost::multiprecision::number<backend> >
{};
}
struct pair_hash {
template <class T1, class T2>
std::size_t operator () (const std::pair<T1,T2> &p) const {
auto h1 = std::hash<T1>{}(p.first);
auto h2 = std::hash<T2>{}(p.second);
// Mainly for demonstration purposes, i.e. works but is overly simple
// In the real world, use sth. like boost.hash_combine
return h1 ^ h2;
}
};
void function()
{
std::unordered_map<MyPair, double, pair_hash> M;
}
推荐答案
是的,您采用了我之前提供的Multiprecision哈希,并为std::pair
添加了哈希.我不喜欢手动推散列组合(好的普通散列组合并非微不足道).
Yes, you took the Multiprecision hash I contributed earlier and added the hash for std::pair
. I'm not a fan of handrolling the hash combination (good general hash combination is not trivial).
所以我要对boost::hash_combine
做同样的事情:
So I'd do the same with boost::hash_combine
:
template <typename K, typename V>
struct hash<std::pair<K, V> >
{
size_t operator()(std::pair<K, V> const& pair) const {
size_t seed = std::hash<K>{}(pair.first);
boost::hash_combine(seed, pair.second);
return seed;
}
};
#include <iostream>
#include <iomanip>
#include <boost/archive/binary_oarchive.hpp>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_int/serialize.hpp>
#include <boost/iostreams/device/back_inserter.hpp>
#include <boost/iostreams/stream_buffer.hpp>
#include <boost/iostreams/stream.hpp>
#include <boost/functional/hash.hpp>
namespace mp_hashing {
namespace io = boost::iostreams;
struct hash_sink {
hash_sink(size_t& seed_ref) : _ptr(&seed_ref) {}
typedef char char_type;
typedef io::sink_tag category;
std::streamsize write(const char* s, std::streamsize n) {
boost::hash_combine(*_ptr, boost::hash_range(s, s+n));
return n;
}
private:
size_t* _ptr;
};
template <typename T> struct hash_impl {
size_t operator()(T const& v) const {
using namespace boost;
size_t seed = 0;
{
iostreams::stream<hash_sink> os(seed);
archive::binary_oarchive oa(os, archive::no_header | archive::no_codecvt);
oa << v;
}
return seed;
}
};
}
#include <unordered_map>
#include <boost/unordered_map.hpp>
namespace std {
template <typename backend>
struct hash<boost::multiprecision::number<backend> >
: mp_hashing::hash_impl<boost::multiprecision::number<backend> >
{};
template <typename K, typename V>
struct hash<std::pair<K, V> >
{
size_t operator()(std::pair<K, V> const& pair) const {
size_t seed = std::hash<K>{}(pair.first);
boost::hash_combine(seed, pair.second);
return seed;
}
};
}
int main() {
using boost::multiprecision::cpp_int;
std::unordered_map<std::pair<cpp_int, int>, int> m {
{ { cpp_int(1) << 111, -1 }, 1 },
{ { cpp_int(2) << 222, -2 }, 2 },
{ { cpp_int(3) << 333, -3 }, 3 },
};
for (auto& p : m)
std::cout << p.first.first << " -> " << p.second << "\n";
}
这篇关于C ++:使用一对(cpp_int,int)整数作为unordered_map中的键(其中cpp_int是升压多精度整数)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!