经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
c++11-模板元实战
来源:cnblogs  作者:XDU18清欢  时间:2021/5/31 9:12:46  对本文有异议

前言

黑魔法,应用场景 :
1.实现宿生语言
2.压榨机器性能 : 表达式模板,循环展开...特别是在高性能计算领域...可以获得媲美手工展开的高效代码
3.作为实现各种库的基本组件 :Stl,Boost,标准库都大量运用了模板元技术

很多人比较排斥这个东西...一些炫技模板元代码能看得人头皮发麻...
个人觉得实用就行,工具终究是为人服务的
just enjoy it ??

推荐的资料

《C++ Templates》
《C++模板元编程》
C++11模板元入门 https://www.cnblogs.com/qicosmos/p/4480460.html
C++高质量社区 http://purecpp.org/

Part 1 实现一个基于C++的宿生Lisp方言

基本约定

建议先看看江南的博客入个门 :C++11模板元入门 https://www.cnblogs.com/qicosmos/p/4480460.html
这是一个类型的世界,首先定义三种基本类型
1.与值关联的类型 : integral_constant
2.类型的类型
3.元计算类型
当然这是一种定义风格,三种类型并无严格区别,可以相互代替...只是会带来巨大的混乱(个人经验
所以直接严格划分三种类型...就不容易在类型的世界迷失

1.integral_constant

c++11中的标准库元函数,先看源代码

template <typename T,T v>
struct integral_constant
  {
	using value_type = T ;
	using type = integral_constant<T,v>;
	static constexpr T value = v;
	constexpr operator value_type() 
	  {
	  	return value;
	  }
  };

看几个栗子

using true_type = integral_constant<bool, true>;
using ten = integral_constant<int,10>;
ten::value_type val = 10;
cout << ten::type::type::type::value << endl;
cout << ten() << endl;

(typedef和using指令等效,using指令更直观,元表达式一复杂,采用using指令更清晰
可以观察到 integral_constant作为一个元函数,可以生成一个新类型,新类型绑定一个值和该值的类型
并且特别的是 :integral_constant::type指向类型本身,这一点的用处比较大,后面还会说,先观察到即可

类型2.类型的类型

特征十分明显 :结构体为空 (建议元编程的时候全部采用struct,struct与class没什么区别,仅仅默认访问权限、继承全部为public

template<typename a,typename b>
struct sum : integral_constant<typename a::value_type,a::value + b::value>
  {};
int main()
  {
  	using ten = integral_constant<int,10>;
  	using five = integral_constant<int,5>;
  	cout << sum<ten,five>::value << endl;
	return 0;
  }

继续观察样例,可以看到sum完成了两个数的加法
观察点1 : 第二行 typename a::value_type,为什么要加奇怪的typename?因为c++模板的特殊性质,编译器在看到a::value_type的时候并不能分析出来a::value_type是成员变量还是类型,所以需要显式说明
观察点2 : sum的结构体为空,所以sum是"类型的类型",但是,sum却完成一个元函数行为 :计算两数和。既然"类型的类型"可以进行元计算,为什么我们还需要划分出一个元计算类型?
答案是"类型的类型"可以进行元计算,但是完成不了复杂的元计算,因为在"类型的类型"做元计算的时候,声明不了新类型,导致只能实现一句代码的元计算,做不了复杂计算

类型3.元计算类型

特征也十分明显:没有继承行为,结构体内部充满一些using指令,用来做元计算

template<typename a,typename b>
struct sum
  {
  	using result = integral_constant<typename a::value_type,a::value + b::value>;
  };
int main()
  {
  	using ten = integral_constant<int,10>;
  	using five = integral_constant<int,5>;
  	cout << sum<ten,five>::result() << endl;
	return 0;
  }

类似于c/c++中的函数,元函数也有"函数名" : sum,"函数参数" :typename a,typename b,"返回值" result
观察点1.我们约定,元函数的"返回值"全部定义为result
观察点2.cout << sum<ten,five>::result() << endl; result是类型,我们可以通过类似 cout << int() << endl;的形式来打印元信息,重载一下流输出即可,后面还会涉及
观察点3.我们约定,元函数不继承任何类型

lisp方言基本类型与操作

1.基本类型,如整形,字符串
2.null类型
3.pair
4.元函数car,cdr
有一个非常庞大的证明和实践体系证明上述简单类型/操作能实现非常复杂的计算,是图灵完备的

1.基本类型

整形

template<int val>
struct number : integral_constant<int,val> {};

字符串 : 因为c++11不滋滋模板字符串,所以不能直接定义(因为 "string"的类型是const cahr* const 两个相同的字符串常量拥有不同的常量地址,模板不能识别这种
因为本次模板元实战主要在模板,我采用了一种取巧的办法 :把字符串压进unsigned long long int(简记为ull,可以滋滋长度在8及以下的任何字符串

  	constexpr ull stoull(const char *p,ull now = 0)
  	  {
  	  	return *p == 0 ? now : stoull(p + 1,now * 255 + *p); 
		}
	template<ull val>
	struct string : public integral_constant<ull,val> {};
#define str(x) string<stoull(x)>

这样就可以很方便的用str("string")来产生字符串类型
浮点 : 因为c++的历史原因,模板也不滋滋浮点常量,取巧的办法是定义一个pair<int,int> 即"int.int",与主题关系不大,故不再赘述

2.null类型

为什么要把null单独说明呢...因为空类型相当重要,设计良好的空类型可以很好的简化很多设计

struct null : integral_constant<ull,stoull("null")> {};

特别是,空类型要保证null::type == null,这样才能契合进元计算的整体框架
也可以看到integral_constant的重要性,integral_constant是一个很重要的基础设施

3.pair类型

和c++中的pair类似,只不过first -> car,second -> cdr(仅仅是遵循lisp方言惯例,没什么特别含义

template<typename T,typename U>
struct pair
  {
  	using car = T;
  	using cdr = U;
  };
4.元函数car,cdr

没啥好说的,注意我们预定result为元函数返回值

template<typename T>
struct car
  {
  	using result = typename T::car;
  };
template<typename T>
struct cdr
  {
  	using result = typename T::cdr;
  };

有些用过lisp的人可能要说了,你怎么没有实现一个cons?这个直接pair<type,type>即可,没必要重复...毕竟我们是在做宿生语言,适当的修改使得宿生更契合宿主,没必要严格实现

实现一个异类字典

先看效果

using table = list<pair<str("a"),str("value_a")>,
             	   pair<str("b"),integral_constant<bool,0>>,
	           pair<number<10>,str("x")>
	           >;
cout << table_find<table,str("12")>::result() << endl;  // null
cout << table_find<table,str("a")>::result() << endl;   // value_A
cout << table_find<table,number<10>>::result() << endl; // x

看起来很复杂?我们分三步实现
1.实现list
2.实现table_find
3.实现输出

1.实现list
template<typename ...T>
struct list;
template<typename T,typename ...arg>
struct list<T,arg...> : pair<T,list<arg...>> {};
template<typename T>
struct list<T> : pair<T,null> {};

不会模板参数包的建议百度
首先

template<typename ...T>
struct list;

声明了一个list

template<typename T,typename ...arg>
struct list<T,arg...> : pair<T,list<arg...>> {};
template<typename T>
struct list<T> : pair<T,null> {};

然后两个模板偏特化,看起来挺清晰的,就是list<a,b,c> = pair<a,pair<b,pair<c,null>>>;
就没了...参数包用起来qs很好用
因为list对类型没有啥要求,所以直接实现了一个异类字典

2.实现table_find
template<typename list,typename key>
struct table_find
  {
  	using check = integral_constant<bool,is_same<typename car<typename car<list>::result>::result,key>::value>;
  	using if_found = typename cdr<typename car<list>::result>::result;
  	using if_not_found = typename table_find<typename cdr<list>::result,key>::result;
  	using result = typename conditional<check::value,if_found,if_not_found>::type;
  };
template<typename key>
struct table_find<null,key>
  {
  	using result = null;
  };

首先观察第二个偏特化,找遍字典还没找到,那就无了,返回null
然后看第一个
首先看结尾处的

using result = typename conditional<check::value,if_found,if_not_found>::type;

conditional是c++11模板元函数,就是实现一个if-else的逻辑 ::type就是拿到元计算结果(这与我们定义::result作为元函数计算结果不同)
注意typename告诉编译器这是个类型,不然会报错

using check = integral_constant<bool,is_same<typename car<typename car<list>::result>::result,key>::value>;

check是判断条件,is_same也是标准库元函数,判断两个类型是不是一样
因为字典本质上是个pair<a,pair<b,pair<c,null>>>用car,cdr把对应部分提取出来比较即可,(car,cdr为了方便可以直接写作宏,car(type)这样。我为了使得代码直观易懂,没有写

using if_found = typename cdr<typename car<list>::result>::result;
using if_not_found = typename table_find<typename cdr<list>::result,key>::result;

没找到就递归调用table_find即可,因为我们对元函数定义的约定,这对于熟悉递归的人非常直观
另外,我们可以直观观察到
值(类型)只能被创造,不能被摧毁
这句话相当重要,这是函数式编程语言的特色,我编写代码的时候忽然领悟了这句话的精髓...这是函数式编程风格的一个重要特色,一块基石
还可以观察到,我们通过using指令创造新类型,相当于在元函数里面声明新变量,元函数通过约定,变得直观易懂
运算结果通过result返回
...tabld_find就完成了,仍有一些注意点
因为模板元的特性,建议增量开发模板元程序...不然报错一报若干行...初学者很容易懵逼...
偏特化,参数包基本操作,不会的多练练

实现输出

下面结尾c++输出风格,如果你喜欢printf()这样的,原理一样

cout << integral_constant<int,10>() << endl;
cout << table_find<table,str("12")>::result() << endl;  // null

首先integral_constant里面重载了类型转换运算符,编译器会自动转化,我们只需要写自己类型的输出格式即可

template<ull val>
ostream& operator << (ostream& os,string<val>)
  {
  	std::string ret;
  	ull now = val;
  	while (now)
  	  ret.push_back(now % 255),
  	  now /= 255;
  	reverse(ret.begin(),ret.end());
  	return os << ret;
  }
ostream& operator << (ostream& os,null)
  {
  	return os << "null";
  }
template<typename T,typename U>
ostream& operator << (ostream& os,pair<T,U>)
  {
  	return os << "(" << T() << "," << U() <<")";
  }

注意ostream& operator << (ostream& os,string);第二个没参数,只有类型
因为信息都在类型里面,参数写不写无所谓,你写的话,编译器自动会优化掉
调用的时候func(type()),编译器就能演绎类型了,func(type)这样是不行滴,因为违背了c\c++参数传递规则
就是函数重载 + 模板特化,大多数输出就这三种特化方式...都在这了...比较简单,照猫画虎即可
list<number<10>,str("22")> : [10,22]
list的输出比较麻烦一点,因为要控制输出格式 + 参数包,代码里有,原理没区别,不赘述了

小结

至此,我们实现了一个字典...难者不会,会者不难...写熟练之后还是挺简单的
小练习,实现一个length的元函数,计算list,字典的元素个数
多动手,练习是必须滴

template<typename T>
struct length
  {
  	using result = number<1 + length<typename cdr<T>::result>::result::value>;
  };
template<>
struct length<null>
  {
  	using result = number<0>;
  };

实现一个归并排序

1.实现merge : 按顺序合并两个list得到新的list
2.实现split : 切割一个list为长度差不超过1的两个list
3.实现sort_merge : 合并两个有序list为一个有序list
4.实现sort : 排序一个list

1.实现merge : 按顺序合并两个list得到新的list

这里需要一个技巧 : 模板的模板参数,不会的百度一下
模板的模板参数,在这里的作用是拿到list内部的类型,常规手段拿不到
其实模板的模板参数类似于函数的实参演绎,只不过挪到了编译期,作用依旧是推导类型

template<typename list1,typename list2>
struct merge {};

template<typename ...args1,template<typename ...args1> class list1,
         typename ...args2,template<typename ...args2> class list2 
         >
struct merge<list1<args1...>,list2<args2...>>
  {
  	using result = list<args1...,args2...>;
  };

template<typename ...args1,template<typename ...args1> class list1>
struct merge<list1<args1...>,list<null>>
  {
  	using result = list<args1...>;
  };
template<typename ...args2,template<typename ...args2> class list2>
struct merge<list2<null>,list2<args2...>>
  {
  	using result = list<args2...>;
  };
template<>
struct merge<list<null>,list<null>>
  {
  	using result = list<null>;
  };

结构就是一个声明 + 4个偏特化...后面三个偏特化很简单,重点看第一个偏特化

template<typename ...args1,template<typename ...args1> class list1,
         typename ...args2,template<typename ...args2> class list2 
         >
struct merge<list1<args1...>,list2<args2...>>
  {
  	using result = list<args1...,args2...>;
  };

这里的merge其实可以通过lisp形式完成...(偷个懒顺便练习一下模板的模板参数...后面还会用lisp的风格写元函数的
元函数体里面很直观,就是拿到两个list的参数,合并到一个新的list就完了
重点在于模板的模板参数,因为是偏特化,所以template中的顺序无所谓,编译器会推导出正确的类型
template<typename ...args1> class list1因为模板类才有模板的模板参数,c++要求在这里写一个class...(比较憨,但是你得写...以后的标准可能改进这一点...
merge就没了...(偷懒成功,大雾

2.实现split : 切割一个list为长度差不超过1的两个list

split的实现就很lisp了,先康代码

template<typename T,typename first = list<null>,typename second = list<null>>
struct split
  {
  	using car = typename car<T>::result;
  	using cdr = typename cdr<T>::result;
  	using new_first  = typename merge<first,list<car>>::result;
  	using new_second = typename merge<second,list<car>>::result;

  	using result = typename conditional<length<new_first>::result::value < length<new_second>::result::value,
			                    typename split<cdr,new_first,second>::result,
				            typename split<cdr,first,new_second>::result
					    >::type;
  }; 
template<typename first,typename second>
struct split<null,first,second>
  {
  	using result = pair<first,second>;
  };

老样子,先看简单的第二个特化...
split概念上是一个带参数的dfs(T,first,second),运算结果存在参数里面,T为空的时候运算结束,返回参数作为计算结果
再看

template<typename T,typename first = list<null>,typename second = list<null>>
struct split
  {
  	using car = typename car<T>::result;
  	using cdr = typename cdr<T>::result;
  	using new_first  = typename merge<first,list<car>>::result;
  	using new_second = typename merge<second,list<car>>::result;

  	using result = typename conditional<length<new_first>::result::value < length<new_second>::result::value,
			                    typename split<cdr,new_first,second>::result,
				            typename split<cdr,first,new_second>::result
					    >::type;
  }; 

首先,first,second默认为list<null>。模板也可以设默认type。运算结果是一个pair<list<>,list<>>
注意偏特化不能有默认参数

cout << split<a>::result() << endl;

思路很直观,比较一下两个参数first,second的长短,给短的添加当前元素
这里有一个阴间坑 : 如果你split实现的不对,比如 [1,2] -> [1,2],[] 也就是没有正确切割...split会编译通过,但是在某些计算中模板会报一大推错...
老样子,conditional实现一下,给短的添加一个元素即可...注意我们不能销毁、改写一个已经存在的类型...必须生成新的类型,代码很直观...
其实这样子的元函数已经和普通函数差别不大了...这得益于我们的约定 : 严格区分三种类型,从而带来实现上的方便

3.实现sort_merge : 合并两个有序list为一个有序list
template<typename list1,typename list2,typename ret = list<null>>
struct sort_merge
  {
  	using car1 = typename car<list1>::result;
  	using car2 = typename car<list2>::result;
  	using cdr1 = typename cdr<list1>::result;
  	using cdr2 = typename cdr<list2>::result;
  	using ret1 = typename merge<ret,list<car1>>::result;
  	using ret2 = typename merge<ret,list<car2>>::result;
  	using result = typename conditional<car1::value <= car2::value,
			                    typename sort_merge<cdr1,list2,ret1>::result,
				            typename sort_merge<list1,cdr2,ret2>::result
				            >::type;
  };
template<typename list1,typename ret>
struct sort_merge<list1,null,ret>
  {
  	using result = typename merge<ret,list1>::result;
  };
template<typename list2,typename ret>
struct sort_merge<null,list2,ret>
  {
  	using result = typename merge<ret,list2>::result;
  };

老样子,先看简单的偏特化:)
和slpit类似,计算结果带在参数ret里面
只有一个list的时候,直接和ret合并返回,注意合并顺序

template<typename list1,typename list2,typename ret = list<null>>
struct sort_merge
  {
  	using car1 = typename car<list1>::result;
  	using car2 = typename car<list2>::result;
  	using cdr1 = typename cdr<list1>::result;
  	using cdr2 = typename cdr<list2>::result;
  	using ret1 = typename merge<ret,list<car1>>::result;
  	using ret2 = typename merge<ret,list<car2>>::result;
  	using result = typename conditional<car1::value <= car2::value,
			                    typename sort_merge<cdr1,list2,ret1>::result,
				            typename sort_merge<list1,cdr2,ret2>::result
				            >::type;
  };

明显cdr,car写成宏更好用(大雾
很直观了...这里再强调一下,为什么,类型的类型也可以计算,但是我们不用
类型的类型通过继承做元计算的时候,没办法声明新类型
这导致了它的计算能力大大下降...直接写元函数,简单直观,没必要用一些诡异的技巧折磨自己
sort_merge就没了

4.实现sort : 排序一个list

万事俱备...轻松愉快

template<typename T>
struct mysort
  {
  	using split_res = typename split<T>::result;
  	using left = typename car<split_res>::result;
  	using right = typename cdr<split_res>::result;
  	using left_ans = typename mysort<left>::result;
  	using right_ans = typename mysort<right>::result;
  	using result = typename sort_merge<left_ans,right_ans>::result;
  };
template<typename T>
struct mysort<list<T>>
  {
  	using result = list<T>;
  };

是8是很直观...某种意义上编译期排序并不比普通排序难...来个栗子

因为函数式编程语言在语法简洁性上有巨大优势

lisp 2.0

约定

为了写出这样的阳间代码 : (是不是比lisp 1.0 阳间了很多)

#define split(type) typename Split<type>::result
#define _split(type,typeb,typec) typename Split<type,typeb,typec>::result
	template<typename T,typename first = list<null>,typename second = list<null>>
	struct Split
	  {
	  	using new_first  = merge(first,list<car(T)>);
	  	using new_second = merge(second,list<car(T)>);
	  	using len_first = length(new_first);
	  	using len_second = length(new_second);
	  	using result = typename conditional<len_first::value < len_second::value,
				                    _split(cdr(T),new_first,second),
						    _split(cdr(T),first,new_second)
						    >::type;
	  }; 
	template<typename first,typename second>
	struct Split<null,first,second>
	  {
	  	using result = pair<first,second>;
	  };

我们约定 :
1.所有的元函数首字母大写,并且每个元函数都有一个对应的宏,宏名仅首字母小写 如#define split(type) typename Split<type>::result
2.所有的类型的类型,改称为元类型 所有的类型无需搭配宏,比如pair<type,type>
遵循约定,我们就能写出非常阳间的代码
特例

using len_first = length(new_first);
using len_second = length(new_second);
using result = typename conditional<len_first::value < len_second::value,
		                    typename Split<cdr(T),new_first,second>::result,
		                    typename Split<cdr(T),first,new_second>::result
		                    >::type;

使用integral_constant的value时,我们需要增加一个间接类型,因为宏里面和编译器约定了typename,就不能再使用::value这个成员
解决办法就是using指令加个间接层

-----------------------分割线----------------------以下均不是博客内容---------------------------------

代码,可能托管到github更好一点,后面再弄

/*
---- Author : XDU_mzb 
---- lisp 2.0
*/ 
#include <bits/stdc++.h>

namespace DSL
  {
  	using std::endl;
  	using std::cout;
  	using std::integral_constant;
  	using std::conditional;
  	using std::is_same;
  	using std::ostream;
  	
  	using ll = long long int;
    using ull = unsigned long long int;
    
  	constexpr ull stoull(const char *p,ull now = 0)
  	  {
  	  	return *p == 0 ? now : stoull(p + 1,now * 255 + *p); 
		}
	template<ull val>
	struct string : public integral_constant<ull,val> {};
#define str(x) string<stoull(x)>
    
  	template<typename T,typename U>
	struct pair
	  {
	  	using car = T;
	  	using cdr = U;
	  };
	template<typename T>
	struct Car
	  {
	  	using result = typename T::car;
	  };
#define car(x) typename Car<x>::result
	template<typename T>
	struct Cdr
	  {
	  	using result = typename T::cdr;
	  };
#define cdr(x) typename Cdr<x>::result

	template<ll val>
	struct number : integral_constant<ll,val> {};
	
	struct null : str("null") {};
	  
	template<typename T,typename ...arg>
	struct list : pair<T,list<arg...>> {};
	template<typename T>
	struct list<T> : pair<T,null> {};
	
#define table_find(table,value) typename Table_find<table,value>::result	
	template<typename list,typename key>
	struct Table_find
	  {
	  	using if_found = cdr(car(list));
	  	using if_not_found = table_find(cdr(list),key);
	  	using result = typename conditional<is_same<car(car(list)),key>::value,if_found,if_not_found>::type;
	  };
	template<typename key>
	struct Table_find<null,key>
	  {
	  	using result = null;
	  };


	template<typename T>
	struct typeinfo
	  {
	  	static std::string name()
	  	  {
	  	  	return std::string("unknow_type::") + std::string("std::typeid::name::") + typeid(T).name();
			}
	  };
#define CREATE_NAME(type,type_name)  template<> struct typeinfo< type >     	  {                             	  	static std::string name()   	  	  {                         	  	  	return type_name;       			}                       	  }
	CREATE_NAME(void,"void");
	CREATE_NAME(long long int,"ll");
	CREATE_NAME(null,"null");
    CREATE_NAME(unsigned long long int,"ull");
    CREATE_NAME(short,"short");
    CREATE_NAME(int,"int");
    CREATE_NAME(std::string,"std::string");
    CREATE_NAME(bool,"bool");
    CREATE_NAME(double,"double");
    CREATE_NAME(float,"float");
	template<ull val>
	struct typeinfo<string<val>>
	  {
	  	static std::string name()
	  	  {
	  	  	return "string";
			} 
		}; 
	template<ll val>
	struct typeinfo<number<val>>
	  {
	  	static std::string name()
	  	  {
	  	  	return "number";
			}
	  };
	template<typename T,T val>
	struct typeinfo<integral_constant<T,val>>
	  {
	  	static std::string name()
	  	  {
	  	  	return "const_value::" + typeinfo<T>::name();
			}
	  };
	template<typename T,typename U>
	struct typeinfo<pair<T,U>>
	  {
	  	static std::string name()
	  	  {
	  	  	return std::string("pair<") + std::string(typeinfo<T>::name()) + std::string(",") + std::string(typeinfo<U>::name()) + std::string(">");
			}
	  };       
	 template<typename ...args>
	 struct typeinfo<list<args...>>
	   {
	   	static std::string name()
	   	  {
	   	  	return std::string("[") + help(list<args...>()) + std::string("]");
			 }
		template<typename T,typename ...args2>
		static std::string help(list<T,args2...> r)
		  {
		  	return typeinfo<T>::name() + _help(list<args2...>());
		  }
		template<typename T>
		static std::string help(list<T>)
		  {
		  	return typeinfo<T>::name();
		  }
		template<typename T,typename ...args3>
		static std::string _help(list<T,args3...>)
		  {
		  	return "," + typeinfo<T>::name() + _help(list<args3...>());
		  }
		template<typename T>
		static std::string _help(list<T>)
		  {
		  	return "," + typeinfo<T>::name();
		  }
		};         
#undef CREATE_NAME

#define length(type) typename Length<type>::result    
	template<typename T>
	struct Length
	  {
	  	using len = length(cdr(T));
	  	using result = number<1 + len::value>;
	  };
	template<>
	struct Length<null>
	  {
	  	using result = number<0>;
	  };


	template<ull val>
	ostream& operator << (ostream& os,string<val>)
	  {
	  	std::string ret;
	  	ull now = val;
	  	while (now)
	  	  ret.push_back(now % 255),
	  	  now /= 255;
	  	reverse(ret.begin(),ret.end());
	  	return os << ret;
	  }
	ostream& operator << (ostream& os,null)
	  {
	  	return os << "null";
	  }
	template<typename T,typename U>
	ostream& operator << (ostream& os,pair<T,U>)
	  {
	  	return os << "(" << T() << "," << U() <<")";
	  }
	template<typename T>
	ostream& _print(ostream& os,list<T>)
	  {
	  	return os << "," << T();
	  }
	template<typename T,typename ...args>
	ostream& _print(ostream& os,list<T,args...>)
	  {
	  	cout << "," << T();
	    _print(os,list<args...>());
	  	return os;
	  }
	template<typename T,typename ...args>
	ostream& print(ostream& os,list<T,args...>)
	  {
	  	cout << T();
		_print(os,list<args...>());
	  	return os;
	  }
	template<typename T>
	ostream& print(ostream& os,list<T>)
	  {
	  	cout << T();
	  	return os;
	  }
	template<typename ...args>
	ostream& operator << (ostream& os,list<args...>)
	  {
	  	os << "[";
	  	print(os,list<args...>());
	  	os << "]";
	  	return os;
	  }

#define merge(typea,typeb) typename Merge<typea,typeb>::result	  
	template<typename list1,typename list2>
	struct Merge {};
	template<typename ...args1,template<typename ...args1> class list1,
	         typename ...args2,template<typename ...args2> class list2
			 >
	struct Merge<list1<args1...>,list2<args2...>>
	  {
	  	using result = list<args1...,args2...>;
	  };
	template<typename ...args1,template<typename ...args1> class list1>
	struct Merge<list1<args1...>,list<null>>
	  {
	  	using result = list<args1...>;
	  };
	template<typename ...args2,template<typename ...args2> class list2>
	struct Merge<list2<null>,list2<args2...>>
	  {
	  	using result = list<args2...>;
	  };
	template<>
	struct Merge<list<null>,list<null>>
	  {
	  	using result = list<null>;
	  };

#define sort_merge(typea,typeb) typename Sort_merge<typea,typeb>::result
#define _sort_merge(typea,typeb,typec) typename Sort_merge<typea,typeb,typec>::result	
	template<typename list1,typename list2,typename ret = list<null>>
	struct Sort_merge
	  {
	  	using car1 = car(list1);
	  	using car2 = car(list2);
	  	using cdr1 = cdr(list1);
	  	using cdr2 = cdr(list2);
	  	using ret1 = merge(ret,list<car1>);
	  	using ret2 = merge(ret,list<car2>);
	  	using result = typename conditional<car1::value <= car2::value,
				                            _sort_merge(cdr1,list2,ret1),
										    _sort_merge(list1,cdr2,ret2)
										    >::type;
	  };
	template<typename list1,typename ret>
	struct Sort_merge<list1,null,ret>
	  {
	  	using result = merge(ret,list1);
	  };
	template<typename list2,typename ret>
	struct Sort_merge<null,list2,ret>
	  {
	  	using result = merge(ret,list2);
	  };

#define split(type) typename Split<type>::result
#define _split(type,typeb,typec) typename Split<type,typeb,typec>::result
	template<typename T,typename first = list<null>,typename second = list<null>>
	struct Split
	  {
	  	using new_first  = merge(first,list<car(T)>);
	  	using new_second = merge(second,list<car(T)>);
	  	using len_first = length(new_first);
	  	using len_second = length(new_second);
	  	using result = typename conditional<len_first::value < len_second::value,
				                            _split(cdr(T),new_first,second),
										    _split(cdr(T),first,new_second)
											>::type;
	  }; 
	template<typename first,typename second>
	struct Split<null,first,second>
	  {
	  	using result = pair<first,second>;
	  };

#define sort(type) typename Sort<type>::result	  
	template<typename T>
	struct Sort
	  {
	  	using left = car(split(T));
	  	using right = cdr(split(T));
	  	using result = sort_merge(sort(left),sort(right));
	  };
	template<typename T>
	struct Sort<list<T>>
	  {
	  	using result = list<T>;
	  };

	
	int main()
	  {
		using table = list<pair<str("a"),str("value_a")>,
		             	   pair<str("b"),integral_constant<bool,0>>,
						   pair<number<10>,str("x")>
						   >;
				   
		cout << typeinfo<integral_constant<bool,false>>::name() << endl;
		cout << integral_constant<int,10>() << endl;
		
		cout << length(table)() << endl;
		cout << table_find(table,str("12"))() << endl;  // null
		cout << table_find(table,str("a"))() << endl;   // value_A
		cout << table_find(table,number<10>)() << endl; // x
		using l = list<null,number<10>,str("200")>;
		cout << null() << endl;
	    cout << l() << endl;
	    using a = list<number<10>,number<-1>,number<-100>,number<123>,number<-50>>;
	    using b = sort(a);
	    cout << "a : " << a() << endl;
	    cout << "b : " << b() << endl;
	  	return 0;
	  }
#undef str
#undef null
  }

int main()
  {
  	DSL::main();
	return 0;
  }

原文链接:http://www.cnblogs.com/XDU-mzb/p/14804536.html

 友情链接: NPS