Runguo Li

Runguo Li

M.S. student in Information Science @ UIUC, advised by Prof. Minjia Zhang. Working on ML systems for large-scale models: MoE inference and expert streaming, distributed training and rollout, GPU compiler correctness.

Lecture 10 (Week 5 - Thursday): 函数模板 (Function Templates)

目录 · ← l9 · l11 →

Lecture 10 (Week 5 - Thursday): 函数模板 (Function Templates)

概述

上一讲我们学会了”模板类”——为任意类型生成类代码的蓝图；本讲把同一思想延伸到函数：模板函数（function template） 让 min、find 这样的算法对任何类型自动生成对应版本，编译器像工厂一样按需”打印”出具体函数。课程依次介绍模板函数的显式/隐式实例化、基于模板的泛型 find（它正是 STL <algorithm> 中所有算法的雏形）、C++20 Concepts（在实例化之前约束模板参数、改善报错信息）、可变参数模板（variadic templates，用参数包支持任意数量实参），以及模板元编程（编译期递归实例化计算阶乘/斐波那契）与 constexpr/consteval。学完本讲，你就能读懂 STL 算法的签名，也为下一讲 lambda 与 ranges 打下基础。

核心特性与语法详解

1. 模板函数（Template Functions）

  • 定义与目的：用 template <typename T> 前缀声明一个”函数蓝图”，T 是类型占位符。调用时编译器用具体类型替换 T，生成真正的函数。目的：消除为每种类型重复编写相同逻辑的重载代码，实现代码生成自动化。
  • 核心语法：template <typename T> T min(T a, T b);——声明模板函数；template <typename T> T min(const T& a, const T& b);——按 const 引用传参，避免复制。
  • 设计意图与最佳实践：模板本身不是函数，min<std::string> 才是一个函数（称为一次实例化，instantiation）。模板像工厂：喂进类型，产出函数。实践中模板声明与定义都要放在头文件中（否则链接期找不到实例化代码）；对大对象（如 std::string）优先用 const T& 参数。

2. 显式实例化与隐式实例化

  • 定义与目的：两种”告诉编译器 T 是什么”的方式。显式实例化由程序员指定类型，隐式实例化由编译器从实参推导。
  • 核心语法：
    • 显式：min<int>(106, 107);——与模板类 vector<int> 的写法一致。
    • 隐式：min(106, 107);——编译器推导出 T = int，等价于 min<int>(106, 107)，就像 auto number = 106; 让编译器推断类型。
  • 设计意图与最佳实践：日常优先隐式实例化（更简洁）；当推导失败或结果有歧义时（字符串字面量、混合类型实参），显式实例化是可靠的退路。

3. 泛型算法思想：以 find 为例

  • 定义与目的：把 find 写成模板，参数类型为”迭代器”而不是具体容器，从而一套实现通用于 vector、set、unordered_map 等所有容器。
  • 核心语法：template <typename Iterator, typename TElem> Iterator find(Iterator begin, Iterator end, TElem value);
  • 设计意图与最佳实践：<algorithm> 里每个算法都是这样的模板函数。只依赖迭代器协议（*it、++it、it != end、*it == value），不关心容器内部结构。这也是为什么 std::find 是 find(first, last, value) 而不是 find(container, value)——传迭代器可以只搜索容器的一部分（子区间）。

4. Concepts（C++20）

  • 定义与目的：给模板参数加约束的命名集合。没有约束时，min<StanfordID> 会先被实例化、然后在函数体内报出”invalid operands to binary expression”这种令人困惑的错误（错误只出现在实例化之后）；有了 concept，约束不满足时根本不实例化，直接给出清晰信息，同时提升 IDE 支持。
  • 核心语法：
    template <typename T>
concept Comparable = requires(const T a, const T b) {
  { a < b } -> std::convertible_to<bool>;   // 约束：a < b 必须合法且结果可转 bool
};
template <Comparable T> T min(const T& a, const T& b);      // 简写
template <typename T> requires Comparable<T> T min(const T& a, const T& b);  // 等价写法
  • 设计意图与最佳实践：C++ 一直在补 Java（T extends Comparable<T>）、C#（where T : IComparable）早就有的”泛型约束”能力。标准库自带大量 concept：std::convertible_to、std::input_iterator、std::ranges::range 等。注意 STL 目前尚未全面使用 concepts。

