去年年底我在重构一个内部RPC分发层时碰到一件很拧巴的事消息处理器有十几种每种在编译期就能确定优先级我却不能在运行期慢慢排序。手写函数指针数组之后更头疼数组里的顺序只能靠人肉维护再加一种类型就乱一次。当时脑子里冒出的方案是C模板元编程把处理器对应的C类型塞进类型列表在编译期按某个优先级特征排序最后展开成一张静态分派表。这篇文章就是那段时间把编译期排序算法从查资料到逐一实现、再到落地的全过程。如果你也在跟类型列表、模板特化、编译期常量较劲这篇可以直接拿来当抄作业的底稿。模板编译期排序不是一个炫技名词它解决的是“在代码还没有跑起来之前就把顺序确定下来”的问题。后面我会从类型列表的基本心智模型讲起给出一套可运行的插入排序模板再聊快排和归并在模板世界里的思路最后对比现代C里constexpr方案并把我踩过的几个坑一并倒出来。1. 为什么要在编译期排序先搞清楚你买的是什么1.1 排序对象不是“数组”而是“类型列表”运行期的std::sort作用在内存容器上排序过程交换的是对象的值。编译期没有“对象”只有类型和编译期常量。如果要对一堆C类型排序比如TypeListFastHandler, SlowHandler, MediumHandler这堆类型本身并不占据任何运行期内存它只是模板实例化时一个个“类型参数”的组合。要对这种组合排序就不能指望std::sort的迭代器模型必须自己用模板递归做“不可变列表”操作。换个角度理解把模板参数包typename... Ts当成一个编译期数组把每次排序的结果当成一个新的TypeList。这个新列表不会被复用也不会被原地修改因为模板元编程世界里根本没有“内存”和“指针”只有“类型”和“递归”。这个心智模型非常像函数式语言里的不可变链表只是存储单元从整数变成了类型。1.2 排序的直接收益和隐藏成本我选择编译期排序最直接的收益有三个运行期零开销排序在编译期完成生成的分派表天然有序运行时只要按顺序线性扫描或查表。结果确定同样的输入类型只要比较器严格且确定排序结果在任何平台、任何编译器下都一致不会出现“同一堆handler, 我这边快那边慢”的诡异问题。可组合排序依据可以来自类型traits、优先级元函数、依赖关系甚至多个条件的组合这些逻辑都属于编译期纯函数。成本也不能装看不见编译时间明显变长每排一个元素都会多一组模板实例化排几十个类型可能让单文件编译从秒级变成十秒级。模板实例化爆炸排序算法复杂度不只看比较次数还要看递归展开时生成了多少中间类型。报错信息可读性差一个比较器写错GCC能把几百行模板实例化堆栈甩到你脸上。我用一张表把运行期排序和编译期排序的差异列清楚维度运行期std::sort模板编译期排序数据载体vector/array/deque等容器类型列表/整数序列排序时机程序运行时模板实例化阶段交换对象内存中的值类型参数列表时间开销运行期CPU周期编译期CPU周期调试手段断点、日志static_assert、模板实例化trace元素数量量级几千到几百万通常几个到几十个典型应用普通业务排序类型分派、代码生成、元函数计算可以看出来编译期排序注定不是拿来做大规模数据排序的它适合的是“少量、但必须在编译期完成”的顺序计算。2. 编译期列表的“容器”长什么样类型列表与模板递归的心智模型2.1 用模板参数包当数组用特化当迭代器准备模板编译期排序前先把容器操作做好。我用的容器是一个极简的TypeListtemplatetypename... Ts struct TypeList { static constexpr std::size_t size sizeof...(Ts); };这个结构看起来像空壳实际上模板参数包Ts...就是容器本体。你可以在特化中抓住参数包进行展开、连接、取头取尾本质上就是把“对容器的遍历”变成了“对特化模式的匹配”。迭代器在哪里模板元编程里迭代器就是“偏特化的递归步骤”。比如取头元素templatetypename List struct Head; templatetypename T, typename... Rest struct HeadTypeListT, Rest... { using type T; };Head专门匹配“至少一个元素”的列表并取出第一个类型。取尾列表则把TypeListT, Rest...匹配成TypeListRest...templatetypename List struct Tail; templatetypename T, typename... Rest struct TailTypeListT, Rest... { using type TypeListRest...; };这两个原语一个告诉你“当前元素是谁”一个告诉你“剩下还有谁”排序算法的每次递归都靠它们缩小问题规模。2.2 必须提前备齐的四个基础操作除了Head和Tail我建议把下面这几个元函数也先定义好后面排序和验证都会用到#include type_traits // 在列表头部插入一个类型 templatetypename List, typename T struct PushFront; templatetypename... Ts, typename T struct PushFrontTypeListTs..., T { using type TypeListT, Ts...; }; // 连接两个类型列表 templatetypename List1, typename List2 struct Concat; templatetypename... Ts, typename... Us struct ConcatTypeListTs..., TypeListUs... { using type TypeListTs..., Us...; }; // 从一个列表中筛选出满足条件P的类型 templatetemplatetypename class P, typename List struct Filter; templatetemplatetypename class P struct FilterP, TypeList { using type TypeList; }; templatetemplatetypename class P, typename T, typename... Rest struct FilterP, TypeListT, Rest... { using rest typename FilterP, TypeListRest...::type; using type typename std::conditionalPT::value, typename PushFrontrest, T::type, rest::type; };PushFront和Concat是排序结果拼接的“胶水”Filter则是快速排序里分区逻辑的基础。每定义一个原语我都会加一个static_assert测一遍确认行为符合预期再接上排排序比如static_assert(std::is_same_vtypename HeadTypeListint, double::type, int); static_assert(std::is_same_vtypename TailTypeListint, double::type, TypeListdouble); static_assert(std::is_same_vtypename ConcatTypeListint, TypeListdouble::type, TypeListint, double);这些测试看着土却是模板元编程项目里的命根子。类型层面的错误没有运行期堆栈只能靠一层层断言缩小范围。2.3 数值序列与类型列表两种编译期容器两套玩法我还经常用到另一种编译期容器那就是std::integer_sequence。它存储的是int, size_t这类编译期数值可以理解成“编译期整数数组”。它跟TypeList的核心区别是TypeList的元素是类型integer_sequence的元素是值。using Numbers std::integer_sequenceint, 5, 2, 4, 1, 3;对类型排序必须走TypeList那套递归模板对数值排序可以走constexpr函数也可以把它们转成TypeList再继续元编程。C17以后非类型模板参数也可以放进auto...里但类型列表的独立性更强因为同一个类型可以携带不同优先级、不同大小、不同tag信息这是整数序列单薄的int很难做到的。3. 手写一个可用的编译期插入排序从比较器到完整验证3.1 比较器的工程意义不要把“小于”写死在算法里模板排序和运行期排序一样也应该把“比较规则”从算法本身抽出来。在模板世界里常见做法是用“模板模板参数”把比较器当作类型传进去也就是传给算法一个templatetypename, typename class Less类型的模板。这样做的意义很大。同一个排序算法你可以按sizeof排序按自定义PriorityT::value排序甚至按两个条件的组合排序。排序算法只关心它能否从LessA, B::value拿到一个bool完全不关心这个bool是怎么算出来的。下面定义一个最直观的比较器按类型大小排序templatetypename A, typename B struct LessSize { static constexpr bool value (sizeof(A) sizeof(B)); };之后设计算法时默认比较器就用它。如果某个场景需要按优先级排序只需要换一个LessPriority排序模板一模一样。3.2 插入排序模板的完整拆解插入排序的思路和运行期一致一个空列表每次拿一个新元素按“小于”关系插入到已经排好序的列表里。模板版本的实现如下。先做“插入单个元素”的元函数templatetypename List, typename T, templatetypename, typename class Less struct Insert; templatetypename T, templatetypename, typename class Less struct InsertTypeList, T, Less { using type TypeListT; }; templatetypename T, typename Head, typename... Tail, templatetypename, typename class Less struct InsertTypeListHead, Tail..., T, Less { using type typename std::conditional LessT, Head::value, TypeListT, Head, Tail..., typename PushFronttypename InsertTypeListTail..., T, Less::type, Head::type ::type; };这个元函数做的判断是如果新元素T比当前列表头Head小就把T放到最前面一次插入完成。如果不小说明插入位置在后面于是把Head先放到结果前面继续在后面Tail...中递归插入。然后是排序主体templatetypename List, templatetypename, typename class Less LessSize struct InsertionSort; templatetemplatetypename, typename class Less struct InsertionSortTypeList, Less { using type TypeList; }; templatetypename T, typename... Rest, templatetypename, typename class Less struct InsertionSortTypeListT, Rest..., Less { using sorted_rest typename InsertionSortTypeListRest..., Less::type; using type typename Insertsorted_rest, T, Less::type; };递归过程就是先排序尾部Rest...再把当前元素T插入到排序后的尾部列表。把整个过程拆开看每次排序都会生成很多个新的临时类型但最终只有一个type指针指向结果。3.3 static_assert把排序结果钉在编译期写完元函数必须验证。我创建了几个大小递增的占位类型然后直接断言排序结果struct TagA { char c; }; // sizeof(1) struct TagB { short s; }; // sizeof(2) struct TagC { int i; }; // sizeof(4) struct TagD { double d; }; // sizeof(8) using Unsorted TypeListTagD, TagA, TagC, TagB; using Sorted typename InsertionSortUnsorted::type; static_assert(std::is_same_vSorted, TypeListTagA, TagB, TagC, TagD); static_assert(std::is_same_vtypename HeadSorted::type, TagA); static_assert(std::is_same_vtypename TailSorted::type, TypeListTagB, TagC, TagD);这个断言是在编译期执行的一旦排序逻辑有偏差编译器会直接告诉你“类型不匹配”而且很可能甩出几十层实例化记录。所以我建议每个模板元编程排序算法边上都常备一组类似的static_assert一旦后面要融合更多功能这些断言能守住旧行为。3.4 为什么我优先选插入排序而不是快排我之前好奇直接上快排不是更高级吗后来在模板元编程里试了一遍发现“高级”不等于“好用”。插入排序的优势在于模板实现最简单边界条件少。不额外生成大量分区临时列表对编译期内存压力小。元素个数通常在个位数到十几位O(n²)的运行期劣势完全体现不出来。我给自己定的经验法则是编译期要排序的类型少于20个无脑用插入排序。类型一多先重新审视设计——是不是把不该塞进类型表里的东西硬塞进去了如果确实要排很多再看快排或constexpr方案。4. 快排和归并排序的模板实现思路复杂度与实例化消耗的博弈4.1 快速排序用分区谓词甩掉“逐个插入”的笨重感快速排序在编译期完全能够实现思路也直接取第一个元素作为pivot把剩余列表分成“小于pivot”和“不小于pivot”两组递归排序两组后拼接。分区这一步可以用之前定义好的Filter或手写一个Partition特化。下面是我在项目中用的简化实现templatetypename Pivot, typename List, templatetypename, typename class Less struct Partition; templatetypename Pivot, templatetypename, typename class Less struct PartitionPivot, TypeList, Less { using left TypeList; using right TypeList; }; templatetypename Pivot, typename T, typename... Rest, templatetypename, typename class Less struct PartitionPivot, TypeListT, Rest..., Less { using rest PartitionPivot, TypeListRest..., Less; using left_if_true typename PushFronttypename rest::left, T::type; using right_if_false typename PushFronttypename rest::right, T::type; using left typename std::conditionalLessT, Pivot::value, left_if_true, typename rest::left::type; using right typename std::conditionalLessT, Pivot::value, typename rest::right, right_if_false::type; }; templatetypename List, templatetypename, typename class Less LessSize struct QuickSort; templatetemplatetypename, typename class Less struct QuickSortTypeList, Less { using type TypeList; }; templatetypename Pivot, typename... Rest, templatetypename, typename class Less struct QuickSortTypeListPivot, Rest..., Less { using partition PartitionPivot, TypeListRest..., Less; using left_sorted typename QuickSorttypename partition::left, Less::type; using right_sorted typename QuickSorttypename partition::right, Less::type; using type typename Concatleft_sorted, typename ConcatTypeListPivot, right_sorted::type::type; };注意点在于当某个元素和pivot“相等”也就是LessT, Pivot::value为false时它会被分到右侧。这会让快排不稳定两个相等元素的相对顺序可能发生变化。如果只是按大小排序无所谓如果相等对应同一优先级原始声明顺序有业务意义就要小心。4.2 归并排序稳定的代价是中途生成大量拼接类型编译期归并排序要保证稳定性同时要做“从中间切分”的操作。这个“从中间切分”本身就是一次递归遍历切分得到两个子列表后再分别归并排序最后合并两个有序列表。合并部分要写一个Merge元函数每次比较两个列表头把更小的一方先放进结果递归处理剩余部分。代码量和边界情况比插入排序复杂不少而且因为需要Split操作额外生成的中间类型数量是插入排序的几倍。我在实际项目里没有用归并做类型排序反而在constexpr数值排序中没少用归并因为那里是普通代码代价完全可控。4.3 算法复杂度之外的真正瓶颈实例化数量模板排序最需要关注的不是“比较了几次”而是“生成了多少个类型”。我把三个算法的实例化特征整理了一下算法递归深度中间类型产生量稳定性模板实现难度插入排序O(n)较少稳定低快速排序平均O(log n)分区中间类型较多不稳定中归并排序O(log n)拆分、合并中间类型最多稳定高所以当我在项目里看到类型排序需求时第一选择几乎都是插入排序。只有在类型数量很大、或者明确要求稳定排序时才会上归并或快排的模板实现。5. 现代C的另一条路用constexpr函数在编译期排序数值5.1 C14的constexpr函数让排序代码终于长得像普通代码不得不承认模板元编程写排序算法是真的费劲。C14之后我有了更好的选择constexpr函数里允许局部变量和循环了。如果你想在编译期给一堆同一类型的数值排序可以直接写一个普通的冒泡排序然后前面加个constexprtemplatetypename T, std::size_t N constexpr std::arrayT, N constexpr_sort(std::arrayT, N input) { for (std::size_t i 0; i 1 N; i) { for (std::size_t j 0; j i 1 N; j) { if (input[j] input[j 1]) { const T tmp input[j]; input[j] input[j 1]; input[j 1] tmp; } } } return input; }然后在编译期调用constexpr std::arrayint, 5 kSorted constexpr_sort(std::arrayint, 5{5, 2, 4, 1, 3}); static_assert(kSorted[0] 1); static_assert(kSorted[4] 5);这就是我在项目里真正处理“编译期数值排序”的方式。它把排序的实现难度直接降到了运行期代码水平又保留了编译期求值的性能优势。5.2 通过std::index_sequence把排序结果带进类型世界数值排序的产物是std::arrayT, N如果后续还需要把它展开成模板参数包比如生成一个std::integer_sequence可以配合std::index_sequence完成templatetypename T, std::size_t N, std::size_t... I constexpr auto to_sequence(std::arrayT, N const arr, std::index_sequenceI...) { return std::integer_sequenceT, arr[I]...{}; } constexpr auto kSortedSeq to_sequence(kSorted, std::make_index_sequence5{});这等于把constexpr算出的数值重新投喂给模板元编程世界。现代项目里我经常混合使用数值部分用constexpr函数算类型部分用模板递归操作中间用index_sequence作为转接口。5.3 constexpr排序和模板排序怎么分活儿我自己的分工原则很简单排序对象是“普通数值常量数组”时用constexpr函数可读性高编译器成熟度高。排序对象是“C类型列表”时用模板递归因为constexpr函数根本不认识“类型”这种一等公民。排序后需要把结果作为类型参数继续参与模板推导时优先模板元编程排序后只需要一张运行期静态表时constexpr函数更省事。有一点必须提醒C20之前constexpr函数不一定非要在编译期求值。如果你的排序结果被赋给一个非constexpr运行期变量编译器可能选择在运行期执行。想强制编译期求值要么保证constexpr变量初始化要么直接用C20的consteval。6. 真实工程中的落地与三番两次踩坑6.1 场景一按类型特征构建编译期分派表我在RPC分发层里有一组handler每个handler都有自己的静态优先级。优先级信息可以封装在一个traits里struct FastHandler { static void handle(Message); }; struct MediumHandler { static void handle(Message); }; struct SlowHandler { static void handle(Message); }; templatetypename T struct Priority; template struct PriorityFastHandler : std::integral_constantint, 3 {}; template struct PriorityMediumHandler : std::integral_constantint, 2 {}; template struct PrioritySlowHandler : std::integral_constantint, 1 {}; templatetypename A, typename B struct LessPriority { static constexpr bool value PriorityA::value PriorityB::value; };然后直接用模板排序using Handlers TypeListMediumHandler, SlowHandler, FastHandler; using SortedHandlers typename InsertionSortHandlers, LessPriority::type; static_assert(std::is_same_vSortedHandlers, TypeListFastHandler, MediumHandler, SlowHandler);为了把这组排序后的类型变成可在运行期访问的静态表我会再写一个简单的ToTupletemplatetypename List struct ToTuple; templatetypename... Ts struct ToTupleTypeListTs... { using type std::tupleTs...; }; using SortedTuple typename ToTupleSortedHandlers::type;之后std::get0(sorted_tuple)就是优先级最高的handler。这比手写数组顺序可靠得多新增handler类型后所有顺序都在编译期自动维护。6.2 场景二代码生成器里保证映射顺序稳定另一个落地场景是代码生成。我在做一个通过模板生成注册表的工具输入有一些无序的TypeList如果不排序每次重编工程时注册表里的顺序可能跟着声明顺序变动导致生成的源码diff很难看。把类型列表按名字或按优先级排序之后生成结果与输入声明顺序完全解耦每次生成的代码字符级一致。那种“明明是同一段逻辑生成的代码却总在变”的烦恼一次排序就解决了。编译期排序在这里的价值不是性能而是确定性。编译期排序的确定性与平台无关这比任何运行期后处理都可靠。6.3 编译期排序的深坑递归深度、报错可读性和求值时机这里把我踩过的几个大坑集中讲一遍。第一模板递归深度不够。编译器默认-ftemplate-depth通常是900一个简单的插入排序排20个元素就有可能在深层递归时爆掉。我遇到过排序列表本身不深但外层模板递归加上排序递归叠加起来超过限制的情况。解决手段有两个一是用-ftemplate-depth3000这类编译选项扩展深度二是把排序逻辑尽量改用constexpr方案避免模板递归叠加。第二报错信息根本没法看。GCC在模板排序编译失败时输出的“template argument deduction/substitution failed”可以带出几百行实例化链看起来像天书。我养成的习惯是每完成一个小的元函数马上用static_assert验证排序主函数完成后先在只有三四个元素的小列表上验证再扩大。同时可以给中间类型加using别名这样报错时你能看到具体哪一步类型不匹配。第三constexpr排序的求值时机坑。在C17里constexpr auto x sort(...)一定会编译期求值但如果你写成auto x sort(...)或者把结果塞进一个非constexpr的函数返回值里编译器很可能让你在运行期白跑一遍排序。我还遇到过一个更隐蔽的情况编译器为了“减少编译时间”把本来可以编译期求值的constexpr函数留到了运行期导致性能测试的时候出现诡异延迟。排查方法是把排序变量标记为constexpr或者用C20的consteval强制。第四比较器的严格弱序问题。模板递归本身没有“排序终止检测”比较器如果写成了AB和BA都为false但还是交换位置递归可能会在几个类型之间反复横跳直到触发模板深度上限。写比较器时先保证它是一个严格弱序最简单的验证方式是把比较器用在一堆有全序关系的占位类型上跑一遍std::is_same断言。我自己现在的习惯是类型列表排序先用插入排序模板限定在20个类型以内数值常量排序一律用C17的constexpr函数需要保证稳定性的场景再多花一点时间去写归并模板而不是在快排不稳定上做弥补。排序这个看似古老的算法放到模板编译期之后考验的其实不再是算法本身而是你对C编译模型的理解到底有多深。希望这篇能把你在类型排序门口前的那段弯路缩短一些。
去年年底我在重构一个内部RPC分发层时碰到一件很拧巴的事消息处理器有十几种每种在编译期就能确定优先级我却不能在运行期慢慢排序。手写函数指针数组之后更头疼数组里的顺序只能靠人肉维护再加一种类型就乱一次。当时脑子里冒出的方案是C模板元编程把处理器对应的C类型塞进类型列表在编译期按某个优先级特征排序最后展开成一张静态分派表。这篇文章就是那段时间把编译期排序算法从查资料到逐一实现、再到落地的全过程。如果你也在跟类型列表、模板特化、编译期常量较劲这篇可以直接拿来当抄作业的底稿。模板编译期排序不是一个炫技名词它解决的是“在代码还没有跑起来之前就把顺序确定下来”的问题。后面我会从类型列表的基本心智模型讲起给出一套可运行的插入排序模板再聊快排和归并在模板世界里的思路最后对比现代C里constexpr方案并把我踩过的几个坑一并倒出来。1. 为什么要在编译期排序先搞清楚你买的是什么1.1 排序对象不是“数组”而是“类型列表”运行期的std::sort作用在内存容器上排序过程交换的是对象的值。编译期没有“对象”只有类型和编译期常量。如果要对一堆C类型排序比如TypeListFastHandler, SlowHandler, MediumHandler这堆类型本身并不占据任何运行期内存它只是模板实例化时一个个“类型参数”的组合。要对这种组合排序就不能指望std::sort的迭代器模型必须自己用模板递归做“不可变列表”操作。换个角度理解把模板参数包typename... Ts当成一个编译期数组把每次排序的结果当成一个新的TypeList。这个新列表不会被复用也不会被原地修改因为模板元编程世界里根本没有“内存”和“指针”只有“类型”和“递归”。这个心智模型非常像函数式语言里的不可变链表只是存储单元从整数变成了类型。1.2 排序的直接收益和隐藏成本我选择编译期排序最直接的收益有三个运行期零开销排序在编译期完成生成的分派表天然有序运行时只要按顺序线性扫描或查表。结果确定同样的输入类型只要比较器严格且确定排序结果在任何平台、任何编译器下都一致不会出现“同一堆handler, 我这边快那边慢”的诡异问题。可组合排序依据可以来自类型traits、优先级元函数、依赖关系甚至多个条件的组合这些逻辑都属于编译期纯函数。成本也不能装看不见编译时间明显变长每排一个元素都会多一组模板实例化排几十个类型可能让单文件编译从秒级变成十秒级。模板实例化爆炸排序算法复杂度不只看比较次数还要看递归展开时生成了多少中间类型。报错信息可读性差一个比较器写错GCC能把几百行模板实例化堆栈甩到你脸上。我用一张表把运行期排序和编译期排序的差异列清楚维度运行期std::sort模板编译期排序数据载体vector/array/deque等容器类型列表/整数序列排序时机程序运行时模板实例化阶段交换对象内存中的值类型参数列表时间开销运行期CPU周期编译期CPU周期调试手段断点、日志static_assert、模板实例化trace元素数量量级几千到几百万通常几个到几十个典型应用普通业务排序类型分派、代码生成、元函数计算可以看出来编译期排序注定不是拿来做大规模数据排序的它适合的是“少量、但必须在编译期完成”的顺序计算。2. 编译期列表的“容器”长什么样类型列表与模板递归的心智模型2.1 用模板参数包当数组用特化当迭代器准备模板编译期排序前先把容器操作做好。我用的容器是一个极简的TypeListtemplatetypename... Ts struct TypeList { static constexpr std::size_t size sizeof...(Ts); };这个结构看起来像空壳实际上模板参数包Ts...就是容器本体。你可以在特化中抓住参数包进行展开、连接、取头取尾本质上就是把“对容器的遍历”变成了“对特化模式的匹配”。迭代器在哪里模板元编程里迭代器就是“偏特化的递归步骤”。比如取头元素templatetypename List struct Head; templatetypename T, typename... Rest struct HeadTypeListT, Rest... { using type T; };Head专门匹配“至少一个元素”的列表并取出第一个类型。取尾列表则把TypeListT, Rest...匹配成TypeListRest...templatetypename List struct Tail; templatetypename T, typename... Rest struct TailTypeListT, Rest... { using type TypeListRest...; };这两个原语一个告诉你“当前元素是谁”一个告诉你“剩下还有谁”排序算法的每次递归都靠它们缩小问题规模。2.2 必须提前备齐的四个基础操作除了Head和Tail我建议把下面这几个元函数也先定义好后面排序和验证都会用到#include type_traits // 在列表头部插入一个类型 templatetypename List, typename T struct PushFront; templatetypename... Ts, typename T struct PushFrontTypeListTs..., T { using type TypeListT, Ts...; }; // 连接两个类型列表 templatetypename List1, typename List2 struct Concat; templatetypename... Ts, typename... Us struct ConcatTypeListTs..., TypeListUs... { using type TypeListTs..., Us...; }; // 从一个列表中筛选出满足条件P的类型 templatetemplatetypename class P, typename List struct Filter; templatetemplatetypename class P struct FilterP, TypeList { using type TypeList; }; templatetemplatetypename class P, typename T, typename... Rest struct FilterP, TypeListT, Rest... { using rest typename FilterP, TypeListRest...::type; using type typename std::conditionalPT::value, typename PushFrontrest, T::type, rest::type; };PushFront和Concat是排序结果拼接的“胶水”Filter则是快速排序里分区逻辑的基础。每定义一个原语我都会加一个static_assert测一遍确认行为符合预期再接上排排序比如static_assert(std::is_same_vtypename HeadTypeListint, double::type, int); static_assert(std::is_same_vtypename TailTypeListint, double::type, TypeListdouble); static_assert(std::is_same_vtypename ConcatTypeListint, TypeListdouble::type, TypeListint, double);这些测试看着土却是模板元编程项目里的命根子。类型层面的错误没有运行期堆栈只能靠一层层断言缩小范围。2.3 数值序列与类型列表两种编译期容器两套玩法我还经常用到另一种编译期容器那就是std::integer_sequence。它存储的是int, size_t这类编译期数值可以理解成“编译期整数数组”。它跟TypeList的核心区别是TypeList的元素是类型integer_sequence的元素是值。using Numbers std::integer_sequenceint, 5, 2, 4, 1, 3;对类型排序必须走TypeList那套递归模板对数值排序可以走constexpr函数也可以把它们转成TypeList再继续元编程。C17以后非类型模板参数也可以放进auto...里但类型列表的独立性更强因为同一个类型可以携带不同优先级、不同大小、不同tag信息这是整数序列单薄的int很难做到的。3. 手写一个可用的编译期插入排序从比较器到完整验证3.1 比较器的工程意义不要把“小于”写死在算法里模板排序和运行期排序一样也应该把“比较规则”从算法本身抽出来。在模板世界里常见做法是用“模板模板参数”把比较器当作类型传进去也就是传给算法一个templatetypename, typename class Less类型的模板。这样做的意义很大。同一个排序算法你可以按sizeof排序按自定义PriorityT::value排序甚至按两个条件的组合排序。排序算法只关心它能否从LessA, B::value拿到一个bool完全不关心这个bool是怎么算出来的。下面定义一个最直观的比较器按类型大小排序templatetypename A, typename B struct LessSize { static constexpr bool value (sizeof(A) sizeof(B)); };之后设计算法时默认比较器就用它。如果某个场景需要按优先级排序只需要换一个LessPriority排序模板一模一样。3.2 插入排序模板的完整拆解插入排序的思路和运行期一致一个空列表每次拿一个新元素按“小于”关系插入到已经排好序的列表里。模板版本的实现如下。先做“插入单个元素”的元函数templatetypename List, typename T, templatetypename, typename class Less struct Insert; templatetypename T, templatetypename, typename class Less struct InsertTypeList, T, Less { using type TypeListT; }; templatetypename T, typename Head, typename... Tail, templatetypename, typename class Less struct InsertTypeListHead, Tail..., T, Less { using type typename std::conditional LessT, Head::value, TypeListT, Head, Tail..., typename PushFronttypename InsertTypeListTail..., T, Less::type, Head::type ::type; };这个元函数做的判断是如果新元素T比当前列表头Head小就把T放到最前面一次插入完成。如果不小说明插入位置在后面于是把Head先放到结果前面继续在后面Tail...中递归插入。然后是排序主体templatetypename List, templatetypename, typename class Less LessSize struct InsertionSort; templatetemplatetypename, typename class Less struct InsertionSortTypeList, Less { using type TypeList; }; templatetypename T, typename... Rest, templatetypename, typename class Less struct InsertionSortTypeListT, Rest..., Less { using sorted_rest typename InsertionSortTypeListRest..., Less::type; using type typename Insertsorted_rest, T, Less::type; };递归过程就是先排序尾部Rest...再把当前元素T插入到排序后的尾部列表。把整个过程拆开看每次排序都会生成很多个新的临时类型但最终只有一个type指针指向结果。3.3 static_assert把排序结果钉在编译期写完元函数必须验证。我创建了几个大小递增的占位类型然后直接断言排序结果struct TagA { char c; }; // sizeof(1) struct TagB { short s; }; // sizeof(2) struct TagC { int i; }; // sizeof(4) struct TagD { double d; }; // sizeof(8) using Unsorted TypeListTagD, TagA, TagC, TagB; using Sorted typename InsertionSortUnsorted::type; static_assert(std::is_same_vSorted, TypeListTagA, TagB, TagC, TagD); static_assert(std::is_same_vtypename HeadSorted::type, TagA); static_assert(std::is_same_vtypename TailSorted::type, TypeListTagB, TagC, TagD);这个断言是在编译期执行的一旦排序逻辑有偏差编译器会直接告诉你“类型不匹配”而且很可能甩出几十层实例化记录。所以我建议每个模板元编程排序算法边上都常备一组类似的static_assert一旦后面要融合更多功能这些断言能守住旧行为。3.4 为什么我优先选插入排序而不是快排我之前好奇直接上快排不是更高级吗后来在模板元编程里试了一遍发现“高级”不等于“好用”。插入排序的优势在于模板实现最简单边界条件少。不额外生成大量分区临时列表对编译期内存压力小。元素个数通常在个位数到十几位O(n²)的运行期劣势完全体现不出来。我给自己定的经验法则是编译期要排序的类型少于20个无脑用插入排序。类型一多先重新审视设计——是不是把不该塞进类型表里的东西硬塞进去了如果确实要排很多再看快排或constexpr方案。4. 快排和归并排序的模板实现思路复杂度与实例化消耗的博弈4.1 快速排序用分区谓词甩掉“逐个插入”的笨重感快速排序在编译期完全能够实现思路也直接取第一个元素作为pivot把剩余列表分成“小于pivot”和“不小于pivot”两组递归排序两组后拼接。分区这一步可以用之前定义好的Filter或手写一个Partition特化。下面是我在项目中用的简化实现templatetypename Pivot, typename List, templatetypename, typename class Less struct Partition; templatetypename Pivot, templatetypename, typename class Less struct PartitionPivot, TypeList, Less { using left TypeList; using right TypeList; }; templatetypename Pivot, typename T, typename... Rest, templatetypename, typename class Less struct PartitionPivot, TypeListT, Rest..., Less { using rest PartitionPivot, TypeListRest..., Less; using left_if_true typename PushFronttypename rest::left, T::type; using right_if_false typename PushFronttypename rest::right, T::type; using left typename std::conditionalLessT, Pivot::value, left_if_true, typename rest::left::type; using right typename std::conditionalLessT, Pivot::value, typename rest::right, right_if_false::type; }; templatetypename List, templatetypename, typename class Less LessSize struct QuickSort; templatetemplatetypename, typename class Less struct QuickSortTypeList, Less { using type TypeList; }; templatetypename Pivot, typename... Rest, templatetypename, typename class Less struct QuickSortTypeListPivot, Rest..., Less { using partition PartitionPivot, TypeListRest..., Less; using left_sorted typename QuickSorttypename partition::left, Less::type; using right_sorted typename QuickSorttypename partition::right, Less::type; using type typename Concatleft_sorted, typename ConcatTypeListPivot, right_sorted::type::type; };注意点在于当某个元素和pivot“相等”也就是LessT, Pivot::value为false时它会被分到右侧。这会让快排不稳定两个相等元素的相对顺序可能发生变化。如果只是按大小排序无所谓如果相等对应同一优先级原始声明顺序有业务意义就要小心。4.2 归并排序稳定的代价是中途生成大量拼接类型编译期归并排序要保证稳定性同时要做“从中间切分”的操作。这个“从中间切分”本身就是一次递归遍历切分得到两个子列表后再分别归并排序最后合并两个有序列表。合并部分要写一个Merge元函数每次比较两个列表头把更小的一方先放进结果递归处理剩余部分。代码量和边界情况比插入排序复杂不少而且因为需要Split操作额外生成的中间类型数量是插入排序的几倍。我在实际项目里没有用归并做类型排序反而在constexpr数值排序中没少用归并因为那里是普通代码代价完全可控。4.3 算法复杂度之外的真正瓶颈实例化数量模板排序最需要关注的不是“比较了几次”而是“生成了多少个类型”。我把三个算法的实例化特征整理了一下算法递归深度中间类型产生量稳定性模板实现难度插入排序O(n)较少稳定低快速排序平均O(log n)分区中间类型较多不稳定中归并排序O(log n)拆分、合并中间类型最多稳定高所以当我在项目里看到类型排序需求时第一选择几乎都是插入排序。只有在类型数量很大、或者明确要求稳定排序时才会上归并或快排的模板实现。5. 现代C的另一条路用constexpr函数在编译期排序数值5.1 C14的constexpr函数让排序代码终于长得像普通代码不得不承认模板元编程写排序算法是真的费劲。C14之后我有了更好的选择constexpr函数里允许局部变量和循环了。如果你想在编译期给一堆同一类型的数值排序可以直接写一个普通的冒泡排序然后前面加个constexprtemplatetypename T, std::size_t N constexpr std::arrayT, N constexpr_sort(std::arrayT, N input) { for (std::size_t i 0; i 1 N; i) { for (std::size_t j 0; j i 1 N; j) { if (input[j] input[j 1]) { const T tmp input[j]; input[j] input[j 1]; input[j 1] tmp; } } } return input; }然后在编译期调用constexpr std::arrayint, 5 kSorted constexpr_sort(std::arrayint, 5{5, 2, 4, 1, 3}); static_assert(kSorted[0] 1); static_assert(kSorted[4] 5);这就是我在项目里真正处理“编译期数值排序”的方式。它把排序的实现难度直接降到了运行期代码水平又保留了编译期求值的性能优势。5.2 通过std::index_sequence把排序结果带进类型世界数值排序的产物是std::arrayT, N如果后续还需要把它展开成模板参数包比如生成一个std::integer_sequence可以配合std::index_sequence完成templatetypename T, std::size_t N, std::size_t... I constexpr auto to_sequence(std::arrayT, N const arr, std::index_sequenceI...) { return std::integer_sequenceT, arr[I]...{}; } constexpr auto kSortedSeq to_sequence(kSorted, std::make_index_sequence5{});这等于把constexpr算出的数值重新投喂给模板元编程世界。现代项目里我经常混合使用数值部分用constexpr函数算类型部分用模板递归操作中间用index_sequence作为转接口。5.3 constexpr排序和模板排序怎么分活儿我自己的分工原则很简单排序对象是“普通数值常量数组”时用constexpr函数可读性高编译器成熟度高。排序对象是“C类型列表”时用模板递归因为constexpr函数根本不认识“类型”这种一等公民。排序后需要把结果作为类型参数继续参与模板推导时优先模板元编程排序后只需要一张运行期静态表时constexpr函数更省事。有一点必须提醒C20之前constexpr函数不一定非要在编译期求值。如果你的排序结果被赋给一个非constexpr运行期变量编译器可能选择在运行期执行。想强制编译期求值要么保证constexpr变量初始化要么直接用C20的consteval。6. 真实工程中的落地与三番两次踩坑6.1 场景一按类型特征构建编译期分派表我在RPC分发层里有一组handler每个handler都有自己的静态优先级。优先级信息可以封装在一个traits里struct FastHandler { static void handle(Message); }; struct MediumHandler { static void handle(Message); }; struct SlowHandler { static void handle(Message); }; templatetypename T struct Priority; template struct PriorityFastHandler : std::integral_constantint, 3 {}; template struct PriorityMediumHandler : std::integral_constantint, 2 {}; template struct PrioritySlowHandler : std::integral_constantint, 1 {}; templatetypename A, typename B struct LessPriority { static constexpr bool value PriorityA::value PriorityB::value; };然后直接用模板排序using Handlers TypeListMediumHandler, SlowHandler, FastHandler; using SortedHandlers typename InsertionSortHandlers, LessPriority::type; static_assert(std::is_same_vSortedHandlers, TypeListFastHandler, MediumHandler, SlowHandler);为了把这组排序后的类型变成可在运行期访问的静态表我会再写一个简单的ToTupletemplatetypename List struct ToTuple; templatetypename... Ts struct ToTupleTypeListTs... { using type std::tupleTs...; }; using SortedTuple typename ToTupleSortedHandlers::type;之后std::get0(sorted_tuple)就是优先级最高的handler。这比手写数组顺序可靠得多新增handler类型后所有顺序都在编译期自动维护。6.2 场景二代码生成器里保证映射顺序稳定另一个落地场景是代码生成。我在做一个通过模板生成注册表的工具输入有一些无序的TypeList如果不排序每次重编工程时注册表里的顺序可能跟着声明顺序变动导致生成的源码diff很难看。把类型列表按名字或按优先级排序之后生成结果与输入声明顺序完全解耦每次生成的代码字符级一致。那种“明明是同一段逻辑生成的代码却总在变”的烦恼一次排序就解决了。编译期排序在这里的价值不是性能而是确定性。编译期排序的确定性与平台无关这比任何运行期后处理都可靠。6.3 编译期排序的深坑递归深度、报错可读性和求值时机这里把我踩过的几个大坑集中讲一遍。第一模板递归深度不够。编译器默认-ftemplate-depth通常是900一个简单的插入排序排20个元素就有可能在深层递归时爆掉。我遇到过排序列表本身不深但外层模板递归加上排序递归叠加起来超过限制的情况。解决手段有两个一是用-ftemplate-depth3000这类编译选项扩展深度二是把排序逻辑尽量改用constexpr方案避免模板递归叠加。第二报错信息根本没法看。GCC在模板排序编译失败时输出的“template argument deduction/substitution failed”可以带出几百行实例化链看起来像天书。我养成的习惯是每完成一个小的元函数马上用static_assert验证排序主函数完成后先在只有三四个元素的小列表上验证再扩大。同时可以给中间类型加using别名这样报错时你能看到具体哪一步类型不匹配。第三constexpr排序的求值时机坑。在C17里constexpr auto x sort(...)一定会编译期求值但如果你写成auto x sort(...)或者把结果塞进一个非constexpr的函数返回值里编译器很可能让你在运行期白跑一遍排序。我还遇到过一个更隐蔽的情况编译器为了“减少编译时间”把本来可以编译期求值的constexpr函数留到了运行期导致性能测试的时候出现诡异延迟。排查方法是把排序变量标记为constexpr或者用C20的consteval强制。第四比较器的严格弱序问题。模板递归本身没有“排序终止检测”比较器如果写成了AB和BA都为false但还是交换位置递归可能会在几个类型之间反复横跳直到触发模板深度上限。写比较器时先保证它是一个严格弱序最简单的验证方式是把比较器用在一堆有全序关系的占位类型上跑一遍std::is_same断言。我自己现在的习惯是类型列表排序先用插入排序模板限定在20个类型以内数值常量排序一律用C17的constexpr函数需要保证稳定性的场景再多花一点时间去写归并模板而不是在快排不稳定上做弥补。排序这个看似古老的算法放到模板编译期之后考验的其实不再是算法本身而是你对C编译模型的理解到底有多深。希望这篇能把你在类型排序门口前的那段弯路缩短一些。
