C++17 STL Стандартная библиотека шаблонов

Декартово произведение — математическая операция. Она обозначается как 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

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{

        (((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);

}