模板元编程

// Erwin Unruh 1994 年原始程序的现代简化重构（保留原意）
// 该程序在编译期通过模板递归计算素数，并在错误信息中输出
#include <cstdio>

template<int p, int i>
struct is_prime {
    enum { value = (p % i != 0) && is_prime<p, i - 1>::value };
};

template<int p>
struct is_prime<p, 1> {
    enum { value = 1 };
};

template<int i>
struct Prime_print {
    Prime_print<i - 1> a;
    // 强制编译器在错误信息中输出 i，前提是 i 为素数
    static_assert(is_prime<i, i - 1>::value, "i is prime");
    enum { value = i };
    void f() { printf("%d\n", value); }  // 仅为占位，实际从不调用
};

template<>
struct Prime_print<1> {
    enum { value = 1 };
};

// 实例化将触发编译期素数计算
// Prime_print<18> b;  // 取消注释后编译错误信息中可见素数列表

// C++98 风格的元函数与 traits 示例
#include <iterator>
#include <vector>
#include <list>

// C++98 风格的元函数：通过嵌套 ::type 实现
template<typename T>
struct remove_const {
    typedef T type;
};

template<typename T>
struct remove_const<const T> {
    typedef T type;
};

// C++98 风格的迭代器分类分发
template<typename Iter, typename Distance>
void advance_impl(Iter& it, Distance n, std::input_iterator_tag) {
    while (n--) ++it;
}

template<typename Iter, typename Distance>
void advance_impl(Iter& it, Distance n, std::random_access_iterator_tag) {
    it += n;
}

template<typename Iter, typename Distance>
void advance(Iter& it, Distance n) {
    advance_impl(it, n, typename std::iterator_traits<Iter>::iterator_category());
}

// 使用
int main() {
    std::vector<int>::iterator vit;
    std::list<int>::iterator lit;
    advance(vit, 5);   // 调用 random_access 版本
    advance(lit, 5);   // 调用 input_iterator 版本（list 是双向迭代器）
    return 0;
}

// C++11 可变参数模板与 type_traits
#include <type_traits>

// 可变参数模板：编译期求和
template<typename... Args>
struct Sum;

template<typename T>
struct Sum<T> {
    static constexpr T value = T{};
};

template<typename T, typename... Rest>
struct Sum<T, Rest...> {
    static constexpr T value = T{} + Sum<Rest...>::value;
};

// 别名模板简化元函数
template<typename T>
using RemoveConst = typename std::remove_const<T>::type;

// SFINAE 配合 trailing return type
template<typename T>
auto get_size(const T& c) -> decltype(c.size()) {
    return c.size();
}

// static_assert 编译期断言
static_assert(Sum<int, 1, 2, 3, 4>::value == 10, "Sum failed");
static_assert(std::is_same<RemoveConst<const int>, int>::value, "RemoveConst failed");

// C++14 变量模板与 constexpr
#include <type_traits>

// 变量模板：替代传统元函数的 ::value
template<typename T>
constexpr bool is_pointer_v = false;

template<typename T>
constexpr bool is_pointer_v<T*> = true;

// constexpr 函数支持循环
constexpr int factorial(int n) {
    int r = 1;
    for (int i = 2; i <= n; ++i) r *= i;
    return r;
}

static_assert(factorial(5) == 120, "factorial failed");
static_assert(is_pointer_v<int*>, "is_pointer failed");
static_assert(!is_pointer_v<int>, "is_not_pointer failed");

// C++17 折叠表达式
#include <iostream>

// 一元右折叠：(args + ...)
template<typename... Args>
auto sum(Args... args) {
    return (args + ...);  // 等价于 ((arg1 + arg2) + arg3) + ...
}

// 一元左折叠：(... + args)
template<typename... Args>
auto left_sum(Args... args) {
    return (... + args);  // 等价于 arg1 + (arg2 + arg3) + ...
}

// 二元右折叠：(args + ... + init)
template<typename... Args>
auto sum_with_init(Args... args) {
    return (args + ... + 0);  // 空包时返回 0
}

