函数模板

原理

模板实例化机制

编译器看到模板定义时不生成任何代码——仅进行第一阶段语法检查（括号匹配等与模板参数无关的检查）。只有当模板被调用（实例化）时，编译器才根据实际模板实参生成具体函数——此即第二阶段检查（实例化时检查）。

这个两阶段编译模型的核心：

第一阶段：检查非依赖名（不依赖模板参数的代码）
第二阶段：实例化时检查依赖名（依赖模板参数的代码）

template<typename T>
void foo(T x) {
 x.hello(); // 第二阶段检查（依赖名）
 int y = "abc"; // 第一阶段就报错（非依赖名）
}

编译期多态 vs 运行时多态

	模板（编译期多态）	虚函数（运行时多态）
绑定时机	编译期	运行时
实现机制	代码生成（实例化）	vtable 间接调用
性能	零运行时开销，可内联	额外解引用，不可内联
代码体积	每种实例化一份代码（代码膨胀）	一份函数体
灵活性	必须编译期确定类型	可运行时扩展

代码膨胀与去重

每种不同的模板参数组合产生一份独立的代码副本。同一个模板函数在多个编译单元中被实例化时，每个 .o 文件中都有一份机器码——链接器通过 COMDAT 折叠去重，最终只保留一份。

缓解策略：瘦模板技术（将不依赖模板参数的代码提取到非模板基类中）；类型擦除（用 void* 只实例化一次）；C++20 Concepts 约束实例化范围。

if constexpr 的编译期分支（C++17）

if constexpr 的条件在编译期求值，不满足条件的分支完全不被实例化——甚至连语法检查都不需要：

template<typename T>
auto format(const T& v) {
 if constexpr (std::is_integral_v<T>)
 return std::to_string(v); // 仅当 T 是整数时实例化
 else if constexpr (std::is_same_v<T, std::string>)
 return v; // 仅当 T 是 string 时实例化
}

SFINAE 与 enable_if

SFINAE（Substitution Failure Is Not An Error，替换失败不是错误）——模板参数替换失败时编译器不会报错，而是静默地跳过该候选函数。std::enable_if 利用此机制实现条件编译：

template<typename T>
typename std::enable_if<std::is_integral_v<T>, T>::type
safeDivide(T a, T b) { /* 整数版本 */ }
 
template<typename T>
typename std::enable_if<std::is_floating_point_v<T>, T>::type
safeDivide(T a, T b) { /* 浮点版本 */ }

模板参数推导规则

编译器根据函数调用表达式推导模板参数，遵循以下规则：

// 规则1：引用参数的推导保留引用
template<typename T> void f(T& x);
int a = 10;
f(a); // T = int，参数类型为 int&
 
// 规则2：const 属性保留
const int b = 20;
f(b); // T = const int，参数类型为 const int&
 
// 规则3：右值引用参数（转发引用）
template<typename T> void g(T&& x);
g(42); // T = int，参数类型为 int&&（转发引用绑定到右值）
int c = 30;
g(c); // T = int&，参数类型为 int& && = int&（折叠规则）
 
// 规则4：可变参数模板的推导
template<typename... Args> void h(Args... args);
h(1, 2.0, "hello"); // Args = {int, double, const char*}
 
// 规则5：指定模板参数时推导被跳过
template<typename T> T identity(T x) { return x; }
identity<int>(3.14); // T = int（显式指定），3.14 被截断为 3
// 不指定时：identity(3.14) → T = double
 
// 规则6：多参数推导的冲突报错
template<typename T> void k(T a, T b);
k(1, 2.0); // 错误：T 无法同时推导为 int 和 double

折叠表达式详解（C++17）

折叠表达式将参数包展开为二元运算表达式，有四种形式：

// 一元左折叠：(... op pack) → ((p1 op p2) op p3) ...
template<typename... Args>
auto sum(Args... args) { return (... + args); }
// sum(1, 2, 3, 4) → ((1 + 2) + 3) + 4
 
// 一元右折叠：(pack op ...) → (p1 op (p2 op (p3 op ...)))
template<typename... Args>
auto rsum(Args... args) { return (args + ...); }
// rsum(1, 2, 3, 4) → 1 + (2 + (3 + 4))
 
// 二元左折叠：(init op ... op pack) → ((init op p1) op p2) ...
template<typename... Args>
auto sub(Args... args) { return (0 - ... - args); }
// sub(1, 2, 3) → ((0 - 1) - 2) - 3
 
// 二元右折叠：(pack op ... op init)
template<typename... Args>
auto rsub(Args... args) { return (args - ... - 0); }
// rsub(1, 2, 3) → 1 - (2 - (3 - 0))
 
// 实用折叠表达式示例：
// 1. 打印所有参数
template<typename... Args>
void printAll(Args... args) {
    ((std::cout << args << " "), ...); // 逗号运算符折叠
}
 
// 2. 检查所有参数是否满足条件
template<typename... Args>
bool allPositive(Args... args) {
    return (... && (args > 0)); // 逻辑与折叠
}
 
// 3. 在容器中查找
template<typename T, typename... Args>
bool contains(const std::vector<T>& vec, Args... args) {
    return (... || std::find(vec.begin(), vec.end(), args) != vec.end());
}

Concepts（C++20）

Concepts 是对 SFINAE 的现代化替代，提供更清晰的约束语法：

