C++中的「模板元编程」——Template Metaprogramming(TMP)

0.00 avg. rating (0% score) - 0 votes
转载请注明: 吹水小镇 | reetsee.com
原文链接地址: http://blog.reetsee.com/archives/219

之前在coolshell看到一遍文章:类型的本质和函数式实现,讲怎么使用函数式编程来实现一个栈,十分有意思。今天在看《Effective C++》的时候也看到了一种类似的编程方法,这本书确实是让人学到太多了,必须点个赞,有些东西虽然基础,但是没看过是不知道可以这样用的。

以下的内容主要就是说其中的条款48——“认识template元编程”。最具体的讲解还是参考原书啦,这里只是提一下。

模板元编程最主要的好处,就是能够将运行期执行的任务放到编译期,好处当然就是将某些可能出错的地方让其提前在编译期就被检查出来,而且生成的程序在执行时会更加高效——”较小的可执行文件、较短的运行期、较少的内存需求“。当然这样做也有一个副作用,那就是编译的时间可能会变长。

敲了这么多文字,是时候上点code暖场。先思考一个问题:怎么计算一个数(例如10)的阶乘?

很多方法,可以使用迭代或者递归,这里使用递归的方法,代码如下

#include <iostream>
unsigned int normalFactorial(int n) {
    if(0 == n)
        return 1;
    return n * normalFactorial(n-1);
}
int main(int argc, const char * argv[])
{
    std::cout<<normalFactorial(10)<<std::endl;
}

是不是很简单呢~?哈哈,但是要注意的是,上面对函数的递归调用,最终计算的结果都是在运行期完成的。到底运行期完成的运算会慢多少?在最后会做一个速度测试,现在先看基本代码就可以了。

好了,下面就要展示模板元编程的威力了。要用TPM,就要巧妙地运用C++模板的特性,C++模板的具现化(也就是变成实际东西)是在编译期就确定的,利用“编译期具现化”这个时机,我们将对10的阶乘的计算提前到编译期,代码如下

#include <iostream>
using namespace std;
template <unsigned int n>
struct TMPFactorial {
    enum { value = n * TMPFactorial<n-1>::value };
};
template<>
struct TMPFactorial<0> {
    enum { value = 1 };
};
int main()
{
    cout<<TMPFactorial<10>::value<<endl;
}

这种编程利用了模板,以及一个叫“enum hack”的技巧(关于enum hack的渊源,可以自行百度……或者直接参看《Effective C++》的条款2,或者,另外认识其意义的方法就是,请使用另外一种比较简洁的方法实现上述代码的逻辑,看看如何,static?const?define?如果实现效果不理想,那就基本抓住enum hack的小尾巴,知道为什么要这样用了)。对10的阶乘的计算,是在编译期就完成了,所以程序运行时的效率就比较高了。另外,从上面的代码可以看出,针对TMPFactorial<0>的情况,我们需要对其进行一个模板的特化处理。

借小米每次发布会都说的一句话——“要不来跑个分吧?”,现在我们可以测试一下两个程序的运行速度。

首先测试第一种方法的运行时间,将要赋值的变量加入volatile属性,以免编译期对重复的过程进行干扰,代码如下:

#include <iostream>
using namespace std;
unsigned int normalFactorial(int n) {
    if(0 == n)
        return 1;
    return n * normalFactorial(n-1);
}
int main(int argc, const char * argv[])
{
    volatile unsigned int res = 0;
    time_t st = time(0);
    for(int i = 0; i < 1000; ++i)
        for(int j = 0; j < 1000000; ++j)
            res = normalFactorial(10);
    time_t ed = time(0);
    cout<<res<<endl;
    cout<<ed - st<<endl;
}

在Macbook air上面运行,我最终的结果如下:

3628800
52
Program ended with exit code: 0

 

花了52秒,等了好一会儿。

下面测试第二种方法,即TMP的运行时间,代码如下:

#include <iostream>
using namespace std;
template <unsigned int n>
struct TMPFactorial {
    enum { value = n * TMPFactorial<n-1>::value };
};
template<>
struct TMPFactorial<0> {
    enum { value = 1 };
};
int main()
{
    volatile unsigned int res = 0;
    time_t st = time(0);
    for(int i = 0; i < 1000; ++i)
        for(int j = 0; j < 1000000; ++j)
            res = TMPFactorial<10>::value;
    time_t ed = time(0);
    cout<<res<<endl;
    cout<<ed - st<<endl;
}

好了,同样是在Macbook air上面运行,我最终的结果是:

3628800
2
Program ended with exit code: 0

 

眨眼完成……2秒,有木有高端大气上档次的感觉?

—————————————————————————————————————————

TMP大概就是如此了,关于其应用,其实上面也就只是一个类似Hello World的程序,用来作一个最基本的展示,TMP在很多地方有更加让人惊叹的应用场景。在《Effecitve C++》里面,条款47(这篇博文主要是条款48的内容)已经有说到TMP,是在确定iterator迭代器的类型(单向,双向,随机)的时候应用的,将对迭代器类型的检测从原本的运行期提前到编译期,这就是程序运行效率的优化了。

在《Effective C++》中,有很多这样让人赞叹的编程细节、规范、技巧,目前我依然觉得全书皆精华,强烈推荐。

最近好像都没写什么有营养的东西,哎,每天做着几乎没有生产力的东西,很郁闷呢。要多做有生产力的东西

发表评论

电子邮件地址不会被公开。 必填项已用*标注