// 折叠与逻辑运算
template<typename... Args>
bool all_positive(Args... args) {
    return (... && (args > 0));  // 全部为正
}

// constexpr if 简化 SFINAE
template<typename T>
void process(T x) {
    if constexpr (std::is_integral_v<T>) {
        std::cout << "integral: " << x << std::endl;
    } else if constexpr (std::is_floating_point_v<T>) {
        std::cout << "float: " << x << std::endl;
    } else {
        std::cout << "other" << std::endl;
    }
}

// C++20 Concepts 全景
#include <concepts>
#include <iostream>

// 命名概念
template<typename T>
concept Addable = requires(T a, T b) {
    { a + b } -> std::convertible_to<T>;
    { a - b } -> std::convertible_to<T>;
};

// 多参数概念
template<typename From, typename To>
concept ConvertibleTo = std::convertible_to<From, To>;

// 复合概念
template<typename T>
concept Numeric = std::integral<T> || std::floating_point<T>;

template<typename T>
concept Arithmetic = Numeric<T> && requires(T a, T b) {
    { a + b } -> std::same_as<T>;
    { a * b } -> std::same_as<T>;
};

// 三种使用形式

// 形式 1：constrained type parameter
template<Arithmetic T>
T dot_product(const std::vector<T>& a, const std::vector<T>& b) {
    T result = T{};
    for (size_t i = 0; i < a.size(); ++i) result += a[i] * b[i];
    return result;
}

// 形式 2：requires 子句
template<typename T>
    requires Arithmetic<T>
T square(T x) { return x * x; }

// 形式 3：缩写形式
auto cube(Arithmetic auto x) { return x * x * x; }

// subsumption 实现重载排序
template<typename T>
    requires std::integral<T>
void describe(T) { std::cout << "integral\n"; }

template<typename T>
    requires std::signed_integral<T>
void describe(T) { std::cout << "signed integral\n"; }  // 更受约束，优先匹配

// C++23 Deducing this 简化 CRTP
#include <iostream>

// 传统 CRTP：需要 static_cast<Derived*>(this)
template<typename Derived>
struct OldCRTPBase {
    void interface() {
        static_cast<Derived*>(this)->implementation();
    }
};

// C++23 Deducing this：显式接收 self 参数
struct NewBase {
    // self 是推导出的 this，类型根据调用对象决定
    template<typename Self>
    void interface(this Self&& self) {
        std::forward<Self>(self).implementation();
    }
};

struct Derived : NewBase {
    void implementation() { std::cout << "Derived::impl\n"; }
};

// 按值类别重载
struct Logger {
    template<typename Self>
    void log(this Self&& self, const char* msg) {
        if constexpr (std::is_lvalue_reference_v<Self>) {
            std::cout << "[lvalue] " << msg << "\n";
        } else {
            std::cout << "[rvalue] " << msg << "\n";
        }
    }
};

int main() {
    Derived d;
    d.interface();  // 输出 "Derived::impl"

    Logger l;
    l.log("hello");          // [lvalue]
    std::move(l).log("bye"); // [rvalue]
    return 0;
}

// 类型代数的实现
#include <variant>
#include <utility>
#include <type_traits>

// Sum Type: A + B
template<typename A, typename B>
using Sum = std::variant<A, B>;

// Product Type: A × B
template<typename A, typename B>
using Product = std::pair<A, B>;

// 类型函数：将类型 T 映射到类型 List<T>
template<typename T>
struct List {
    struct Node {
        T value;
        Node* next;
    };
    Node* head = nullptr;
};

// 类型函数的「复合」：List<List<T>>
template<typename T>
using ListList = List<List<T>>;

// 类型上的「恒等函数」
template<typename T>
struct Identity { using type = T; };

// 类型上的「常量函数」
template<typename T, typename Ignored>
struct Constant { using type = T; };

// 编译期类型等价性证明
static_assert(std::is_same_v<Identity<int>::type, int>);
static_assert(std::is_same_v<Constant<double, int>::type, double>);

