• 打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮
  • 打赏支付宝扫一扫

首页

 > 

编程语言 > 

C/C++

FunctionalProgramming与C++的模板元编程

winter-cnwinter-cn • 9年前
先来看一个例子:
#include <stdio.h>
template 
<int depth>
class Fibnacci
{
public:
    
static const int value = Fibnacci<depth-1>::value + Fibnacci<depth-2>::value;
};

template 
<>
class Fibnacci<0>
{
public:
    
static const int value = 0;
};

template 
<>
class Fibnacci<1>
{
public:
    
static const int value = 1;
};

template 
<int depth>
void printFibnacci()
{
    printFibnacci
<depth-1>();
    wprintf(L
"%dn", Fibnacci<depth>::value);
}

template 
<>
void printFibnacci<0>()
{
    wprintf(L
"%dn", Fibnacci<0>::value);
}

int main()
{
    printFibnacci
<8>();
    
return 0;
}

Fibnacci数列,相信是个程序员都能写出来,重点是,这个Fibnacci数列的计算完全是在编译时完成!后面的print也是如此,当你把参数调得很大时,运行时间不会有任何改变,但是你会花费长时间在编译阶段。
如果你听说过一些模板元编程,你一定会知道"C++模板是图灵完备的"这个说法。模板元是如何图灵完备的?答案是,模板元跟Functional原理是一样的。
模板的本质是定义与替换,lambda函数的本质也是定义与替换,这里的替换实际上符合的是数学中的lambda演算理论:
Lambda演算

λ演算lambda calculus)是一套用于研究函数定义、函数应用和递归形式系统。它由丘奇(Alonzo Church)和他的學生克莱尼(Stephen Cole Kleene)在20世纪30年代引入。Church 运用λ演算在1936年给出判定性问题(Entscheidungsproblem)的一个否定的答案。这种演算可以用来清晰地定义什么是一个可计算函数。关于两个 lambda 演算表达式是否等价的命题无法通过一个“通用的算法”来解决,这是不可判定性能够证明的头一个问题,甚至还在停机问题之先。Lambda 演算对函数式编程语言有巨大的影响,比如 Lisp 语言ML 语言Haskell 语言

Lambda 演算可以被称为最小的通用程序设计语言。它包括一条变换规则(变量替换)和一条函数定义方式,Lambda 演算之通用在于,任何一个可计算函数都能用这种形式来表达和求值。因而,它是等价于图灵机的。尽管如此,Lambda 演算强调的是变换规则的运用,而非实现它们的具体机器。可以认为这是一种更接近软件而非硬件的方式。v

所以C++的模板元编程实际上属于函数式风格编程,这也是很多C++程序员觉得它不舒服的原因。

另外说一点,所谓图灵完备的语言,则必定可以用它来表达任何算法,那么我们现在使用的这个直接Fibnacci是一个非常低效的算法。
有一个常见的说法"Fibnacci的迭代算法比递归算法快",这里我想强调,递归只是形式,与算法无关,下面奉上O(n)的Fibnacci算法(这回就不那么折磨编译器了):
#include <stdio.h>
template 
<int depth>
class Fibnacci
{
public:
    
static const int value = Fibnacci<depth-1>::value + Fibnacci<depth-1>::last;
    
static const int last = Fibnacci<depth-1>::value ;
};

template 
<>
class Fibnacci<0>
{
public:
    
static const int value = 0;
};

template 
<>
class Fibnacci<1>
{
public:
    
static const int value = 1;
    
static const int last = 0;
};

template 
<int depth>
void printFibnacci()
{
    printFibnacci
<depth-1>();
    wprintf(L
"%dn", Fibnacci<depth>::value);
}

template 
<>
void printFibnacci<0>()
{
    wprintf(L
"%dn", Fibnacci<0>::value);
}

int main()
{
    printFibnacci
<8>();
    
return 0;
}
最后留一道题目,各位看官如果有兴趣,可以做做,回复在下面或者留下链接均可,用C++模板或C#lambda函数都可以:
1994年的一次会议上,Erwin Unruh写了一个程序,在编译错误里面打印出一个素数序列。这个程序当时震惊了当时在场的包括C++之父Bjarne Stroustrup在内的几位大师,这个事情正标志了C++模板系统的图灵完备性被发现。那么,让我们也来向先辈致敬,来实现这个打印出一个素数序列的模板吧!

“看完这篇还不够?如果你也在学习IT,并希望记录自己的成长日志,请戳这里告诉我们!”
新人作者

好好学习,天天向上,有工作有兼职可以找我。微信号:gethost

文章总数
总阅读量
程序猿们,如果你或你的朋友想升职加薪,请狠戳这里我要成长
参与讨论
后参与讨论
winter-cn
新人作者

