整段源碼鏈接
C++的模板元堆排序
要點
- 組建數(shù)據(jù)結構list
- 組建對list的各種基本操作
- 堆排序中組建堆排序個個函數(shù)以及其中 if粟害，for之類的結構
PS：其實你以為這些東西很容易……但是我重構了4遍啊……
PS2: using integer = int; <=> typedef int integer;
PS3: typename是為了顯式的告訴編譯期這個東西是一個類型
PS4: 不要吐槽取名
下面開始
一. 建立數(shù)據(jù)結構list
但是這個list呢實際上由cons組成的
即(list 1 2 3) == (cons 1 (cons 2 (cons 3 nil)))
也就是C++中是list<1,2,3> == cons<1, cons<2, cons<3, null>>>
那么首先是想list這東西該怎么來茫陆，list的參數(shù)必然是可變長參數(shù)仗岖，這就有點傷腦筋了，所以第一步還是先去解決cons览妖，然后把list定義成cons的遞歸轧拄。
struct null {};
template<class left, class right>
struct cons {};
template<class left>
struct cons<left, null> {};
這里面的null其實并不太好解決，實際上我還未參透null到底是什么讽膏，不過這么寫是可以用的檩电，但是元函數(shù)類要訪問越界list訪問到它的時候需要小心。
其實這樣就完事了府树，這里的一切其實都好像運行在參數(shù)上面俐末，但是這樣不用方便使用，我們來為它添加上可以訪問到這個序對的左節(jié)點(car)和右節(jié)點(cdr ,鏈表中cdr會是除了頭節(jié)點以外剩下的節(jié)點)挺尾，再加上計算長度鹅搪。
template<class left, class right>
struct cons {
using car = left;
using cdr = right;
static int const length = cdr::length + 1; //這里當然是遞歸了，它會找得到下一層的遭铺。
};
template<class left>
struct cons<left, null> {
using car = left;
using cdr = null;
static int const length = 1;
};
接下來要解決list和cons遞歸體的統(tǒng)一丽柿，
template<class head, class ...tail>
struct list_item {
using type = cons<head, typename list_item<tail...>::type>;
};
template<class head>
struct list_item<head> {
using type = cons<head, null>;
};
template<>
struct list_item<null> {
using type = null;
};
為了list和cons巴拉巴拉的真正統(tǒng)一
template<class T, class ...tail> using list = typename list_item<T, tail...>::type;
從此以后所有對list的操作應該都寫稱對cons巴拉巴體的操作。
二.對鏈表的操作
四大函數(shù)
- 查找鏈表中的某個值： find_list
- 拷貝鏈表從start到end：copy_list
- 改變鏈表中的某個值:：change_list
- 合并兩個鏈表：append
每個函數(shù)我們定義它給出的結果是result（是一個類型）魂挂，實際上這個result會給出新的鏈表甫题，原來的鏈表是不會被改變的。
考慮到后面兩個可能會基于第一個涂召，那么必然是先寫第一個了坠非。
查找鏈表中的第n個，到底怎么查呢果正？
別急炎码，我們先模擬一下：比如我們要查找list<555,666,777,888>的第1個 666(第0個是55)
find<1, list<555,666,777,888>>那就是相當于 find<0, list<666,777,888>>, 0是固定找鏈表的第一個的（給出car就行）那么這樣一來遞歸公式就找到了:
find<n, list> = find<n-1, list::cdr>;
template<int n, class _list> //_list傳入諸如cons<num<1>, cons<num<2>, null>>
struct find_list {
using result = typename find_list<n - 1, typename _list::cdr>::result;
};
template<class head>
struct find_list<0, list_item<head>> {
using result = typename list_item<head>::car;
};
template<class _list>
struct find_list<0, _list> {
using result = typename _list::car;
};
那么copy自然是會利用到find的。還是一樣秋泳，思考原來的例子 list<555,666,777,888>全copy該怎么實現(xiàn)呢
之前說了潦闲，result會丟出一個cons的結構體，那么這里必然要用到cons了
copy<0, 2, list<555,666,777,888>> = cons<555迫皱，copy<1, 2, list<666,777,888>>>
copy<1, 2, list<666,777,888> = cons<666, copy<2, 2, list<666,777,888>>
copy<2, 2, list<777,888> = cons<777, null> //這里該是null了
答案呼之欲出
template<int start, int end, class _list>
struct copy_list {
using result = cons<typename find_list<start, _list>::result,
typename copy_list<start, end - 1, typename _list::cdr>::result>;
};
template<int start, class _list>
struct copy_list<start, start, _list> {
using result = cons<typename find_list<start, _list>::result, null>;
append一樣需要用到cons歉闰，
倒不如直接思考傳入的是cons的情景：
cons<1, cons<2, null>>想合并 cons<3, cons<4, null>>
想一下發(fā)現(xiàn)，list<1,2,3,4>其實就是把cons<1, cons<2, null>>中的null 替換為cons<3, cons<4, null>>
不過這個替換并不容易卓起。再想一下又發(fā)現(xiàn)和敬，在cons<3, cons<4, null>>前面包一個數(shù)據(jù)變成
cons<2 , cons<3, cons<4, null>>也不錯，但是實際上從cons<1, cons<2, null>>拆出最里面的也不這么好做
那么只能暴力一點了戏阅，直接全拆昼弟，先拆第一個cons體，再拆第二個
遞歸體：
append<cons<1, cons<2, null>>, cons<3, cons<4, null>>>------結果是|=>null
append< cons<2, null>, cons<3, cons<4, null>>>--------------結果是|=>cons<1, null>
append<null , cons<3, cons<4, null>>>-----------------------結果是|=>cons<1, cons<2, null>>
append<null , cons<4, null>>--------------------------------結果是|=>cons<1, cons<2, cons<3,null>>>
append<null , null>>----------------------------------------結果是|=>cons<1, cons<2, cons<3, cons<4, null>>>>
template<class cons1, class cons2>
struct append {
using result = cons<typename cons1::car,
typename append<typename cons1::cdr, cons2>::result>;
};
template<class cons2>
struct append<null, cons2> {
using result = cons<typename cons2::car,
typename append<null, typename cons2::cdr>::result>;
};
template<>
struct append<null, null> {
using result = null;
};
change就寫的比較惡心了奕筐，當時遇到了訪問過界出錯舱痘，于是生造了一個if結構蚕键。
首先change<2, 3, list<555,666,777,888>>給出result為list<555,666,3,888>
怎么change呢，先是copy從0到1衰粹，包裝3這個數(shù), 然后copy從3到length-1，再把這三個東西組合一下（append）
但是實際上change要分三類笆怠，上述所說是change非0非length-1的情況铝耻。
change<0 , 某個數(shù) ,list>也簡單，但是change<length-1, 某個數(shù) ,list> 必然要提前判斷傳入的index是不是length -1蹬刷，如果是瓢捉，那么給出的結果是cons<某個數(shù), null>
遞歸體不再贅述……
template<int index, int val, class _list>
struct change_list {
template<bool cond, int index, int length, class _list>
struct if_need_null {};
template<int index, int length, class _list>
struct if_need_null<true, index, length, _list> { using type = null; };
template<int index, int length, class _list>
struct if_need_null<false, index, length, _list> {
using type = typename copy_list<index + 1, length - 1, _list>::result;
};
using result = typename append<typename copy_list<0, index - 1, _list>::result,
cons<num<val>,
typename if_need_null<index == _list::length - 1,
index,
_list::length,
_list>::type>>::result;
};
template<int val, class _list>
struct change_list<0, val, _list> {
using result = typename append<null,
cons<num<val>, typename copy_list<1, _list::length - 1, _list>::result>>::result;
};
