18、模板元编程进阶：编译期列表(typelist)、编译期算法、编译期排序
好，咱们今天聊点硬核的。模板元编程（TMP）走到这一步，才算真正进入深水区。
前面我们讲了模板基础、特化、SFINAE，那些说白了是「工具」。今天要讲的，是用这些工具搭建完整的数据结构和算法——在编译期。
你想想看，运行时我们能写链表、排序、查找。编译期能不能？当然能。而且一旦你掌握了编译期列表（typelist）和编译期算法，很多运行时才能暴露的问题，在编译期就能直接扼杀掉。我个人习惯把这种能力叫做「把错误消灭在 -O0 阶段」。
18.1 编译期列表（Typelist）—— 编译期的 std::vector
Typelist 是什么？说白了就是一个类型组成的列表。运行时我们用 vector<int> 存整数，编译期我们用 Typelist<int, double, char> 存类型。
它的定义极其简单：
template<typename... Ts>
struct Typelist {};嗯，就这？对，就这。但别小看它。空壳子里面能玩出花来。
我在项目中遇到过这样一个场景：需要根据不同的平台（x86、ARM、RISC-V）选择不同的算法实现。如果运行时做 if-else，分支预测失败会掉性能。用 Typelist + 编译期查找，直接生成最优代码路径，零开销。
18.2 编译期算法——遍历、查找、转换
有了列表，自然要有算法。我们来看几个最常用的。
18.2.1 获取列表长度
template<typename TL>
struct Length;
template<typename... Ts>
struct Length<Typelist<Ts...>> {
static constexpr size_t value = sizeof...(Ts);
};这里用到了 sizeof... 运算符，C++11 就有了。没什么难度，但它是所有算法的基础。
18.2.2 按索引获取类型
template<size_t N, typename TL>
struct TypeAt;
template<size_t N, typename T, typename... Ts>
struct TypeAt<N, Typelist<T, Ts...>> {
using type = typename TypeAt<N-1, Typelist<Ts...>>::type;
};
template<typename T, typename... Ts>
struct TypeAt<0, Typelist<T, Ts...>> {
using type = T;
};递归展开，每次剥掉第一个类型，直到 N 减到 0。这就是编译期的「数组下标访问」。
18.2.3 编译期查找（Find）
template<typename T, typename TL>
struct IndexOf;
template<typename T, typename... Ts>
struct IndexOf<T, Typelist<T, Ts...>> {
static constexpr size_t value = 0;
};
template<typename T, typename U, typename... Ts>
struct IndexOf<T, Typelist<U, Ts...>> {
static constexpr size_t value = 1 + IndexOf<T, Typelist<Ts...>>::value;
};这个算法在运行时就是线性查找。但在编译期，它没有循环，只有递归模板实例化。编译器会帮你展开成最优形式。
18.3 编译期排序——冒泡排序的模板元实现
好，重头戏来了。编译期排序。
你可能会问：排序不是运行时的事吗？为什么要在编译期做？
原因很简单：类型顺序影响代码生成。比如你要根据类型的对齐要求，从大到小排列，以减少内存填充。这种信息编译期完全可知，为什么不提前排好？
我们以冒泡排序为例，因为它最容易用模板递归实现。
// 辅助：比较两个类型的大小（这里按 sizeof 排序）
template<typename A, typename B>
struct TypeSizeLess {
static constexpr bool value = (sizeof(A) < sizeof(B));
};
// 一次冒泡：将最大元素冒到末尾
template<typename TL, template<typename, typename> class Compare>
struct BubbleOnce;
template<template<typename, typename> class Compare>
struct BubbleOnce<Typelist<>, Compare> {
using type = Typelist<>;
};
template<typename T, template<typename, typename> class Compare>
struct BubbleOnce<Typelist<T>, Compare> {
using type = Typelist<T>;
};
template<typename A, typename B, typename... Rest,
template<typename, typename> class Compare>
struct BubbleOnce<Typelist<A, B, Rest...>, Compare> {
using Next = typename BubbleOnce<Typelist<B, Rest...>, Compare>::type;
using First = typename TypeAt<0, Next>::type;
using Tail = typename TypeAtHelper<1, Next>::type; // 简化示意
// 如果 A < First，则 A 在前，否则交换
using type = typename std::conditional<
Compare<A, First>::value,
Typelist<A, First, Tail...>,
Typelist<First, A, Tail...>
>::type;
};
// 完整排序：重复 BubbleOnce N 次
template<typename TL, template<typename, typename> class Compare>
struct Sort : Sort<typename BubbleOnce<TL, Compare>::type, Compare> {};
template<template<typename, typename> class Compare>
struct Sort<Typelist<>, Compare> {
using type = Typelist<>;
};
template<typename T, template<typename, typename> class Compare>
struct Sort<Typelist<T>, Compare> {
using type = Typelist<T>;
};18.4 实战：用编译期排序优化内存布局
我记得有一次做嵌入式开发，需要把一组结构体按对齐要求重新排列。运行时做这件事有额外开销，而且嵌入式设备上 ROM 空间宝贵。
于是我用编译期排序，把类型按 sizeof 从大到小排列，然后生成一个联合体（union）来复用内存。代码大概长这样：
using MyTypes = Typelist<char, double, int, short, long long>;
using SortedTypes = Sort<MyTypes, TypeSizeGreater>::type;
// SortedTypes 现在是 Typelist<long long, double, int, short, char>
// 然后生成 union
template<typename TL>
struct UnionFromTypelist;
template<typename... Ts>
struct UnionFromTypelist<Typelist<Ts...>> {
union {
Ts... members;
};
};这样生成的 union，内存浪费最小，而且所有工作都在编译期完成。运行时零开销。
18.5 知识体系总览
下面这张图总结了本章的核心脉络：
18.6 小结与个人体会
编译期列表和算法，是模板元编程从「玩具」走向「工程」的分水岭。
我个人觉得，掌握 Typelist 的关键不在于记住那些递归模板的写法，而在于建立「类型即数据」的思维模式。一旦你习惯了把类型当作值来操作，很多运行时才能做的事情，你都会下意识地想：能不能提到编译期？
当然，凡事有度。编译期排序的模板实例化深度和编译时间是需要权衡的。我一般只在类型数量不超过 30 个时使用，超过这个数，我会考虑用代码生成器或者运行时一次初始化。
公众号：蓝海资料掘金营，微信 deep3321