at
по умолчанию. Если полученный код слишком медленный, но при этом безошибочный, то вместо данной функции можно задействовать оператор []
в тех местах, где важна высокая производительность.
Дополнительная информация
Конечно, можно обработать ситуацию выполнения доступа к элементу, лежащему за пределами вектора, вместо того чтобы прерывать работу программы. Для ее обработки нужно перехватить исключение, которое в нашем случае будет сгенерировано функцией
at
. Сделать это нетрудно. Мы окружим вызов функции at
блоком try
и определим код обработки ошибки в блоке catch
:
try {
std::cout << "Out of range element value: "
<< v.at(container_size + 10) << '\n';
} catch (const std::out_of_range &e) {
std::cout << "Ooops, out of range access detected: "
<< e.what() << '\n';
}
Кстати говоря, контейнер
std::array
также предоставляет функцию at
.Сохраняем сортировку экземпляров класса std::vector
Массивы и векторы не сортируются самостоятельно. Если нам потребуется такая возможность, мы всегда можем воспользоваться структурами данных, которые предоставляют ее автоматически. Контейнер
std::vector
идеально подходит для нашего случая, ведь добавлять в него новые элементы в порядке сортировки несложно и удобно.
Как это делается
В этом примере мы заполним контейнер
std::vector
случайными словами, отсортируем их, а затем вставим дополнительные слова с учетом сортировки.
1. Сначала включим все необходимые заголовочные файлы:
#include
#include
#include
#include
#include
#include
2. Кроме того, объявим пространство имен
std
, чтобы не писать префиксы std::
:
using namespace std;
3. Далее напишем небольшую функцию
main
, в которой вектор заполняется случайными строками:
int main()
{
vector v {"some", "random", "words",
"without", "order", "aaa",
"yyy"};
4. Затем отсортируем вектор. Для этого воспользуемся некоторыми утверждениями и функцией
is_sorted
из STL, показывающей, что изначально вектор не был отсортирован, а теперь все его элементы расположены по порядку:
assert(false == is_sorted(begin(v), end(v)));
sort(begin(v), end(v));
assert(true == is_sorted(begin(v), end(v)));
5. Наконец, добавим случайные слова в отсортированный вектор с помощью новой функции
insert_sorted
, которую будем реализовывать далее. Эти слова сразу нужно помещать в правильную позицию, поэтому вектор останется отсортированным:
insert_sorted(v, "foobar");
insert_sorted(v, "zzz");
6. Теперь реализуем функцию
insert_sorted
и расположим ее перед функцией main:
void insert_sorted(vector&v, const string &word)
{
const auto insert_pos (lower_bound(begin(v), end(v), word));
v.insert(insert_pos, word);
}
7. Теперь вернемся в функцию
main
— туда, где мы остановились, — и продолжим работу, выведя содержимое вектора и увидев, что процедура вставки отработала:
for (const auto &w : v) {
cout << w << " ";
}
cout << '\n';
}
8. Компиляция и запуск программы дадут следующий результат:
aaa foobar order random some without words yyy zzz
Как это работает
Вся программа построена вокруг функции
insert_sorted
, решающей задачу, которой посвящен этот раздел. Для каждой новой строки эта функция определяет позицию в отсортированном векторе (куда нужно произвести вставку), позволяющую сохранить порядок строк в векторе. Однако мы предполагаем, что вектор был отсортирован заранее. Иначе этот подход не сработает.Позиция определяется с помощью функции STL
lower_bound
, принимающей три аргумента. Первые два из них указывают на начало и конец диапазона. В нашем случае таковым является вектор слов. Третий аргумент — вставляемое слово. Функция находит первый элемент диапазона, который больше ее третьего параметра или равен ему, и возвращает итератор, указывающий на него.Определив правильную позицию, мы передаем ее методу
insert
контейнера std::vector
, который принимает всего два аргумента. Первый аргумент — итератор, указывающий на позицию в векторе, в которую будет вставлен второй параметр. Очень удобно, что можно использовать итератор, возвращаемый функцией lower_ bound
. Второй аргумент — это, конечно же, вставляемый элемент.
Дополнительная информация
Функция
insert_sorted
довольно универсальна. Если мы обобщим типы ее параметров, то она будет работать и с другими типами содержимого контейнеров, и даже для других контейнеров, таких как std::set
, std::deque
, std::list
и т.д.! (Обратите внимание: контейнер set
имеет собственную функцию-член lower_bound
, которая делает то же самое, что и функция std::lower_bound
, но более эффективно, поскольку создана специально для множеств.)
template
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
.
Как это делается
В этом примере мы реализуем приложение, которое создает ассоциативный массив на основе списка миллиардеров. В нем отображаются названия стран и ссылки на самого богатого человека, проживающего в данной стране, а также счетчик, указывающий количество миллиардеров.