文章总数
总阅读量
程序猿们,如果你或你的朋友想升职加薪,请狠戳这里我要成长
48h快讯7天最热月榜More
  • 6年前

    本以为这么多年C#经验,学个C++没多难,现在发现错了。C++真TM难。今天遇到int转string绊了半天,方法很多,不知道为什么搞那么复杂,我只挑最简单易懂的,管他效率不效率的。int转stringintn=0;std::stringstreamss;std::stringstr;ssn;ssstr;string转intstd::stringstr="123";intn=atoi(str.c_str());#include"stdafx.h"#includestring
    收起
  • 6年前

    输入原理:程序的输入都建有一个缓冲区,即输入缓冲区。一次输入过程是这样的,当一次键盘输入结束时会将输入的数据存入输入缓冲区,而cin函数直接从输入缓冲区中取数据。正因为cin函数是直接从缓冲区取数据的,所以有时候当缓冲区中有残留数据时,cin函数会直接取得这些残留数据而不会请求键盘输入#1:#includeiostreamusingnamespacestd;intmain(){charstr[8];cin.getline(str,5);cout
    收起
  • 6年前

      经常碰到字符串分割的问题,这里总结下,也方便我以后使用。一、用strtok函数进行字符串分割原型:char*strtok(char*str,constchar*delim);功能:分解字符串为一组字符串。参数说明:str为要分解的字符串,delim为分隔符字符串。返回值:从str开头开始的一个个被分割的串。当没有被分割的串时则返回NULL。其它:strtok函数线程不安全,可以使用strtok_r替代。示例:1//借助strtok实现spl
    收起
  • 7年前

    网上已有很多FlexPaper仿百度文库的一些文章,园子里也有很多大牛的详细教程。结合这次做的例子,在这里详细记录一下使用Flexpaper实现仿百度文库的效果,及自己在跟着园子里的教程做的时候,遇到的一些小问题。希望能给初次接触或者遇到同样问题的同学们提供一些小小的帮助。(描述不足之处,请大家多多见谅,毕竟是第一次在园子里写文章)。1.准备工作:下载FlexPaper及PDF转换工具pdf2swf.exeFlexpaper下载地址:下载(我下的是1.4.5FlashVe
    收起
  • 10年前

    作者:911说明:本文参考了http://www2.tsu.edu.cn/www/cjc/online/cyuyan/,算是对其的修正,在此将本文列为原创,实有抄袭之嫌疑。甚是惭愧!位运算是指按二进制进行的运算。在系统软件中,常常需要处理二进制位的问题。C语言提供了6个位操作运算符。这些运算符只能用于整型操作数,即只能用于带符号或无符号的char,short,int与long类型。C语言提供的位运算符列表:运算符含义描述按位与如果两个相应的二进制位都为1,则该位的
    收起
  • 8年前

    C/C++堆栈指引 Binhua Liu 前言 我们经常会讨论这样的问题:什么时候数据存储在堆栈(Stack)中,什么时候数据存储在堆(Heap)中。我们知道,局部变量是存储在堆栈中的;debug时,查看堆栈可以知道函数的调用顺序;函数调用时传递参数,事实上是把参数压入堆栈,听起来,堆栈象一个大杂烩。那么,堆栈(Stack)到底是如何工作的呢? 本文将详解C/C++堆栈的工作机制。阅读时请注意以下几点: 1)本文讨论的编译环境是 Visual C/C++,由于高级语言的堆栈工作机制大
    收起
  • 7年前

    学习C++已经有一段时间了,一直都是学习基础的东西,每次写的代码都比较少,没有明确的学习目标,基础还是基础,漫无边际的,基本上都是做一道或者几道算法题,连一个小小的实战都没有,也不知道自己学得怎么样了,现在终于有一个小小的实战了《C++一个网络编程实例》。由于自己一直在做C#,只能业余时间学习C++,都说C++是那么的难,暂时还没有感觉到有多难,毕竟写代码也有两年多了。我要学习多久才能进一家做C++研发的公司呢?相信在不远处有一家C++研发公司在等着我。这只是一个小小的实例,包括So
    收起
  • 6年前

    文章来自:http://blog.csdn.net/shanzhizi/article/details/7726679一、下载和安装LIBXML2【方法一】Libxml2是个C语言的XML程式库,能简单方便的提供对XML文件的各种操作,并且支持XPATH查询,及部分的支持XSLT转换等功能。Libxml2的下载地址是http://xmlsoft.org/完全版的库是开源的,并且带有例子程式和说明文件。由于我是在linux下用C语言进行研发的,所以我下载的是libxml2-2.6.20.t
    收起
  • 7年前

    Access在小型系统开发中等到了广泛使用。虽然Access提供了可视化的操作方法,但许多开发人员还是喜欢直接用SQL语句操作数据表。如何在Access中打开SQL视图,对于初次使用Access的程序员可得费点时间呢。1、ACESS2007(1)点击创建--点击查询设计(2)点击关闭(3)点击左上角的"SQL视图"就可以打开SQL窗口了2、ACCESS2003(1)点击对象里的查询(2)点击在设计视图创建查询,再点击关闭(3)再点击左上
    收起