C++17 STL Стандартная библиотека шаблонов

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

{

  using argument_type = coord;

  using result_type = size_t;

5. Основная часть данной структуры — определение функции operator(). Мы просто складываем значения численных членов структуры coord. Эта техника хеширования не самая лучшая, но для демонстрации подойдет. Хорошая хеш-функция пытается максимально равномерно распределить значения в рамках допустимого диапазона, чтобы сократить количество хеш-столкновений.

  result_type operator()(const argument_type &c) const

  {

    return static_cast(c.x)

      + static_cast(c.y);

    }

  };

}

6. Теперь можно создать новый экземпляр контейнера std::unordered_map, который принимает в качестве ключа структуру coord и соотносит ее с некоторыми значениями. Поскольку этот раздел посвящен использованию собственных типов для контейнера std::unordered_map, наш пример почти завершен. Создадим ассоциативный массив, основанный на хеше, с нашим собственным типом, заполним его какими-нибудь элементами и выведем содержимое на экран:

int main()

{

  std::unordered_map 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 my_unordered_map;

Не вполне очевиден тот факт, что при создании компилятором контейнера уточненного типа std::unordered_map за кулисами творится настоящее волшебство. Поэтому взглянем на полное определение шаблонного типа:

template<

  class Key,

  class T,

  class Hash = std::hash,

  class KeyEqual = std::equal_to,

  class Allocator = std::allocator< std::pair>

> class unordered_map;

В качестве первых двух типов шаблона мы выбрали coord и int, здесь все просто и очевидно. Три остальных типа шаблона являются необязательными, так что автоматически заполняются существующими стандартными шаблонными классами, которые сами принимают типы шаблонов. В случае если последние аргументы заполняются значениями по умолчанию, в качестве типов шаблонов передаются те типы, которые мы указали в первых двух аргументах.

Для нас сейчас особый интерес представляет шаблонный параметр class Hash: когда мы не указываем явно что-то другое, он будет специализирован как std::hash. STL уже содержит специализации std::hash, std::hash, std::hash и многие другие. Эти классы знают, как работать с подобными конкретными типами, что позволяет вычислять оптимальные хеш-значения.

Однако STL пока не знает, как рассчитывать хеш-значение на основе нашей структуры coord. Мы лишь определили еще одну специализацию, которая знает, как это делается. Компилятор теперь может пройти по списку всех известных специализаций для контейнера std::hash и найти нашу реализацию, что позволит соотнести ее с типом, который мы выбрали для ключа.

Если бы мы не добавили новую специализацию std::hash, а назвали бы имеющуюся вместо этого my_hash_type, то нам пришлось бы использовать следующую строку для создания объекта:

std::unordered_map my_unordered_map;

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