Шрифт:
Интервал:
Закладка:
В нашей ситуации описанная характеристика очень полезна: когда мы видим миллиардера из конкретной страны в первый раз, это говорит о том, что ее еще нет в ассоциативном массиве. В таком случае нам следует добавить эту страну и установить значение счетчика, равное 1. Если мы уже встречали миллиардера из этой страны, то нужно получить ссылку на существующий счетчик, чтобы увеличить его. Именно это и происходит на шаге 6:
if (!success) {
iterator->second.second += 1;
}
Обратите внимание: функции insert и emplace контейнера std::map работают одинаково. Основное различие между ними заключается в том, что функция try_emplace не будет создавать объект, связанный с ключом, если последний уже существует. Это повышает производительность в ситуациях, когда создание объектов занимает много времени.
Дополнительная информация
Наша программа продолжит работать, если мы сменим тип контейнера с std::map на std::unordered_map. Таким образом мы просто переключимся с одной реализации на другую, которая имеет иные характеристики производительности. В этом примере есть единственное отличие: ассоциативный массив больше не будет выводиться в алфавитном порядке, поскольку подобные массивы на основе хешей не упорядочивают свои объекты так, как это делается для деревьев поиска.
Исследуем новую семантику подсказок для вставки элементов с помощью метода std::map::insert
Поиск элементов в контейнере std::map занимает время O(log(n)). То же касается вставки новых элементов, поскольку позицию, на которую нужно добавить новый элемент, тоже необходимо найти. Простая вставка М новых элементов займет время O(M * log(n)).
Чтобы операция была более эффективной, функция вставки контейнера std::map принимает необязательный параметр, представляющий собой подсказку для вставки. Это, по сути, итератор, который указывает на место, близкое к будущей позиции вставляемого элемента. Если подсказка корректна, то амортизированное время вставки составит O(1).
Как это делается
В этом примере мы вставим несколько элементов в контейнер std::map и используем подсказки для вставки, чтобы снизить количество операций поиска.
1. Мы преобразуем строки в числа, поэтому включим заголовочные файлы для std::map и std::string:
#include <iostream>
#include <map>
#include <string>
2. Далее создаем ассоциативный массив, в котором содержатся некие символы:
int main()
{
std::map<std::string, size_t> 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, поскольку нельзя поместить между ними ни одно целое число), они часто могут оказаться в дереве рядом друг с другом. Это нетрудно проверить, если это верно для определенного ключа и соответствующей подсказки. В таком случае в алгоритме вставки будет пропущен этап поиска, что позволит сэкономить существенное количество времени. Тем не менее после этого все равно может быть запущен алгоритм перебалансировки. Поскольку