Почему я не могу использовать ни std::unordered_map, ни boost::unordered_map с типами boost::multiprecision?

Я пытаюсь создать STL (или boost) unordered_map с boost::mulprecision типами, например. cpp_int, но gcc выдает ошибки после попытки вставить элементы в этот контейнер.

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

Полный журнал ошибок находится здесь

Первая из ошибок:

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

Есть ли ограничение на использование контейнера STL/boost в отношении типов мультиточности boost? Я использую буст 1.54.

ИЗМЕНИТЬ:

В вопросе, который может быть дубликатом, используется поддержка сериализации boost::multiprecision, которая был добавлен в boost 1.56 (по крайней мере, в соответствии с различиями в документах @1.55 и @1.56.

Кроме того, в этом вопросе не было упомянуто никаких других подходов для решения этой проблемы без поддержки сериализации в boost::multiprecision.


c++ boost stl unordered-map multiprecision
person Patryk    schedule 18.08.2015    source источник
comment
Как говорится, для этого типа не существует функции hash_value. Вам нужно написать один.   -  person David Schwartz    schedule 19.08.2015
comment
Прочтите документацию для неупорядоченных коллекций. В основном это хеш-таблицы, и поэтому им нужна хеш-функция. Сообщение об ошибке, которое вы получаете, совершенно ясно.   -  person Jody Hagins    schedule 19.08.2015

Ответы (1)


arrow_upward
3
arrow_downward

Ваш "вопрос, который может быть дубликатом" документирует рабочий техника в самом вопросе - хеширование строкового представления:

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

Примечания:

  • Я не знаю, выводит ли cpp_int::str() полную точность, которую хранит тип, но если это не так, то разные значения, дающие одно и то же str(), и, следовательно, хеш будут сталкиваться в одном и том же сегменте в хеш-таблице, что не нарушит функциональность, но уходит от O(1) к производительности O(N). Таким образом, если по умолчанию str() не отображает полную точность, но есть способ заставить ее, это было бы хорошей идеей, если вы имеете дело с большим количеством значений, отличающихся очень незначительно.

  • Как и при любом использовании типов с плавающей запятой в качестве ключей, будьте осторожны, так как крошечные различия в округлении могут привести к тому, что существующие записи карты не будут найдены/сопоставлены, и, следовательно, непреднамеренные «дубликаты» и т. д.

Если ваша программа слишком медленная, и профиль доказывает, что причиной является хеширование, тогда побеспокойтесь об альтернативах или обновлении Boost....

person Tony Delroy    schedule 19.08.2015