5. 可变参数模板（Variadic Templates）

  • 定义与目的：让函数接受任意数量、任意类型的实参（如 min(2.4, 7.5, 5.3, 1.2, 3.4) 或 Python 风格 format）。原理是”模板 + 递归”：编译器在实例化时自动生成所需数量的重载。
  • 核心语法：
    template <Comparable T>
T min(const T& v) { return v; }                        // 基例：终止递归
template <Comparable T, Comparable... Args>            // Args 是类型参数包
T min(const T& v, const Args&... args) {               // args 是函数参数包
  auto m = min(args...);                               // 包展开：替换为实际参数
  return v < m ? v : m;
}
  • 设计意图与最佳实践：参数包可以匹配 0 个或多个类型；args... 在调用点被展开成逗号分隔的实际参数列表。必须有基例（base case）终止递归。各参数类型不必相同（如 format("{} {}", "Rhaenyra", 7)），但递归写法中返回类型通常由第一个参数决定，需要混合类型时要显式实例化。

6. 模板元编程（TMP）与 constexpr/consteval

  • 定义与目的：利用”模板在编译期实例化”这一事实，在编译期完成计算，把结果烘焙进可执行文件，运行时零开销。TMP 是图灵完备的，Boost.MPL 等库用”类型组成的 vector”做策略式设计（policy-based design）。
  • 核心语法：递归模板结构 + 模板特化基例；C++20 起用 constexpr（”请尽量在编译期运行”）与 consteval（”必须在编译期运行”）函数代替晦涩的模板结构。
  • 设计意图与最佳实践：先考虑 constexpr/consteval（可读、是 C++20 对 TMP 的”制度化”），只有需要操作类型本身时才写传统 TMP。

代码示例与逐步解说（核心）

示例 1：min 的三种形态与显式/隐式实例化（C++17）

代码

#include <iostream>
#include <string>

// 形态一：按值传参，简单但会复制实参
template <typename T>
T min_basic(T a, T b) { return a < b ? a : b; }

// 形态二：按 const 引用传参，避免复制，最常用
template <typename T>
T min_ref(const T& a, const T& b) { return a < b ? a : b; }

// 形态三：允许两个实参类型不同，返回类型交给编译器推导
template <typename U, typename V>
auto min_flex(const U& a, const V& b) { return a < b ? a : b; }

int main() {
  // 显式实例化：手动指定类型
  int m1 = min_basic<int>(106, 107);
  double m2 = min_basic<double>(42.5, 3.14);

  // 隐式实例化：编译器从实参推导 T
  int m3 = min_ref(106, 107);                     // 等价于 min_ref<int>(106, 107)

  // 字符串字面量是 const char*，必须显式实例化才能得到字符串比较
  std::string s = min_ref<std::string>("Arwen", "Aragorn");

  // 混合类型：U = int, V = double，返回类型由三元运算符推导为 double
  auto m4 = min_flex(106, 107.5);

  std::cout << m1 << " " << m2 << " " << m3 << " "
            << s << " " << m4 << "\n";            // 106 3.14 106 Aragorn 106
}

代码做什么：定义了 min 的三种模板形态，分别演示显式实例化（min_basic<int>）、隐式实例化（min_ref(106, 107)）、多类型参数（min_flex(106, 107.5)），最后打印结果。

特性机制解说：min_ref(106, 107) 中，编译器把实参类型代入形参 const T& 反向推导出 T = int，与 auto 的推导思路完全一致。显式实例化则直接替换：min_ref<std::string>("Arwen", "Aragorn") 中 T = std::string，两个 const char* 字面量在绑定 const std::string& 时隐式转换为 std::string。min_flex 的 auto 返回类型在函数体确定后才推导——a < b ? a : b 中 int 与 double 的三元表达式公共类型是 double，故返回 double。注意形态一按值传参会复制整个对象，形态二只复制引用——对 std::string 这类大对象，性能差异明显（课堂代码 main.cpp 里 min_basic/min_ref/min_flex 正是这三个版本）。

示例 2：泛型 find——一套代码服务所有容器（C++17）

代码

#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>

