C++基礎入門之模板堆排序(上):模板上的list的創(chuàng)造與操作

整段源碼鏈接
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;
};

C++基礎入門之模板堆排序(下):堆排序——簡單的翻譯

最后編輯于
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市办成,隨后出現(xiàn)的幾起案子泡态,更是在濱河造成了極大的恐慌,老刑警劉巖迂卢,帶你破解...
    沈念sama閱讀 217,084評論 6 503
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件某弦,死亡現(xiàn)場離奇詭異,居然都是意外死亡而克,警方通過查閱死者的電腦和手機靶壮,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,623評論 3 392
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來员萍,“玉大人腾降,你說我怎么就攤上這事∷橐铮” “怎么了螃壤?”我有些...
    開封第一講書人閱讀 163,450評論 0 353
  • 文/不壞的土叔 我叫張陵,是天一觀的道長筋帖。 經(jīng)常有香客問我奸晴,道長,這世上最難降的妖魔是什么幕随? 我笑而不...
    開封第一講書人閱讀 58,322評論 1 293
  • 正文 為了忘掉前任蚁滋,我火速辦了婚禮,結果婚禮上赘淮,老公的妹妹穿的比我還像新娘辕录。我一直安慰自己,他們只是感情好梢卸,可當我...
    茶點故事閱讀 67,370評論 6 390
  • 文/花漫 我一把揭開白布走诞。 她就那樣靜靜地躺著,像睡著了一般蛤高。 火紅的嫁衣襯著肌膚如雪蚣旱。 梳的紋絲不亂的頭發(fā)上碑幅,一...
    開封第一講書人閱讀 51,274評論 1 300
  • 那天,我揣著相機與錄音塞绿,去河邊找鬼沟涨。 笑死,一個胖子當著我的面吹牛异吻,可吹牛的內容都是我干的裹赴。 我是一名探鬼主播,決...
    沈念sama閱讀 40,126評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼诀浪,長吁一口氣:“原來是場噩夢啊……” “哼棋返!你這毒婦竟也來了?” 一聲冷哼從身側響起雷猪,我...
    開封第一講書人閱讀 38,980評論 0 275
  • 序言:老撾萬榮一對情侶失蹤睛竣,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后求摇,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體射沟,經(jīng)...
    沈念sama閱讀 45,414評論 1 313
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 37,599評論 3 334
  • 正文 我和宋清朗相戀三年月帝,在試婚紗的時候發(fā)現(xiàn)自己被綠了躏惋。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 39,773評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡嚷辅,死狀恐怖簿姨,靈堂內的尸體忽然破棺而出,到底是詐尸還是另有隱情簸搞,我是刑警寧澤扁位,帶...
    沈念sama閱讀 35,470評論 5 344
  • 正文 年R本政府宣布,位于F島的核電站趁俊,受9級特大地震影響域仇,放射性物質發(fā)生泄漏。R本人自食惡果不足惜寺擂,卻給世界環(huán)境...
    茶點故事閱讀 41,080評論 3 327
  • 文/蒙蒙 一暇务、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧怔软,春花似錦垦细、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,713評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至家坎,卻和暖如春嘱能,著一層夾襖步出監(jiān)牢的瞬間吝梅,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,852評論 1 269
  • 我被黑心中介騙來泰國打工惹骂, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留苏携,地道東北人。 一個月前我還...
    沈念sama閱讀 47,865評論 2 370
  • 正文 我出身青樓对粪,卻偏偏與公主長得像兜叨,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子衩侥,可洞房花燭夜當晚...
    茶點故事閱讀 44,689評論 2 354

推薦閱讀更多精彩內容