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

模板、编译期、排序算法，这三个词放在一起，最容易劝退一拨人。我第一次看到“编译期冒泡排序”的时候，心里想的就是“这玩意图啥”，后来做类型列表相关的项目，发现不少需求根本绕不开它，才花了一晚上把它啃下来。编译期排序算法是 C++ 模板元编程里一个很有意思的切面，它的输入不是运行时的数组，而是模板参数里的一组元素，输出是一个已经排好序的新的类型列表。整个过程由编译器在模板展开阶段完成，最终编译产物里连一个运行时排序指令都不会出现。这篇文章我就把自己的实现套路和踩过的坑全盘托出，从动机讲起，用编译期冒泡排序和编译期快速排序两个实现把整条思路串起来，适合有基本 C++ 模板使用经验、想搞懂编译期计算的读者。哪怕你以前完全没碰过模板元编程，照着代码敲一遍也能搞清楚里面的门道。

1. 为什么要把排序算法放进编译期

1.1 编译期常量的刚需

运行时排序谁都会写，把排序挪到编译期听起来更像炫技。但我做过的项目里，确实遇到过必须这样干的场景。典型的例子是：程序里有一堆编译期常量表，比如技能配置、按键映射、错误码对照表，这些表在编译期就已经完全确定，运行时根本不会变化。如果每次启动进程都重新排序一次，纯属浪费。把排序挪到编译期，运行时拿到的就是一张已经排好的表，启动路径上能省下一截实实在在的时间。对嵌入式这种资源敏感的场景，省掉排序代码和数据搬移，收益还要更明显。

另一个场景更隐蔽但也更常见：在模板元编程内部，经常需要把一组类型按某种规则排好。比如从一个模板参数包里挑出“体积最小的几个类型”，或者把一组整型常量按大小组织成编译期查找表。这时候你手里没有运行时的 vector，也没有循环，只有一堆类型。掌握了编译期排序，这些需求就能直接在类型层面用算法解决，不需要把类型先转换成运行时数据再排序，省掉一层不必要的折腾。

1.2 编译期排序和运行时、constexpr 排序差在哪

这里得把概念说透。运行时排序就是数据放进数组，调用std::sort，程序执行到那一步才开始比较和交换，最后数组里才是排好的顺序。编译期排序不同，它发生在编译器解析模板的阶段，通过模板递归展开完成比较与重排，最后产出一个新的类型列表。如果把这个类型列表再转换成运行时的std::array，数组里的顺序已经是最终结果，运行时什么也不用做。

和 constexpr 排序的差别更值得讲清楚。C++14 之后 constexpr 函数里能写循环了，C++20 更是允许 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 {};

这里的Int<3>就代表数字 3，TypeList<Int<3>, Int<1>, Int<2>>相当于编译期版本的数组{3, 1, 2}。为什么非要包一层？如果你只需要一组整数，其实可以直接定义template <int...> struct IntList {};，模板参数包里直接存 int，更干脆。但只要排序的目标不是 int 而是自定义类型，非类型模板参数就不够用了，所以用类型包装更通用。后面给出的所有工具函数也都可以直接套用到任意类型上，只需要把比较的规则改一下。

更标准的写法是直接用std::integral_constant<int, V>，连自定义 Int 都省掉。我在文章里保留自定义的Int，就是为了演示原理。实际项目里，除非你需要给类型附加额外行为，否则用std::integral_constant就够了，毕竟库里已经帮你写好了value和operator()，跟模板代码配合起来也少一些自定义陷阱。

2.2 编译期“循环”的本质是模板递归

编译期没有循环，所以在模板元编程里想把一件事重复做下去，核心只有一招：递归。每递归一次，就是一次新的模板展开，编译器会为每一组不同的模板实参生成对应的特化实例。本质上，编译器在你编译代码的时候就替你“跑”了一遍程序，只不过跑的路径是你用模板特化和偏特化画出来的。

拿一个最基础的例子说明，比如求类型列表长度：

template <typename List> struct Length; template <typename... Ts> struct Length<TypeList<Ts...>> { static constexpr std::size_t value = sizeof...(Ts); };

这里没有递归，直接利用模板参数包的sizeof...就能得到长度。但冒泡排序这种需要多轮重复操作的算法，依靠的就是真正的递归展开：一个模板每一步调用自己，但实参比上一步更接近终止条件。每一步展开都会在编译器中留下一个实例，递归的“深度”就是编译器实际生成的嵌套类型层数。所以你在设计模板递归时，脑子里要有一根弦：这不是运行时能靠栈回溯的问题，一旦递归不收敛，编译器会直接报“模板实例化深度超过最大值”，那场面相当难看。

2.3 提前准备好小工具

排序算法看起来复杂，其实底层只需要几个基础操作：在列表头部插入、在列表尾部追加、拼接两个列表、求长度。这些工具函数与运行时容器的接口一一对应，只是全部落到类型层面。我平时会先把它们写好，再动排序，调试起来思路更清爽。