// 泛型 find：对任何"迭代器对 + 值"都成立
template <typename It, typename T>
It my_find(It begin, It end, const T& value) {
  for (auto it = begin; it != end; ++it)
    if (*it == value) return it;
  return end;                       // 找不到返回 end
}

int main() {
  std::vector<int> v { 1, 2, 3, 4, 5 };
  auto it1 = my_find(v.begin(), v.end(), 3);
  if (it1 != v.end()) *it1 = 107;   // v = {1, 2, 107, 4, 5}

  std::unordered_set<std::string> us { "hello", "welcome", "cs106l!" };
  auto it2 = my_find(us.begin(), us.end(), "welcome");

  std::cout << v[2] << "\n";                    // 107
  std::cout << (it2 == us.end() ? "not found" : "found") << "\n";  // found
}

代码做什么：手写一个不依赖任何具体容器的 find，先在一个 vector<int> 中找到 3 并改写为 107，再在 unordered_set<string> 中查找 “welcome”，两处调用共用同一份模板实现。

特性机制解说：第一次调用推导 It = std::vector<int>::iterator、T = int；第二次推导 It = std::unordered_set<std::string>::iterator、T = std::string。模板体只依赖迭代器协议（*it、++it、!=、==），所以只要类型满足这四点即可实例化——这正是 STL 算法的设计哲学：用迭代器把算法与容器解耦。课堂代码里该函数叫 find 并放在全局命名空间，调用时必须写 ::find(...)，因为实参（std::vector<int>::iterator）位于 std 命名空间，触发 ADL（实参依赖查找） 后编译器更倾向选择 std::find——这是取名时值得注意的细节（此处改名 my_find 规避）。另外，传迭代器对而非容器，让我们能只搜索子区间，例如 find(v.begin() + 1, v.end() - 1, 106)。

示例 3：用 Concepts 约束模板（C++20）

代码

#include <concepts>
#include <iostream>
#include <sstream>
#include <string>
#include <type_traits>

// 定义 concept：T 的 < 运算必须合法且结果可转换为 bool
template <typename T>
concept Comparable = requires(const T a, const T b) {
  { a < b } -> std::convertible_to<bool>;
};

// 简写语法：模板参数表里直接放 concept 名
template <Comparable T>
T min_c(const T& a, const T& b) { return a < b ? a : b; }

int main() {
  std::cout << min_c(10, 20) << "\n";                        // 20
  std::cout << min_c<std::string>("a", "b") << "\n";         // a

  // 编译期检查类型是否满足 concept
  static_assert(Comparable<int>);
  static_assert(!Comparable<std::stringstream>);  // stringstream 没有 operator<

  // 若取消注释，会得到"约束未满足"的清晰报错，而不是函数体内的难懂错误：
  // min_c(std::stringstream(), std::stringstream());
}

代码做什么：定义 Comparable concept 并用它约束 min_c，随后用 static_assert 在编译期验证 int 满足、std::stringstream 不满足该 concept。

特性机制解说：requires(const T a, const T b) { ... } 是一个 requires 表达式——花括号内每一条”约束”（constraint）都必须能通过编译；{ a < b } -> std::convertible_to<bool> 额外要求表达式的结果类型满足 std::convertible_to<bool>（convertible_to 本身也是一个 concept）。约束检查发生在实例化之前：min_c(std::stringstream(), ...) 会因为不满足 Comparable 而直接拒绝重载解析，报错信息点明”约束未满足”，远好于过去先实例化 min<StanfordID>、再在函数体 return a < b ? a : b; 处报 invalid operands（幻灯片展示了两种报错的对比）。课堂代码还用 if constexpr (Comparable<T>) 在编译期分支输出”是否满足”，展示了 concept 可作为编译期布尔值使用。

示例 4：可变参数 min——编译器替我们写重载（C++20）

代码

#include <concepts>
#include <iostream>
#include <string>

// 定义 Comparable concept（见示例 3）：要求 T 支持 a < b 且结果可转 bool
template <typename T>
concept Comparable = requires(const T a, const T b) {
    { a < b } -> std::convertible_to<bool>;
};

template <Comparable T>
T min_v(const T& v) { return v; }        // 基例：单个元素就是最小值

template <Comparable T, Comparable... Args>
T min_v(const T& v, const Args&... rest) {
  auto m = min_v<T>(rest...);            // 包展开 + 显式实例化，保持类型一致
  return v < m ? v : m;
}

