前言
黑魔法，應用場景 ：
1.實作宿生語言
2.實作一些常規手段做不到的東西，比如 c++11::share_prt::enable_share_from_this
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方言
Part 2 實作一些小玩意
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 = https://www.cnblogs.com/XDU-mzb/p/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和uisng指令等效，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 : str("null") {};
null也可以定義成別的樣子，這樣方便一些
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
#define car(x) typename Car<x>::result
template<typename T>
struct Car
{
using result = typename T::car;
};
#define cdr(x) typename Cdr<x>::result
template<typename T>
struct Cdr
{
using result = typename T::cdr;
};
#define equal(typea,typeb) typename std::is_same<typea,typeb>::type
#define if_else(a,b,c) typename std::conditional<a,b,c>::type
順便包裝一下std::is_same std::conditional
元函式約定 ：
1.每一個元函式都會搭配一個宏
2.統一用result作為元函式回傳值
3.元函式不繼承任何型別
實作一個異類字典
先看效果
using table = list<pair<str("a"),str("value_a")>,
pair<str("b"),integral_constant<bool,0>>,
pair<number<10>,str("x")>
>;
using resulta = table_find(table,str("a"));
using resultb = table_find(table,number<10>);
using resultc = table_find(table,str("c"));
cout << resulta() << endl; //value_a
cout << resultb() << endl; //x
cout << resultc() << endl; //null
看起來很復雜？我們分三步實作
1.實作list
2.實作table_find
3.實作輸出
1.實作list
template<typename T,typename ...arg>
struct list : pair<T,list<arg...>> {};
template<typename T>
struct list<T> : pair<T,null> {};
不會模板引數包的建議百度
概念上list<a,b,c> = pair<a,pair<b,pair<c,null>>>;
利用引數包 + pair不斷展開即可
template<typename T,typename ...arg>
struct list<T,arg...> : pair<T,list<arg...>> {};
template<typename T>
struct list<T> : pair<T,null> {};
因為list對型別沒有啥要求，所以直接實作了一個異類字典
2.實作table_find
#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 check_equal = equal(car(car(list)),key);
using result = if_else(check_equal::value,if_found,if_not_found);
};
template<typename key>
struct Table_find<null,key>
{
using result = null;
};
首先定義宏，得益我們良好的約定，我們可以寫出非常陽間的代碼
遞回終止的條件十分簡單：找不到回傳null即可，注意偏特化的寫法
概念上，table_find里面核心就是一個if_else邏輯
代碼寫的十分清楚，不停的遞回list結構，層層尋找即可
注意using check_equal = equal(car(car(list)),key);因為我們的宏中有typename
所以equal(car(car(list)),key)::value;的代碼是錯誤的，因為value是個靜態成員，解決辦法是加個間接型別
實作輸出
下面結尾c++輸出風格，如果你喜歡printf()這樣的，原理一樣
cout << integral_constant<int,10>() << endl; // 10
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,字典的元素個數
多動手，練習是必須滴
#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>;
};
實作一個歸并排序
1.實作merge : 按順序合并兩個list得到新的list
2.實作split : 切割一個list為長度差不超過1的兩個list
3.實作sort_merge : 合并兩個有序list為一個有序list
4.實作sort : 排序一個list
1.實作merge : 按順序合并兩個list得到新的list
這里需要一個技巧 : 模板的模板引數，不會的百度一下
模板的模板引數，在這里的作用是拿到list內部的型別，常規手段拿不到
其實模板的模板引數類似于函式的實參演繹，只不過挪到了編譯期，作用依舊是推導型別
#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...>;
};
結構就是一個宣告 + 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了，先康代碼
#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 = if_else(len_first::value < len_second::value,
_split(cdr(T),new_first,second),
_split(cdr(T),first,new_second));
};
template<typename first,typename second>
struct Split<null,first,second>
{
using result = pair<first,second>;
};
老樣子，先看簡單的第二個特化...
split概念上是一個帶引數的dfs(T,first,second)，運算結果存在引數里面，T為空的時候運算結束，回傳引數作為計算結果
再看
#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 = if_else(len_first::value < len_second::value,
_split(cdr(T),new_first,second),
_split(cdr(T),first,new_second));
};
注意偏特化不能有默認引數
思路很直觀，比較一下兩個引數new_first，new_second的長短，給短的添加當前元素
這里有一個陰間坑 : 如果你split實作的不對，比如 [1,2] -> [1,2],[] 也就是沒有正確切割...split會編譯通過，但是在某些計算中模板會報一大推錯...
老樣子，if_else實作一下，給短的添加一個元素即可...注意我們不能銷毀、改寫一個已經存在的型別...必須生成新的型別，代碼很直觀...
其實這樣子的元函式已經和普通函式差別不大了...只不過把值的運算變成了型別的運算
3.實作sort_merge : 合并兩個有序list為一個有序list
#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 = if_else(car1::value <= car2::value,
_sort_merge(cdr1,list2,ret1),
_sort_merge(list1,cdr2,ret2));
};
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);
};
老樣子，先看簡單的偏特化:)
和slpit類似，計算結果帶在引數ret里面
只有一個list的時候，直接和ret合并回傳，注意合并順序
#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 = if_else(car1::value <= car2::value,
_sort_merge(cdr1,list2,ret1),
_sort_merge(list1,cdr2,ret2));
};
很直觀了...這里再強調一下，為什么，元型別也可以計算，但是我們不用
元型別通過繼承做元計算的時候，沒辦法宣告新型別
這導致了它的計算能力大大下降...直接寫元函式，簡單直觀，沒必要用一些詭異的技巧折磨自己
sort_merge就沒了
4.實作sort : 排序一個list
萬事俱備...輕松愉快
#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>;
};
是8是很直觀...某種意義上編譯期排序并不比普通排序難...來個栗子
因為函式式編程語言在語法簡潔性上有巨大優勢
編譯期計算8皇后
#include <bits/stdc++.h>
using namespace std;
int dfs(int n,int now = 0,int zuo = 0,int you = 0,int has = 0)
{
if ((1 << n) - 1 == has)
return 1;
int ret = 0;
int state = zuo | you | has;
state = ((1 << n) - 1) & (~state);
for (int i = 0;i < 32;i++)
if ((1 << i) & (state))
{
int pos = (1 << i);
ret += dfs(n,now + 1,zuo + pos << 1,you + pos >> 1,has + pos);
}
return ret;
}
int main()
{
int n;
cin >> n;
cout << dfs(n);
return 0;
}
我們把這個良好的實作挪到編譯期就行了...八皇后的實作還是比較復雜了...包含了一部分元編程難點...有興趣的自己看看代碼
https://www.cnblogs.com/XDU-mzb/p/14832089.html
完整實作過一遍模板元實作lisp，對編程能力有一個巨大的鍛煉
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/285505.html
標籤：C++