Comment on page

编译时生成笛卡尔乘积

Lambda表达式结合参数包一起使用,可以用来解决比较复杂的问题。本节中,我们将实现一个函数对象,其能接受任意多的输入参数,然后生成相应的笛卡尔乘积
笛卡尔乘积是一个数学运算。其可以表示为A x B,其意思为使用集合A和集合B来结算笛卡尔乘积。结果为另一个单独的集合,其包含集合A和集合B一一对应的组对。这个运算的意义在于,将两个集合中的元素进行匹配。下图就描述了这种运算操作:
图中,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)。笛卡尔乘积可以通过一个简单的条件,对结果进行过滤。

How to do it...

我们实现了一个函数对形象,其能接受一个函数f,以及一组参数。该函数对象将会通过输出参数集合创建笛卡尔乘积,将冗余的部分进行过滤,并对每个乘积调用函数f
  1. 1.
    包含打印输出的头文件。
    #include <iostream>
  2. 2.
    然后,我们定义一个简单的辅助函数,用来对组对中的值进行打印:
    static void print(int x, int y)
    {
    std::cout << "(" << x << ", " << y << ")\n";
    }
    int main()
    {
  3. 3.
    复杂的地方到了。我们先实现了一个辅助函数cartesian,我们将在下一步实现这个函数。这个函数能接受一个参数f,在我们使用过程中,这个f函数就是print函数。另一些参数是x和参数包rest。其包含了计算笛卡尔乘积的元素。在f(x, rest)表达式中:当x=1rest=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. 4.
    cartesian函数在本节中,算是最复杂的部分了。其能接受一个参数包xs,并返回一个其捕获的函数对象。返回的函数对象能接受一个函数对象f。参数包,比如xs = 1, 2, 3,其内部Lambda表达式将会生成如下调用:call_cart(f, 1, 1, 2, 3); call_cart(f, 2, 1, 2, 3); call_cart(f, 3, 1, 2, 3);。通过对这些函数的调用,我们能得到我们想要的所有笛卡尔乘积。我们使用...xs参数包扩展了两次,第一次看起来有些奇怪。调用call_cart时,我们第一次对xs进行了扩展。第二次扩展将会使得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. 5.
    那么,现在让我们使用数字集1, 2, 3来生成笛卡尔乘积,并对组对进行打印。过滤了冗余的组对,所剩的结果应该为 (1, 2) , (2, 3) , 和 (1, 3)。我们对很多的结果进行了过滤,并且不考虑结果中组对中的数字顺序。这也就是说,我们不需要(1, 1),并且认为(1, 2)(2, 1)为同一个组对。首先,我们让cartesian函数产生一个函数对象,其会包含所有可能的组对,并且能够接受我们的打印函数。然后,我们将所产生的组对,使用打印函数进行打印输出。我们将print_cart变量声明为constexpr,这样我们就能在编译时获得所有的乘积结果:
    constexpr auto print_cart (cartesian(1, 2, 3));
    print_cart(print);
    }
  6. 6.
    编译并运行程序,我们就会得到如下的输出。通过call_cart中的x < rest判断条件,我们可以将一些冗余组对结果进行删除:
    $ ./cartesian_product
    (1, 2)
    (1, 3)
    (2, 3)

How it works...

另一个看起来比较复杂的地方就是Lambda表达式了。但当我们充分的了解后,我们就不会再对Lambda表达式有任何的困惑了!
那么,让我们来仔细的了解一下吧。我们将所发生的事情,画了一张图来说明:
这里有3步:
  1. 1.
    我们将1, 2, 3作为新集合中的三个元素,其报了三个新的集合。第一个则是集合中的每一个单独向,而第二部分则是整个集合本身。
  2. 2.
    我们可以将第一个元素与每一个元素相组合(包括自己),就能得到很多组对。
  3. 3.
    对于三个结果组对来说,我们只需要将其中不冗余的部分取出就好。
好了,回到我们例子:
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)...其将...放在外部,其会将集合进行拆解,我们将会得到2,[1, 2, 3]3, [1, 2, 3]
call_cart完成了第2和第3步:
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条件来过滤冗余的组对了。
我们先给所有Lambda表达式和持有变量声明成constexpr。通过这样做,我们可以在运行时对代码进行评估,这样编译出的二进制文件将会包含所有组对,而无需在运行时对其进行计算。需要注意的是,这里需要传入常量函数的参数为已知量,这样才能在运行时让编译器知道,并对函数进行执行。