// 定义 concept
template<typename T>
concept Numeric = std::is_arithmetic_v<T>;
 
template<typename T>
concept Container = requires(T t) {
    std::begin(t);
    std::end(t);
    t.size();
};
 
// 使用 concept 约束模板
template<Numeric T>
T add(T a, T b) { return a + b; }
 
// 等价的 requires 子句
template<typename T>
    requires Numeric<T>
T add2(T a, T b) { return a + b; }
 
// 复杂约束
template<typename T>
concept Sortable = requires(T t) {
    { t.begin() } -> std::input_or_output_iterator;
    { t.end() } -> std::input_or_output_iterator;
    requires std::totally_ordered<typename T::value_type>;
};
 
// if constexpr + concepts
template<typename T>
void process(T value) {
    if constexpr (Numeric<T>) {
        std::cout << "Number: " << value * 2 << std::endl;
    } else if constexpr (Container<T>) {
        std::cout << "Container size: " << value.size() << std::endl;
    }
}

可变参数模板的编译期递归展开

可变参数模板通过编译期递归展开：

template<typename T>
void print(T v) { cout << v << endl; } // 终止条件
 
template<typename T, typename... Args>
void print(T first, Args... rest) {
 cout << first << ", ";
 print(rest...); // 每次递归参数包减少一个
}

C++17 的折叠表达式简化了常用展开模式：

template<typename... Args>
auto sum(Args... args) { return (... + args); } // 一元左折叠

语法

函数模板

template<typename T>
T max(T a, T b) { return a > b ? a : b; }
 
// 隐式实例化
max(3, 7); // T = int
max(3.14, 2.71); // T = double
 
// 显式实例化
max<int>(5.5, 3.3); // T = int，浮点数截断

类模板

template<typename T>
class Stack {
 T* data; int top, cap;
public:
 void push(const T& v);
 T pop();
};
Stack<int> s; // 实例化

非类型模板参数

template<typename T, int N>
class Array {
 T data[N];
};
Array<int, 5> arr; // N 是编译期常量

模板特化：全特化与偏特化

// 通用模板
template<typename T> struct TypeInfo { static const char* name() { return "?"; } };
 
// 全特化
template<> struct TypeInfo<int> { static const char* name() { return "int"; } };
 
// 偏特化（仅针对指针类型）
template<typename T> struct TypeInfo<T*> {
 static const char* name() { return "ptr"; }
};

默认模板参数

template<typename T, typename Container = std::vector<T>>
class Queue { Container data; };

decltype 与 auto 返回类型

template<typename T1, typename T2>
auto add(T1 a, T2 b) -> decltype(a + b) { return a + b; }
 
// C++14：直接 auto 推导
template<typename T1, typename T2>
auto multiply(T1 a, T2 b) { return a * b; }

模板元编程

template<unsigned N>
struct Factorial {
 static constexpr auto value = N * Factorial<N - 1>::value;
};
template<> struct Factorial<0> { static constexpr auto value = 1; };
// Factorial<5>::value → 120（编译期计算）

实践

练习：第k小题（理解 nth_element 的模板设计），排序题题（模板版本的 sort 实现）。

练习

题号	题目	链接	知识点
P1001	A+B Problem	https://www.luogu.com.cn/problem/P1001	语法练习
P1023	tickets	https://www.luogu.com.cn/problem/P1023	语法练习
215	数组中的第K个最大元素	https://www.luogu.com.cn/problem/P1001	nth_element 模板化、快速选择
912	排序数组	https://www.luogu.com.cn/problem/P1001	模板化排序算法、泛型比较函数
347	前 K 个高频元素	https://www.luogu.com.cn/problem/P1001	模板化优先队列、堆操作
75	颜色分类	https://www.luogu.com.cn/problem/P1001	模板化双指针、泛型分区
23	合并K个升序链表	https://www.luogu.com.cn/problem/P1001	模板化优先队列（最小堆）
46	全排列	https://www.luogu.com.cn/problem/P1001	模板化回溯、泛型结果容器
39	组合总和	https://www.luogu.com.cn/problem/P1001	模板化回溯、可变参数剪枝
22	括号生成	https://www.luogu.com.cn/problem/P1001	模板化字符串构建、泛型验证
415	字符串相加	https://www.luogu.com.cn/problem/P1001	模板化大数运算、泛型数字处理
102	二叉树的层序遍历	https://www.luogu.com.cn/problem/P1001	模板化 BFS 队列、泛型层次遍历
543	二叉树的直径	https://www.luogu.com.cn/problem/P1001	模板化递归返回值、泛型树统计
124	二叉树中的最大路径和	https://www.luogu.com.cn/problem/P1001	模板化递归、泛型路径计算
236	二叉树的最近公共祖先	https://www.luogu.com.cn/problem/P1001	模板化递归、泛型树搜索

RootStack

探索

09_函数模板

函数模板

原理

模板实例化机制

编译期多态 vs 运行时多态

代码膨胀与去重

if constexpr 的编译期分支（C++17）

SFINAE 与 enable_if

模板参数推导规则

折叠表达式详解（C++17）

Concepts（C++20）

可变参数模板的编译期递归展开

语法

函数模板

类模板

非类型模板参数

模板特化：全特化与偏特化

默认模板参数

decltype 与 auto 返回类型

模板元编程

实践

练习

关系图谱

目录

反向链接