// Type Function 示例
#include <type_traits>

// 一元类型函数：移除引用
template<typename T>
struct RemoveReference {
    using type = T;
};

template<typename T>
struct RemoveReference<T&> {
    using type = T;
};

template<typename T>
struct RemoveReference<T&&> {
    using type = T;
};

// 二元类型函数：条件选择
template<bool Cond, typename IfTrue, typename IfFalse>
struct Conditional {
    using type = IfFalse;
};

template<typename IfTrue, typename IfFalse>
struct Conditional<true, IfTrue, IfFalse> {
    using type = IfTrue;
};

// 高阶类型函数：接收类型函数作为参数
template<template<typename> class F, typename T>
struct Apply {
    using type = typename F<T>::type;
};

// 使用
static_assert(std::is_same_v<RemoveReference<int&>::type, int>);
static_assert(std::is_same_v<RemoveReference<int&&>::type, int>);
static_assert(std::is_same_v<Conditional<true, int, double>::type, int>);
static_assert(std::is_same_v<Apply<RemoveReference, int&>::type, int>);

// SFINAE 立即上下文示例
#include <type_traits>

// 立即上下文：返回类型中的 SFINAE
template<typename T>
auto f(T x) -> decltype(x.foo(), int{}) {  // 若 x.foo() 不合法，SFINAE 剔除
    return 0;
}

template<typename T>
auto f(T x) -> decltype(x.bar(), int{}) {  // 备选重载
    return 1;
}

// 非立即上下文：函数体内的错误是硬错误
// template<typename T>
// void g(T x) {
//     x.nonexistent();  // 硬错误，不会被 SFINAE 容错
// }

// void_t 的魔法：将类型表达式纳入立即上下文
template<typename, typename = void>
struct has_foo : std::false_type {};

template<typename T>
struct has_foo<T, std::void_t<decltype(std::declval<T>().foo())>>
    : std::true_type {};

struct WithFoo { void foo() {} };
struct WithoutFoo {};

static_assert(has_foo<WithFoo>::value);
static_assert(!has_foo<WithoutFoo>::value);

// Concepts subsumption 形式化演示
#include <concepts>

// 原子约束
template<typename T>
concept HasPlus = requires(T a, T b) {
    { a + b } -> std::same_as<T>;
};

// 合取：C1 = HasPlus && std::copyable<T>
template<typename T>
concept AddableCopyable = HasPlus<T> && std::copyable<T>;

// C1 ⊢ HasPlus（C1 蕴含 HasPlus），故 C1 比 HasPlus 更受约束
// 重载时若两者均匹配，选择 C1 版本

template<typename T>
    requires HasPlus<T>
int priority(T) { return 1; }

template<typename T>
    requires AddableCopyable<T>
int priority(T) { return 2; }  // 优先匹配

// std::signed_integral ⊢ std::integral
template<typename T>
    requires std::integral<T>
void sort_tag(T) {}

template<typename T>
    requires std::signed_integral<T>
void sort_tag(T) {}  // 对 signed_integral 优先匹配

// 实例化空间演示
#include <type_traits>

// 二元 op：n^2 实例化空间
template<typename A, typename B>
struct BinaryOp {
    using result_type = decltype(std::declval<A>() + std::declval<B>());
};

// 三元 op：n^3 实例化空间
template<typename A, typename B, typename C>
struct TernaryOp {
    using result_type = decltype(
        std::declval<A>() + std::declval<B>() + std::declval<C>()
    );
};

// 用 type_traits 限制实例化爆炸
template<typename A, typename B>
    requires std::is_arithmetic_v<A> && std::is_arithmetic_v<B>
struct SafeBinaryOp {
    using result_type = decltype(std::declval<A>() + std::declval<B>());
};

// 递归深度测量
#include <cstdio>

template<int N>
struct Depth {
    static constexpr int value = Depth<N - 1>::value + 1;
};

template<>
struct Depth<0> {
    static constexpr int value = 0;
};

