Why I cannot use neither std::unordered_map nor boost::unordered_map with boost::multiprecision types?

Question

I am trying to create a STL (or boost) unordered_map with boost::mulprecision types e.g. cpp_int but gcc throws errors after trying to insert elements to this container.

#include <boost/multiprecision/cpp_int.hpp>
#include <boost/unordered_map.hpp>

using namespace boost::multiprecision;

int main()
{
  cpp_int z(123123123);
  cpp_int x(123123123);

  boost::unordered_map<cpp_int, cpp_int> data;

  // line below will throw compilation errors
  //data.insert(std::make_pair(z,x));
  return 0;
}

Full error log is here

First of the errors:

In file included from /usr/include/boost/functional/hash/hash.hpp:529:0,
                 from /usr/include/boost/functional/hash.hpp:6,
                 from /usr/include/boost/unordered/unordered_map.hpp:20,
                 from /usr/include/boost/unordered_map.hpp:16,
                 from main.cpp:2:
/usr/include/boost/functional/hash/extensions.hpp: In instantiation of
  ........
main.cpp:13:34:   required from here
/usr/include/boost/functional/hash/extensions.hpp:269:34: error: no matching function for call to ‘hash_value(const boost::multiprecision::number<boost::multiprecision::backends::cpp_int_backend<> >&)’
             return hash_value(val);
                                  ^

Is there a limitation to STL/boost container usage regarding boost's multiprecision types? I am using boost 1.54.

EDIT:

The question of which this might be a duplicate uses boost::multiprecision's serialization support which has been added in boost 1.56 (at least according to differences in docs @1.55 and @1.56.

Also, in that question there has been no other approaches mentioned to solve this issue without serialization support in boost::multiprecision.

As it says, no `hash_value` function exists for this type. You need to write one. — David Schwartz, Aug 18 '15 at 21:24
Read the documentation for unordered collections. They are basically hash tables, and as such need a hash function. The error message you are getting is quite clear. — Jody Hagins, Aug 18 '15 at 21:51

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

Your "question of which this might be a duplicate" documents a working technique in the question itself - hashing the string representation:

#include <boost/multiprecision/cpp_int.hpp>
#include <boost/unordered_map.hpp>

using namespace boost::multiprecision;

template <typename T>
struct hash_str
{
    size_t operator()(const T& t) const { return std::hash<std::string>()(t.str()); }
};

int main()
{
  cpp_int z(123123123);
  cpp_int x(123123123);

  boost::unordered_map<cpp_int, cpp_int, hash_str<cpp_int>> data;

  data.insert(std::make_pair(z,x));
}

Notes:

I don't know if cpp_int::str() outputs the full precision the type stores, but if it doesn't then distinct values yielding the same str() and hence hash will collide in the same bucket in the hash table, which won't break the functionality but moves away from O(1) towards O(N) performance. So, if by default str() doesn't display full precision but there's a way to force it, that would be a good idea if you deal in lots of values differing very slightly.
As with all uses of floating point types as keys, be careful as tiny rounding differences can lead to existing map entries not being found/matched, and hence unintended "duplicates" etc..

It your program is too slow and the profile proves the hashing is the cause, then worry about alternatives or upgrading boost....

Why I cannot use neither std::unordered_map nor boost::unordered_map with boost::multiprecision types?

1 Answers1