经验首页 前端设计 程序设计 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中的标准库元函数,先看源代码

  1. template <typename T,T v>
  2. struct integral_constant
  3. {
  4. using value_type = T ;
  5. using type = integral_constant<T,v>;
  6. static constexpr T value = v;
  7. constexpr operator value_type()
  8. {
  9. return value;
  10. }
  11. };

看几个栗子

  1. using true_type = integral_constant<bool, true>;
  2. using ten = integral_constant<int,10>;
  3. ten::value_type val = 10;
  4. cout << ten::type::type::type::value << endl;
  5. cout << ten() << endl;

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

类型2.类型的类型

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

  1. template<typename a,typename b>
  2. struct sum : integral_constant<typename a::value_type,a::value + b::value>
  3. {};
  4. int main()
  5. {
  6. using ten = integral_constant<int,10>;
  7. using five = integral_constant<int,5>;
  8. cout << sum<ten,five>::value << endl;
  9. return 0;
  10. }

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

类型3.元计算类型

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

  1. template<typename a,typename b>
  2. struct sum
  3. {
  4. using result = integral_constant<typename a::value_type,a::value + b::value>;
  5. };
  6. int main()
  7. {
  8. using ten = integral_constant<int,10>;
  9. using five = integral_constant<int,5>;
  10. cout << sum<ten,five>::result() << endl;
  11. return 0;
  12. }

类似于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.基本类型

整形

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

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

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

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

2.null类型

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

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

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

3.pair类型

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

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

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

  1. template<typename T>
  2. struct car
  3. {
  4. using result = typename T::car;
  5. };
  6. template<typename T>
  7. struct cdr
  8. {
  9. using result = typename T::cdr;
  10. };

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

实现一个异类字典

先看效果

  1. using table = list<pair<str("a"),str("value_a")>,
  2. pair<str("b"),integral_constant<bool,0>>,
  3. pair<number<10>,str("x")>
  4. >;
  5. cout << table_find<table,str("12")>::result() << endl; // null
  6. cout << table_find<table,str("a")>::result() << endl; // value_A
  7. cout << table_find<table,number<10>>::result() << endl; // x

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

1.实现list
  1. template<typename ...T>
  2. struct list;
  3. template<typename T,typename ...arg>
  4. struct list<T,arg...> : pair<T,list<arg...>> {};
  5. template<typename T>
  6. struct list<T> : pair<T,null> {};

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

  1. template<typename ...T>
  2. struct list;

声明了一个list

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

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

2.实现table_find
  1. template<typename list,typename key>
  2. struct table_find
  3. {
  4. using check = integral_constant<bool,is_same<typename car<typename car<list>::result>::result,key>::value>;
  5. using if_found = typename cdr<typename car<list>::result>::result;
  6. using if_not_found = typename table_find<typename cdr<list>::result,key>::result;
  7. using result = typename conditional<check::value,if_found,if_not_found>::type;
  8. };
  9. template<typename key>
  10. struct table_find<null,key>
  11. {
  12. using result = null;
  13. };

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

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

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

  1. 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)这样。我为了使得代码直观易懂,没有写

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

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

实现输出

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

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

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

  1. template<ull val>
  2. ostream& operator << (ostream& os,string<val>)
  3. {
  4. std::string ret;
  5. ull now = val;
  6. while (now)
  7. ret.push_back(now % 255),
  8. now /= 255;
  9. reverse(ret.begin(),ret.end());
  10. return os << ret;
  11. }
  12. ostream& operator << (ostream& os,null)
  13. {
  14. return os << "null";
  15. }
  16. template<typename T,typename U>
  17. ostream& operator << (ostream& os,pair<T,U>)
  18. {
  19. return os << "(" << T() << "," << U() <<")";
  20. }

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

小结

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

  1. template<typename T>
  2. struct length
  3. {
  4. using result = number<1 + length<typename cdr<T>::result>::result::value>;
  5. };
  6. template<>
  7. struct length<null>
  8. {
  9. using result = number<0>;
  10. };

