x
и набор параметров rest
. Они содержат реальные элементы, для которых мы будем искать декартово произведение. Взглянем на выражение f(x,rest)
: для x=1
и rest=2,3,4
мы получим вызовы f(1,2); f(1,3); f(1,4);
. Проверка (x < rest)
нужна для избавления от избыточности в сгенерированных парах. Мы рассмотрим этот вопрос более подробно позднее.
constexpr auto call_cart (
[=](auto f, auto x, auto ...rest) constexpr {
(void)std::initializer_list{
(((x < rest)
? (void)f(x, rest)
: (void)0)
,0)...
};
});
4. Функция
cartesian
— самая сложная часть кода всего примера. Она принимает набор параметров xs
и возвращает захватывающий его объект функции. Полученный объект функции принимает объект функции f
.Для набора параметров
xs=1,2,3
внутреннее лямбда-выражение сгенерирует следующие вызовы: call_cart(f,1,1,2,3); call_cart(f,2,1,2,3); call_cart(f,3,1,2,3);
. Из этого набора вызовов можно сгенерировать все необходимые пары произведения.Обратите внимание: мы дважды используем нотацию
...
для распаковки набора параметров xs
, что на первый взгляд может показаться странным. Первое включение конструкции ...
распаковывает весь набор параметров xs
в вызов call_cart
. Второе включение приводит к нескольким вызовам функции call_cart
, имеющим разные вторые параметры.
constexpr auto cartesian ([=](auto ...xs) constexpr {
return [=] (auto f) constexpr {
(void)std::initializer_list {
((void)call_cart(f, xs, xs...), 0)...
};
};
});
5. Теперь сгенерируем декартово произведение для численного множества
1
, 2
, 3
и выведем полученные пары на экран. Если не учитывать избыточные пары, то мы должны получить следующий результат: (1,2)
, (2,3)
и (1,3)
. Другие комбинации невозможны при условии, что не важен порядок и не нужны одинаковые числа в паре. Т.е. не нужны пары вроде (1,1)
, а пары (1,2)
и (2,1)
считаются одинаковыми.Сначала сгенерируем объект функции, который содержит все возможные пары и принимает функцию
print
. Далее используем его, чтобы позволить вызывать данную функцию для всех этих пар. Объявляем переменную print_cart
с модификатором constexpr;
это позволит гарантировать, что хранимый ею объект функции (и все сгенерированные пары) будет создаваться во время компиляции:
constexpr auto print_cart(cartesian(1,2,3));
print_cart(print);
}
6. Компиляция и запуск программы дадут следующий ожидаемый результат. Можно убрать условие
(x < xs)
из функции call_cart
, чтобы увидеть полное декартово произведение, содержащее избыточные пары и пары с одинаковыми номерами:
$ ./cartesian_product
(1, 2)
(1, 3)
(2, 3)
Как это работает
Мы создали еще одну очень сложную конструкцию с помощью лямбда-выражений. Но после того, как разберемся с ней, нас больше не запутают никакие другие лямбда-выражения!
Взглянем на нее более внимательно. Нам следует получить представление о том, что должно произойти (рис. 4.4).
Работа проходит в три шага.
1. Берем наше множество
1
, 2
, 3
и создаем на его основе три новых. Первая часть каждого из этих множеств — один элемент множества, а вторая — все множества.2. Объединяем первый элемент с каждым элементом множества и получаем все пары.
3. Из полученных пар выбираем те, которые не являются избыточными (например, пары
(1,2)
и (2,1)
избыточны) и не содержат одинаковых чисел (как, скажем, (1,1)
).Теперь вернемся к реализации:
constexpr auto cartesian ([=](auto ...xs) constexpr {
return [=](auto f) constexpr {
(void)std::initializer_list {
((void)call_cart(f, xs, xs...), 0)...
};
};
});
Внутреннее выражение,
call_cart(xs, xs...)
, явно представляет собой разделение множества (1,2,3)
на эти новые множества наподобие 1
, [1,2,3]
. Полное выражение, ((void)call_cart(f,xs, xs...),0)...
, имеющее снаружи дополнительную конструкцию ...
, выполняет такое разделение для каждого значения множества, так что мы также получаем множества 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{
(((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 содержит не только структуры данных, но и алгоритмы. В то время как структуры помогают хранить и поддерживать данные разными способами для различных целей, алгоритмы позволяют выполнять конкретные преобразования данных в этих структурах.
Рассмотрим стандартную задачу, например сложение элементов вектора. Это можно без труда сделать с помощью цикла, в котором мы суммируем все элементы вектора и поместим их в переменную-аккумулятор