m {{"b", 1}, {"c", 2}, {"d", 3}};
3. Теперь вставим несколько элементов и для каждого из них используем подсказку для вставки. Поскольку изначально ее у нас нет, выполним первую операцию вставки, указывая на конечный итератор ассоциативного массива:
auto insert_it (std::end(m));
4. Вставим элементы в порядке, обратном алфавитному, используя имеющуюся у нас подсказку для вставки, а затем повторно инициализируем ее значением, которое возвращает функция insert. Следующий элемент будет вставлен прямо перед подсказкой:
for (const auto &s : {"z", "y", "x", "w"}) {
insert_it = m.insert(insert_it, {s, 1});
}
5. Чтобы продемонстрировать, как не нужно решать задачу, вставим строку, которая окажется с левого края ассоциативного массива, но зададим для нее неправильную подсказку, указывающую на крайнюю правую позицию ассоциативного массива —
end
:
m.insert(std::end(m), {"a", 1});
6. Наконец, просто выведем на экран полученный результат.
for (const auto & [key, value] : m) {
std::cout << "\"" << key << "\": " << value << ", ";
}
std::cout << '\n';
}
7. Скомпилировав и запустив программу, мы получим следующий результат. Очевидно, ошибочная подсказка при вставке ничего не испортила, поскольку порядок ассоциативного массива все еще правильный:
"a": 1, "b": 1, "c": 2, "d": 3, "w": 1, "x": 1, "y": 1, "z": 1,
Как это работает
Единственное отличие от обычной вставки в этом примере заключается в том, что мы используем дополнительный итератор-подсказку. Кроме того, мы говорили о правильных и неправильных подсказках.
Правильная подсказка будет указывать на существующий элемент, чье значение превышает значение вставляемого элемента, чтобы новый элемент занял позицию прямо перед ней. Если с подсказкой, предоставленной пользователем, это невозможно сделать, то функция
insert
откатится к неоптимизированной версии, которая выполнится за время O(log(n)).Во время первой вставки у нас есть итератор, указывающий на конечный элемент ассоциативного массива, поскольку у нас нет более удачной стартовой позиции. После вставки в дерево символа
z
нам станет известно, что прямо перед ним будет вставлен символ y
, и это вполне сгодится на роль правильной подсказки. То же применимо и к символу x
, если мы будем вставлять его в дерево после добавления символа y
, и т.д. Именно поэтому вы можете использовать итератор, который был возвращен последней операцией вставки, для выполнения следующей вставки.
Важно знать, что до появления С++11 подсказки для вставки считались правильными, если указывали на позицию, которая стоит перед вновь вставленным элементом.
Дополнительная информация
Что интересно, неправильная подсказка не нарушает порядок элементов в ассоциативном массиве. Как же тогда это вообще работает и что же означает выражение «амортизированное время вставки равно O(1)»?
Контейнер
std::map
обычно реализуется с применением бинарного дерева поиска. При вставке в данное дерево новый ключ сравнивается с ключами других узлов, начиная с вершины. Если ключ меньше или больше, чем ключ текущего узла, то алгоритм поиска смещается влево или вправо и опускается вниз на один узел. Выполняя такие операции, поисковый алгоритм остановится в точке, где глубина текущего дерева максимальна, и поместит туда новый узел и его ключ. Вполне возможно, что данный шаг нарушит баланс дерева, поэтому после вставки будет выполнен алгоритм перебалансировки.Когда мы вставляем в дерево элементы, которые имеют ключи, являющиеся непосредственными соседями друг друга (например, целое число
1
выступает соседом целого числа 2
, поскольку нельзя поместить между ними ни одно целое число), они часто могут оказаться в дереве рядом друг с другом. Это нетрудно проверить, если это верно для определенного ключа и соответствующей подсказки. В таком случае в алгоритме вставки будет пропущен этап поиска, что позволит сэкономить существенное количество времени. Тем не менее после этого все равно может быть запущен алгоритм перебалансировки. Поскольку такую оптимизацию можно выполнять часто (хоть и не всегда), это приводит к повышению средней производительности. После выполнения нескольких вставок итоговая сложность алгоритма снижается, вот и получается амортизированная сложность (рис. 2.3).
Если же подсказка ошибочна, то функция вставки попросту проигнорирует ее и начнет работу с выполнения алгоритма поиска. В итоге она отработает корректно, но, очевидно, медленнее.
Эффективно изменяем ключи элементов std::map
Поскольку структура данных
std::map
соотносит ключи со значениями таким образом, что ключи всегда уникальны и отсортированы, очень важно исключить для пользователей возможность изменить ключи узлов, которые уже вставлены в контейнер. Чтобы пользователи не могли изменять ключи элементов идеально отсортированных узлов ассоциативного массива, к типу ключа добавляется слово const
.Такого рода ограничение разумно, поскольку пользователю будет сложнее неправильно задействовать контейнер
std::map
. Но что же делать, если нам вдруг действительно понадобится изменить ключи некоторых элементов ассоциативного массива?До появления С++17 нам приходилось удалять элементы, для которых нужно изменить ключ, а затем вставлять их снова. Недостаток такого подхода состоит в выполнении бесполезных выделений и высвобождений памяти, что плохо с точки зрения производительности.
Начиная с С++17 можно удалить и снова вставить элементы ассоциативного массива без повторного выделения памяти. Далее мы увидим, как это работает.
Как это делается
В этом примере мы реализуем небольшое приложение, которое упорядочивает список водителей, участвующих в вымышленной гонке, в структуре
std::map
. По мере того, как водители обходят друг друга во время гонки, нужно изменять ключи, показывающие их текущее место. Мы будем делать это в стиле С++17.
1. Начнем с того, что включим все необходимые заголовочные файлы и объявим об использовании пространства имен
std
:
#include
#include
using namespace std;
2. Мы выведем на экран места всех водителей до и после изменения контейнера map, поэтому реализуем вспомогательную функцию, посвященную именно этому:
template
void print(const M &m)
{
cout << "Race placement:\n";
for (const auto &[placement, driver] : m) {
cout << placement << ": " << driver << '\n';
}
}
3. В функции
main
создадим и инициализируем ассоциативный массив, в котором целые числа, указывающие текущее место гонщика, будут соотноситься со строками, содержащими его имя. Кроме того, выведем содержимое ассоциативного массива на экран, поскольку на следующих шагах изменим его.
int main()
{
map 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. Она удаляет элементы из массива, притом не вызывая побочных эффектов, связанных с выделением памяти. Создадим также новую область видимости для данной задачи.