算法的一般性操作

优质

小牛编辑

137浏览

2023-12-01

很像前面的部分介绍了异构容器的一般但重要的概念，本节介绍异构算法的一般概念。

传值语义

Hana中的算法总是返回一个包含结果的新容器。这允许通过简单地使用第一个的结果作为第二个的输入以便于很轻易地链接算法。例如，要对元组的每个元素应用函数，然后反转结果，只需要连接reverse和transform算法：

auto to_str = [](auto const& x) {
  std::stringstream ss;
  ss << x;
  return ss.str();
};
auto xs = hana::make_tuple(1, 2.2, 'a', "bcde");
BOOST_HANA_RUNTIME_CHECK(
  hana::reverse(hana::transform(xs, to_str)) == hana::make_tuple("bcde", "a", "2.2", "1")
);

这不同于标准库的算法，它们要求必须向基础序列提供迭代器。由[rationales](#Fair warning: functional programming ahead)所述的原因，起先考虑了基于迭代器的设计，但很快被否决。有利于可组合和有效的抽象更适合异构编程的特定上下文。

也可以认为从算法返回拥有其元素的完整序列将导致大量不期望的副本。例如，当使用reverse和transform时，可以认为在调用transform之后产生一个中间副本：

hana::reverse(
  hana::transform(xs, to_str) // <-- copy into reverse(...) here?
);

为了确保这不会发生，Hana使用完美转发和移动语义，所以它可以提供几乎最佳的运行时性能。因此，不是创建一个副本，而是在reverse和transform之间发生了移动：

hana::reverse(
  hana::transform(xs, to_str) // <-- nope, move from the temporary instead!
);

最终，目标是使用Hana编写的代码应该相当于最佳的手写代码，除非这些代码写起来很容易。性能注意事项在各自的章节中进行深入解释。

(非)惰性

Hana的算法是非惰性的。当一个算法被调用时，它完成它的工作，并返回一个包含结果的新序列。例如，在大序列上调用排列算法是一个不明智的想法，因为Hana实际上将计算所有的排列：

auto perms = hana::permutations(hana::make_tuple(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
// perms has 3 628 800 elements, and your compiler just crashed

作为比较，Boost.Fusion中的算法返回视图，它通过引用保存原始序列，并且在访问序列的元素时根据需要应用算法。这会导致微妙的生命周期问题，例如有一个视图指向的是被破坏的序列。 Hana的设计假设大多数时候，我们想访问序列中的所有或几乎所有的元素，因此对惰性来说性能上不是很有利。

生成什么

Hana中的算法对于它们被扩展到运行时的代码是有点特别的。本小节的目标不是要准确地解释代码生成什么，因为这取决于编译器。基本上，Hana算法就像一个等价的经典算法的展开版本。实际上，由于处理的序列的边界在编译时是已知的，所以我们可以在该序列上展开循环是有意义的。例如，让我们考虑for_each算法：

auto xs = hana::make_tuple(0, 1, 2, 3);
hana::for_each(xs, f);

如果xs是一个运行时序列而不是一个元组，它的长度只会在运行时才可知，上面的代码必须实现为一个循环：

for (int i = 0; i < xs.size(); ++i) {
  f(xs[i]);
}

然而，在我们的例子中，序列的长度在编译时是已知的，因此我们不必在每次迭代时检查索引。因此，我们可以写成这样：

f(xs[0_c]);
f(xs[1_c]);
f(xs[2_c]);
f(xs[3_c]);

这里的主要区别是在每个步骤都不进行绑定检查和索引递增，因为没有索引; 循环被有效地展开。在一些情况下，出于性能原因，这可能是期望的。在其他情况下，这可能会对性能造成不利影响，因为它会导致代码膨胀。和往常一样，性能是一个棘手的问题，是否你真的想要循环展开还是逐步处理。作为经验法则，处理容器的所有（或子集）元素的算法被展开。事实上，如果你考虑它，这个展开是异构序列的唯一途径，因为序列的不同元素可能有不同的类型。正如你可能已经注意到的，我们不使用正常的索引到元组，而是编译时索引，它不能由正常的for循环生成。换句话说，以下是没有意义的：

for (??? i = 0_c; i < xs.size(); ++i) {
  f(xs[i]);
}

副作用和纯度(purity)

默认情况下，Hana假定函数是纯(pure)的。纯函数是根本没有副作用的函数。换句话说，它是一个对程序的影响仅由其返回值决定的函数。特别地，这样的函数可以不访问比函数的单次调用更长的任何状态。这些函数具有非常好的属性，如对它们进行数学推理的能力，重新排序或甚至消除调用等等。除非另有规定，与Hana一起使用的所有函数（即在高阶算法中使用的函数）应该是纯的。特别地，传递给高阶算法的函数不能保证被称为任何特定次数。此外，执行顺序通常没有指定，因此不应该被认为是理所当然的。如果这种缺乏对函数调用的保证看起来很疯狂，请考虑以下any_of算法的使用：

auto r = hana::any_of(hana::make_tuple("hello"s, 1.2, 3), [](auto x) {
  return std::is_integral<decltype(x)>{};
});
BOOST_HANA_CONSTANT_CHECK(r);

注意： 为使这些代码可工作，必须包含在<boost/hana/ext/std/integral_constant.hpp>中的std::integr_constant外部适配器。

根据前面的展开部分，这个算法应该展开如下：

  auto xs = hana::make_tuple("hello"s, 1.2, 3);
  auto pred = [](auto x) { return std::is_integral<decltype(x)>{}; };
  auto r = hana::bool_c<
    pred(xs[0_c]) ? true :
    pred(xs[1_c]) ? true :
    pred(xs[2_c]) ? true :
    false
  >;
  BOOST_HANA_CONSTANT_CHECK(r);

当然，上面的代码不能工作，因为我们在需要是一个常量表达式的东西中调用pred，但是pred是一个lambda（并且lambdas不能在常量表达式中调用）。然而，这些对象是否具有整数类型在编译时是清楚地知道的，因此我们希望计算答案只涉及编译时计算。事实上，这正是Hana做的，上述算法被扩展成类似：

auto xs = hana::make_tuple("hello"s, 1.2, 3);
auto pred = [](auto x) { return std::is_integral<decltype(x)>{}; };
auto r = hana::bool_c<
  decltype(pred(xs[0_c]))::value ? true :
  decltype(pred(xs[1_c]))::value ? true :
  decltype(pred(xs[2_c]))::value ? true :
  false
>;
BOOST_HANA_CONSTANT_CHECK(r);

注意： 正如你将能够从下一节交叉相位计算中推断出的，any_of的实现实际上必须比这更通用。然而，这个Lie-to-children仅出于教育目的。

正如你所看到的，谓词永远不会被执行; 仅使用其对特定对象的结果类型。关于执行的顺序，考虑transform算法，其被指定（对于元组）为：

   hana::transform(hana::make_tuple(x1, ..., xn), f) == hana::make_tuple(f(x1), ..., f(xn))

因为make_tuple是一个函数，并且因为函数的参数的求值顺序是未指定的，所以在元组的每个元素上调用f的顺序也是未指定的。如果持有一个纯函数，一切工作正常，所得到的代码通常更容易理解。然而，一些例外的算法，如for_each，预期不纯的函数，并且它们保证了求值的顺序。的确，一个只使用纯函数的for_each算法几乎没有用。当一个算法可以接受一个不纯的函数或保证某种顺序的评价，该算法的文档将明确提及它。但是，默认情况下，不能保证是理所当然的。

交叉相位(Cross-phase)算法

本节介绍交叉相位计算和算法的概念。事实上，我们已经在快速入门中使用了交叉相位算法，例如使用滤波器，但是我们没有准确解释当时发生了什么。但在我们介绍交叉相位算法之前，让我们定义交叉相位是什么意思。这里所指的阶段是程序的编译和执行。在C++等大多数静态类型语言中，编译时和运行时有明显的区别; 这被称为相位差(phase distinction)。当我们谈到交叉相位计算时，我们是指以某种方式在这些阶段上执行的计算; 即在编译时部分执行并在运行时部分执行。

就像我们在前面的例子中看到的，一些函数能够返回在编译时可以使用的东西，即使它们是在运行时值上调用的。例如，让我们考虑应用于非constexpr容器的长度函数：

struct Fish { std::string name; };
struct Cat  { std::string name; };
struct Dog  { std::string name; };
auto animals = hana::make_tuple(Fish{"Nemo"}, Cat{"Garfield"}, Dog{"Snoopy"});
//   ^^^^^^^ not a compile-time value
BOOST_HANA_CONSTANT_CHECK(hana::length(animals) == hana::size_c<3>);
//                        ^^^^^^^^^^^^^^^^^

显然，元组不能被constexpr修饰，因为它包含运行时std::string。尽管它不是在常量表达式上调用，但是length返回可以在编译时使用的东西。如果你想到的话，元组的大小在编译时是已知的，而不管它的内容，因此，这些信息只有在编译时可供我们使用才有意义。如果这似乎令人惊讶，考虑std::tuple和std::tuple_size：

std::tuple<int, char, std::string> xs{1, '2', std::string{"345"}};
static_assert(std::tuple_size<decltype(xs)>::value == 3u, "");

由于元组的大小是以其类型编码的，所以无论元组是否为constexpr，它在编译时都是可用的。在Hana中，这是通过返回一个IntegralConstant的长度来实现的。由于IntegralConstant的值是在其类型中编码的，所以长度的结果包含在它返回的对象的类型中，因此长度在编译时是已知的。因为长度（的取得是）从运行时值（容器）到编译时值（IntegralConstant），所以长度是一个交叉相位算法的一个简单例子（无关紧要，因为它并不真正操作元组）。另一个非常类似于length的算法是is_empty算法，它返回容器是否为空：

BOOST_HANA_CONSTANT_CHECK(!hana::is_empty(animals));
//                         ^^^^^^^^^^^^^^^^^^^^^^^ assertion done at compile-time

更一般地，任何采用其值在运行时才可知的容器但查询在编译时可知的容器的任何算法应该能够返回IntegralConstant或另一个类似的编译时数值。让我们通过考虑any_of算法使事情稍微复杂一些，我们已经在上一节中遇到过：

bool any_garfield = hana::any_of(animals, [](auto animal) {
  return animal.name == "Garfield"s;
});
BOOST_HANA_RUNTIME_CHECK(any_garfield);

在这个例子中，在编译时不能知道结果，因为谓词返回一个bool，它是比较两个std::string的结果。由于std::string不能在编译时进行比较，所以谓词必须在运行时操作，并且算法的整体结果只能在运行时才知道。因此，我们要替换any_of谓词如下：

auto any_cat = hana::any_of(animals, [](auto x) {
  return std::is_same<decltype(x), Cat>{};
});
BOOST_HANA_CONSTANT_CHECK(any_cat);

注意： 为使这些代码工作，必须包含在<boost/hana/ext/std/integral_constant.hpp>中的std::integral_constant的外部适配器。

首先，由于谓词仅查询关于元组的每个元素的类型的信息，所以很清楚的是，其结果可以在编译时知道。由于元组中元素的数量在编译时也是已知的，所以算法的总体结果理论上可以在编译时知道。更确切地说，谓词返回的是一个经std::is_same<...>初始化的值，它继承自std::integral_constant。 Hana识别这些对象，并且以这样的方式编写算法，使得它能将谓词保留在compile-timeness。最后，any_of返回一个IntegralConstant保存算法的结果，我们以一种聪明的方式使用编译器的类型推导，使它看起来容易。因此，它相当于（但是你需要已经知道算法的结果！）：

hana::integral_constant<bool, true> any_cat = hana::any_of(animals, [](auto x) {
  return std::is_same<decltype(x), Cat>{};
});
BOOST_HANA_CONSTANT_CHECK(any_cat);

Ok，当算法的输入满足编译时的一些约束时一些算法能够返回编译时数值。然而，其他算法更具限制性，并且它们需要它们的输入以满足关于编译时间的一些约束，没有它们，它们根本不能操作。一个示例是filter，它接受一个序列和一个谓词，并返回一个只包含那些满足该谓词的元素的新序列。过滤器需要谓词返回一个IntegralConstant。虽然这个要求可能看起来很严格，但如果你考虑这个要求真的有意义。实际上，由于我们从异构序列中去除一些元素，所以得到的序列的类型取决于谓词的结果。因此，谓词的结果必须在编译时知道，编译器才能为返回的序列分配类型。例如，考虑当我们尝试过滤异构序列时发生的情况：

auto animals = hana::make_tuple(Fish{"Nemo"}, Cat{"Garfield"}, Dog{"Snoopy"});
auto no_garfield = hana::filter(animals, [](auto animal) {
  return animal.name != "Garfield"s;
});

显然，我们知道谓词只会在第二个元素上返回false，因此结果应该是[Fish，Dog]元组。然而，编译器没有办法知道这一点，因为谓词的结果是运行时计算的结果，这发生在编译器完成其工作之后。因此，编译器没有足够的信息来确定算法的返回类型。但是，我们可以使用在编译时获得结果的任何谓词过滤相同的序列：

auto mammals = hana::filter(animals, [](auto animal) {
  return hana::type_c<decltype(animal)> != hana::type_c<Fish>;
});

由于谓词返回一个IntegralConstant，因此我们知道在编译时将保持异构序列的哪些元素。因此，编译器能够找出算法的返回类型。其他算法，如分区和排序工作类似; 特殊算法的要求总是在文档中可查的，只是你需要在使用它们之前阅读算法的参考文档，以避免意外。

到这里我们就结束了关于算法部分，我们给了算法中相位相互作用的相当完整的解释，参见constexpr的高级部分、Constant、IntegralConstant，可以获得更深入的理解。

警告： Hana的算法是constexpr函数对象，而不是模板函数。这就允许将它们传递到更高阶的算法，这是非常有用的。然而，由于那些函数对象被定义在头文件中的命名空间中，这使得每个翻译单元看到不同的算法对象。因此，不保证算法函数对象的地址在翻译单元之间是唯一的，如果依赖于这样的地址，这可能导致违反ODR(One Definition Rule)。所以，简而言之，不要依赖Hana提供的任何全局对象的地址的唯一性，这在一般情况下没有意义，因为这样的对象是constexpr。有关详细信息，请参阅问题#76。