2

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

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>.

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

This doesn't compile:

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

My question is: how to use pairs of (cpp_int,int) as keys in an unordered_map?

Thank you very much in advance!

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;
    }
f10w
  • 1,524
  • 4
  • 24
  • 39
  • Do you have a hash for cpp_int? Do you know how to combine hashes? If yes to both, what is your problem? If no, what have you tried? – Yakk - Adam Nevraumont Dec 09 '17 at 18:28
  • @Ron I've updated the question. Sorry it was not very clear. – f10w Dec 09 '17 at 18:40
  • @Yakk I'm pretty new to these things, I haven't found what I need on the web, so... I don't have a hash for cpp_int. – f10w Dec 09 '17 at 18:41
  • You do now though, @Khue (next time, simply search for that :)). Here's a live demo with MSVC using `unordered_map`: http://rextester.com/l/cpp_online_compiler_visual /cc @Yakk – sehe Dec 09 '17 at 18:49
  • @sehe Thanks for your link to the similar question. I've played with it for a while and am about to come up with a solution I think. – f10w Dec 09 '17 at 18:50
  • @sehe There's nothing in the demo? – f10w Dec 09 '17 at 18:51
  • @sehe I've updated the question with a solution at the end. Could you please share your opinion on it? Thanks a lot! – f10w Dec 09 '17 at 19:00
  • @Khue oops I messed up the link (should have been http://rextester.com/UHZQCZ49900). Anyways, I made up for my mistake by posting a full reply – sehe Dec 09 '17 at 19:05
  • 1
    Yup, as I wrote: "Mainly for demonstration purposes, i.e. works but is overly simple" As you are using boost anyways. `boost.hash_combine` or, even more straight forward, `boost::hash_value(std::pair)` is the way to go. http://www.boost.org/doc/libs/1_65_1/doc/html/hash/reference.html – Baum mit Augen Dec 10 '17 at 00:34
  • @BaummitAugen Thanks. I've got a working solution (to the shortest Hamiltonian path problem that I mentioned in [this question](https://stackoverflow.com/questions/47723270/c-how-to-implement-sparse-matrices-with-very-large-indices)) but it is not practical at all for high numbers of nodes (e.g. > 100). I'm trying now other methods (such as Depth-first search). – f10w Dec 10 '17 at 19:46

1 Answers1

1

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).

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

Live On MSVC RexTester

#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";
}
sehe
  • 374,641
  • 47
  • 450
  • 633