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

пару со значением true логического типа. В противном случае булева переменная в паре будет иметь значение false, а итератор станет указывать на элемент, с которым пересекается вставляемый элемент.

В нашей ситуации описанная характеристика очень полезна: когда мы видим миллиардера из конкретной страны в первый раз, это говорит о том, что ее еще нет в ассоциативном массиве. В таком случае нам следует добавить эту страну и установить значение счетчика, равное 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, поскольку нельзя поместить между ними ни одно целое число), они часто могут оказаться в дереве рядом друг с другом. Это нетрудно проверить, если это верно для определенного ключа и соответствующей подсказки. В таком случае в алгоритме вставки будет пропущен этап поиска, что позволит сэкономить существенное количество времени. Тем не менее после этого все равно может быть запущен алгоритм перебалансировки. Поскольку