C++17 STL Стандартная библиотека шаблонов — страница 17 из 119

  {
    auto a (race_placement.extract(3));
    auto b (race_placement.extract(8));

5. Теперь поменяем местами ключи Боузера и Донки Конга — младшего. Несмотря на то, что ключи элементов ассоциативного массива обычно неизменяемы (поскольку объявлены с модификатором const), можно изменить ключи извлеченных элементов, полученных с помощью метода extract.

    swap(a.key(), b.key());

6. Метод insert контейнера std::map в С++17 получил новую перегруженную версию, которая принимает дескрипторы извлеченных узлов, чтобы вставить их в контейнер, не вызывая выделения памяти:

    race_placement.insert(move(a));
    race_placement.insert(move(b));
  }

7. Выходим из области видимости, и на этом все. Выводим на экран новые места гонщиков и позволяем приложению завершиться:

  print(race_placement);
}

8. Компиляция и запуск программы дадут следующий результат. Сначала мы видим изначальную расстановку гонщиков, а затем новую, которую получили после изменения позиций Боузера и Донки Конга — младшего:

$ ./mapnode_key_modification Race placement:
1: Mario
2: Luigi
3: Bowser
4: Peach
5: Yoshi
6: Koopa
7: Toad
8: Donkey Kong Jr.
Race placement:
1: Mario
2: Luigi
3: Donkey Kong Jr.
4: Peach
5: Yoshi
6: Koopa
7: Toad
8: Bowser

Как это работает

В C++17 контейнер std::map получил новую функцию-член extract. Она поставляется в двух версиях:

node_type extract(const_iterator position);
node_type extract(const key_type& x);

В этом примере мы используем вторую версию, которая принимает ключ, а затем находит и извлекает соответствующий ему элемент ассоциативного массива. Первая версия функции принимает итератор, что подразумевает ее более быструю работу, поскольку ей не нужно искать элемент.

Если мы попробуем извлечь с помощью второго метода (выполняющего поиск по ключу) элемент, которого не существует, то получим пустой экземпляр типа node_type. Метод-член empty() возвращает булево значение, которое указывает, пуст ли экземпляр node_type. Вызов любого метода для пустого экземпляра приводит к неопределенному поведению.

После извлечения узлов можно изменить их ключи с помощью метода key(), который предоставляет неконстантный доступ к ключам, несмотря на то что они обычно являются неизменяемыми.

Обратите внимание: для повторного добавления узлов в ассоциативный массив нужно передать их в функцию insert. Это логично, поскольку функция extract стремится избежать создания ненужных копий и выделения памяти. Еще одно примечание: хотя мы перемещаем экземпляр типа node_type, на самом деле никакие значения из контейнера не перемещаются.

Дополнительная информация

Элементы ассоциативного массива, которые были извлечены с помощью метода extract, обычно довольно гибкие. Можно извлечь элементы из одного экземпляра типа map и вставить их в любой другой экземпляр типа map или даже multimap. Это верно и для контейнеров unordered_map и unordered_multimap, а также set/multiset и, соответственно, unordered_set/unordered_multiset.

Для того чтобы можно было перемещать элементы из одной структуры ассоциативного массива или множества в другую, типы ключей, значений и средство выделения памяти должны быть идентичны. Обратите внимание: даже при совпадении этих типов мы не можем перемещать элементы из map в unordered_map или из set в unordered_set. 

Применяем контейнер std::unordered_map для пользовательских типов

 Использование контейнера std::unordered_map вместо std::map подразумевает дополнительную степень свободы при выборе типа ключа. Контейнер std::map требует наличия между ключами естественного порядка. Таким образом элементы можно отсортировать. Но если мы хотим, например, использовать в качестве ключа математический вектор? Мы не можем сказать, что вектор (0, 1) меньше или больше вектора (1, 0). Они просто указывают в разных направлениях. Это верно для контейнера std::unordered_map, поскольку мы станем различать элементы не по их величине, а по значениям их хеша. Единственное, что нужно сделать, — реализовать хеш-функцию для нашего собственного типа, а также оператор ==, который будет проверять идентичность двух объектов. В данном разделе мы рассмотрим пример такой реализации.

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

В примере мы определим простую структуру coord, которая по умолчанию не имеет хеш-функции, поэтому нам потребуется установить ее самостоятельно. Затем задействуем ее, задав соотношение значений coord с числами.

1. Сначала включим все необходимое, чтобы вывести на экран и использовать контейнер std::unordered_map:

#include 
#include 

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
{
  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
<