最近我在維護(hù)一個(gè)內(nèi)部通信框架時(shí)遇到了一個(gè)很實(shí)際的問題事件回調(diào)的注冊(cè)表需要在啟動(dòng)前把所有處理器按優(yōu)先級(jí)排好而“優(yōu)先級(jí)”來自類型的固有屬性。如果放在運(yùn)行時(shí)排序每次啟動(dòng)都要多跑一段循環(huán)還要忍受動(dòng)態(tài)分配和額外的依賴如果寫死順序每加一個(gè)類型就得手改一坨代碼。最后我把目光放到了模板編譯期排序算法上——它能讓編譯器在編譯現(xiàn)場(chǎng)把類型列表排好編出來的程序直接帶著一個(gè)已經(jīng)定序的清單進(jìn)入運(yùn)行階段。這篇文章想聊的就是這件事什么是編譯期排序我需要排序時(shí)如何用模板寫出穩(wěn)定可用的算法以及編譯期排序在真實(shí)項(xiàng)目里該不該用、怎么用。內(nèi)容適合正在接觸模板元編程的人也適合那些已經(jīng)會(huì)在 C11/14/17 里寫點(diǎn) traits但沒真正把“類型作為數(shù)據(jù)”玩起來的讀者。1. 為什么要把排序搬進(jìn)編譯器1.1 一個(gè)真正出現(xiàn)過的場(chǎng)景我之前維護(hù)過一個(gè)模擬的“消息分發(fā)中樞”消息類型有一百多種每種類型帶一個(gè)優(yōu)先級(jí)標(biāo)簽。我需要做一張表把類型按優(yōu)先級(jí)從高到低排好讓分發(fā)函數(shù)按這個(gè)順序去匹配處理器。優(yōu)先級(jí)是編譯期就能確定的只是當(dāng)時(shí)的工程里沒人把這個(gè)順序編譯出來所有人都在運(yùn)行時(shí)通過std::sort排序一個(gè)“類型指紋 優(yōu)先級(jí)”的數(shù)組。這套做法的問題不在排序本身而在“順序”是運(yùn)行期才產(chǎn)生的。數(shù)據(jù)要放進(jìn)內(nèi)存排序要執(zhí)行比較函數(shù)初始化路徑上會(huì)多出一層對(duì)象構(gòu)造和函數(shù)調(diào)用如果這個(gè)模塊會(huì)被頻繁地動(dòng)態(tài)加載那每次加載都要重新算一遍。更難受的是按優(yōu)先級(jí)排好的順序本來是整個(gè)模塊穩(wěn)定性的基礎(chǔ)你卻不希望在運(yùn)行時(shí)有任何機(jī)會(huì)發(fā)生變化。于是我把“類型列表”抽象出來一個(gè)TypeListint, string, char然后在編譯期調(diào)用某個(gè)排序模板得到一個(gè)排好序的TypeList。整個(gè)過程沒有任何循環(huán)在運(yùn)行期執(zhí)行也沒有任何對(duì)象被構(gòu)造。最終生成的分發(fā)表只需要按這個(gè)類型清單從上往下展開即可。1.2 編譯期排序和運(yùn)行期排序的分界線很多人一聽到“編譯期排序”就會(huì)想到 CPU 指令和算法復(fù)雜度。實(shí)際上在模板元編程里復(fù)雜度度量的是“模板實(shí)例化的次數(shù)”和“模板遞歸的深度”而不是納秒或毫秒。比如插入排序的遞歸深度大致等于元素?cái)?shù)量而實(shí)例化數(shù)量大概是 O(n2)歸并排序深度是 O(log n)但模板數(shù)量和符號(hào)數(shù)量會(huì)顯著增加。選擇算法時(shí)要考慮的因素和運(yùn)行期排序完全不同不是為了省幾個(gè)時(shí)鐘周期而是為了控制編譯器的負(fù)擔(dān)和編譯失敗的概率。所以一句話總結(jié)如果你排序的是運(yùn)行時(shí)才產(chǎn)生的值用運(yùn)行期排序如果你排序的是類型本身或者類型的固有屬性并且這個(gè)順序不需要在運(yùn)行時(shí)改變那就可以考慮編譯期排序。C20 出現(xiàn)后還有第三種做法用 constexpr 函數(shù)在編譯期給一組整數(shù)或std::array排序再把結(jié)果喂給模板。這條路線我放到后面單開一節(jié)聊。2. TypeList 與排序謂詞編譯期算法的兩塊地基2.1 用變參模板定義類型列表模板元編程里最重要的數(shù)據(jù)結(jié)構(gòu)不是數(shù)組不是 vector而是一個(gè)可以含任意數(shù)量類型的“類型列表”。最簡(jiǎn)單的形式是#include cstddef template typename... Ts struct TypeList { static constexpr size_t size sizeof...(Ts); };它看起來像一個(gè)空殼但排序算法正是在這個(gè)空殼里堆積模板特化。你用TypeListint, char, long表示一個(gè)三個(gè)元素的序列編譯器在處理這個(gè)類型時(shí)其實(shí)已經(jīng)把三個(gè)類型打包進(jìn)了一個(gè)包parameter pack。元編程排序要做的就是把這個(gè)包重新排列成另一個(gè)包最終再實(shí)例化出一個(gè)新的TypeList。C 元編程里類型列表往往不是最終目的而是中間手段。它的價(jià)值在于你可以在編譯期遍歷它、過濾它、排序它然后用它去生成函數(shù)表、注冊(cè)表、組合類型序列等。而排序就是這種處理中最常見的一步。2.2 排序標(biāo)準(zhǔn)不能只靠sizeof運(yùn)行期排序的標(biāo)準(zhǔn)是“比較函數(shù)”編譯期排序的標(biāo)準(zhǔn)是“元函數(shù)”。最常見的寫法是像std::less一樣定義一個(gè)模板類型template typename T struct Rank; template struct Rankchar { static constexpr int value 1; }; template struct Rankshort { static constexpr int value 2; }; template struct Rankint { static constexpr int value 3; }; template struct Ranklong { static constexpr int value 4; }; template typename A, typename B struct RankLess { static constexpr bool value (RankA::value RankB::value); };我的一個(gè)建議是不要直接用sizeof(A) sizeof(B)作為默認(rèn)比較標(biāo)準(zhǔn)因?yàn)轭愋痛笮≡诓煌脚_(tái)上并不穩(wěn)定而且很多類型會(huì)有相同的大小。如果你排序的是“概念上的優(yōu)先級(jí)”最好的方式就是定義顯式的Rank數(shù)值。這樣既穩(wěn)定又讓意圖直接出現(xiàn)在代碼里。如果將來要調(diào)整某個(gè)類型的優(yōu)先級(jí)也只需改一個(gè)特化。2.3 把“遞歸”當(dāng)循環(huán)來理解模板元編程中幾乎一切操作都由“特化 遞歸”完成。我習(xí)慣這樣思考一個(gè)算法處理TypeListHead, Tail...時(shí)先對(duì)Tail...遞歸調(diào)用同樣結(jié)構(gòu)的模板拿到一個(gè)中間結(jié)果再和Head組合。這非常像一個(gè)函數(shù)式程序里對(duì)列表做 fold 或者 map 的操作。就排序而言你可以用遞歸把問題拆成“排序一個(gè)更小的列表”“插入一個(gè)元素”“合并兩段有序列表”這樣基礎(chǔ)的操作。這也是后面我實(shí)現(xiàn)插入排序時(shí)用的思路不是直接照搬運(yùn)行期for循環(huán)而是把一個(gè)元素遞歸地塞到已經(jīng)排好的列表里。3. 從零實(shí)現(xiàn)編譯期插入排序3.1 整體思路把頭部插到排好序的尾部插入排序在運(yùn)行期非常好理解從第二個(gè)元素開始每次把當(dāng)前元素插入到前面已經(jīng)有序的序列里。模板元編程版也是一樣的只不過“序列”是TypeList“插入”是一個(gè)模板特化。我先定義一個(gè)Prepend用來把一個(gè)類型放到列表頭部template typename T, typename List struct Prepend; template typename T, typename... Ts struct PrependT, TypeListTs... { using type TypeListT, Ts...; };然后定義Insert把一個(gè)值插入到一個(gè)已經(jīng)有序的TypeList中template typename List, typename Value, template typename, typename class Cmp struct Insert; template typename Value, template typename, typename class Cmp struct InsertTypeList, Value, Cmp { using type TypeListValue; }; template typename Head, typename... Tail, typename Value, template typename, typename class Cmp struct InsertTypeListHead, Tail..., Value, Cmp { using tail_insert typename InsertTypeListTail..., Value, Cmp::type; using type std::conditional_t CmpValue, Head::value, TypeListValue, Head, Tail..., typename PrependHead, tail_insert::type ; };這里的核心分支是如果Value應(yīng)該排在Head前面就直接把Value放到整個(gè)有序列表頭部否則讓Value去和后面的Tail...繼續(xù)比較然后把Head接到結(jié)果前面。這樣遞歸地跑下去最終得到一個(gè)完全有序的新列表。3.2 Sort 模板本身遞歸吃掉一個(gè)元素有了Insert之后排序外殼幾乎可以直接“抄”下來template typename List, template typename, typename class Cmp struct Sort; template template typename, typename class Cmp struct SortTypeList, Cmp { using type TypeList; }; template typename Head, typename... Tail, template typename, typename class Cmp struct SortTypeListHead, Tail..., Cmp { using sorted_tail typename SortTypeListTail..., Cmp::type; using type typename Insertsorted_tail, Head, Cmp::type; };你可能會(huì)問我為什么不是“把后面的元素插入到前面的有序前綴中”其實(shí)兩種方向都行。這里選擇“先排好尾巴再把頭插進(jìn)去”是函數(shù)式列表處理中最順手的寫法頭永遠(yuǎn)是單個(gè)元素尾是遞歸入口。寫成這樣之后語義很清晰SortTypeListHead, Tail... InsertSortTail..., Head。3.3 驗(yàn)證排序結(jié)果模板寫出來不代表它真的對(duì)最好用靜態(tài)斷言把小樣例釘死在代碼里。我習(xí)慣加一段這樣的測(cè)試using input_list TypeListlong, int, char, short; using sorted_list Sortinput_list, RankLess::type; static_assert(std::is_samesorted_list, TypeListchar, short, int, long::value, RankLess should sort by Rank value);這段代碼能編譯通過說明long、int、char、short在編譯期被正確重排為char short int long。遇到順序不穩(wěn)定或者謂詞寫反的時(shí)候靜態(tài)斷言會(huì)直接告訴你“sort failed”不用等到運(yùn)行期。3.4 插入排序?yàn)槭裁粗贿m合小集合我實(shí)際用的規(guī)則是類型數(shù)量在 32 以內(nèi)插入排序非常舒服超過 64就要開始盯編譯時(shí)間了超過兩三百通常我會(huì)考慮別的方法或者改用庫。原因不是算法本身錯(cuò)了而是每插入一個(gè)新元素都可能觸發(fā)一批新的std::conditional_t實(shí)例化數(shù)量近似 O(n2)。當(dāng) n 到幾百實(shí)例化數(shù)量就是幾萬甚至幾十萬編譯器會(huì)變得非常吃力。插入排序的優(yōu)點(diǎn)在于實(shí)現(xiàn)短、思路簡(jiǎn)單、不容易寫錯(cuò)。在小規(guī)模類型列表上它幾乎總是一個(gè)足夠好的選擇。如果你列表里的類型數(shù)量真的很大那就應(yīng)該正視歸并排序或快速排序這類分治算法了。4. 歸并排序與快速排序模板能搬多重的排序4.1 二路歸并在編譯期的代價(jià)歸并排序在運(yùn)行期幾乎是穩(wěn)定高效的代名詞但在模板元編程里它并不顯得優(yōu)雅。拆成兩半需要按索引把TypeList切開這一步在參數(shù)包里并不直接通常要先實(shí)現(xiàn)類似Take和Drop的元函數(shù)然后遞歸排序左右兩段最后再實(shí)現(xiàn)Merge把兩個(gè)有序TypeList按謂詞合并。模板代碼大致會(huì)長(zhǎng)得像這樣TakeN, List取出列表前 N 個(gè)類型生成一個(gè)新的TypeListDropN, List去掉列表前 N 個(gè)類型返回剩余部分MergeListA, ListB, Cmp比較兩個(gè)列表頭把頭部較小的那一個(gè)并入結(jié)果繼續(xù)合并剩余部分SortND...遞歸調(diào)用Sort于左右兩半然后再M(fèi)erge功能是可以實(shí)現(xiàn)的但代碼量幾乎是指數(shù)級(jí)增長(zhǎng)。而且有兩個(gè)特別需要注意的點(diǎn)其一遞歸深度雖然只有 O(log n)但每一次遞歸都會(huì)同時(shí)展開左右兩個(gè)分支編譯器要維護(hù)的“實(shí)例化?！逼鋵?shí)不止一個(gè)維度其二因?yàn)樵幊虥]有真正的運(yùn)行時(shí)函數(shù)調(diào)用歸并中有些本可以“共用的中間結(jié)果”在模板實(shí)例化層面會(huì)被重復(fù)生成導(dǎo)致編譯器符號(hào)數(shù)量暴漲。4.2 快速排序基準(zhǔn)點(diǎn)和篩選快速排序的元編程版也更像“篩選 拼接”而不是常規(guī)意義上的“原地交換”。你選取一個(gè)基準(zhǔn)類型 pivot然后把剩余類型分成兩組一組是“比 pivot 小”的一組是“比 pivot 大”的再遞歸排序這兩組最后拼成Less pivot Greater。模板里沒有一個(gè)可以直接復(fù)用的“分區(qū)”循環(huán)通常還是要寫遞歸去遍歷整個(gè)列表。而且基準(zhǔn)點(diǎn)如果選得不好例如總是取第一個(gè)元素而輸入恰好是接近有序的列表那么快排會(huì)退化成 O(n2)模板實(shí)例化數(shù)量也會(huì)跟著惡化。在運(yùn)行期我們可以隨機(jī)選基準(zhǔn)點(diǎn)來規(guī)避最壞情況可在編譯期隨機(jī)不是個(gè)自然概念。因此元編程快排完全不比歸并更“快”它只是思路更貼近常見教科書寫起來同樣繁瑣。4.3 三種算法的復(fù)雜度對(duì)照我把三者的關(guān)鍵特性整理成了一張表方便你在設(shè)計(jì)時(shí)快速判斷算法模板遞歸深度實(shí)例化數(shù)量級(jí)對(duì)輸入順序的敏感度實(shí)現(xiàn)難度插入排序O(n)O(n2)低很低歸并排序O(log n)O(n log n) 但常數(shù)大低較高快速排序平均 O(log n)最壞 O(n)平均 O(n log n) 但基準(zhǔn)選擇影響大高高我的經(jīng)驗(yàn)是在模板元編程里除非你面對(duì)的是幾百上千個(gè)類型否則沒有必要為了“更優(yōu)復(fù)雜度”去忍受更長(zhǎng)的代碼和更難查的編譯錯(cuò)誤。插入排序?qū)懗鰜?20 行歸并排序可能要寫一百行而收益卻要等類型列表足夠大時(shí)才能體現(xiàn)出來。這個(gè)權(quán)衡和運(yùn)行期是不一樣的編譯器編譯模板的過程不會(huì)像 CPU 執(zhí)行指令那樣“流水線化”每多一層實(shí)例化都可能是實(shí)打?qū)嵉木幾g秒數(shù)。5. 實(shí)例化深度、編譯時(shí)間和“災(zāi)難性”錯(cuò)誤消息5.1 繞不開的-ftemplate-depth一旦你開始遞歸這些模板你很快就會(huì)遇到一個(gè)經(jīng)典錯(cuò)誤template instantiation depth exceeds maximum of 900。GCC 和 Clang 默認(rèn)模板遞歸深度大約是 900插入排序?qū)σ粋€(gè) 900 個(gè)類型的列表排序時(shí)光遞歸深度就觸頂了。你可以用-ftemplate-depth2048或者更高把它抬上去但這只是把限制往后推不是消除問題。我在實(shí)際項(xiàng)目里見過有人為了排 1000 個(gè)類型把深度直接調(diào)到 10000結(jié)果編譯內(nèi)存漲了幾 GB單次編譯動(dòng)輒幾分鐘。更理智的做法是如果列表在幾百以內(nèi)優(yōu)先考慮用庫或者 C20 constexpr 方案如果不能換方案就通過顯式分桶把一個(gè)大列表拆成多個(gè)小列表再進(jìn)行排序或者讓遞歸深度保持在線性范圍但減少每個(gè)遞歸層里產(chǎn)生的嵌套模板數(shù)量5.2 實(shí)例化數(shù)量與編譯器內(nèi)存模板遞歸深度只是“棧有多深”真正讓編譯變慢的是“總共生成了多少個(gè)類模板實(shí)例”。插入排序的實(shí)例化數(shù)量大概相當(dāng)于 n2/2 量級(jí)因?yàn)槊坎迦胍粋€(gè)新元素它都要和已排序列表里的元素逐個(gè)比較。一個(gè) 500 個(gè)類型的列表在最壞情況下會(huì)有十幾萬個(gè)類的符號(hào)被編譯器記住。這不是運(yùn)行時(shí)的std::sort每多一個(gè)符號(hào)IDE、靜態(tài)分析工具和鏈接器都會(huì)受到影響。所以元編程排序里真正要優(yōu)化的指標(biāo)不是比較次數(shù)而是“避免創(chuàng)建不必要的模板實(shí)例”。常見的優(yōu)化包括用using別名而不是用一個(gè)空殼結(jié)構(gòu)體去包裝中間結(jié)果把不需要對(duì)外暴露的特化寫進(jìn)私有細(xì)節(jié)命名空間盡量少用std::conditional_t一層套一層的方式組合結(jié)果因?yàn)樗矔?huì)遞歸實(shí)例化出很多內(nèi)部節(jié)點(diǎn)。5.3 把編譯錯(cuò)誤拆成可以理解的最小件編譯期排序最勸退人的一點(diǎn)是錯(cuò)誤信息能把一個(gè) 30 行的模板報(bào)出一整屏的實(shí)例化棧。我自己調(diào)試時(shí)只有一個(gè)心得把所有能拆的步驟都拆成獨(dú)立命名模板設(shè)置最小的測(cè)試輸入。比如先只測(cè)Insert再測(cè)Prepend最后才測(cè)整個(gè)Sort。不要讓編譯器一口氣展開三層遞歸。如果一段靜態(tài)斷言失敗我會(huì)在注釋里留下“當(dāng)前應(yīng)該得到什么類型”的說明然后一點(diǎn)一點(diǎn)縮短測(cè)試列表。很多時(shí)候錯(cuò)誤不在排序算法本身而是比較謂詞在某個(gè)類型上實(shí)例化失敗了比如Rank沒有對(duì)應(yīng)特化。把謂詞單獨(dú)拿出來用static_assert(RankLesschar, int::value)驗(yàn)證通常幾秒鐘就能發(fā)現(xiàn)問題。6. C20 的 constexpr 排序另一條編譯期排序路線6.1 一個(gè)可直接跑的 constexpr 插入排序C20 之后我越來越?？吹綀F(tuán)隊(duì)不再寫遞歸模板而是用 constexpr 函數(shù)在編譯期對(duì)值排序再驅(qū)動(dòng)類型重排。這更接近“編譯期算出來一個(gè)順序然后讓模板按順序拼裝”比直接在模板里處理參數(shù)包要直觀得多。最簡(jiǎn)單的示例是排序一個(gè)std::arrayint, N#include array #include cstddef template std::size_t N constexpr std::arrayint, N compile_time_sort(std::arrayint, N input) { for (std::size_t i 1; i N; i) { int key input[i]; std::size_t j i; while (j 0 input[j - 1] key) { input[j] input[j - 1]; --j; } input[j] key; } return input; } constexpr std::arrayint, 5 input{5, 3, 1, 4, 2}; static_assert(compile_time_sort(input)[0] 1);這段代碼很普通但它在編譯期完成不會(huì)生成任何運(yùn)行期代碼。你甚至可以把它變成constexpr std::arraystd::size_t, N order compute_order(...)然后利用...展開按order從std::tuple里取出對(duì)應(yīng)元素得到一個(gè)重新排序后的std::tuple或TypeList。6.2 用排序結(jié)果驅(qū)動(dòng)類型重排如果我要對(duì)一組類型按Rank排序運(yùn)行在 C20 下我會(huì)把類型的索引放進(jìn) constexpr 數(shù)組用一段普通的 constexpr 排序計(jì)算出索引順序再用std::index_sequence把該順序映射回類型template typename... Ts struct TypeList { }; template typename RankFunc, typename... Ts constexpr std::arraysize_t, sizeof...(Ts) sorted_rank_indices() { // 把 Ts... 對(duì)應(yīng)的 Rank 放進(jìn)數(shù)組用普通排序得到升序索引 } template std::size_t... I, typename List auto reorder_by_index(std::index_sequenceI..., List); // 最終把 TypeList... 按 constexpr 排序后的索引重新組裝起來。這種“值驅(qū)動(dòng)類型”的思路比直接在模板里寫歸并要容易理解得多但也不是沒有代價(jià)你需要同時(shí)維護(hù)“值側(cè)”和“類型側(cè)”兩套邏輯。而且constexpr 排序結(jié)果的靜態(tài)檢查能力有時(shí)候不如模板直接斷言強(qiáng)比如無法輕易在編譯期“遍歷”一個(gè)數(shù)組并逐個(gè)比較相鄰元素類型順序。不過對(duì)于大多數(shù)應(yīng)用場(chǎng)景它已經(jīng)綽綽有余。6.3 constexpr 方案與模板方案的取舍我現(xiàn)在的判斷標(biāo)準(zhǔn)大概是這樣的如果排序?qū)ο蟊旧砭褪穷愋颓乙獏⑴c模板重載、特化或生成類型列表優(yōu)先用模板元編程排序因?yàn)榻Y(jié)果直接就是類型。如果排序?qū)ο笫强捎成錇橹档膶傩员热鐑?yōu)先級(jí)、大小、字母序索引并且后面主要用索引去tuple或數(shù)組取數(shù)據(jù)那 constexpr 方案更省事編譯速度也更快。如果項(xiàng)目已經(jīng)用了 C17 甚至 C20大部分新代碼我都會(huì)嘗試用 constexpr 函數(shù)先算一個(gè)“順序”再手動(dòng)映射到類型因?yàn)橹辽馘e(cuò)誤信息好懂一大截。7. 生產(chǎn)里更省心的選擇與我的實(shí)踐建議7.1 直接使用現(xiàn)成庫Boost.MPL 與 Boost.Hana如果你在真實(shí)項(xiàng)目里并不想維護(hù)一套自己的元編程排序算法我的第一個(gè)建議永遠(yuǎn)是“先看看 Boost”。Boost.MPL 里有mpl::sort可以在類型序列上排序只是它基于較老的 MPL 世界觀接口相對(duì)生澀。Boost.Hana 是更現(xiàn)代化的編譯期算法庫它提供了hana::sort可以排序 tuple-like 結(jié)構(gòu)直接表達(dá)“編譯期排序”的意圖。舉個(gè)例子如果項(xiàng)目能接受 Boost我的排序代碼往往就是一兩行#include boost/hana.hpp namespace hana boost::hana; using my_tuple decltype(hana::sort(hana::make_tuple( hana::type_clong, hana::type_cchar, hana::type_cint )));它的輸出也是一個(gè) tuple-like 編譯期容器你可以繼續(xù)用hana::integral_constant等機(jī)制取元素。好處是庫作者已經(jīng)處理了各種枯燥的邊緣情況壞處是模板實(shí)例化深度和編譯時(shí)間一樣會(huì)體現(xiàn)在你的構(gòu)建系統(tǒng)里。但站在工程角度用現(xiàn)成方案永遠(yuǎn)比自己造一個(gè)半成品更穩(wěn)。7.2 真實(shí)可用的編譯期排序需求我在實(shí)際項(xiàng)目中接觸到的編譯期排序需求通常不是“純粹為了好玩”而是這類場(chǎng)景事件/回調(diào)注冊(cè)表按優(yōu)先級(jí)把類型順序固定進(jìn)編譯期產(chǎn)物運(yùn)行時(shí)不排序反射與序列化需要穩(wěn)定輸出字段順序避免不同的編譯器或平臺(tái)產(chǎn)生不可預(yù)期順序數(shù)據(jù)庫表行裝配按類型映射到列索引再用編譯期排序索引生成訪問代碼動(dòng)態(tài)多態(tài)替代類型列表排序后再逐一生成if constexpr或者策略類組合這些場(chǎng)景有個(gè)共同特點(diǎn)一旦順序被編譯期確定整個(gè)模塊的行為就會(huì)變得可預(yù)測(cè)也能被編譯器和優(yōu)化器更徹底地內(nèi)聯(lián)。我很少在項(xiàng)目里處理超過幾十個(gè)類型的排序但如果真的遇到上千個(gè)類型我一定會(huì)選擇 C20 constexpr 方案或 Boost.Hana而不會(huì)自己手搓一個(gè)深度上千的歸并。7.3 判斷要不要自己寫排序模板最后聊聊我的個(gè)人判斷標(biāo)準(zhǔn)。如果一個(gè)團(tuán)隊(duì)里沒有幾個(gè)人熟悉模板元編程我通常不建議自己寫排序模板因?yàn)榇a一旦進(jìn)入深水區(qū)后續(xù)維護(hù)成本會(huì)非常高。比較好的做法是先確定排序數(shù)據(jù)到底在“類型側(cè)”還是“值側(cè)”再?zèng)Q定用庫、用 constexpr還是用自制模板。我自己在實(shí)踐中最大的體會(huì)是編譯期排序算法最有價(jià)值的產(chǎn)出往往不是“讓編譯更快”而是“讓順序在被編譯之后就固定下來”不再依賴初始化上下文也不再被運(yùn)行時(shí)環(huán)境影響。模板元編程里的插入、歸并、快排本質(zhì)上是在幫編譯器建立一個(gè)關(guān)于類型順序的“事實(shí)數(shù)據(jù)庫”。當(dāng)你需要把類型列表轉(zhuǎn)換成一組可索引的策略、一張穩(wěn)定的函數(shù)表、或一段可預(yù)測(cè)的反射元數(shù)據(jù)時(shí)這個(gè)事實(shí)數(shù)據(jù)庫能幫你省掉大量運(yùn)行時(shí)防御性代碼。如果非要給一條直接可用的建議小列表用插入排序模板中列表用 Boost.Hana 或 constexpr 方案大列表先把數(shù)據(jù)轉(zhuǎn)化為索引序列再排序千萬不要在模板遞歸深度上逞強(qiáng)。這個(gè)順序我踩過幾次坑之后才確定下來也是我目前覺得最省心的做法。