C++编译期排序：用模板元编程把排序放进编译器

模板、编译期、排序算法这三个词放在一起最容易劝退一拨人。我第一次看到“编译期冒泡排序”的时候心里想的就是“这玩意图啥”后来做类型列表相关的项目发现不少需求根本绕不开它才花了一晚上把它啃下来。编译期排序算法是 C 模板元编程里一个很有意思的切面它的输入不是运行时的数组而是模板参数里的一组元素输出是一个已经排好序的新的类型列表。整个过程由编译器在模板展开阶段完成最终编译产物里连一个运行时排序指令都不会出现。这篇文章我就把自己的实现套路和踩过的坑全盘托出从动机讲起用编译期冒泡排序和编译期快速排序两个实现把整条思路串起来适合有基本 C 模板使用经验、想搞懂编译期计算的读者。哪怕你以前完全没碰过模板元编程照着代码敲一遍也能搞清楚里面的门道。1. 为什么要把排序算法放进编译期1.1 编译期常量的刚需运行时排序谁都会写把排序挪到编译期听起来更像炫技。但我做过的项目里确实遇到过必须这样干的场景。典型的例子是程序里有一堆编译期常量表比如技能配置、按键映射、错误码对照表这些表在编译期就已经完全确定运行时根本不会变化。如果每次启动进程都重新排序一次纯属浪费。把排序挪到编译期运行时拿到的就是一张已经排好的表启动路径上能省下一截实实在在的时间。对嵌入式这种资源敏感的场景省掉排序代码和数据搬移收益还要更明显。另一个场景更隐蔽但也更常见在模板元编程内部经常需要把一组类型按某种规则排好。比如从一个模板参数包里挑出“体积最小的几个类型”或者把一组整型常量按大小组织成编译期查找表。这时候你手里没有运行时的 vector也没有循环只有一堆类型。掌握了编译期排序这些需求就能直接在类型层面用算法解决不需要把类型先转换成运行时数据再排序省掉一层不必要的折腾。1.2 编译期排序和运行时、constexpr 排序差在哪这里得把概念说透。运行时排序就是数据放进数组调用std::sort程序执行到那一步才开始比较和交换最后数组里才是排好的顺序。编译期排序不同它发生在编译器解析模板的阶段通过模板递归展开完成比较与重排最后产出一个新的类型列表。如果把这个类型列表再转换成运行时的std::array数组里的顺序已经是最终结果运行时什么也不用做。和 constexpr 排序的差别更值得讲清楚。C14 之后 constexpr 函数里能写循环了C20 更是允许 constexpr 分配内存所以用 constexpr 函数完全可以在编译期把一个std::array排好序。那模板元编程里的编译期排序还有没有价值有而且不可替代。constexpr 只能处理值没法直接对“类型列表”做选择、拼接和递归展开。当你要排序的是类型而不是值或者排序结果还要继续参与模板推导模板元编程依然是唯一的选择。说白了值层面的编译期排序用 constexpr 更舒服类型层面的编译期排序只能靠模板。2. 先把数组搬进类型系统2.1 类型化的数字Int 与 TypeList模板的推导过程只会跟“类型”打交道所以第一步就是把要排序的数据从“值”变“类型”。最简单的做法是写一个包装器只存一个静态常量template int V struct Int { static constexpr int value V; }; template typename... Ts struct TypeList {};这里的Int3就代表数字 3TypeListInt3, Int1, Int2相当于编译期版本的数组{3, 1, 2}。为什么非要包一层如果你只需要一组整数其实可以直接定义template int... struct IntList {};模板参数包里直接存 int更干脆。但只要排序的目标不是 int 而是自定义类型非类型模板参数就不够用了所以用类型包装更通用。后面给出的所有工具函数也都可以直接套用到任意类型上只需要把比较的规则改一下。更标准的写法是直接用std::integral_constantint, V连自定义 Int 都省掉。我在文章里保留自定义的Int就是为了演示原理。实际项目里除非你需要给类型附加额外行为否则用std::integral_constant就够了毕竟库里已经帮你写好了value和operator()跟模板代码配合起来也少一些自定义陷阱。2.2 编译期“循环”的本质是模板递归编译期没有循环所以在模板元编程里想把一件事重复做下去核心只有一招递归。每递归一次就是一次新的模板展开编译器会为每一组不同的模板实参生成对应的特化实例。本质上编译器在你编译代码的时候就替你“跑”了一遍程序只不过跑的路径是你用模板特化和偏特化画出来的。拿一个最基础的例子说明比如求类型列表长度template typename List struct Length; template typename... Ts struct LengthTypeListTs... { static constexpr std::size_t value sizeof...(Ts); };这里没有递归直接利用模板参数包的sizeof...就能得到长度。但冒泡排序这种需要多轮重复操作的算法依靠的就是真正的递归展开一个模板每一步调用自己但实参比上一步更接近终止条件。每一步展开都会在编译器中留下一个实例递归的“深度”就是编译器实际生成的嵌套类型层数。所以你在设计模板递归时脑子里要有一根弦这不是运行时能靠栈回溯的问题一旦递归不收敛编译器会直接报“模板实例化深度超过最大值”那场面相当难看。2.3 提前准备好小工具排序算法看起来复杂其实底层只需要几个基础操作在列表头部插入、在列表尾部追加、拼接两个列表、求长度。这些工具函数与运行时容器的接口一一对应只是全部落到类型层面。我平时会先把它们写好再动排序调试起来思路更清爽。template typename T, typename List struct Prepend; template typename T, typename... Ts struct PrependT, TypeListTs... { using type TypeListT, Ts...; }; template typename T, typename List struct PushBack; template typename T, typename... Ts struct PushBackT, TypeListTs... { using type TypeListTs..., T; }; template typename L, typename R struct Concat; template typename... Ts, typename... Us struct ConcatTypeListTs..., TypeListUs... { using type TypeListTs..., Us...; };注意Prepend和PushBack在处理空列表时都能正确工作因为TypeList展开后会把 T 放到唯一的位置。Concat用来合并两个列表时不需要递归因为两个参数包可以直接展开进同一个模板参数列表。有了这三个工具后面排序里的“把元素拎出来再塞回去”就都能拼出来。3. 手写一个编译期冒泡排序3.1 一趟冒泡怎么用模板表达冒泡排序最核心的动作是“从左往右扫描遇到逆序的相邻元素就交换一趟结束后最大的元素一定到最右边”。在编译期把这个动作翻译成模板我是这样处理的每一趟递归比较列表头和第二个元素如果需要交换就把较小的元素放到结果头部较大的元素继续参与剩余部分的扫描。直接看BubblePass的实现template typename List struct BubblePass; template typename T struct BubblePassTypeListT { using type TypeListT; }; template typename T, typename U, typename... Rest struct BubblePassTypeListT, U, Rest... { private: static constexpr bool needSwap (T::value U::value); using smaller std::conditional_tneedSwap, U, T; using larger std::conditional_tneedSwap, T, U; using tail typename BubblePassTypeListlarger, Rest...::type; public: using type typename Prependsmaller, tail::type; };第一次看到这段代码的人很容易卡在tail那一步。我解释一下当 T 和 U 需要交换时smaller 是 Ularger 是 T然后把 larger 和剩下的Rest...继续交给下一层BubblePass处理最后把 smaller 放到整体结果的前面。这样设计的目的是让“比较大的元素”持续向右传递而不是做完一次交换就停。比如对TypeListInt3, Int1, Int2做一趟第一层比较 3 和 1交换后 smaller 是 1larger 是 3继续处理TypeList3, 2第二层比较 3 和 2交换后 smaller 是 2larger 是 3递归终止得到TypeList3回溯拼接最终得到TypeList1, 2, 3。一趟结束最大的 3 已经沉到最右边。这就是冒泡排序里“一趟扫描”的编译期版本。3.2 用计数循环控制排序趟数一趟冒泡只能保证最大的元素到位完整排序需要重复操作。运行时可以用for循环控制趟数模板里只能用专门的“重复”模板。我定义了一个RepeatPass第一个参数是待处理的列表第二个参数是剩余趟数template typename List, int Times struct RepeatPass; template typename List struct RepeatPassList, 0 { using type List; }; template typename List, int Times struct RepeatPass { private: using once typename BubblePassList::type; public: using type typename RepeatPassonce, Times - 1::type; }; template typename List struct BubbleSort { static constexpr std::size_t n LengthList::value; using type typename RepeatPassList, static_castint(n - 1)::type; };这里用偏特化处理Times 0的终止条件递归的主体每次执行完一趟BubblePass后趟数减一。n 个元素的冒泡排序理论上只需要最多 n-1 趟所以我把趟数设定为n - 1。需要特别注意的是我并没有做“这一趟有没有发生交换”的提前退出判断因为模板偏特化做这种运行时判断非常麻烦而且会引入大量额外的元编程代码。现实中如果遇到接近有序的数据这种无脑重复所有趟数的方式会有不少无效扫描但编译期你通常对数据规模有数得不偿失。空列表的情况也要防一下。如果对TypeList执行Lengthn - 1会变成一个巨大的无符号数转到int后是未定义行为。最稳妥的做法是给BubbleSort加一个空列表的偏特化或者直接约定排序目标不能为空。我真实写代码时更喜欢加偏特化因为模板代码本身已经很绕没必要给自己埋一个隐蔽的坑。3.3 验证结果不能靠打印编译期算出来的类型列表没法直接打印所以验证方式只有一个用类型断言确认结果。C11 之后可以用std::is_sameC17 以后有了std::is_same_v写起来更短。完整验证代码长这样static_assert( std::is_same_v BubbleSortTypeListInt3, Int1, Int2::type, TypeListInt1, Int2, Int3 );这个断言如果通过编译器不会有任何输出如果失败错误信息里会清清楚楚列出两个类型不一致。我开发模板元编程工具时每写完一个模块就扔一串static_assert上去量大但省心因为它会在编译阶段把所有逻辑问题暴露出来不用等运行期。如果确实需要在运行时用一个真正的数组把排序结果装起来可以再写一个转换模板template typename List struct ToArray; template typename... Ts struct ToArrayTypeListTs... { static std::arrayint, sizeof...(Ts) value() { return {{Ts::value...}}; } };这样排序后的类型列表直接被展开成初始化列表数组元素顺序就是编译期排序的结果。这个数组可以直接参与运行期业务逻辑因为它已经是排好序的后面不用再做任何比较操作。3.4 这套写法有哪些坑编译期冒泡排序最大的坑不是代码写不出来而是写完之后编译器资源被无情消耗。BubblePass每一层递归都会生成一个新的实例一趟扫描处理 n 个元素就会展开大约 n 层外层再把整趟重复 n 次总体实例化数量是 O(n²) 级别。这个复杂度和运行时冒泡排序是一样的但代价从“CPU 时间”变成了“编译器内存和编译时间”。我试过用上面这个实现排序 64 个随机整数结果 GCC 差点把内存吃光。所以我的原则很简单编译期排序只适合小规模数据一般控制在 16 到 32 个元素以内比较舒服。一旦排 64 个以上就得换更优的算法比如接下来要写的快速排序或者干脆重新评估需求看看是不是真的需要在编译期把这件事做掉。另外模板递归里的typename不能丢。取某个模板的::type时如果不加typename编译器会直接报错。第一次用模板元编程的人通常会被这个错误卡得怀疑人生但其实原因非常简单::type是一个依赖类型C 编译器必须看到typename才能知道它是类型而不是静态成员。4. 再进一步编译期快速排序4.1 分治思想映射到模板特化快速排序的核心是分治选一个基准值把小于等于基准的放左边大于基准的放右边然后对左右两边递归排序。这个逻辑翻译成模板反而比冒泡排序更直接因为它天然就是“分解成子问题再合并”的递归结构和模板递归的思维方式完全吻合。递归终止条件用空列表特化即可template typename List struct QuickSort; template struct QuickSortTypeList { using type TypeList; };这里注意终止条件用的是“全特化”也就是整个TypeList都匹配上了。全特化和偏特化在模板元编程里都是控制逻辑分支的关键手段理解这两者的区别是读编译期排序代码的基础。4.2 用 Filter 做分区快速排序需要一个把列表按规则分区成两个列表的工具我习惯叫它Filter。它接收一个类型列表和一个谓词模板把满足条件的元素保留下来template typename List, template typename class Pred struct Filter; template template typename class Pred struct FilterTypeList, Pred { using type TypeList; }; template typename T, typename... Rest, template typename class Pred struct FilterTypeListT, Rest..., Pred { private: using tail typename FilterTypeListRest..., Pred::type; public: using type std::conditional_t PredT::value, typename PrependT, tail::type, tail; };PredT::value就是谓词的判断结果。满足条件时把 T 放进结果列表的前面不满足就直接跳过。这里用了std::conditional_t做类型选择它是元编程里的三目运算符专门用来在编译期从两个类型里挑一个。用Filter配合两个谓词就能完成快速排序的分区动作谓词一U::value T::value小于等于基准谓词二U::value T::value大于基准。注意谓词定义在QuickSort内部这样它可以访问当前基准值 T。模板元编程里这种“在类模板内部再定义局部模板”的写法非常常见能让你把和某个具体对象相关的状态封装在局部作用域里。4.3 QuickSort 的完整实现全套代码是这样拼起来的template typename List struct QuickSort; template struct QuickSortTypeList { using type TypeList; }; template typename T, typename... Rest struct QuickSortTypeListT, Rest... { private: template typename U struct LessOrEqual { static constexpr bool value (U::value T::value); }; template typename U struct Greater { static constexpr bool value (U::value T::value); }; using leftSorted typename QuickSorttypename FilterTypeListRest..., LessOrEqual::type::type; using rightSorted typename QuickSorttypename FilterTypeListRest..., Greater::type::type; using leftAndPivot typename PushBackT, leftSorted::type; public: using type typename ConcatleftAndPivot, rightSorted::type; };执行过程我拆解一下。先把除了基准 T 之外的所有元素分别按小于等于和大于两个谓词过滤得到两个子列表。接着对调出的子列表递归排序。然后定义leftAndPivot把基准 T 追加到左边排好序的结果后面这一步相当于运行时快排里“将基准放到分区中间”的动作。最后把左边结果和右边结果拼起来整个排序完成。这里有个细节值得说明因为LessOrEqual包含了等于基准的元素所以等于基准的元素都会被分到左边不会出现左右两边都包含同一个基准值的重复问题。也有人习惯把小于和大于等于分开不影响正确性只是分区策略不同。我实测下来把等于丢左边更省事因为PushBackT, leftSorted时不需要担心 pivot 已经在 leftSorted 里反正主键就是 T。4.4 编译期快排的开销从哪来快速排序在实例化数量上比冒泡好得多平均是 O(n log n)。以我自己的测试为例编译期排序 32 个元素时GCC 几乎察觉不到变化冒泡排序同样规模已经开始明显变慢。但如果输入本身接近逆序快速排序会退化到 O(n²)编译期的递归深度也会相应增加这时体验甚至比冒泡还难受。还有一个隐藏开销来自Filter。每递归一层就要对当前子列表完整扫描一遍也就是在QuickSort里调用两次Filter扫描所有剩余元素。虽然时间复杂度在平均意义下是 O(n log n)但这个常数不小。如果元素数量到 100 以上用模板元编程做快速排序仍然会让编译时间明显拉长。我的建议是超过 64 个元素就不要再考虑模板元编程了直接换成 constexpr 函数或者运行期排序都更理智。5. 常见问题与排查技巧5.1 错误信息长到怀疑人生模板元编程的编译错误是所有 C 报错里最让人头疼的因为编译器会把一长串实例化堆栈全部贴出来。第一次写编译期排序时我对着报错里几十行“in instantiation of template class”看了半天才发现问题只是少了一个typename。排查这种问题我的经验是先看最底层的报错而不是开头那一段。“错误从哪个特化里起源”往往才是真正的根因。看到no type named type in ...基本就是特化匹配失败说明某个模板的结构和你预期不一致。把报错逐层往上翻找到第一个出现问题的被实例化特化通常就能定位到具体的模板定义。实在看不懂的时候我会把代码拆小把QuickSort里的几个using逐步注释掉一次只留一个用二分法定位是哪一步崩了。土办法但极有效。5.2 递归深度超限怎么办编译期递归不是无限深的编译器有默认的模板实例化深度限制。GCC 默认只允许 900 层Clang 是 1024 层。写快速排序时如果数据规模稍大很容易撞上这个上限。报错一般是template instantiation depth exceeds maximum of 900之类。解决方案有三个方向。最直接的是增大编译器限制GCC 和 Clang 都支持-ftemplate-depth2048GCC 选项或者-ftemplate-depth2048对面 Clang 也认MSVC 则用/constexpr:depth之类的参数。另一个方向是优化算法让递归深度更低。比如快速排序可以改成三路分区或者用循环递归混合的策略把深度从 n 压到 log n。第三个方向是彻底绕开模板元编程改用 C20 的 constexpr 排序递归深度交给标准库内部处理你只需要保证 constexpr 求值能在编译期完成。5.3 这些工具库能少写一半代码如果你只是为了项目需要而不是为了研究模板递归原理完全可以站在巨人的肩膀上。Boost.Hana 提供了非常完整的编译期容器和算法其中hana::sort可以直接对编译期序列排序底层早已把各种极端情况处理好。std::integral_constant、std::tuple和 C17 的if constexpr组合起来也能写出比传统特化更易读的编译期代码。比如用if constexpr写Filter就和写普通函数几乎一样流畅template typename T, typename... Rest, template typename class Pred struct FilterTypeListT, Rest..., Pred { using tail typename FilterTypeListRest..., Pred::type; static constexpr bool keep PredT::value; using type std::conditional_tkeep, typename PrependT, tail::type, tail; };不过用现成库和自己实现一遍并不冲突。我到现在还会时不时手写一遍编译期快排不是为了效率而是为了保持对模板递归和特化机制的敏感度。真在业务里需要排序逻辑我反而会先看 Boost.Hana 合不合用。5.4 经验速查该不该用编译期排序我做了个项目总结直接帮你判断什么时候该用编译期排序什么时候该绕道场景推荐方案原因排序对象是类型排序结果要参与模板推导模板元编程constexpr 无法直接处理类型列表排序对象是少量整数常量想要零运行时开销编译期排序 或 constexpr 排序数据量小编译器压力可接受排序规模超过 64 个元素constexpr 函数或运行时排序模板实例化开销太大编译时间不可控排序结果希望直接生成只读查找表constexpr 排序后转std::arrayC20 后的 constexpr 更简单直接在现实的项目里编译期排序算法的调试成本远高于运行期算法你不会想在每次编译都重复等待模板展开的。我把编译期排序当成一种思维方式训练平时更多是用 Boost.Hana 或 constexpr 来解决问题。但一旦哪天你接到一个“必须把类型列表排好序”的需求书里、网上那些零散的模板知识会立刻汇成你脑子里的主线因为排序算法是你把模板递归、偏特化和参数包放到同一个棋盘上操练的最佳题目。最后再分享一个小技巧。如果你第一次写这类代码别一上来就挑战快速排序。先用BubblePass把“一趟扫描”跑通用static_assert验证几个边界样例再去尝试泛化成分区工具。模板元编程的所有复杂度都来自递归状态的管理先把小步走稳后面的路会顺很多。