// 编译期计算：受 -ftemplate-depth 限制
constexpr int result = Depth<500>::value;
// Depth<900>::value 可能触发 "template recursion depth exceeded"

int main() {
    printf("Depth<500>::value = %d\n", result);
    return 0;
}
// 输出：Depth<500>::value = 500

// extern template 演示
// 头文件 myvec.h
template<typename T>
class MyVec {
    // 完整实现
};

// 显式实例化声明：告诉编译器「别处已实例化，不要重复」
extern template class MyVec<int>;
extern template class MyVec<double>;

// 源文件 myvec.cpp
#include "myvec.h"
// 显式实例化定义：在此处生成代码
template class MyVec<int>;
template class MyVec<double>;

// 类型级别的模式匹配
#include <type_traits>

// 模式：空列表
template<typename List>
struct IsEmpty {
    static constexpr bool value = false;
};

template<>
struct IsEmpty<TypeList<>> {  // 需先定义 TypeList（见后续章节）
    static constexpr bool value = true;
};

// 类型级别的 if-else
template<bool Cond, typename Then, typename Else>
struct TypeIf {
    using type = Then;
};

template<typename Then, typename Else>
struct TypeIf<false, Then, Else> {
    using type = Else;
};

// 类型列表（前向声明）
template<typename... Ts>
struct TypeList {};

// 使用 TypeIf
static_assert(std::is_same_v<
    TypeIf<true, int, double>::type, int>);
static_assert(std::is_same_v<
    TypeIf<false, int, double>::type, double>);

// Rust 泛型示例（对照参考）
fn max_of<T: PartialOrd>(a: T, b: T) -> T {
    if a > b { a } else { b }
}

// Rust Traits 比 C++ Concepts 更强大：可定义默认方法、关联类型
trait Container {
    type Item;
    fn get(&self, idx: usize) -> Option<&Self::Item>;
    fn len(&self) -> usize;
}

// Java 泛型示例（对照参考）
public class Box<T extends Comparable<T>> {
    private T value;
    public Box(T v) { value = v; }
    public T get() { return value; }
}

// 类型擦除：Box<Integer> 与 Box<String> 在运行时均为 Box
// 无法 new T()，无法 T[].class

-- Haskell Type Classes 示例（对照参考）
class Eq a where
    (==) :: a -> a -> Bool

instance Eq Int where
    x == y = x `primEqInt` y

-- 高阶类型
class Functor f where
    fmap :: (a -> b) -> f a -> f b

instance Functor Maybe where
    fmap _ Nothing = Nothing
    fmap f (Just x) = Just (f x)

// Zig comptime 示例（对照参考）
fn Matrix(comptime T: type, comptime rows: usize, comptime cols: usize) type {
    return struct {
        data: [rows][cols]T,
        const Self = @This();

        fn identity() Self {
            var m: Self = undefined;
            for (m.data) |*row, i| {
                for (row.*) |*cell, j| {
                    cell.* = if (i == j) 1 else 0;
                }
            }
            return m;
        }
    };
}

// D 模板示例（对照参考）
T max(T)(T a, T b) {
    return a > b ? a : b;
}

// 约束
T sum(T)(T[] arr) if (isNumeric!T) {
    T result = 0;
    foreach (e; arr) result += e;
    return result;
}

// 字符串混编
mixin("int x = 42;");

#include <iostream>
#include <vector>

// CRTP 基类
template<typename Derived>
struct ShapeBase {
    double area() const {
        return static_cast<const Derived*>(this)->area_impl();
    }
    double perimeter() const {
        return static_cast<const Derived*>(this)->perimeter_impl();
    }

    // 公共算法：模板方法模式
    void describe() const {
        std::cout << "Shape: area=" << area()
                  << ", perimeter=" << perimeter() << "\n";
    }
};

struct Circle : ShapeBase<Circle> {
    double r;
    Circle(double r) : r(r) {}
    double area_impl() const { return 3.14159 * r * r; }
    double perimeter_impl() const { return 2 * 3.14159 * r; }
};