int main() {
  std::cout << min_v(2, 7, 5, 1) << "\n";                       // 1
  std::cout << min_v<std::string>("cool", "variadic", "template!") << "\n";
  std::cout << min_v(10, 2.5, 3.0f) << "\n";      // 2：第一个参数决定返回类型！
  std::cout << min_v<double>(10, 2.5, 3.0f) << "\n";  // 2.5：显式实例化得到正确结果
}

代码做什么：用”基例 + 递归实例化”实现任意个数的 min，并演示混合类型时显式实例化（min_v<double>）的作用。

特性机制解说：调用 min_v(2, 7, 5, 1) 时，编译器选择递归模板并推导 T = int、Args = [int, int, int]，即实例化 min<int, int, int, int>；其函数体里的 min_v<T>(rest...) 被包展开为 min_v<int>(a0, a1, a2)——注意展开发生在编译期，rest... 被替换成逗号分隔的实参列表。这一调用又实例化 min<int, int, int>，依次递推：min<int, int> → min<int>，直到匹配基例 min_v(const T& v)（单参数、非变参、更特化，编译器总是选择最特化的模板）。于是一次 min_v(2, 7, 5, 1) 让编译器自动生成了 4 个重载，正是幻灯片”Templates + recursion = code generation”的体现。类型方面：递归调用显式写 min_v<T> 强制每次都用同一类型 T，所以 min_v(10, 2.5, 3.0f) 把一切都按 int 比较（结果为 2）；想要真正按 double 比较必须 min_v<double>(...)。可变参数模板的另一个经典应用是 format 式的异构参数函数（幻灯片实现了 Python 风格 f-string 打印器，Args 中每个类型可以不同）。

示例 5：编译期计算——TMP 与 constexpr/consteval（C++20）

代码

#include <iostream>

// 传统模板元编程：递归实例化 + 模板特化基例
template <size_t N>
struct Factorial {
  enum { value = N * Factorial<N - 1>::value };
};
template <>
struct Factorial<0> {           // 全特化：N = 0 的基例
  enum { value = 1 };
};

// constexpr：编译器"尽量"在编译期求值（C++14 起函数体可递归）
constexpr size_t factorial_cx(size_t n) {
  if (n == 0) return 1;
  return n * factorial_cx(n - 1);
}

// consteval：强制在编译期求值（C++20）
consteval size_t factorial_ce(size_t n) {
  if (n == 0) return 1;
  return n * factorial_ce(n - 1);
}

int main() {
  std::cout << Factorial<7>::value << "\n";   // 5040，编译期算好
  constexpr auto a = factorial_cx(7);         // 编译期求值
  auto b = factorial_cx(7);                   // 运行期求值也可以
  constexpr auto c = factorial_ce(7);         // 必须是编译期
  std::cout << a << " " << b << " " << c << "\n";
}

代码做什么：三种方式在编译期计算 7 的阶乘 5040：模板元编程（Factorial<7>）、constexpr 函数、consteval 函数。

特性机制解说：Factorial<7>::value 触发实例化链 Factorial<7> → Factorial<6> → … → Factorial<0>（特化基例给出 value = 1），随后逐层回填：1、2、6、24、120、720、5040。整条链发生在编译期，幻灯片展示的汇编显示结果直接以常量 mov esi, 5040 烘焙进可执行文件，运行时零开销。constexpr 是”尽力而为”——只要上下文需要常量表达式（如 constexpr auto a）就在编译期算；consteval 是”强制执行”——任何运行期调用都是编译错误。同类例子还有斐波那契（需要 Fibonacci<0> 与 Fibonacci<1> 两个特化基例：value = Fibonacci<N-1>::value + Fibonacci<N-2>::value）。一句话总结两者定位：constexpr 是”亲爱的编译器，请尽量在编译期跑我 😘”，consteval 是”你必须给我在编译期跑 🤬”。传统 TMP 语法晦涩（enum、BOOST_PP_* 宏满天飞），所以幻灯片建议：能写 constexpr/consteval 就别写 TMP。

