11、编译期算法：编译期 find、编译期 count、编译期 transform

说实话，很多人一听到「编译期算法」就觉得玄乎。其实没那么复杂。

你想想看，既然我们能在编译期算出一个值，那为什么不能算出一个序列？既然能算出一个序列，那为什么不能在这个序列上做查找、计数、变换？

嗯，这就是我们今天要聊的东西。

11.1 编译期算法到底在算什么？

先明确一个概念：编译期算法操作的对象，是类型列表（TypeList）或者值列表（ValueList）。

说白了，就是把运行时对数组做的那些操作——find、count、transform——搬到编译期来做。只不过操作的对象从「运行时变量」变成了「编译期类型或常量」。

我在项目中遇到过这样一个场景：需要根据某个类型在列表中的位置，决定是否启用某个特化版本。如果运行时做，就得用 RTTI，性能差不说，代码还丑。用编译期 find，几行模板搞定。

11.2 编译期 find：在类型列表中查找

先来个最简单的：给定一个类型列表，查找某个类型是否存在，返回索引位置。

// 前置声明
template <typename T, typename List>
struct IndexOf;

// 递归终止：找到了
template <typename T, typename... Rest>
struct IndexOf<T, TypeList<T, Rest...>> {
    static constexpr std::size_t value = 0;
};

// 递归步骤：没找到，继续往后找
template <typename T, typename First, typename... Rest>
struct IndexOf<T, TypeList<First, Rest...>> {
    static constexpr std::size_t value = 
        1 + IndexOf<T, TypeList<Rest...>>::value;
};

// 没找到的情况
template <typename T>
struct IndexOf<T, TypeList<>> {
    static constexpr std::size_t value = static_cast<std::size_t>(-1);
};

用法很简单：

using MyList = TypeList<int, double, char, float>;
constexpr auto idx = IndexOf<double, MyList>::value; // idx = 1

11.3 编译期 count：统计类型出现次数

find 是找位置，count 是数个数。实现思路类似，但递归时要做加法。

template <typename T, typename List>
struct Count;

template <typename T>
struct Count<T, TypeList<>> {
    static constexpr std::size_t value = 0;
};

template <typename T, typename... Rest>
struct Count<T, TypeList<T, Rest...>> {
    static constexpr std::size_t value = 
        1 + Count<T, TypeList<Rest...>>::value;
};

template <typename T, typename First, typename... Rest>
struct Count<T, TypeList<First, Rest...>> {
    static constexpr std::size_t value = 
        Count<T, TypeList<Rest...>>::value;
};

注意第三个特化：当第一个元素不匹配时，不加 1，继续递归。

11.4 编译期 transform：对每个类型做变换

transform 就更有意思了。它把一个类型列表里的每个类型，通过一个「元函数」映射成另一个类型，生成新的类型列表。

// 元函数：给类型加一层指针
template <typename T>
struct AddPointer {
    using type = T*;
};

// transform 实现
template <template<typename> class F, typename List>
struct Transform;

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

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

用起来很直观：

using Original = TypeList<int, double, char>;
using Transformed = Transform<AddPointer, Original>::type;
// 结果：TypeList<int*, double*, char*>

11.5 把这些算法串起来：一个实际例子

光讲理论没意思。我给你们看一个我在项目中用过的真实场景。

假设我们要实现一个「类型过滤器」：从一个类型列表里，挑出所有满足某个条件的类型，组成新列表。

// 条件：判断是否是整数类型
template <typename T>
struct IsInteger {
    static constexpr bool value = false;
};

template <>
struct IsInteger<int> {
    static constexpr bool value = true;
};

template <>
struct IsInteger<long> {
    static constexpr bool value = true;
};

// 编译期 filter（简化版）
template <template<typename> class Pred, typename List>
struct Filter;

template <template<typename> class Pred>
struct Filter<Pred, TypeList<>> {
    using type = TypeList<>;
};

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

你看，这里用了 std::conditional_t 来做编译期的 if-else。如果满足条件，就把当前类型加入结果列表；否则跳过。

11.6 编译期算法的性能真相

很多人觉得编译期算法「快」，其实要分两面看：

方面	说明
编译时间	递归深度越大，编译越慢。100 个类型的列表，递归 100 层，编译时间肉眼可见地涨。
运行时间	零开销。所有计算都在编译期完成，运行时直接拿结果。
代码体积	每个特化都会生成一份代码。如果列表很长，二进制体积会膨胀。

说白了，编译期算法是用「编译时间」换「运行时间」。如果你的列表只有几十个类型，完全没问题。但如果上千个，我建议你重新考虑设计。

11.7 知识体系图

下面这张图总结了编译期 find、count、transform 的核心逻辑和关系：

11.8 避坑指南

最后，分享几个我这些年积累的经验：

• 递归深度限制：编译器默认模板递归深度一般是 256 或 512。如果列表太长，可以用 -ftemplate-depth 调整，但不建议超过 1024。
• 类型列表不要用 std::tuple：虽然 std::tuple 也能当类型列表用，但它的特化机制不如自己写的 TypeList 灵活。我建议自己定义一个简单的 TypeList。
• 注意编译错误信息：模板递归出错时，编译器报错能长达几百行。我的习惯是：先写一个最小用例验证递归逻辑，再逐步扩展。
• C++17 的 if constexpr：如果你用 C++17，可以用 if constexpr 简化递归实现，代码会清晰很多。但底层原理还是模板递归。

编译期算法，说白了就是「用模板递归模拟循环」。掌握了 find、count、transform 这三个基础操作，你就能组合出更复杂的编译期算法。比如 filter、reduce、zip 等等。

这些内容，我们后面会陆续讲到。

---

公众号:蓝海资料掘金营，微信deep3321