struct Rectangle : ShapeBase<Rectangle> {
    double w, h;
    Rectangle(double w, double h) : w(w), h(h) {}
    double area_impl() const { return w * h; }
    double perimeter_impl() const { return 2 * (w + h); }
};

// CRTP + 混入（Mixin）
template<typename Derived>
struct Comparable : Comparable<Derived> {  // 注意：此处递归用 CRTP
    bool operator==(const Derived& other) const {
        return static_cast<const Derived*>(this)->compare_impl(other) == 0;
    }
    bool operator!=(const Derived& other) const {
        return !(*this == other);
    }
};

template<typename Derived>
struct Hashable {
    size_t hash() const {
        return static_cast<const Derived*>(this)->hash_impl();
    }
};

// 多重 CRTP 混入
struct MyType :
    Comparable<MyType>,
    Hashable<MyType> {
    int value;
    MyType(int v) : value(v) {}
    int compare_impl(const MyType& other) const {
        return value - other.value;
    }
    size_t hash_impl() const { return std::hash<int>{}(value); }
};

void test_crtp() {
    Circle c(1.0);
    Rectangle r(2.0, 3.0);
    c.describe();  // Shape: area=3.14159, perimeter=6.28318
    r.describe();  // Shape: area=6, perimeter=10
}

#include <cstddef>
#include <iostream>
#include <vector>

// Expression Templates 完整示例
template<typename E>
class VecExpr {
public:
    auto operator[](size_t i) const {
        return static_cast<const E&>(*this)[i];
    }
    size_t size() const {
        return static_cast<const E&>(*this).size();
    }
};

// 具体向量
template<typename T>
class Vec : public VecExpr<Vec<T>> {
    std::vector<T> data_;
public:
    Vec(std::initializer_list<T> il) : data_(il) {}
    explicit Vec(size_t n) : data_(n) {}

    T operator[](size_t i) const { return data_[i]; }
    T& operator[](size_t i) { return data_[i]; }
    size_t size() const { return data_.size(); }

    template<typename E>
    Vec& operator=(const VecExpr<E>& expr) {
        const E& e = static_cast<const E&>(expr);
        data_.resize(e.size());
        for (size_t i = 0; i < e.size(); ++i) {
            data_[i] = e[i];
        }
        return *this;
    }
};

// 二元表达式节点
template<typename L, typename R, typename Op>
class BinExpr : public VecExpr<BinExpr<L, R, Op>> {
    const L& l_;
    const R& r_;
    Op op_;
public:
    BinExpr(const L& l, const R& r, Op op = Op{})
        : l_(l), r_(r), op_(op) {}

    auto operator[](size_t i) const { return op_(l_[i], r_[i]); }
    size_t size() const { return l_.size(); }
};

// 运算符重载：返回表达式节点
template<typename L, typename R>
auto operator+(const VecExpr<L>& a, const VecExpr<R>& b) {
    return BinExpr<L, R, std::plus<>>(static_cast<const L&>(a), static_cast<const R&>(b));
}

template<typename L, typename R>
auto operator*(const VecExpr<L>& a, const VecExpr<R>& b) {
    return BinExpr<L, R, std::multiplies<>>(static_cast<const L&>(a), static_cast<const R&>(b));
}

void test_expr_templates() {
    Vec<double> a{1.0, 2.0, 3.0};
    Vec<double> b{4.0, 5.0, 6.0};
    Vec<double> c{7.0, 8.0, 9.0};
    Vec<double> d(3);

    d = a + b * c;  // 不产生临时对象，单次遍历求值
    // 输出: 29 42 57
    for (size_t i = 0; i < d.size(); ++i) {
        std::cout << d[i] << " ";
    }
    std::cout << "\n";
}

#include <iostream>
#include <mutex>
#include <memory>

// Policy: 线程策略
template<typename T>
struct SingleThreaded {
    struct Lock {
        Lock(const T&) {}
    };
};