template <typename T, typename List> struct Prepend; template <typename T, typename... Ts> struct Prepend<T, TypeList<Ts...>> { using type = TypeList<T, Ts...>; }; template <typename T, typename List> struct PushBack; template <typename T, typename... Ts> struct PushBack<T, TypeList<Ts...>> { using type = TypeList<Ts..., T>; }; template <typename L, typename R> struct Concat; template <typename... Ts, typename... Us> struct Concat<TypeList<Ts...>, TypeList<Us...>> { using type = TypeList<Ts..., Us...>; };

注意Prepend和PushBack在处理空列表时都能正确工作，因为TypeList<>展开后会把 T 放到唯一的位置。Concat用来合并两个列表时，不需要递归，因为两个参数包可以直接展开进同一个模板参数列表。有了这三个工具，后面排序里的“把元素拎出来再塞回去”就都能拼出来。

3. 手写一个编译期冒泡排序

3.1 一趟冒泡怎么用模板表达

冒泡排序最核心的动作是“从左往右扫描，遇到逆序的相邻元素就交换，一趟结束后最大的元素一定到最右边”。在编译期把这个动作翻译成模板，我是这样处理的：每一趟递归，比较列表头和第二个元素；如果需要交换，就把较小的元素放到结果头部，较大的元素继续参与剩余部分的扫描。

直接看BubblePass的实现：

template <typename List> struct BubblePass; template <typename T> struct BubblePass<TypeList<T>> { using type = TypeList<T>; }; template <typename T, typename U, typename... Rest> struct BubblePass<TypeList<T, U, Rest...>> { private: static constexpr bool needSwap = (T::value > U::value); using smaller = std::conditional_t<needSwap, U, T>; using larger = std::conditional_t<needSwap, T, U>; using tail = typename BubblePass<TypeList<larger, Rest...>>::type; public: using type = typename Prepend<smaller, tail>::type; };

第一次看到这段代码的人很容易卡在tail那一步。我解释一下：当 T 和 U 需要交换时，smaller 是 U，larger 是 T，然后把 larger 和剩下的Rest...继续交给下一层BubblePass处理，最后把 smaller 放到整体结果的前面。这样设计的目的，是让“比较大的元素”持续向右传递，而不是做完一次交换就停。比如对TypeList<Int<3>, Int<1>, Int<2>>做一趟：

• 第一层比较 3 和 1，交换后 smaller 是 1，larger 是 3，继续处理TypeList<3, 2>；
• 第二层比较 3 和 2，交换后 smaller 是 2，larger 是 3，递归终止，得到TypeList<3>；
• 回溯拼接，最终得到TypeList<1, 2, 3>。

一趟结束，最大的 3 已经沉到最右边。这就是冒泡排序里“一趟扫描”的编译期版本。

3.2 用计数循环控制排序趟数

一趟冒泡只能保证最大的元素到位，完整排序需要重复操作。运行时可以用for循环控制趟数，模板里只能用专门的“重复”模板。我定义了一个RepeatPass，第一个参数是待处理的列表，第二个参数是剩余趟数：

template <typename List, int Times> struct RepeatPass; template <typename List> struct RepeatPass<List, 0> { using type = List; }; template <typename List, int Times> struct RepeatPass { private: using once = typename BubblePass<List>::type; public: using type = typename RepeatPass<once, Times - 1>::type; }; template <typename List> struct BubbleSort { static constexpr std::size_t n = Length<List>::value; using type = typename RepeatPass<List, static_cast<int>(n - 1)>::type; };

这里用偏特化处理Times == 0的终止条件，递归的主体每次执行完一趟BubblePass后趟数减一。n 个元素的冒泡排序理论上只需要最多 n-1 趟，所以我把趟数设定为n - 1。需要特别注意的是，我并没有做“这一趟有没有发生交换”的提前退出判断，因为模板偏特化做这种运行时判断非常麻烦，而且会引入大量额外的元编程代码。现实中如果遇到接近有序的数据，这种无脑重复所有趟数的方式会有不少无效扫描，但编译期你通常对数据规模有数，得不偿失。

空列表的情况也要防一下。如果对TypeList<>执行Length，n - 1会变成一个巨大的无符号数，转到int后是未定义行为。最稳妥的做法是给BubbleSort加一个空列表的偏特化，或者直接约定排序目标不能为空。我真实写代码时更喜欢加偏特化，因为模板代码本身已经很绕，没必要给自己埋一个隐蔽的坑。

3.3 验证结果不能靠打印

编译期算出来的类型列表没法直接打印，所以验证方式只有一个：用类型断言确认结果。C++11 之后可以用std::is_same，C++17 以后有了std::is_same_v，写起来更短。完整验证代码长这样：

static_assert( std::is_same_v< BubbleSort<TypeList<Int<3>, Int<1>, Int<2>>>::type, TypeList<Int<1>, Int<2>, Int<3>> >);

这个断言如果通过，编译器不会有任何输出；如果失败，错误信息里会清清楚楚列出两个类型不一致。我开发模板元编程工具时，每写完一个模块就扔一串static_assert上去，量大但省心，因为它会在编译阶段把所有逻辑问题暴露出来，不用等运行期。

