C++模板入門

函數(shù)模板

C++可以重載函數(shù)，即可以定義多個函數(shù)名相同但是參數(shù)不同的函數(shù)，使用時編譯器會自動選擇。

我們可以定義兩個分別計算 float?和 int?類型的相加的函數(shù)：

注意定義的浮點字面量后面沒有?f?的話是默認(rèn)為 double 類型。

問題出現(xiàn)了，如果我們想要其它類型也能使用?add 這個函數(shù)呢，或者要兩個不同類型（如?int?和?float）相加呢？每增加一個類型就需要寫一遍函數(shù)，太費程序員鍵盤了。

我們可以定義一個函數(shù)模板來解決這個問題：

在函數(shù)定義上面一行加上 template?關(guān)鍵字，尖括號里的 typename?表示定義的模板是一種類型，T1?是程序員自己定義的標(biāo)識符，稱為模板參數(shù)，代表了一個類型，T2?同理，后面就可以使用這個類型了，T1 a?表示 a?是?T1?類型的，T1?具體是哪個類型是調(diào)用這個 add 函數(shù)的時候確定的。比如 main 函數(shù)里的第一個調(diào)用，T1 是?int ，T2?是?double，確定模板參數(shù)的過程叫實例化。

學(xué)了模板就明白剛?cè)腴T寫的 ”hello?world“?原來也是有學(xué)問的，cin?和?cout?用的 >>?和 <<?也是模板函數(shù)，所以能處理各種類型的數(shù)據(jù)。

返回值類型是 auto ，這也是由編譯器自動推斷返回類型，C++14的特性，編譯時注意使用C++14以上標(biāo)準(zhǔn)，如 g++?編譯時的命令：

除了用模板定義類型，還可以定義數(shù)據(jù)：

N?是模板參數(shù)，它是一個 int?類型的數(shù)，這個函數(shù)在調(diào)用時編譯器就沒法推斷了，我們需要指定 N?是多少，調(diào)用處的函數(shù)名后面尖括號填入模板參數(shù) 100?，這個函數(shù)實現(xiàn)的是控制臺打印 0 - 99 。

模板類

我們定義類的時候可以使用模板，模板類使用得較多，STL?當(dāng)中定義了豐富的模板類。

我們可以定義一個模板類，可以存儲任意類型，只有一個成員函數(shù)，就是把存儲的數(shù)據(jù)打印出來：

模板類本身是一個類型，使用時需要把模板參數(shù)加上，模板參數(shù)也可以是數(shù)據(jù)，而且類成員函數(shù)也可以是模板函數(shù)。

特化和偏特化

特化是指定特定的模板參數(shù)對應(yīng)的函數(shù)體，有點抽象，請看代碼：

這段程序會先輸出一句 "specialization"，再打印 0 - 99。

語法就是 template<>，尖括號里不寫東西，下一行是是函數(shù)定義，函數(shù)名后面的尖括號寫要特化的模板參數(shù)，調(diào)用的時候用到這個模板時就會調(diào)用你新定義的那個函數(shù)。模板類的特化就是類名后面寫特化的參數(shù)了。

偏特化是只對部分模板參數(shù)特化，只有模板類支持，模板函數(shù)不支持：

我們用構(gòu)造函數(shù)檢驗?zāi)０鍏?shù)，這段程序會輸出 1 - 6，再打印 "specialization"。

只要其中一個模板參數(shù)符合你偏特化的情況，那無論其它模板參數(shù)是什么，都會選擇特化的那個定義。

上面只演示了模板參數(shù)是數(shù)值的情況，模板參數(shù)是類型其實也是類似的。

總結(jié)

所謂模板，是定義一個模子，填入不同的模板參數(shù)會生成不同的函數(shù)（類），gcc 和?msvc?等編譯器就會針對不同的特化生成不同的匯編代碼，所以特化越多，生成的代碼體積越大。

上面的知識對C++復(fù)雜的模板系統(tǒng)來說只是很小一部分，我自己也太菜了，只能介紹這么多了。

前置芝士先到這里，下面點題。

利用模板進(jìn)行循環(huán)展開

模板遞歸計算階乘

以下內(nèi)容應(yīng)該不是語言層面的，但 gcc，msvc 等編譯器應(yīng)該適用。

上面提到模板的實例化是由編譯器完成的，也就是在編譯期所有特化的函數(shù)內(nèi)部匯編，什么意思呢，我們實現(xiàn)一個階乘計算函數(shù)：

它會遞歸地實例化 factorial<5>?到 factorial<0>，factorial<0>?是特化的返回 1，則到這里就停止了。

用模板遞歸代替循環(huán)

上面的階乘實際上已經(jīng)實現(xiàn)了類似循環(huán)的效果，利用遞歸的思想，我們設(shè)計一個函數(shù)從? 0 打印到?N?：

函數(shù)會打印 0-100。

和階乘類似，改變調(diào)用時的模板參數(shù)可以改變循環(huán)上界，改變模板特化的值可以改變循環(huán)下界。

現(xiàn)在的問題是，模板函數(shù)遞歸好像和普通遞歸一樣，但根據(jù)生成的匯編來看，只不過生成了很多的函數(shù)依次調(diào)用，并沒有降低函數(shù)調(diào)用開銷（存在push、pop和ret等語句說明在調(diào)用函數(shù)），也就無法實現(xiàn)優(yōu)化。但是當(dāng)我們開-O2及以上優(yōu)化呢？

我們發(fā)現(xiàn)和函數(shù)調(diào)用有關(guān)的語句幾乎沒有了，這些代碼大家都可以自己去測試一下。

運行時改變參數(shù)

前面的代碼的模板參數(shù)都是在編譯期定好的，現(xiàn)在要我們從控制臺輸入一個 n，打印 0 到 n?要如何做到呢？我們可以定義一個選擇函數(shù) print_it ，用?switch?或者?if?語句判斷：

但是又是個費鍵盤的活，所以我們讓 print_it?使用模板遞歸：

這里模板參數(shù)也用了默認(rèn)參數(shù) N = 0 ，也就是說不填模板參數(shù)時，N 默認(rèn)為?0，再特化一個上限（因為?gcc?允許的模板遞歸層數(shù)為 900），當(dāng)然，現(xiàn)在的問題是它似乎又回到了普通的遞歸，所以建議主體函數(shù)（在這里就是?print?函數(shù)）體執(zhí)行時間較長使用這個方法，否則 switch 可能會更快。

性能實測

直接貼?洛谷P1919 測試結(jié)果，使用模板遞歸的 FFT 性能接近第一名 NTT+AVX2 優(yōu)化，而我沒有對其進(jìn)行任何手動的 simd 優(yōu)化，可讀性較好。

后面可能會更新這個?FFT?的實現(xiàn)細(xì)節(jié)，或者?FFT?從最基礎(chǔ)開始優(yōu)化的個人歷程。透露一下，基于這個 FFT 設(shè)計的高精度乘法，在編譯器開啟自動 AVX 優(yōu)化后的性能可以接近甚至超過GMP?庫！