{"Bill Gates", 86.0, "USA"},
{"Warren Buffet", 75.6, "USA"},
{"Jeff Bezos", 72.8, "USA"},
{"Amancio Ortega", 71.3, "Spain"},
{"Mark Zuckerberg", 56.0, "USA"},
{"Carlos Slim", 54.5, "Mexico"},
// ...
{"Bernard Arnault", 41.5, "France"},
// ...
{"Liliane Bettencourt", 39.5, "France"},
// ...
{"Wang Jianlin", 31.3, "China"},
{"Li Ka-shing", 31.2, "Hong Kong"}
// ...
};
4. Теперь определим ассоциативный массив. В нем строка, содержащая страну, соотносится с парой. Пара включает неизменяемую копию первого миллиардера из каждой страны из нашего списка. Эти люди являются самыми богатыми жителями своей страны. Другая переменная, входящая в пару, — счетчик, который будет увеличиваться на каждого последующего миллиардера в стране:
map<string, pair<const billionaire, size_t>> m;
5. Теперь пройдем по списку и попробуем для каждой страны заменить соответствующее значение новой парой. Пара включает ссылку на миллиардера, которого мы просматриваем в данный момент, и значение счетчика, равное 1:
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<iterator, bool> 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. Таким образом мы просто переключимся с одной реализации на другую, которая имеет иные характеристики производительности. В этом примере есть единственное отличие: ассоциативный массив больше не будет выводиться в алфавитном порядке, поскольку подобные массивы на основе хешей не упорядочивают свои объекты так, как это делается для деревьев поиска.