如果确实需要在运行时用一个真正的数组把排序结果装起来，可以再写一个转换模板：

template <typename List> struct ToArray; template <typename... Ts> struct ToArray<TypeList<Ts...>> { static std::array<int, 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 QuickSort<TypeList<>> { using type = TypeList<>; };

这里注意，终止条件用的是“全特化”，也就是整个TypeList<>都匹配上了。全特化和偏特化在模板元编程里都是控制逻辑分支的关键手段，理解这两者的区别，是读编译期排序代码的基础。

4.2 用 Filter 做分区

快速排序需要一个把列表按规则分区成两个列表的工具，我习惯叫它Filter。它接收一个类型列表和一个谓词模板，把满足条件的元素保留下来：

template <typename List, template <typename> class Pred> struct Filter; template <template <typename> class Pred> struct Filter<TypeList<>, Pred> { using type = TypeList<>; }; template <typename T, typename... Rest, template <typename> class Pred> struct Filter<TypeList<T, Rest...>, Pred> { private: using tail = typename Filter<TypeList<Rest...>, Pred>::type; public: using type = std::conditional_t< Pred<T>::value, typename Prepend<T, tail>::type, tail>; };

Pred<T>::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 QuickSort<TypeList<>> { using type = TypeList<>; }; template <typename T, typename... Rest> struct QuickSort<TypeList<T, 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 QuickSort<typename Filter<TypeList<Rest...>, LessOrEqual>::type>::type; using rightSorted = typename QuickSort<typename Filter<TypeList<Rest...>, Greater>::type>::type; using leftAndPivot = typename PushBack<T, leftSorted>::type; public: using type = typename Concat<leftAndPivot, rightSorted>::type; };

执行过程我拆解一下。先把除了基准 T 之外的所有元素，分别按小于等于和大于两个谓词过滤，得到两个子列表。接着对调出的子列表递归排序。然后定义leftAndPivot，把基准 T 追加到左边排好序的结果后面，这一步相当于运行时快排里“将基准放到分区中间”的动作。最后把左边结果和右边结果拼起来，整个排序完成。

这里有个细节值得说明：因为LessOrEqual包含了等于基准的元素，所以等于基准的元素都会被分到左边，不会出现左右两边都包含同一个基准值的重复问题。也有人习惯把小于和大于等于分开，不影响正确性，只是分区策略不同。我实测下来，把等于丢左边更省事，因为PushBack<T, 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-depth=2048（GCC 选项）或者-ftemplate-depth=2048对面 Clang 也认，MSVC 则用/constexpr:depth之类的参数。另一个方向是优化算法，让递归深度更低。比如快速排序可以改成三路分区，或者用循环递归混合的策略，把深度从 n 压到 log n。第三个方向是彻底绕开模板元编程，改用 C++20 的 constexpr 排序，递归深度交给标准库内部处理，你只需要保证 constexpr 求值能在编译期完成。

5.3 这些工具库能少写一半代码

如果你只是为了项目需要，而不是为了研究模板递归原理，完全可以站在巨人的肩膀上。Boost.Hana 提供了非常完整的编译期容器和算法，其中hana::sort可以直接对编译期序列排序，底层早已把各种极端情况处理好。std::integral_constant、std::tuple和 C++17 的if constexpr组合起来，也能写出比传统特化更易读的编译期代码。比如用if constexpr写Filter，就和写普通函数几乎一样流畅：

template <typename T, typename... Rest, template <typename> class Pred> struct Filter<TypeList<T, Rest...>, Pred> { using tail = typename Filter<TypeList<Rest...>, Pred>::type; static constexpr bool keep = Pred<T>::value; using type = std::conditional_t<keep, typename Prepend<T, tail>::type, tail>; };

不过，用现成库和自己实现一遍并不冲突。我到现在还会时不时手写一遍编译期快排，不是为了效率，而是为了保持对模板递归和特化机制的敏感度。真在业务里需要排序逻辑，我反而会先看 Boost.Hana 合不合用。

5.4 经验速查：该不该用编译期排序

我做了个项目总结，直接帮你判断什么时候该用编译期排序，什么时候该绕道：

在现实的项目里，编译期排序算法的调试成本远高于运行期算法，你不会想在每次编译都重复等待模板展开的。我把编译期排序当成一种思维方式训练，平时更多是用 Boost.Hana 或 constexpr 来解决问题。但一旦哪天你接到一个“必须把类型列表排好序”的需求，书里、网上那些零散的模板知识会立刻汇成你脑子里的主线，因为排序算法是你把模板递归、偏特化和参数包放到同一个棋盘上操练的最佳题目。

最后再分享一个小技巧。如果你第一次写这类代码，别一上来就挑战快速排序。先用BubblePass把“一趟扫描”跑通，用static_assert验证几个边界样例，再去尝试泛化成分区工具。模板元编程的所有复杂度都来自递归状态的管理，先把小步走稳，后面的路会顺很多。