Применяем контейнер std::unordered_map для пользовательских типов
Использование контейнера std::unordered_map вместо std::map подразумевает дополнительную степень свободы при выборе типа ключа. Контейнер std::map требует наличия между ключами естественного порядка. Таким образом элементы можно отсортировать. Но если мы хотим, например, использовать в качестве ключа математический вектор? Мы не можем сказать, что вектор (0, 1) меньше или больше вектора (1, 0). Они просто указывают в разных направлениях. Это верно для контейнера std::unordered_map, поскольку мы станем различать элементы не по их величине, а по значениям их хеша. Единственное, что нужно сделать, — реализовать хеш-функцию для нашего собственного типа, а также оператор ==, который будет проверять идентичность двух объектов. В данном разделе мы рассмотрим пример такой реализации.
Как это делается
В примере мы определим простую структуру coord, которая по умолчанию не имеет хеш-функции, поэтому нам потребуется установить ее самостоятельно. Затем задействуем ее, задав соотношение значений coord с числами.
1. Сначала включим все необходимое, чтобы вывести на экран и использовать контейнер std::unordered_map:
#include <iostream>
#include <unordered_map>
2. Далее определим собственную структуру, которую не так-то просто хешировать с помощью существующих хеш-функций:
struct coord {
int x;
int y;
};
3. Нам нужна не только хеш-функция, которая позволит использовать структуру в качестве ключа для ассоциативного массива, основанного на хеше, но и реализация оператора сравнения:
bool operator==(const coord &l, const coord &r)
{
return l.x == r.x && l.y == r.y;
}
4. Чтобы расширить возможности хеширования, предоставляемые STL, добавим в пространство имен std свою специализацию шаблонной структуры std::hash. Оно содержит такие же псевдонимы (задаваемые с помощью using), как и другие специализации типа hash.
namespace std
{
template <>
struct hash<coord>
{
using argument_type = coord;
using result_type = size_t;
5. Основная часть данной структуры — определение функции operator(). Мы просто складываем значения численных членов структуры coord. Эта техника хеширования не самая лучшая, но для демонстрации подойдет. Хорошая хеш-функция пытается максимально равномерно распределить значения в рамках допустимого диапазона, чтобы сократить количество хеш-столкновений.
result_type operator()(const argument_type &c) const
{
return static_cast<result_type>(c.x)
+ static_cast<result_type>(c.y);
}
};
}
6. Теперь можно создать новый экземпляр контейнера std::unordered_map, который принимает в качестве ключа структуру coord и соотносит ее с некоторыми значениями. Поскольку этот раздел посвящен использованию собственных типов для контейнера std::unordered_map, наш пример почти завершен. Создадим ассоциативный массив, основанный на хеше, с нашим собственным типом, заполним его какими-нибудь элементами и выведем содержимое на экран:
int main()
{
std::unordered_map<coord, int> m {{{0, 0}, 1}, {{0, 1}, 2},
{{2, 1}, 3}};
for (const auto & [key, value] : m) {
std::cout << "{(" << key.x << ", " << key.y
<< "): " << value << "} ";
}
std::cout << '\n';
}
7. Компиляция и запуск программы дадут следующий результат:
$ ./custom_type_unordered_map
{(2, 1): 3} {(0, 1): 2} {(0, 0): 1}
Как это работает
Обычно при создании экземпляра ассоциативного массива, основанного на хеше, например std::unordered_map, мы пишем следующую команду:
std::unordered_map<key_type, value_type> my_unordered_map;
Не вполне очевиден тот факт, что при создании компилятором контейнера уточненного типа std::unordered_map за кулисами творится настоящее волшебство. Поэтому взглянем на полное определение шаблонного типа:
template<
class Key,
class T,
class Hash = std::hash<Key>,
class KeyEqual = std::equal_to<Key>,
class Allocator = std::allocator< std::pair<const Key, T>>