编译时合并排序[C++]

在C++20中，std：：Sort与其他标准算法一起变成了constexpr。这使得以下代码成为可能。

第14行的sorted_arr在编译时被初始化为{1，2，3，4，5}，并且main返回1。如您所见，机器代码中没有排序算法和逻辑的痕迹。此外，如果您打开优化(-O3)，整个代码就会变成一条指令，从而证明所有排序都发生在编译时。

让我们看看如何使用C++17来实现这一点。在开始实现之前，我们将列出合并排序所需的内容。如果您不知道合并排序是如何工作的，那么您可能不想看到即将到来的代码。

该数组非常简单。它是具有任意数量的整数模板参数的类型。它附带GET功能以启用索引访问。GET以递归方式实现。第7-8行是签名的定义，即GET接受两个参数，一个数组(Type)和一个索引(整数)。第10-14行是递归关系：数组的第i个值是该数组的第(index-1)个值，没有第一个元素。第16-20行是递归的基本情况：第0个值是第一个元素。如果它看起来仍然是胡言乱语，可以将结构行视为函数签名，将尖括号(<；>；)中的内容视为参数，并将“static const int value”行视为返回语句。示例：

第22-23行定义的get_v只是语法糖，以避免总是写入：：value。

准备好之后，让我们开始使用自上而下的方法实现排序。我们要做到以下几点：

在第4-5行，我们定义了原型：它接受单个数组作为输入。第7-11行是递归的基本情况之一：对空数组进行排序会产生空数组。第13-17行是另一种基本情况：对具有单个元素的数组进行排序会得到相同的数组。最后是肉和土豆，在第19-29行，一般情况。在这里，我们需要将任意大小的输入数组一分为二，对每个数组进行排序，最后将它们合并。在第23行，我们“预先计算”数组的长度，以使整个代码更具可读性。在第26行，我们获取数组的前半部分并对其进行排序，在第27行，我们获取后半部分，并再次对其进行排序。在第25行，我们将这两个合并。所以现在，我们必须实现merge_t、take_t和drop_t。同样，第31-32行只是语法糖，以便能够编写sort<；arr>；而不是typeName sort<；arr>；：：type。

让我们从Drop开始，因为它是最简单的(不是吗？)

它接受一个数组和一个数字N，并返回删除该数组的前N个元素后剩下的内容。例如：

实现相当简单。第7-11行是递归关系，其中我们删除第一个元素并递减N，第13-17行是基本情况，即删除0个元素的情况。

这非常类似于Get Up There，所以应该可以很好地工作，对吧？不对!。不是的。问题是模板专门化中的模棱两可。在GET的例子中，一切都很好，因为我们有以下两个专门化。

第一个专门化(第5行)接受两个参数。第一个数组<；I0是.>；，它是一个由1个或多个元素组成的数组，因为I0正好是“1个或多个”。第二个参数是整数。在第二个模板专门化中(第11行)，第一个参数完全相同，但是第二个参数是0，因此第二个专门化更加专门化。总之，第一个参数必须是一个包含1个或多个元素的数组，第二个参数必须是一个数字。如果为0，将实例化第二个专用化(第10-14行)，否则实例化第一个专用化(第4-8行)。

在DROP的实现中，我们对这两个参数都进行了更改。第一个专门化(第5行)用于具有1个或多个元素且任意数字为N的数组。第二个专门化(第11行)用于具有0个或更多元素且数字为0的数组。0比N更加专门化，但是，数组<；is.>；不如数组<；I0，is.>；专门化(因为后者排除了空数组的情况)。因此，这种模棱两可。例如，当编译器看到DROP_t<；array<；1、2、3>；、0>；时，它无法在这些专门化之间进行选择。以下是我们如何解决这种模棱两可的问题：

这里我们有3个模板专业化认证。第一个与以前相同，第二个(第11行)是第一个的更特殊版本，第三个(第17行)涵盖空数组的情况(前两个没有)。我们没有使用非零值专门化空数组的情况，因为这是一个错误的情况，我们确实希望它编译失败。

我们实现Take的方式非常相似。同样，出于同样的原因，我们有3个模板专业化认证。N=0的基本情况相当微不足道。在一般情况下(第10行)，只有一个新的东西，前缀_t，它接受一个整数、一个数组，并且显然将一个前缀到另一个前缀。

最后，拼图的最后一块是merge_t，它应该接受两个排序的数组，并将它们合并成一个排序的数组。

如第4-5行的签名所示，Merge接受两个数组作为输入参数。有三种基本情况是专门的。第19-23行和第25-29行是合并空数组和非空数组的基本情况。31-35上的基本情况的定义只是出于团结，只是为了涵盖合并两个空数组的情况。另外两个专门化没有涵盖它，因为它们同样适用于这种情况，因此造成了歧义。然而，我们的排序实现永远不会要求它。一般的案例逻辑再次递归(第7-17行)。我们基本上找到这两个数组的前两个元素中最小的一个，将其从数组中分离出来，合并其余的元素，最后将这个分离的元素添加到结果前面。下面是一个循序渐进的演示。

正如我们看到的(第4行)，在一般情况下(两个非空数组的情况)，合并解析为预端。此预端的两个参数取决于两个数组的前几个元素(I0和J0)。第一个参数是其中最小的一个(第5行)。如果绿色条件为真，则第二个参数(第6-8行)是与红色数组合并的结果，否则是与蓝色数组合并的结果。Conditional_t的工作方式与三元运算符(？：)非常相似。