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

Чтобы операция была более эффективной, функция вставки контейнера std::map принимает необязательный параметр, представляющий собой подсказку для вставки. Это, по сути, итератор, который указывает на место, близкое к будущей позиции вставляемого элемента. Если подсказка корректна, то амортизированное время вставки составит O(1).

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

В этом примере мы вставим несколько элементов в контейнер std::map и используем подсказки для вставки, чтобы снизить количество операций поиска.

1. Мы преобразуем строки в числа, поэтому включим заголовочные файлы для std::map и std::string:

#include

#include

#include

2. Далее создаем ассоциативный массив, в котором содержатся некие символы:

int main()

{

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