### 如何利用C++模板实现编译期链表

C++ 的模板元编程（Template Meta-Programming, TMP）让我们可以在编译期间完成各种计算和数据结构操作。本文将演示如何使用递归模板实现一个编译期链表，并提供基本的插入、查找以及长度统计功能。

1. 设计思路

• 节点类型：使用结构体模板 Node，包含值 Value 和指向下一节点的类型 Next。
• 空节点：定义一个 NullNode 作为链表尾部标识。
• 插入：通过递归模板 PushFront 在链表前端插入新节点。
• 查找：使用 Find 模板在链表中查找特定值，返回布尔值。
• 长度：通过 Length 模板计算链表长度。

2. 代码实现

#include <type_traits>
#include <iostream>

// 1. 空节点
struct NullNode {};

// 2. 节点定义
template <int Value, typename Next>
struct Node {
    static constexpr int value = Value;
    using next = Next;
};

// 3. PushFront: 在链表前端插入新节点
template <int NewValue, typename List>
struct PushFront {
    using type = Node<NewValue, List>;
};

// 4. Length: 计算链表长度
template <typename List>
struct Length;

template <>
struct Length <NullNode> {
    static constexpr std::size_t value = 0;
};

template <int V, typename Next>
struct Length<Node<V, Next>> {
    static constexpr std::size_t value = 1 + Length <Next>::value;
};

// 5. Find: 查找指定值
template <int Target, typename List>
struct Find;

template <int Target>
struct Find<Target, NullNode> {
    static constexpr bool value = false;
};

template <int Target, int V, typename Next>
struct Find<Target, Node<V, Next>> {
    static constexpr bool value = (Target == V) ? true : Find<Target, Next>::value;
};

// 6. 便利类型别名
template <int NewValue, typename List>
using PushFront_t = typename PushFront<NewValue, List>::type;

// 示例
using List0 = NullNode;
using List1 = PushFront_t<10, List0>;
using List2 = PushFront_t<20, List1>;
using List3 = PushFront_t<30, List2>;

int main() {
    std::cout << "List3 length: " << Length<List3>::value << '\n';
    std::cout << "Find 20: " << Find<20, List3>::value << '\n';
    std::cout << "Find 40: " << Find<40, List3>::value << '\n';
    return 0;
}

3. 运行结果

List3 length: 3
Find 20: 1
Find 40: 0

4. 进一步扩展

• 删除节点：实现 PopFront 或 Remove 模板。
• 映射：使用 Transform 模板对每个节点值执行编译期运算。
• 排序：利用递归插入排序实现 Sort 模板。

5. 小结

通过模板递归，我们可以在编译阶段构造和操作链表结构。虽然这种方式在运行时不产生实际数据结构，但在需要在编译期间完成类型决策、参数化配置或优化代码时，模板元编程是非常强大的工具。希望本文能帮助你入门 C++ 的 TMP 并激发更多创意。