мы обобщим типы ее параметров, то она будет работать и с другими типами содержимого контейнеров, и даже для других контейнеров, таких как std::set, std::deque, std::list и т.д.! (Обратите внимание: контейнер set имеет собственную функцию-член lower_bound, которая делает то же самое, что и функция std::lower_bound, но более эффективно, поскольку создана специально для множеств.)
template <typename C, typename T>
void insert_sorted(C &v, const T &item)
{
const auto insert_pos (lower_bound(begin(v), end(v), item));
v.insert(insert_pos, item);
}
При попытке изменить тип контейнера, приведенный в примере, с std::vector на что-то еще нужно учитывать следующий факт: не все контейнеры поддерживают функцию std::sort. Этот алгоритм предполагает использование контейнеров с произвольным доступом. Таковым, например, не является контейнер std::list.
Вставляем элементы в контейнер std::map эффективно и в соответствии с условиями
Иногда нужно заполнить ассоциативный массив парами «ключ — значение», и при выполнении данной задачи можно столкнуться с двумя ситуациями.
1. Заданный ключ не существует. В этом случае создается новая пара «ключ — значение».
2. Заданный ключ уже существует. В такой ситуации берем существующий элемент и модифицируем его.
Конечно, мы могли бы просто воспользоваться методами insert или emplace контейнера map и проверить успешность их выполнения. Или же нужно модифицировать существующий элемент. В обоих вышеперечисленных случаях функции insert и emplace создают элемент, который мы пытаемся вставить, а во втором случае только что созданный элемент отбрасывается. В обоих случаях совершается бесполезный вызов конструктора.
Начиная с С++17, в STL появилась функция try_emplace, позволяющая создавать элементы только при условии, что мы выполняем именно вставку. Реализуем программу, принимающую список миллиардеров и создающую ассоциативный массив, в котором указывается количество миллиардеров в каждой стране. Наш пример не содержит элементов, на создание которых тратится много времени, и если мы окажемся в подобной ситуации в рамках реального проекта, то сможем без труда разрешить ее с помощью try_emplace.
Как это делается
В этом примере мы реализуем приложение, которое создает ассоциативный массив на основе списка миллиардеров. В нем отображаются названия стран и ссылки на самого богатого человека, проживающего в данной стране, а также счетчик, указывающий количество миллиардеров.
1. Как всегда, включим некоторые заголовочные файлы; объявим также об использовании пространства имен std по умолчанию:
#include <iostream>
#include <functional>
#include <list>
#include <map>
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<billionaire> 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<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. При успешной вставке элемента функция вернет итератор, указывающий на новый узел ассоциативного массива, объединенный в
