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

2020-06-19 02:38:54

在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的工作方式与三元运算符(?:)非常相似。