2, [1,2,3] и 3, [1,2,3].
Шаги 2 и 3 выполняются с помощью call_cart:
auto call_cart ([](auto f, auto x, auto ...rest) constexpr {
(void)std::initializer_list<int>{
(((x < rest)
? (void)f(x, rest)
: (void)0)
,0)...
}
});
Параметр x всегда содержит одно значение, взятое из множества, а rest включает все множество. Опустим условие (x < rest). Здесь выражение f(x, rest) и распакованный набор параметров ... генерируют вызовы функции f(1, 1), f(1, 2) и т.д., что приводит к появлению пар на экране. Это был шаг 2.
Шаг 3 достигается за счет фильтрации всех пар, к которым применяется условие
(x < rest)
Мы указали, что все лямбда-выражения и переменные, их содержащие, имеют модификатор constexpr. Это гарантирует, что компилятор оценит их код во время компиляции и скомпилирует бинарный файл, который уже содержит все числовые пары, вместо того, чтобы делать это во время работы программы. Обратите внимание: так происходит только в том случае, если все аргументы, которые мы предоставляем функции с модификатором constexpr, известны на этапе компиляции.
Глава 5
Основы работы с алгоритмами STL
В этой главе:
□ копирование элементов из одних контейнеров в другие;
□ сортировка контейнеров;
□ удаление конкретных элементов из контейнеров;
□ преобразование содержимого контейнеров;
□ поиск элементов в упорядоченных и неупорядоченных векторах;
□ ограничение допустимых значений вектора конкретным численным диапазоном с помощью std::clamp;
□ определение шаблонов в строках с помощью std::search и выбор оптимальной реализации;
□ выборка данных из крупных векторов;
□ создание перестановок во входных последовательностях;
□ реализация инструмента для слияния словарей.
Введение
Библиотека STL содержит не только структуры данных, но и алгоритмы. В то время как структуры помогают хранить и поддерживать данные разными способами для различных целей, алгоритмы позволяют выполнять конкретные преобразования данных в этих структурах.
Рассмотрим стандартную задачу, например сложение элементов вектора. Это можно без труда сделать с помощью цикла, в котором мы суммируем все элементы вектора и поместим их в переменную-аккумулятор sum:
vector<int> v {100, 400, 200 /*, ... */ };
int sum {0};
for (int i : v) { sum += i; }
cout << sum << 'n';
Поскольку эта задача является стандартной, для ее решения предусмотрен алгоритм STL:
cout << accumulate(begin(v), end(v), 0) << 'n';
В таком случае при создании вручную цикл занимает не намного больше места и прочесть его не сложнее, чем одну строку, в которой говорится, что она делает: accumulate. Во многих ситуациях, однако, может возникнуть неловкий момент: приходится читать состоящий из десятка строк цикл только затем, чтобы узнать, что он решает стандартную задачу Х, вместо того чтобы увидеть одну строку кода, в которой используется стандартный алгоритм, чье имя явно указывает на то, какую задачу он решает, например accumulate, copy, move, transform или shuffle.
Основная идея заключается в том, чтобы предоставить множество алгоритмов, которые программисты могут использовать в повседневных задачах, не реализуя каждый раз повторно. Таким образом, разработчики могут просто применить готовый алгоритм и сконцентрироваться на решении новых задач вместо того, чтобы тратить время на проблемы, уже решенные средствами STL. Еще одно преимущество — корректность. При реализации одного и того же решения снова и снова возникает вероятность того, что в одной из попыток может появиться небольшая ошибка. В результате вы можете оказаться в неприятной ситуации, если коллега укажет на ошибку в коде во время обзора, а ведь вы вместо того, чтобы писать свой код, могли воспользоваться стандартным алгоритмом.
Еще одним важным качеством алгоритмов STL является эффективность. Многие из них предоставляют несколько специализированных реализаций одного алгоритма, по-разному решающих задачу, в зависимости от типа итератора, для которого они используются. Например, обнулить элементы вектора, содержащего целые числа, можно с помощью алгоритма std::fill. Поскольку итератор вектора может указать компилятору, что итерирует по непрерывной памяти, он может выбрать ту реализацию алгоритма std::fill, которая задает процедуру C memset. Если программист изменяет тип контейнера с vector на list, то алгоритм STL больше не может использовать процедуру memset и должен итерировать по списку, чтобы обнулять элементы по одному. В том случае, если программист сам задействует процедуру memset, алгоритм обнуления сможет работать только с векторами и массивами, поскольку другие структуры не хранят данные во фрагментах непрерывной памяти. В большинстве случаев не стоит изобретать велосипед, поскольку авторы библиотеки STL уже реализовали эти идеи и вам ничто не мешает воспользоваться их трудом.
Подытожим. Алгоритмы STL предоставляют такие преимущества.
□ Легкость сопровождения: по названию алгоритма сразу понятно, что именно он делает. Явные циклы зачастую труднее прочесть, и им нужно знать о том, какие именно структуры данных будут применяться, в отличие от стандартных алгоритмов.
□ Правильность: библиотеку STL создавали и анализировали профессионалы, она используется и тестируется многими программистами, и вам, скорее всего, не удастся достичь той же степени правильности, если вы будете самостоятельно реализовывать сложные фрагменты алгоритмов.
□ Эффективность: по умолчанию алгоритмы STL эффективны как минимум настолько же, насколько эффективны циклы, написанные вручную.
Большинство алгоритмов работают с итераторами. Принципы работы итераторов мы уже рассмотрели в главе 3. В настоящей главе сконцентрируемся на использовании алгоритмов STL для решения конкретных задач, чтобы понять, какие возможности они предоставляют. Разбор всех алгоритмов превратит эту книгу в очень скучный справочный материал по С++, а подобное руководство уже доступно для широкого круга читателей.
Самый лучший способ стать мастером STL заключается в том, чтобы всегда иметь справочный материал по С++ под рукой или хотя бы в закладках браузера. При решении какой-нибудь задачи каждый программист должен задуматься: «Существует ли в STL алгоритм для решения моей задачи?» — прежде чем писать код самостоятельно.
Хорошая и полная справка по C++ доступна по адресу http://en.cppreference.com/w/. Кроме того, этот материал можно скачать для чтения в режиме офлайн.
На собеседованиях хорошее знание алгоритмов STL зачастую считается показателем глубоких знаний языка С++.
Копируем элементы из одних контейнеров в другие
Большинство важных структур данных STL поддерживают итераторы. Это значит, что вы как минимум сможете получить итераторы с помощью функций
