Skip to content

Latest commit

 

History

History
122 lines (88 loc) · 6.63 KB

chapter4-7-chinese.md

File metadata and controls

122 lines (88 loc) · 6.63 KB
Raw

编译时生成笛卡尔乘积

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. 包含打印输出的头文件。

    #include <iostream>

  2. 然后，我们定义一个简单的辅助函数，用来对组对中的值进行打印：

    static void print(int x, int y)
{
	std::cout << "(" << x << ", " << y << ")\n";
}

int main()
{

  3. 复杂的地方到了。我们先实现了一个辅助函数cartesian，我们将在下一步实现这个函数。这个函数能接受一个参数f，在我们使用过程中，这个f函数就是print函数。另一些参数是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，其内部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)...
            };
        };
    });

  1. 那么，现在让我们使用数字集 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);
}

  2. 编译并运行程序，我们就会得到如下的输出。通过call_cart中的x < rest判断条件，我们可以将一些冗余组对结果进行删除：

    $ ./cartesian_product
(1, 2)
(1, 3)
(2, 3)

How it works...

另一个看起来比较复杂的地方就是Lambda表达式了。但当我们充分的了解后，我们就不会再对Lambda表达式有任何的困惑了！

那么，让我们来仔细的了解一下吧。我们将所发生的事情，画了一张图来说明：

这里有3步：

  1. 我们将1, 2, 3作为新集合中的三个元素，其报了三个新的集合。第一个则是集合中的每一个单独向，而第二部分则是整个集合本身。
  2. 我们可以将第一个元素与每一个元素相组合(包括自己)，就能得到很多组对。
  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。通过这样做，我们可以在运行时对代码进行评估，这样编译出的二进制文件将会包含所有组对，而无需在运行时对其进行计算。需要注意的是，这里需要传入常量函数的参数为已知量，这样才能在运行时让编译器知道，并对函数进行执行。