1. Как всегда, включим некоторые заголовочные файлы; объявим также об использовании пространства имен
std
по умолчанию:
#include
#include
#include
#include
using namespace std;
2. Определим структуру, которая представляет миллиардеров из нашего списка:
struct billionaire {
string name;
double dollars;
string country;
};
3. В функции
main
сначала определяем список миллиардеров. В мире существует множество миллиардеров, поэтому создадим краткий список, включающий самых богатых людей из отдельных стран. Этот список заранее упорядочен. Он основан на списке The World’s Billionaires («Миллиардеры мира»), создаваемом журналом Forbes и находящемся по адресу http://www.forbes.com/billionaires/list/
int main()
{
list billionaires {
{"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> 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 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)).Чтобы операция была более эффективной, функция вставки контейнера
std::map
принимает необязательный параметр, представляющий собой подсказку для вставки. Это, по сути, итератор, который указывает на место, близкое к будущей позиции вставляемого элемента. Если подсказка корректна, то амортизированное время вставки составит O(1).
Как это делается
В этом примере мы вставим несколько элементов в контейнер
std::map
и используем подсказки для вставки, чтобы снизить количество операций поиска.
1. Мы преобразуем строки в числа, поэтому включим заголовочные файлы для
std::map
и std::string
:
#include
#include
#include
2. Далее создаем ассоциативный массив, в котором содержатся некие символы:
int main()
{
std::map