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