std::map, std:unordered_map и ключ-структура

238

19 февраля 2019, 05:40

Есть вот такая простенькая структура:

struct Point
{
    ll X;
    ll Y;
    Point(ll a = 0, ll b = 0)
    {
        X = a;
        Y = b;
    }
};

Требуется словарь с ключем в качестве этой структуры. Для map нужно перегружать оператор "<", это понятно. unordered_map оператор "<" не требуется, зато вот так ругается:

c++\bits\hashtable_policy.h|85|error: no match for call to '(const std::hash) (const Point&)'|

Каким образом исправлять?

И еще один момент. Возможно ли организовать передачу аргументов в конструктор структуры по ссылке, чтобы была возможность создания массива данной структуры? По (ll &a, ll &b) массив создать не может, ввиду отсутствия инициализации. Каким образом инициализацию по ссылкам организовать? Вариант без ссылок крайне нежелателен из-за огромного объема данных.

Answer 1

Для std::unordered_map<> нужны функции, вычисляющие хеш ключа и равенство ключей. Пример использования есть в документации.

upd:

Для второго вопроса

struct Point
{
    ll X = 0;
    ll Y = 0;
    Point(ll& a) : X(a)
    {
    }
    Point(ll& a, ll& b) : X(a), Y(b)
    {
    }
};

Answer 2

Определите собственный функтор для вычисления хэша ваших структур. Вот один из возможных.

// собственная специализация std::hash, которую можно внедрить в пространство имён std
namespace std
{
    template<> struct hash<Point>
    {
        typedef Point argument_type;
        typedef std::size_t result_type;
        result_type operator()(argument_type const& s) const noexcept
        {
            result_type const h1 ( std::hash<ll>{}(s.X) );
            result_type const h2 ( std::hash<ll>{}(s.Y) );
            return h1 ^ (h2 << 1); // или используйте boost::hash_combine
        }
    };
}

Другие примеры смотрите в описании std::hash.