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

  for (const auto &b : billionaires) {

    auto [iterator, success] = m.try_emplace(b.country, b, 1);

6. При успешном выполнении данного шага не нужно больше ничего делать. Пара, для которой мы предоставили аргументы конструктора b, 1, была создана и вставлена в ассоциативный массив. Если вставка завершилась неудачно, поскольку страна-ключ уже существует, то пара не создавалась. Очень большой размер нашей структуры, описывающей миллиардера, сэкономит время, которое пришлось бы потратить на ее копирование.

Однако в случае неудачи нам все еще нужно увеличить счетчик для заданной страны:

    if (!success) {

      iterator->second.second += 1;

    }

  }

7. На этом все. Теперь можно вывести на экран точное количество миллиардеров, живущих в стране, а также имя самого богатого человека для каждой из них:

  for (const auto & [key, value] : m) {

    const auto &[b, count] = value;

    cout << b.country << " : " << count

         << " billionaires. Richest is "

         << b.name << " with " << b.dollars

         << " B$\n";

  }

}

8. Компиляция и запуск программы дадут следующий результат. (Конечно, он будет неполным, поскольку мы ограничили наш входной ассоциативный массив.)

$ ./efficient_insert_or_modify

China : 1 billionaires. Richest is Wang Jianlin with 31.3 B$

France : 2 billionaires. Richest is Bernard Arnault with 41.5 B$

Hong Kong : 1 billionaires. Richest is Li Ka-shing with 31.2 B$

Mexico : 1 billionaires. Richest is Carlos Slim with 54.5 B$

Spain : 1 billionaires. Richest is Amancio Ortega with 71.3 B$

USA : 4 billionaires. Richest is Bill Gates with 86 B$

Как это работает

Весь пример строится на функции try_emplace контейнера std::map, которая появилась в С++17. Она имеет следующую сигнатуру:

std::pair try_emplace(const key_type& k, Args&&... args);

Вставляемый ключ — параметр k, а связанное значение создается на основе набора параметров args. При успешной вставке элемента функция вернет итератор, указывающий на новый узел ассоциативного массива, объединенный в пару со значением 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)).