twice столь же легко, как если бы на их месте были детали «Лего».
Генерируем декартово произведение на основе любых входных данных во время компиляции
Лямбда-выражения и наборы параметров можно использовать для решения сложных задач. В этом разделе мы реализуем объект функции, который принимает произвольное количество входных параметров и генерирует декартово произведение данного множества, умноженного само на себя.
Декартово произведение — математическая операция. Она обозначается как A x B, что означает «декартово произведение множества А на множество В». Результатом будет одно множество, содержащее пары всех комбинаций элементов из множеств А и В. Операция, по сути, означает комбинирование каждого элемента из множества А с каждым элементом множества В. Эта операция показана на рис. 4.3.
Согласно схеме, если A = (x,y,z), а B = (1,2,3), то декартово произведение этих множеств будет равно (x,1), (x,2), (x,3), (y,1), (y,2) и т.д.
Если мы решим, что множества A и B одинаковы, например (1,2), то их декартово произведение будет равно (1,1), (1,2), (2,1) и (2,2). В некоторых случаях это может оказаться избыточным, поскольку комбинация элементов с самими собой (например, (1,1)) или избыточные комбинации (1,2) и (2,1) способны стать ненужными. В таких случаях декартово произведение можно отфильтровать с помощью простого правила.
В этом разделе мы реализуем декартово произведение, не используя циклы, но применяя лямбда-выражения и распаковку набора параметров.
Как это делается
В примере мы реализуем объект функции, принимающий функцию f и набор параметров. Объект создаст декартово произведение набора параметров, отфильтрует избыточные части и вызовет для каждой пары функцию f.
1. Включим только тот заголовочный файл STL, который нужен для печати:
#include <iostream>
2. Затем определим простую вспомогательную функцию, которая выводит на экран пару значений, и начнем реализовывать функцию main:
static void print(int x, int y)
{
std::cout << "(" << x << ", " << y << ")n";
}
int main()
{
3. Теперь начинается сложная часть. Сначала реализуем вспомогательную функцию для функции cartesian, которую напишем на следующем шаге. Данная функция принимает параметр f, являющийся функцией вывода на экран. Другие ее параметры — это 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<int>{
(((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<int> {
((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<int> {
((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)..., имеющее снаружи дополнительную конструкцию ..., выполняет такое разделение для каждого значения множества, так что мы также получаем множества
