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

Применяем контейнер 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>>

> class unordered_map;

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

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

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

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

std::unordered_map<coord, value_type, my_hash_type> my_unordered_map;

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

Отсеиваем повторяющиеся слова из пользовательского ввода и выводим их на экран в алфавитном порядке с помощью контейнера std::set

 Контейнер std::set довольно странный. Принцип его работы похож на принцип работы контейнера std::map. Однако std::set содержит только ключи в качестве значений, а не пары «ключ — значение». Поэтому он не очень подходит для соотношения значения одного типа со значениями другого. Поскольку способы применения этого контейнера не вполне очевидны, многие разработчики даже не знают о его существовании. Они часто начинают реализовывать похожие механизмы самостоятельно, хотя в некоторых ситуациях контейнер std::set оказался бы отличным подспорьем.

В этом разделе будет показано, как применить контейнер std::set, на примере, в котором мы получаем потенциально большое количество разных элементов. Мы отфильтруем их и выведем на экран уникальные элементы.

Как это делается

В этом примере мы считаем поток