Позиция определяется с помощью функции STL lower_bound, принимающей три аргумента. Первые два из них указывают на начало и конец диапазона. В нашем случае таковым является вектор слов. Третий аргумент — вставляемое слово. Функция находит первый элемент диапазона, который больше ее третьего параметра или равен ему, и возвращает итератор, указывающий на него.
Определив правильную позицию, мы передаем ее методу insert контейнера std::vector, который принимает всего два аргумента. Первый аргумент — итератор, указывающий на позицию в векторе, в которую будет вставлен второй параметр. Очень удобно, что можно использовать итератор, возвращаемый функцией lower_ bound. Второй аргумент — это, конечно же, вставляемый элемент.
Дополнительная информация
Функция insert_sorted довольно универсальна. Если мы обобщим типы ее параметров, то она будет работать и с другими типами содержимого контейнеров, и даже для других контейнеров, таких как 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 {