Почему я не могу скомпилировать unordered_map с парой в качестве ключа?

Ответ 1

Вам необходимо предоставить подходящую хеш-функцию для вашего типа ключа. Простой пример:

#include <unordered_map>
#include <functional>
#include <string>
#include <utility>

// Only for pairs of std::hash-able types for simplicity.
// You can of course template this struct to allow other hash functions
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;  
    }
};

using Vote = std::pair<std::string, std::string>;
using Unordered_map = std::unordered_map<Vote, int, pair_hash>;

int main() {
    Unordered_map um;
}

Это будет работать, но не будет иметь лучших хэш-свойств ^†. Возможно, вы захотите взглянуть на что-то вроде boost.hash_combine для получения более качественных результатов при объединении хэшей.

Для реального использования: Boost также предоставляет набор функций hash_value который уже предоставляет хеш-функцию для std::pair, а также std::tuple и большинство стандартных контейнеров.

^† Точнее, он вызовет слишком много столкновений. Например, каждая симметричная пара будет хэшировать до 0, а пары, отличающиеся только перестановкой, будут иметь одинаковый хеш. Это, вероятно, хорошо для вашего программирования, но может серьезно повредить производительности реального кода.

Ответ 2

Мой предпочтительный способ решения этой проблемы - определить функцию key, которая преобразует вашу пару в уникальное целое число (или любой хешируемый тип данных). Этот ключ не является хэш-ключом. Это уникальный идентификатор пары данных, который затем будет оптимально хэширован с помощью unordered_map. Например, вы хотели бы определить unordered_map типа

  unordered_map<pair<int,int>,double> Map;

И вы хотите использовать Map[make_pair(i,j)]=value или Map.find(make_pair(i,j)) для работы на карте. Тогда вам нужно будет сообщить системе, как хэшировать пару целых чисел make_pair(i,j). Вместо этого мы можем определить

  inline size_t key(int i,int j) {return (size_t) i << 32 | (unsigned int) j;}

а затем измените тип карты на

  unordered_map<size_t,double> Map;

Теперь мы можем использовать Map[key(i,j)]=value или Map.find(key(i,j)) для работы на карте. Каждый make_pair теперь вызывает функцию inline key.

Этот метод гарантирует, что ключ будет оптимально хэширован, потому что теперь хеширующая часть выполняется системой, которая всегда будет выбирать размер внутренней хеш-таблицы, чтобы убедиться, что каждый ведро одинаково вероятен. Но вам нужно сделать 100% уверенным, что key уникален для каждой пары, т.е. Никакие две отдельные пары не могут иметь один и тот же ключ, или могут быть очень трудные ошибки для поиска.

Ответ 3

Для ключа пары мы можем использовать хэш-функцию boost пары:

#include <iostream>
#include <boost/functional/hash.hpp>
#include <unordered_map>
using namespace std;

int main() {
  unordered_map<pair<string, string>, int, boost::hash<pair<string, string>>> m;

  m[make_pair("123", "456")] = 1;
  cout << m[make_pair("123", "456")] << endl;
  return 0;
}

Подобным же образом мы можем использовать усиление для векторов,

#include <iostream>
#include <boost/functional/hash.hpp>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
  unordered_map<vector<string>, int, boost::hash<vector<string>>> m;
  vector<string> a({"123", "456"});

  m[a] = 1;
  cout << m[a] << endl;
  return 0;
}

Ответ 4

Как указывает ваша ошибка компиляции, в вашем пространстве имен std нет действительного экземпляра std::hash<std::pair<std::string, std::string>>.

Согласно моему компилятору:

Ошибка C2338 Стандарт С++ не предоставляет хеш для этого тип. c:\program files (x86)\Microsoft Visual Studio 14.0\vc\include\xstddef 381

Вы можете предоставить свою специализацию для std::hash<Vote> следующим образом:

#include <string>
#include <unordered_map>
#include <functional>

using namespace std;
using Vote = pair<string, string>;
using Unordered_map = unordered_map<Vote, int>;

namespace std
{
    template<>
    struct hash<Vote>
    {
        size_t operator()(Vote const& v) const
        {
            // ... hash function here ...
        }
    };
}

int main()
{
    Unordered_map m;
}

Ответ 5

Если использование pair не является строгим требованием, вы можете просто использовать карту дважды.

#include <unordered_map>

using namespace std;
using Unordered_map = unordered_map<string, unordered_map<string, int>>;

Unordered_map um;
um["Region1"]["Candidate1"] = 10;
cout << um["Region1"]["Candidate1"];    // 10

Ответ 6

Я знаю, что это слишком наивная реализация по сравнению с другими ответами, но есть обходной путь.

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

unordered_hash<int, Vote> h;
using Unordered_map = unordered_map<i, int>; // i is corresponding value to pair

Ответ 7

В комментариях к ответу Baum mit Augen пользователь Джо Блэк попросил привести пример использования лямбда-выражений вместо определения хеш-функции. Я согласен с мнением Baum mit Augen, что это может повредить читабельности, особенно если вы хотите внедрить более универсальное решение. Поэтому я хотел бы, чтобы мой пример был коротким, сосредоточив внимание на конкретном решении для std::pair<std::string, std::string>, как представлено в OP. В примере также используется созданная вручную комбинация вызовов функций std::hash<std::string>:

using Vote = std::pair<std::string, std::string>;
auto hash = [](const Vote& v){
    return std::hash<std::string>()(v.first) * 31 + std::hash<std::string>()(v.second);
};
using Unordered_map = std::unordered_map<Vote, int, decltype(hash)>;
Unordered_map um(8, hash);

Код на Ideone