template<typename T>
struct MultiThreaded {
    using Lock = std::lock_guard<std::mutex>;
    static std::mutex& mutex() {
        static std::mutex m;
        return m;
    }
};

// Policy: 创建策略
template<typename T>
struct CreateUsingNew {
    static T* Create() { return new T; }
    static void Destroy(T* p) { delete p; }
};

template<typename T>
struct CreateStatic {
    static T* Create() {
        static T instance;
        return &instance;
    }
    static void Destroy(T*) {}
};

// Policy: 生命周期策略
template<typename T>
struct DefaultLifetime {
    static void OnDeadReference() {
        throw std::runtime_error("dead reference");
    }
};

template<typename T>
struct PhoenixLifetime {
    static void OnDeadReference() {
        std::cout << "Phoenix: resurrecting\n";
    }
};

// 主类：组合所有策略
template<
    typename T,
    template<typename> class CreationPolicy = CreateUsingNew,
    template<typename> class LifetimePolicy = DefaultLifetime,
    template<typename> class ThreadingModel = SingleThreaded
>
class Singleton {
    static T* instance_;
    static bool destroyed_;
public:
    static T& Instance() {
        typename ThreadingModel<T>::Lock lock(ThreadingModel<T>::mutex());
        if (!instance_) {
            if (destroyed_) {
                LifetimePolicy<T>::OnDeadReference();
                destroyed_ = false;
            }
            instance_ = CreationPolicy<T>::Create();
        }
        return *instance_;
    }
    static void Destroy() {
        if (instance_) {
            CreationPolicy<T>::Destroy(instance_);
            instance_ = nullptr;
            destroyed_ = true;
        }
    }
};

template<typename T, template<typename> class C, template<typename> class L, template<typename> class M>
T* Singleton<T, C, L, M>::instance_ = nullptr;

template<typename T, template<typename> class C, template<typename> class L, template<typename> class M>
bool Singleton<T, C, L, M>::destroyed_ = false;

// 使用
struct Config {
    int value = 42;
};

void test_policy() {
    using ConfigSingleton = Singleton<Config, CreateStatic, DefaultLifetime, SingleThreaded>;
    std::cout << ConfigSingleton::Instance().value << "\n";  // 42
}

#include <iterator>
#include <vector>
#include <list>
#include <iostream>

// 通过 iterator_category tag 分发
template<typename Iter, typename Distance>
void advance_impl(Iter& it, Distance n, std::input_iterator_tag) {
    while (n > 0) { --n; ++it; }
}

template<typename Iter, typename Distance>
void advance_impl(Iter& it, Distance n, std::bidirectional_iterator_tag) {
    if (n > 0) while (n > 0) { --n; ++it; }
    else while (n < 0) { ++n; --it; }
}

template<typename Iter, typename Distance>
void advance_impl(Iter& it, Distance n, std::random_access_iterator_tag) {
    it += n;
}

template<typename Iter, typename Distance>
void advance(Iter& it, Distance n) {
    advance_impl(it, n, typename std::iterator_traits<Iter>::iterator_category{});
}

// C++17 constexpr if 替代
template<typename Iter, typename Distance>
void advance_modern(Iter& it, Distance n) {
    if constexpr (std::is_same_v<
            typename std::iterator_traits<Iter>::iterator_category,
            std::random_access_iterator_tag>) {
        it += n;
    } else if constexpr (std::is_same_v<
            typename std::iterator_traits<Iter>::iterator_category,
            std::bidirectional_iterator_tag>) {
        if (n > 0) while (n-- > 0) ++it;
        else while (n++ < 0) --it;
    } else {
        while (n-- > 0) ++it;
    }
}

void test_tag_dispatch() {
    std::vector<int> v{1, 2, 3, 4, 5};
    std::list<int> l{1, 2, 3, 4, 5};
    auto vit = v.begin();
    auto lit = l.begin();
    advance(vit, 3);   // random_access
    advance(lit, 3);   // bidirectional
    std::cout << *vit << " " << *lit << "\n";  // 4 4
}