翻译已经过原作者许可,转载请先征求原作者的许可。图片均取自原文,如果有水印为CSDN所打和老子没关系。出于清晰起见,文章中所有模板中的class都被改为typename。
模板(template)最早是以将类型(type)参数化为目的引入C++语言的。(译注1)链表 (list)是一个典型的例子。实际编码的时候,人们并不希望为保存不同类型变量的链表 分别编码,而是希望在编写的时候能够使用一个占位符(placeholder)来代替具体的类型 (即是模板参数),而让编译器来生成不同的链表类(模板的实例化)。
时至今日,模板的使用已经远远超过C++模板的发明者所预期的范畴。模板的使用已经涵盖 了泛型编程,编译时求值,表达式模板库,模板元编程,产生式编程(generative programming)等诸多领域。在这篇文章中,我们仅限于探讨一些表达式模板的编程知识, 侧重于编写表达式模板程序库这个方面。
我们必须指出:表达式模板库是相当复杂的。出于这个原因,我们读到过的关于表达式模 板的介绍都不是很容易理解的。因此,本文的作者希望能够通过本文为表达式模板提供一 个通俗的介绍,同时又不失对具体实现细节的阐述,从而对读者阅读模板库的代码能够起 到帮助。作者希望提取出表达式模板编码的一些原则性知识。有关于此领域的更多细节可 以参考其他著作。
创世纪
时至今日,我仍然能清晰的记起我的同事Erwin Unruh在一次C++标准委员会会议时展 示的得意之作。这是一段并不能通过编译的代码,但是它却给出了质数数列。(参见:UNR )编译它的过程中产生的错误信息中依次包含了每一个给定范围内的质数。当然,不能够 通过编译的程序是毫无意义的,然而这段代码是有意这样的。它旨在指出,这段计算是在 编译时进行的,没有可执行文件,从而也就没有运行时。质数的计算只是编译时期的副产 物而已。
这段小小的程序引发了之后多年对所谓模板元编程的雪崩般的研究。本文将介绍从中得来 的一些编程技巧和技术。那么,模板元编程的工作原理是什么呢?
从本质上来看,无论是质数的计算,还是本文中所提及的其他技术,都是基于如下原理的 :模板的实例化是一个递归过程。当编译器实例化一个模板时,它可能会发现在此之前另 外的模板需要首先实例化;在实例化这些模板的时候,又会发现有更多的模板需要实例化 。许多模板元编程的技巧就是基于这个原理,来实现递归式的计算的。
阶乘——编译时计算的第一个例子
作为第一个例子,我们来在编译时对N的阶乘进行计算。N的阶乘(记作N!)定义为从1到N 所有整数的积。(译注2),作为一个特例,0的阶乘是1。通常对阶乘的递归计算可以采用 函数递归的方法,如下是一个运行时计算的例子:
[cpp]
int factorial(int n)
{
return (n == 0 ? 1 : n * factorial(n - 1));
}
这个函数反复调用自身,直到参数n的值减少到0为止。使用的例子:
[cpp]
cout << factorial(4) << endl;
递归式的函数调用是昂贵的,特别是在编译器无法进行内联(inline)优化的时候——这样 函数调用的负担马上就凸显出来。我们可以用编译时计算来避免这一点。做法如下:用递 归式的模板实例化来代替递归式的函数调用。这样,名为factorial的函数将由名为 factorial的类代替:
[cpp]
template <int n>
struct factorial
{
enum { ret = factorial<n-1>::ret * n };
};
这个模板类既没有数据也没有成员函数,而仅仅是定义了有唯一enum值的匿名enum类型。 (之后便可以看到,factorial::ret起到了函数返回值的作用。)为了计算这个值,编译 器必须反复实例化以n-1为模板参数的新的模板类,这就是递归的第一推动力。
值得注意的是,factorial模板类的参数并不常见:它并不是一个类型的占位符,而是一个 int类型的常量。常见的模板参数都和下面的例子类似:
[cpp]
template <typename T> class X {...};
其中T是一个实际类型的占位符。在编译器遇到形如X<int>的代码时,T将被具体的类型( int)所取代。在我们的例子中,实际类型int成为了模板的参数,也就是说,在编译时将 被具体的int类型的值所取代。调用此模板类的代码可以是这样的:
[cpp]
cout << factorial<4>::ret <<endl;
编译器将依次实例化factorial<4>,factorial<3>……我们注意到,这个递归是没有终点的 。这样可不行。所以,需要利用模板的特化来提供这样一个终点。在我们的这个例子里:
[cpp]
template <>
struct factorial<0>
{
enum { ret = 1 };
};
从上述代码片段中可以看到递归将止步于此。因为此时enum的值已经不再依赖实例化其他 模板类了。
倘若你不熟悉模板的特化,在这里只需要记住对于特定的模板参数,可以提供一个特殊的 类模板即可。在我们的例子中我们提供了一个特殊的,参数为0的阶乘模板类。在这里编译 器可以不再通过递归来计算需要的值。
那么我们这么计算阶乘,好处是什么呢?表达式factorial<4>::ret在编译时将会被其具体 数值,也就是24所取代。运行时无需对此进行计算。在可执行文件里,是找不到计算的痕迹的。
开平方根——编译时计算的又一个例子
让我们试试另外一个编译时计算的例子。这一次,我们试图计算N的平方根的近似值——更准 确的说,我们希望能找到一个整数,使得它的平方是最小的比N的平方大的完全平方数。例 如:10的平方根大约是3.1622776601,所以哦我们希望能通过编程得到4这个比 3.1622776601大的最小的整数。如果采用运行时计算的方法的话,我们就需要调用C的标准 库:ceil(sqrt(N))。但是如果需要用这个值来定义数组的大小的话,那么我们就倒了大霉 :
[cpp]
int array[ceil(sqrt(N))];
不能通过编译,因为数组的大小在编译时必须是一个常数。(译注3)因此,我们有理由在 编译时进行计算。
回忆一下我们在第一个例子中所做的:我们利用了模板实例化是通过递归进行这一特性。 在这里我们再次通过引发递归式的模板实例化来近似获取相应的值。这里我们定义一个有 一个给定类型int的模板参数N的类模板,并使用一个内部保存的值来返回结果。如果我们 将这个类命名为Root,那么它的一个用例如下:
[cpp]
int array[Root<10>::ret];
Root的代码如下:
[cpp]
template <size_t N, size_t Low = 1, size_t Upp = N> struct Root
{
static const size_t ret = Root<N, (down ? Low : mean + 1),
(down ? mean : Upp)>::ret;
static const size_t mean = (Low + Upp) / 2;
static const bool down = ((mean * mean) >= N);
};
在此我们不拘泥于细节,仅仅给出一些注解。(译注4)模板类有三个参数,其中两个有默 认值。在这三个参数中:
需要开方的数
预期平方根的上界和下界。默认值是1和N。平方根必然是介于1和N之间的某个数。
在这个例子中,返回值ret不是一个enum的值,而是一个静态常数成员,用于引发递归实例 化。余下的静态数据成员mean和down仅仅作为辅助,以简化递归实例化的编码。
在什么时候递归才能停止呢?递归的停止取决于一个特化的,不需要进一步进行模板实例 化的模板。如下是所需的偏特化的Root类:
[cpp]
template <size_t N, size_t Mid>
struct Root<N, Mid, Mid>
{
static const size_t ret = Mid;
};
这里偏特化只有两个模板参数。这是因为在递归结束的时候,上界和下界均已收敛到结果上了。
在我们的递归例子中,会产生如下实例化的模板:
[cpp]
Root<10, 1, 10>;
Root<10, 1, 5>;
补充:软件开发 , C++ ,