Дополнительная информация
Что интересно, неправильная подсказка не нарушает порядок элементов в ассоциативном массиве. Как же тогда это вообще работает и что же означает выражение «амортизированное время вставки равно O(1)»?
Контейнер std::map обычно реализуется с применением бинарного дерева поиска. При вставке в данное дерево новый ключ сравнивается с ключами других узлов, начиная с вершины. Если ключ меньше или больше, чем ключ текущего узла, то алгоритм поиска смещается влево или вправо и опускается вниз на один узел. Выполняя такие операции, поисковый алгоритм остановится в точке, где глубина текущего дерева максимальна, и поместит туда новый узел и его ключ. Вполне возможно, что данный шаг нарушит баланс дерева, поэтому после вставки будет выполнен алгоритм перебалансировки.
Когда мы вставляем в дерево элементы, которые имеют ключи, являющиеся непосредственными соседями друг друга (например, целое число 1 выступает соседом целого числа 2, поскольку нельзя поместить между ними ни одно целое число), они часто могут оказаться в дереве рядом друг с другом. Это нетрудно проверить, если это верно для определенного ключа и соответствующей подсказки. В таком случае в алгоритме вставки будет пропущен этап поиска, что позволит сэкономить существенное количество времени. Тем не менее после этого все равно может быть запущен алгоритм перебалансировки. Поскольку такую оптимизацию можно выполнять часто (хоть и не всегда), это приводит к повышению средней производительности. После выполнения нескольких вставок итоговая сложность алгоритма снижается, вот и получается амортизированная сложность (рис. 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 создадим и инициализируем ассоциативный массив, в котором целые числа, указывающие текущее место гонщика, будут соотноситься со строками, содержащими его имя. Кроме того, выведем содержимое ассоциативного массива на экран, поскольку на следующих шагах изменим его.