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

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;

};