такую оптимизацию можно выполнять часто (хоть и не всегда), это приводит к повышению средней производительности. После выполнения нескольких вставок итоговая сложность алгоритма снижается, вот и получается амортизированная сложность (рис. 2.3).

Если же подсказка ошибочна, то функция вставки попросту проигнорирует ее и начнет работу с выполнения алгоритма поиска. В итоге она отработает корректно, но, очевидно, медленнее. 

Эффективно изменяем ключи элементов std::map

Поскольку структура данных std::map соотносит ключи со значениями таким образом, что ключи всегда уникальны и отсортированы, очень важно исключить для пользователей возможность изменить ключи узлов, которые уже вставлены в контейнер. Чтобы пользователи не могли изменять ключи элементов идеально отсортированных узлов ассоциативного массива, к типу ключа добавляется слово const.

Такого рода ограничение разумно, поскольку пользователю будет сложнее неправильно задействовать контейнер std::map. Но что же делать, если нам вдруг действительно понадобится изменить ключи некоторых элементов ассоциативного массива?

До появления С++17 нам приходилось удалять элементы, для которых нужно изменить ключ, а затем вставлять их снова. Недостаток такого подхода состоит в выполнении бесполезных выделений и высвобождений памяти, что плохо с точки зрения производительности.

Начиная с С++17 можно удалить и снова вставить элементы ассоциативного массива без повторного выделения памяти. Далее мы увидим, как это работает.

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

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

1. Начнем с того, что включим все необходимые заголовочные файлы и объявим об использовании пространства имен std:

#include <iostream>

#include <map>

using namespace std;

2. Мы выведем на экран места всех водителей до и после изменения контейнера map, поэтому реализуем вспомогательную функцию, посвященную именно этому:

template <typename M>

void print(const M &m)

{

  cout << "Race placement:n";

  for (const auto &[placement, driver] : m) {

    cout << placement << ": " << driver << 'n';

  }

}

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

int main()

{

  map<int, string> race_placement {

    {1, "Mario"}, {2, "Luigi"}, {3, "Bowser"},

    {4, "Peach"}, {5, "Yoshi"}, {6, "Koopa"},

    {7, "Toad"}, {8, "Donkey Kong Jr."}

  };

  print(race_placement);

4. Предположим, что на одном из кругов гонки у Боузера (Bowser) произошла небольшая авария и он откатился на последнее место, а Донки Конгу — младшему (Donkey Kong Jr.) представился шанс перескочить с последнего места на третье. В данном случае сначала нужно извлечь указанные элементы из ассоциативного массива, поскольку это единственный способ манипулировать их ключами. Функция extract — новая возможность С++17. Она удаляет элементы из массива, притом не вызывая побочных эффектов, связанных с выделением памяти. Создадим также новую область видимости для данной задачи.

  {

    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.

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