实现一个归并排序

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

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

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

  1. template<typename list1,typename list2>
  2. struct merge {};
  3. template<typename ...args1,template<typename ...args1> class list1,
  4. typename ...args2,template<typename ...args2> class list2
  5. >
  6. struct merge<list1<args1...>,list2<args2...>>
  7. {
  8. using result = list<args1...,args2...>;
  9. };
  10. template<typename ...args1,template<typename ...args1> class list1>
  11. struct merge<list1<args1...>,list<null>>
  12. {
  13. using result = list<args1...>;
  14. };
  15. template<typename ...args2,template<typename ...args2> class list2>
  16. struct merge<list2<null>,list2<args2...>>
  17. {
  18. using result = list<args2...>;
  19. };
  20. template<>
  21. struct merge<list<null>,list<null>>
  22. {
  23. using result = list<null>;
  24. };

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

  1. template<typename ...args1,template<typename ...args1> class list1,
  2. typename ...args2,template<typename ...args2> class list2
  3. >
  4. struct merge<list1<args1...>,list2<args2...>>
  5. {
  6. using result = list<args1...,args2...>;
  7. };

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

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

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

  1. template<typename T,typename first = list<null>,typename second = list<null>>
  2. struct split
  3. {
  4. using car = typename car<T>::result;
  5. using cdr = typename cdr<T>::result;
  6. using new_first = typename merge<first,list<car>>::result;
  7. using new_second = typename merge<second,list<car>>::result;
  8. using result = typename conditional<length<new_first>::result::value < length<new_second>::result::value,
  9. typename split<cdr,new_first,second>::result,
  10. typename split<cdr,first,new_second>::result
  11. >::type;
  12. };
  13. template<typename first,typename second>
  14. struct split<null,first,second>
  15. {
  16. using result = pair<first,second>;
  17. };

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

  1. template<typename T,typename first = list<null>,typename second = list<null>>
  2. struct split
  3. {
  4. using car = typename car<T>::result;
  5. using cdr = typename cdr<T>::result;
  6. using new_first = typename merge<first,list<car>>::result;
  7. using new_second = typename merge<second,list<car>>::result;
  8. using result = typename conditional<length<new_first>::result::value < length<new_second>::result::value,
  9. typename split<cdr,new_first,second>::result,
  10. typename split<cdr,first,new_second>::result
  11. >::type;
  12. };

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

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

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

3.实现sort_merge : 合并两个有序list为一个有序list
  1. template<typename list1,typename list2,typename ret = list<null>>
  2. struct sort_merge
  3. {
  4. using car1 = typename car<list1>::result;
  5. using car2 = typename car<list2>::result;
  6. using cdr1 = typename cdr<list1>::result;
  7. using cdr2 = typename cdr<list2>::result;
  8. using ret1 = typename merge<ret,list<car1>>::result;
  9. using ret2 = typename merge<ret,list<car2>>::result;
  10. using result = typename conditional<car1::value <= car2::value,
  11. typename sort_merge<cdr1,list2,ret1>::result,
  12. typename sort_merge<list1,cdr2,ret2>::result
  13. >::type;
  14. };
  15. template<typename list1,typename ret>
  16. struct sort_merge<list1,null,ret>
  17. {
  18. using result = typename merge<ret,list1>::result;
  19. };
  20. template<typename list2,typename ret>
  21. struct sort_merge<null,list2,ret>
  22. {
  23. using result = typename merge<ret,list2>::result;
  24. };

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

  1. template<typename list1,typename list2,typename ret = list<null>>
  2. struct sort_merge
  3. {
  4. using car1 = typename car<list1>::result;
  5. using car2 = typename car<list2>::result;
  6. using cdr1 = typename cdr<list1>::result;
  7. using cdr2 = typename cdr<list2>::result;
  8. using ret1 = typename merge<ret,list<car1>>::result;
  9. using ret2 = typename merge<ret,list<car2>>::result;
  10. using result = typename conditional<car1::value <= car2::value,
  11. typename sort_merge<cdr1,list2,ret1>::result,
  12. typename sort_merge<list1,cdr2,ret2>::result
  13. >::type;
  14. };

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

4.实现sort : 排序一个list