与旧标准（如C++98）的对比

  • 函数模板本身：C++98 就有，template <typename T> T min(T a, T b); 在 C++98 下同样成立——本讲的实例化机制是经典特性，不是新东西。
  • Concepts：C++98/11/14/17 完全无对应物。过去只能用 SFINAE（std::enable_if）等”黑魔法”实现约束，报错信息晦涩难懂；C++20 的 concept/requires 是第一个一等公民的约束语法。C++98 里 std::set<StanfordID> 报出的错误会绵延数百行，如今一句话点明”约束未满足”。
  • 可变参数模板：C++11 引入。C++98 只能靠 C 风格 ...（如 printf，类型不安全）或手写 N 个重载（幻灯片里写到第 7 个重载时直接放弃）。C++11 起 Args... 参数包 + 递归实例化把这件事类型安全地自动化。
  • 模板元编程：恰恰是 C++98 时代的产物（模板特化 + enum 技巧），但语法痛苦；constexpr 从 C++11 引入（早期函数体限制多、几乎只能写单条 return），C++14 放开循环/递归，consteval 是 C++20 新增。可以说现代 C++ 用 constexpr/consteval “收编”了 TMP 的常用场景。

关键要点

  • 模板 ≠ 函数：模板是生成函数的工厂，min<T> 的实例化才是函数；编译器按需自动生成代码。
  • 默认用隐式实例化，模糊时显式实例化：min(106, 107) 与 min<int>(106, 107) 等价；字符串字面量、混合类型等推导出歧义时，显式实例化是你的救生圈。
  • Concepts 在实例化之前检查约束：template <Comparable T> 让报错信息与 IDE 体验大幅改善，是 C++20 写泛型代码的默认姿势。
  • 可变参数模板 = 基例 + 递归实例化 + 包展开：args... 在编译期展开为实参列表，编译器自动生成所需数量的重载。
  • 需要编译期计算时：优先 constexpr（尽量）或 consteval（强制），传统 TMP（模板特化 + enum）留给操作类型的场景。

常见陷阱与注意事项

  • 字符串字面量隐式实例化为 const char*：min("Preston", "Rachel") 推导出 T = const char*，a < b 变成指针比较（比地址而非字典序）——Bjarne 式摇头现场。改法：显式 min<std::string>(...)。
  • 混合类型实参无法推导：min_ref(106, 3.14) 中 T 既可能是 int 又可能是 double，编译失败。改法：双类型参数 + auto 返回（min_flex），或显式实例化 min<double>(106, 3.14)。
  • 忘记递归基例：可变参数模板没有单参数基例时，递归实例化永不终止，编译期爆炸（报错递归深度超限）。
  • 模板定义放进 .cpp 文件：模板只有被使用时才实例化，定义在别的翻译单元里会”链接期找不到符号”。模板（声明+定义）应放在头文件中。
  • 与 STL 同名冲突（ADL）：自己写 find 且参数是 std 容器迭代器时，ADL 会把调用解析到 std::find；要么改名，要么写 ::find(...) 强制走全局命名空间。
  • 不满足概念的类型也会被”实例化后才发现错误”：没有 concepts 时 min<StanfordID> 会先实例化、再在 a < b 处报错——这正是下一讲/再下一讲运算符重载要解决的问题。

关联作业提示

本讲与 A4: Ispell（拼写检查器）直接相关。A4 要求你完全不用 for/while 循环，只靠 STL 算法与 ranges 完成 tokenize 和 spellcheck，而这一切都建立在模板之上：

  • 讲义提供的 find_all 本身就是一个模板函数：template <typename Iterator, typename UnaryPred> std::vector<Iterator> find_all(Iterator begin, Iterator end, UnaryPred pred);——本讲”泛型 find”的思想让你立刻理解它的签名与行为（返回所有满足谓词的迭代器，含 begin/end 边界）。
  • tokenize 中用到的 std::transform、std::erase_if 都是 <algorithm> 里的模板函数，理解”实例化”帮助你读懂它们为何能对任意容器/迭代器生效。
  • spellcheck 中 ranges 版本的 std::ranges::views::filter/transform 是受约束算法（内部用 concepts 声明 input_range），本讲 concepts 知识帮助你读懂其报错。
  • A4 的 Corpus = std::set<Token> 要求 Token 具备 operator<（由讲义提供）——等学到 Lecture 12 运算符重载后，你会明白这背后的设计动机。