C++17 STL Стандартная библиотека шаблонов - Яцек Галовиц Страница 41

Генерируем декартово произведение на основе любых входных данных во время компиляции

Лямбда-выражения и наборы параметров можно использовать для решения сложных задач. В этом разделе мы реализуем объект функции, который принимает произвольное количество входных параметров и генерирует декартово произведение данного множества, умноженного само на себя.

Декартово произведение — математическая операция. Она обозначается как 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)..., имеющее снаружи дополнительную конструкцию ..., выполняет такое разделение для каждого значения множества, так что мы также получаем множества