万事俱备...轻松愉快

  1. template<typename T>
  2. struct mysort
  3. {
  4. using split_res = typename split<T>::result;
  5. using left = typename car<split_res>::result;
  6. using right = typename cdr<split_res>::result;
  7. using left_ans = typename mysort<left>::result;
  8. using right_ans = typename mysort<right>::result;
  9. using result = typename sort_merge<left_ans,right_ans>::result;
  10. };
  11. template<typename T>
  12. struct mysort<list<T>>
  13. {
  14. using result = list<T>;
  15. };

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

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

lisp 2.0

约定

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

  1. #define split(type) typename Split<type>::result
  2. #define _split(type,typeb,typec) typename Split<type,typeb,typec>::result
  3. template<typename T,typename first = list<null>,typename second = list<null>>
  4. struct Split
  5. {
  6. using new_first = merge(first,list<car(T)>);
  7. using new_second = merge(second,list<car(T)>);
  8. using len_first = length(new_first);
  9. using len_second = length(new_second);
  10. using result = typename conditional<len_first::value < len_second::value,
  11. _split(cdr(T),new_first,second),
  12. _split(cdr(T),first,new_second)
  13. >::type;
  14. };
  15. template<typename first,typename second>
  16. struct Split<null,first,second>
  17. {
  18. using result = pair<first,second>;
  19. };

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

  1. using len_first = length(new_first);
  2. using len_second = length(new_second);
  3. using result = typename conditional<len_first::value < len_second::value,
  4. typename Split<cdr(T),new_first,second>::result,
  5. typename Split<cdr(T),first,new_second>::result
  6. >::type;

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

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

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

  1. /*
  2. ---- Author : XDU_mzb
  3. ---- lisp 2.0
  4. */
  5. #include <bits/stdc++.h>
  6. namespace DSL
  7. {
  8. using std::endl;
  9. using std::cout;
  10. using std::integral_constant;
  11. using std::conditional;
  12. using std::is_same;
  13. using std::ostream;
  14. using ll = long long int;
  15. using ull = unsigned long long int;
  16. constexpr ull stoull(const char *p,ull now = 0)
  17. {
  18. return *p == 0 ? now : stoull(p + 1,now * 255 + *p);
  19. }
  20. template<ull val>
  21. struct string : public integral_constant<ull,val> {};
  22. #define str(x) string<stoull(x)>
  23. template<typename T,typename U>
  24. struct pair
  25. {
  26. using car = T;
  27. using cdr = U;
  28. };
  29. template<typename T>
  30. struct Car
  31. {
  32. using result = typename T::car;
  33. };
  34. #define car(x) typename Car<x>::result
  35. template<typename T>
  36. struct Cdr
  37. {
  38. using result = typename T::cdr;
  39. };
  40. #define cdr(x) typename Cdr<x>::result
  41. template<ll val>
  42. struct number : integral_constant<ll,val> {};
  43. struct null : str("null") {};
  44. template<typename T,typename ...arg>
  45. struct list : pair<T,list<arg...>> {};
  46. template<typename T>
  47. struct list<T> : pair<T,null> {};
  48. #define table_find(table,value) typename Table_find<table,value>::result
  49. template<typename list,typename key>
  50. struct Table_find
  51. {
  52. using if_found = cdr(car(list));
  53. using if_not_found = table_find(cdr(list),key);
  54. using result = typename conditional<is_same<car(car(list)),key>::value,if_found,if_not_found>::type;
  55. };
  56. template<typename key>
  57. struct Table_find<null,key>
  58. {
  59. using result = null;
  60. };
  61. template<typename T>
  62. struct typeinfo
  63. {
  64. static std::string name()
  65. {
  66. return std::string("unknow_type::") + std::string("std::typeid::name::") + typeid(T).name();
  67. }
  68. };
  69. #define CREATE_NAME(type,type_name) template<> struct typeinfo< type > { static std::string name() { return type_name; } }
  70. CREATE_NAME(void,"void");
  71. CREATE_NAME(long long int,"ll");
  72. CREATE_NAME(null,"null");
  73. CREATE_NAME(unsigned long long int,"ull");
  74. CREATE_NAME(short,"short");
  75. CREATE_NAME(int,"int");
  76. CREATE_NAME(std::string,"std::string");
  77. CREATE_NAME(bool,"bool");
  78. CREATE_NAME(double,"double");
  79. CREATE_NAME(float,"float");
  80. template<ull val>
  81. struct typeinfo<string<val>>
  82. {
  83. static std::string name()
  84. {
  85. return "string";
  86. }
  87. };
  88. template<ll val>
  89. struct typeinfo<number<val>>
  90. {
  91. static std::string name()
  92. {
  93. return "number";
  94. }
  95. };
  96. template<typename T,T val>
  97. struct typeinfo<integral_constant<T,val>>
  98. {
  99. static std::string name()
  100. {
  101. return "const_value::" + typeinfo<T>::name();
  102. }
  103. };
  104. template<typename T,typename U>
  105. struct typeinfo<pair<T,U>>
  106. {
  107. static std::string name()
  108. {
  109. return std::string("pair<") + std::string(typeinfo<T>::name()) + std::string(",") + std::string(typeinfo<U>::name()) + std::string(">");
  110. }
  111. };
  112. template<typename ...args>
  113. struct typeinfo<list<args...>>
  114. {
  115. static std::string name()
  116. {
  117. return std::string("[") + help(list<args...>()) + std::string("]");
  118. }
  119. template<typename T,typename ...args2>
  120. static std::string help(list<T,args2...> r)
  121. {
  122. return typeinfo<T>::name() + _help(list<args2...>());
  123. }
  124. template<typename T>
  125. static std::string help(list<T>)
  126. {
  127. return typeinfo<T>::name();
  128. }
  129. template<typename T,typename ...args3>
  130. static std::string _help(list<T,args3...>)
  131. {
  132. return "," + typeinfo<T>::name() + _help(list<args3...>());
  133. }
  134. template<typename T>
  135. static std::string _help(list<T>)
  136. {
  137. return "," + typeinfo<T>::name();
  138. }
  139. };
  140. #undef CREATE_NAME
  141. #define length(type) typename Length<type>::result
  142. template<typename T>
  143. struct Length
  144. {
  145. using len = length(cdr(T));
  146. using result = number<1 + len::value>;
  147. };
  148. template<>
  149. struct Length<null>
  150. {
  151. using result = number<0>;
  152. };
  153. template<ull val>
  154. ostream& operator << (ostream& os,string<val>)
  155. {
  156. std::string ret;
  157. ull now = val;
  158. while (now)
  159. ret.push_back(now % 255),
  160. now /= 255;
  161. reverse(ret.begin(),ret.end());
  162. return os << ret;
  163. }
  164. ostream& operator << (ostream& os,null)
  165. {
  166. return os << "null";
  167. }
  168. template<typename T,typename U>
  169. ostream& operator << (ostream& os,pair<T,U>)
  170. {
  171. return os << "(" << T() << "," << U() <<")";
  172. }
  173. template<typename T>
  174. ostream& _print(ostream& os,list<T>)
  175. {
  176. return os << "," << T();
  177. }
  178. template<typename T,typename ...args>
  179. ostream& _print(ostream& os,list<T,args...>)
  180. {
  181. cout << "," << T();
  182. _print(os,list<args...>());
  183. return os;
  184. }
  185. template<typename T,typename ...args>
  186. ostream& print(ostream& os,list<T,args...>)
  187. {
  188. cout << T();
  189. _print(os,list<args...>());
  190. return os;
  191. }
  192. template<typename T>
  193. ostream& print(ostream& os,list<T>)
  194. {
  195. cout << T();
  196. return os;
  197. }
  198. template<typename ...args>
  199. ostream& operator << (ostream& os,list<args...>)
  200. {
  201. os << "[";
  202. print(os,list<args...>());
  203. os << "]";
  204. return os;
  205. }
  206. #define merge(typea,typeb) typename Merge<typea,typeb>::result
  207. template<typename list1,typename list2>
  208. struct Merge {};
  209. template<typename ...args1,template<typename ...args1> class list1,
  210. typename ...args2,template<typename ...args2> class list2
  211. >
  212. struct Merge<list1<args1...>,list2<args2...>>
  213. {
  214. using result = list<args1...,args2...>;
  215. };
  216. template<typename ...args1,template<typename ...args1> class list1>
  217. struct Merge<list1<args1...>,list<null>>
  218. {
  219. using result = list<args1...>;
  220. };
  221. template<typename ...args2,template<typename ...args2> class list2>
  222. struct Merge<list2<null>,list2<args2...>>
  223. {
  224. using result = list<args2...>;
  225. };
  226. template<>
  227. struct Merge<list<null>,list<null>>
  228. {
  229. using result = list<null>;
  230. };
  231. #define sort_merge(typea,typeb) typename Sort_merge<typea,typeb>::result
  232. #define _sort_merge(typea,typeb,typec) typename Sort_merge<typea,typeb,typec>::result
  233. template<typename list1,typename list2,typename ret = list<null>>
  234. struct Sort_merge
  235. {
  236. using car1 = car(list1);
  237. using car2 = car(list2);
  238. using cdr1 = cdr(list1);
  239. using cdr2 = cdr(list2);
  240. using ret1 = merge(ret,list<car1>);
  241. using ret2 = merge(ret,list<car2>);
  242. using result = typename conditional<car1::value <= car2::value,
  243. _sort_merge(cdr1,list2,ret1),
  244. _sort_merge(list1,cdr2,ret2)
  245. >::type;
  246. };
  247. template<typename list1,typename ret>
  248. struct Sort_merge<list1,null,ret>
  249. {
  250. using result = merge(ret,list1);
  251. };
  252. template<typename list2,typename ret>
  253. struct Sort_merge<null,list2,ret>
  254. {
  255. using result = merge(ret,list2);
  256. };
  257. #define split(type) typename Split<type>::result
  258. #define _split(type,typeb,typec) typename Split<type,typeb,typec>::result
  259. template<typename T,typename first = list<null>,typename second = list<null>>
  260. struct Split
  261. {
  262. using new_first = merge(first,list<car(T)>);
  263. using new_second = merge(second,list<car(T)>);
  264. using len_first = length(new_first);
  265. using len_second = length(new_second);
  266. using result = typename conditional<len_first::value < len_second::value,
  267. _split(cdr(T),new_first,second),
  268. _split(cdr(T),first,new_second)
  269. >::type;
  270. };
  271. template<typename first,typename second>
  272. struct Split<null,first,second>
  273. {
  274. using result = pair<first,second>;
  275. };
  276. #define sort(type) typename Sort<type>::result
  277. template<typename T>
  278. struct Sort
  279. {
  280. using left = car(split(T));
  281. using right = cdr(split(T));
  282. using result = sort_merge(sort(left),sort(right));
  283. };
  284. template<typename T>
  285. struct Sort<list<T>>
  286. {
  287. using result = list<T>;
  288. };
  289. int main()
  290. {
  291. using table = list<pair<str("a"),str("value_a")>,
  292. pair<str("b"),integral_constant<bool,0>>,
  293. pair<number<10>,str("x")>
  294. >;
  295. cout << typeinfo<integral_constant<bool,false>>::name() << endl;
  296. cout << integral_constant<int,10>() << endl;
  297. cout << length(table)() << endl;
  298. cout << table_find(table,str("12"))() << endl; // null
  299. cout << table_find(table,str("a"))() << endl; // value_A
  300. cout << table_find(table,number<10>)() << endl; // x
  301. using l = list<null,number<10>,str("200")>;
  302. cout << null() << endl;
  303. cout << l() << endl;
  304. using a = list<number<10>,number<-1>,number<-100>,number<123>,number<-50>>;
  305. using b = sort(a);
  306. cout << "a : " << a() << endl;
  307. cout << "b : " << b() << endl;
  308. return 0;
  309. }
  310. #undef str
  311. #undef null
  312. }
  313. int main()
  314. {
  315. DSL::main();
  316. return 0;
  317. }

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

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号