类型列表与编译期算法：类型列表的定义，编译期查找、排序、变换

类型列表，说白了就是一个在编译期操作的“容器”。

它不存数据，存的是类型。你想想看，运行时我们有 std::vector、std::list，那编译期呢？我们拿什么来组织一堆类型？嗯，类型列表就是干这个的。

类型列表的定义

先看一个最朴素的实现：

template<typename... Types>
struct TypeList {};

就这么简单。一个可变参数模板，打包了一堆类型。

举个例子：

using MyTypes = TypeList<int, double, char, float>;

我个人习惯把类型列表命名为 TL 或者 Types，短一点，写起来不累。

template<typename... T>
using TL = TypeList<T...>;

编译期查找：在类型列表中找某个类型

查找，就是问一个问题：“这个类型在不在列表里？”

我曾在项目里需要根据配置类型动态选择序列化器，那时候就用到了编译期查找。如果类型不在列表中，编译直接报错——比运行时 crash 友好多了。

实现思路：递归展开参数包。

template<typename T, typename List>
struct Contains;

template<typename T, typename... Rest>
struct Contains<T, TypeList<T, Rest...>> : std::true_type {};

template<typename T, typename First, typename... Rest>
struct Contains<T, TypeList<First, Rest...>> : Contains<T, TypeList<Rest...>> {};

template<typename T>
struct Contains<T, TypeList<>> : std::false_type {};

用法：

static_assert(Contains<int, MyTypes>::value, "int should be in the list");
static_assert(!Contains<long, MyTypes>::value, "long should not be in the list");

为什么会这样？因为模板特化匹配到了 T 和 TypeList<T, Rest...> 时，就直接返回 true_type。如果一直匹配不到，最后落到空列表，返回 false_type。

编译期排序：按类型大小排序

排序就有点意思了。我当年第一次写编译期排序时，写了一个晚上才跑通。说白了，就是冒泡排序的编译期版本。

先定义一个比较大小的 trait：

template<typename A, typename B>
struct Smaller {
    static constexpr bool value = sizeof(A) < sizeof(B);
};

然后实现一个冒泡排序：

template<typename List, template<typename, typename> class Compare>
struct Sort;

// 递归终止：空列表或单元素列表
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>;
};

// 一般情况：取第一个元素，插入到已排序的剩余列表中
template<typename First, typename... Rest, template<typename, typename> class Compare>
struct Sort<TypeList<First, Rest...>, Compare> {
private:
    using sorted_rest = typename Sort<TypeList<Rest...>, Compare>::type;
public:
    using type = typename Insert<First, sorted_rest, Compare>::type;
};

这里还需要一个 Insert 算法，把元素插入到已排序列表的正确位置：

template<typename T, typename List, template<typename, typename> class Compare>
struct Insert;

template<typename T, template<typename, typename> class Compare>
struct Insert<T, TypeList<>, Compare> {
    using type = TypeList<T>;
};

template<typename T, typename First, typename... Rest, template<typename, typename> class Compare>
struct Insert<T, TypeList<First, Rest...>, Compare> {
    using type = std::conditional_t<
        Compare<T, First>::value,
        TypeList<T, First, Rest...>,
        typename Insert<T, TypeList<Rest...>, Compare>::type
    >;
};

使用：

using Sorted = Sort<MyTypes, Smaller>::type;
// 结果：char, float, int, double (按 sizeof 从小到大)

编译期变换：对每个类型做映射

变换，就是给列表里的每个类型“套一层”。比如给每个类型加个指针：

template<typename T>
struct AddPointer {
    using type = T*;
};

template<typename List, template<typename> class Transform>
struct TransformList;

template<template<typename> class Transform>
struct TransformList<TypeList<>, Transform> {
    using type = TypeList<>;
};

template<typename First, typename... Rest, template<typename> class Transform>
struct TransformList<TypeList<First, Rest...>, Transform> {
    using type = typename Prepend<
        typename Transform<First>::type,
        typename TransformList<TypeList<Rest...>, Transform>::type
    >::type;
};

这里 Prepend 是一个辅助：

template<typename T, typename List>
struct Prepend;

template<typename T, typename... Rest>
struct Prepend<T, TypeList<Rest...>> {
    using type = TypeList<T, Rest...>;
};

使用：

using PtrTypes = TransformList<MyTypes, AddPointer>::type;
// 结果：TypeList<int*, double*, char*, float*>

你想想看，这个能力有多强？你可以给每个类型加 const、加引用、加智能指针，甚至根据类型特征做条件变换。

知识体系图

下面这张图总结了类型列表的核心操作：

避坑指南

我曾经在编译期算法里踩过一个坑：递归深度太大导致编译崩溃。那时候我写了一个递归 1000 层的类型列表操作，GCC 直接报 fatal error: template instantiation depth exceeds maximum。

解决办法有两个：

• 增加编译器的模板深度限制（-ftemplate-depth=1024）
• 改用更平衡的递归方式，比如二分法而不是线性递归

我个人建议优先用第二种。毕竟，依赖编译器参数不是长久之计。

总结

类型列表是编译期编程的基石。掌握了定义、查找、排序、变换这四板斧，你就能在编译期做很多“不可能”的事情。

说白了，就是把运行时的算法思维搬到编译期。区别在于：运行时用循环，编译期用递归；运行时用变量，编译期用类型。

嗯，下一节我们会把这些算法组合起来，实现一个完整的编译期容器。敬请期待。