Templates - Be Happy Every Day

概述#

Template（模板） 是 C++ 泛型编程的基础。它解决的问题是：当多份代码的逻辑相同，只有处理的数据类型不同，就把“类型”也做成参数，由编译器在需要时生成具体版本。

主要内容：

function overloading 与 default arguments；
为什么需要 templates，以及不用 templates 的几种替代方案；
function template 的定义、实例化、类型推导和重载规则；
class template 的定义、使用、成员函数写法；
multiple type parameters、nested templates、non-type parameters；
member templates；
templates 与 inheritance 的组合；
CRTP：用模板模拟一种静态多态；
模板代码为什么通常写在 header file 中。

模板的核心思想：不变的是算法或类的逻辑，变化的是类型。把变化的类型参数化，就能在保持类型安全的前提下复用代码。

目录#

概述
目录
Function overloading
- 基本概念
- Overload and auto-cast
Default arguments
- 默认参数的含义
- 默认参数必须从右往左给
Why templates?
Function templates
Class templates
更复杂的模板参数
Member templates
- 跨类型 complex 构造
Templates and inheritance
CRTP
模板代码放在哪里
写模板的建议流程

Function overloading#

基本概念#

Function overloading（函数重载） 指：多个函数可以拥有同一个函数名，但参数表必须不同。

参数表包括：

参数个数；
参数类型；
参数顺序。

返回值类型不能单独用来区分重载函数。

例子：

1
void print(char* str, int width); // #1
2
void print(double d, int width);  // #2
3
void print(long l, int width);    // #3
4
void print(int i, int width);     // #4
5
void print(char* str);            // #5
6

7
print("Pancakes", 15); // #1
8
print("Syrup");        // #5
9
print(1999.0, 10);     // #2
10
print(1999, 12);       // #4
11
print(1999L, 15);      // #3

调用时，编译器根据实参列表选择最合适的函数版本。

函数重载的意义是：把一组语义相同或相似的操作组织成同一个名字。这样使用者只需要记住一个概念性的函数名，具体版本由编译器选择。

Overload and auto-cast#

普通函数重载允许发生一定程度的 implicit conversion（隐式类型转换）。

1
void foo(int i) {}
2
void foo(double d) {}
3

4
int main() {
5
    foo(2);       // exact match: foo(int)
6
    foo(2.3);     // exact match: foo(double)
7
    foo('a');     // char -> int，通常调用 foo(int)
8
    foo(3.2f);    // float -> double，通常调用 foo(double)
9
    // foo(2L);   // long 到 int / double 可能都可行，容易产生 ambiguous call
10
}

注意：

foo(2) 直接匹配 int；
foo(2.3) 直接匹配 double；
foo('a') 中 char 到 int 更自然；
foo(3.2f) 中 float 到 double 更自然；
foo(2L) 可能出现二义性，因为 long 转 int 和转 double 都可能被认为可行。

TIP
普通函数重载可以依赖隐式转换，但隐式转换可能带来二义性。写代码时尽量让调用意图清晰，必要时使用显式类型转换。

Default arguments#

默认参数的含义#

Default argument（默认参数） 是写在函数声明中的默认值。当函数调用时少传了一部分参数，编译器会自动把缺失的参数补上。

1
int harpo(int n, int m = 4, int j = 5);
2

3
int beeps;
4
beeps = harpo(2);      // 等价于 harpo(2, 4, 5)
5
beeps = harpo(1, 8);   // 等价于 harpo(1, 8, 5)
6
beeps = harpo(8, 7, 6); // 三个参数都显式给出

默认参数的重点：

默认值写在 declaration（声明）处；
调用时由编译器补齐；
函数本体仍然只有一个版本；
default arguments 与 function overloading 的机制不同。

可以理解为：

1
harpo(2);

在编译器看来会被补成：

1
harpo(2, 4, 5);

函数定义本身仍然接收三个参数。

默认参数必须从右往左给#

默认参数必须从参数列表右端开始连续提供。

1
int chico(int n, int m = 6, int j); // illegal
2
int groucho(int k = 1, int m = 2, int n = 3); // ok

原因是：调用时实参按从左到右匹配。若中间参数有默认值，右边参数没有默认值，编译器无法判断用户省略的是哪一个参数。

Why templates?#

问题背景#

假设现在需要：

1
list of X
2
list of Y

两者都是线性表，操作逻辑完全一样：

插入；
删除；
遍历；
查找；
取第 i 个元素。

差异只在于元素类型不同。

如果没有泛型能力，就需要为 X 和 Y 各写一份 list 代码。代码逻辑重复，维护困难。

不用模板的几种做法#

1. Clone the code#

直接复制代码，为不同类型写不同版本。

优点：

类型安全；
代码直观。

缺点：

重复代码多；
后续修改必须同步改多份；
某一份漏改就会出现行为不一致。

重复代码通常是设计上的坏味道。

2. Make a common base class#

把所有对象都继承自某个公共基类，例如 Object，然后写 list<Object*>。

问题：

需要统一继承体系；
对某些类型并不合适；
可能引入运行时开销；
使用时经常需要向下转型。

3. Untyped lists#

类似 C 语言风格，用 void* 抹掉类型信息。

问题：

类型不安全；
需要大量显式类型转换；
编译器无法帮你检查元素类型是否正确。

模板的基本思想#

模板的做法是：

把变化的类型抽象成参数。

类比普通函数：

1
int add(int x, int y) {
2
    return x + y;
3
}

这里不变的是加法逻辑，变化的是输入值，所以把值做成参数。

模板中，不变的是算法或类的逻辑，变化的是类型，所以把类型做成参数。

1
template<typename T>
2
class List {
3
    // 用 T 表示元素类型
4
};

标准库中大量使用模板：

function template：例如 std::sort；
class template：例如 std::vector<T>、std::list<T>、std::stack<T>、std::queue<T>。

Function templates#

从 swap 开始#

如果只交换两个 int：

1
void swap_int(int& x, int& y) {
2
    int temp = x;
3
    x = y;
4
    y = temp;
5
}

如果还想交换 float、string、Currency、Person，逻辑完全一样，只是类型不同。

用函数模板可以写成：

1
template<typename T>
2
void my_swap(T& x, T& y) {
3
    T temp = x;
4
    x = y;
5
    y = temp;
6
}

完整例子：

1
#include <iostream>
2
#include <string>
3
using namespace std;
4

5
template<typename T>
6
void my_swap(T& x, T& y) {
7
    T temp = x;
8
    x = y;
9
    y = temp;
10
}
11

12
int main() {
13
    int a = 2, b = 5;
14
    cout << a << "," << b << endl;
15
    my_swap(a, b);
16
    cout << a << "," << b << endl;
17

18
    float fa = 3.14f, fb = 11.9f;
19
    cout << fa << "," << fb << endl;
20
    my_swap(fa, fb);
21
    cout << fa << "," << fb << endl;
22

23
    string sa = "hello", sb = "world";
24
    cout << sa << "," << sb << endl;
25
    my_swap(sa, sb);
26
    cout << sa << "," << sb << endl;
27
}

这个模板对 T 有隐含要求：

T 可以被 copy construction；
T 可以被 copy assignment。

因为函数体中有：

1
T temp = x;
2
x = y;
3
y = temp;

如果某个类型禁止拷贝或赋值，这个模板在该类型上实例化时会编译失败。

模板语法#

1
template<typename T>
2
void my_swap(T& x, T& y) {
3
    T temp = x;
4
    x = y;
5
    y = temp;
6
}

各部分含义：

template：声明接下来是模板；
typename T：声明一个类型参数 T；
class T 与 typename T 在这种场景下等价；
函数体中可以把 T 当作普通类型名使用。

类型参数可以出现在：

函数参数类型；
函数返回值类型；
函数内部局部变量类型。

例如：

1
template<typename T>
2
T max_value(T a, T b) {
3
    T result = (a < b) ? b : a;
4
    return result;
5
}

这里 T 同时出现在参数、返回值和局部变量中。

实例化#

模板本身是一个“板子”，不是最终运行的函数代码。只有当具体类型被用到时，编译器才会根据模板生成真实函数。

这个过程叫 template instantiation（模板实例化）。

例如：

1
int i = 3, j = 4;
2
my_swap(i, j); // 生成 my_swap<int>
3

4
float x = 4.5f, y = 3.7f;
5
my_swap(x, y); // 生成 my_swap<float>
6

7
string s = "Hello", t = "World";
8
my_swap(s, t); // 生成 my_swap<string>

编译器会生成三个具体函数版本：

1
my_swap<int>
2
my_swap<float>
3
my_swap<string>

汇编层面的结果：当 int、float、string 都调用了 my_swap，编译器会生成三个版本；如果某个类型没有被调用，对应版本就不会生成。

这和普通函数不同：普通函数定义出来以后就是一个实体，模板函数只有在具体类型被使用时才实例化。

TIP
模板的类型检查主要发生在实例化阶段。模板定义本身可能看起来没问题，但一旦用某个不满足要求的类型实例化，才会报错。

模板参数推导#

函数模板调用时，编译器会根据实参类型推导模板参数。

1
template<typename T>
2
void print(T a, T b) {
3
    cout << a << "," << b << endl;
4
}
5

6
print(2, 5);       // T = int
7
print(3.4, 7.6);   // T = double
8
// print(2, 5.3);  // error: 一个是 int，一个是 double，无法推出同一个 T

关键规则：

函数模板参数推导要求类型精确匹配，不会先做隐式类型转换。

所以：

1
my_swap(int, int);       // ok
2
my_swap(double, double); // ok
3
my_swap(int, double);    // error

如果确实希望使用某个类型，可以自己把实参转成同一类型：

1
print(static_cast<double>(2), 5.3); // T = double

函数模板与普通函数共存#

函数模板可以和普通函数重载共存。

1
#include <iostream>
2
using namespace std;
3

4
template<typename T>
5
void print(T a, T b) {
6
    cout << "print(T): " << a << "," << b << endl;
7
}
8

9
void print(float a, float b) {
10
    cout << "print(float): " << a << "," << b << endl;
11
}
12

13
int main() {
14
    print(2, 5);          // 模板：T = int
15
    print(3.4, 7.6);      // 模板：T = double
16
    print(2.3f, 3.5f);    // 普通函数：print(float, float)
17
    print(2.3, 3.5);      // 模板：T = double，精确匹配优先
18
    print(2, 3.5);        // 普通函数：两个参数都可转成 float
19
}

匹配顺序可以记成：

查找是否有 exact match 的普通函数；
查找是否有 exact match 的函数模板实例；
查找普通函数是否能通过 implicit conversion 匹配。

对应上面的调用：

1
print(2.3f, 3.5f);

普通函数 print(float, float) 精确匹配，所以调用普通函数。

1
print(2.3, 3.5);

两个实参都是 double，模板能生成 print<double> 精确匹配；普通 print(float, float) 需要转换，所以模板胜出。

1
print(2, 3.5);

模板 print(T, T) 无法推出同一个 T，普通 print(float, float) 可以通过转换调用，所以最终调用普通函数。

显式给出模板参数#

模板参数也可以显式写出来。

1
print<int>(2, 5.3);     // 生成 print<int>，5.3 转成 int，可能有 warning
2
print<double>(2, 5.3);  // 生成 print<double>，2 转成 double

当模板参数无法从函数实参中推导出来时，必须显式给出。

1
template<typename T>
2
void foo() {
3
    // ...
4
}
5

6
foo<int>();
7
foo<float>();

这里 T 没有出现在函数参数中，编译器无法根据实参推导，所以需要写 foo<int>()。

Class templates#

基本概念#

Class template（类模板） 是把类型参数用于类定义。

类由两部分组成：

data members；
member functions。

如果类中保存的数据类型可变，同时操作逻辑不依赖具体类型，就可以把该类型参数化。

典型例子：

1
stack<int>
2
list<Person*>
3
queue<Job>
4
vector<double>

stack 的 push/pop/top 逻辑不依赖元素类型。元素类型可以是 int，也可以是自定义类。

Vector 示例#

一个简化版 Vector：

1
template<typename T>
2
class Vector {
3
public:
4
    explicit Vector(int size);
5
    ~Vector();
6

7
    Vector(const Vector& other);
8
    Vector& operator=(const Vector& other);
9

10
    int size() const;
11
    T& operator[](int index);
12
    const T& operator[](int index) const;
13

14
private:
15
    T* m_elements;
16
    int m_size;
17
};

使用方式：

1
Vector<int> v1(100);
2
Vector<Complex> v2(256);
3

4
v1[20] = 10;
5
v2[20] = Complex(cos(pi / 4), sin(pi / 4));

Vector<int> 和 Vector<Complex> 是两个不同的具体类型。它们来自同一个类模板，但实例化后的类型不同。

类模板的成员函数定义#

如果成员函数写在类外，需要重复写模板头，并且用 Vector<T>:: 指明作用域。

1
template<typename T>
2
Vector<T>::Vector(int size)
3
    : m_elements(new T[size]), m_size(size) {}
4

5
template<typename T>
6
Vector<T>::~Vector() {
7
    delete[] m_elements;
8
}
9

10
template<typename T>
11
int Vector<T>::size() const {
12
    return m_size;
13
}
14

15
template<typename T>
16
T& Vector<T>::operator[](int index) {
17
    if (index >= 0 && index < m_size) {
18
        return m_elements[index];
19
    }
20
    throw std::out_of_range("Vector index out of range");
21
}
22

23
template<typename T>
24
const T& Vector<T>::operator[](int index) const {
25
    if (index >= 0 && index < m_size) {
26
        return m_elements[index];
27
    }
28
    throw std::out_of_range("Vector index out of range");
29
}

写法要点：

1
template<typename T>
2
T& Vector<T>::operator[](int index)

前面的 template<typename T> 表示这是模板定义；
Vector<T>:: 表示这是 Vector<T> 这个类模板实例的成员；
返回值、参数和函数体中都可以使用 T。

类模板与函数模板组合：sort#

函数模板可以接收类模板实例。

1
// bubble sort，仅用于说明模板机制，不推荐实际使用
2
template<typename T>
3
void sort(Vector<T>& arr) {
4
    const int last = arr.size() - 1;
5

6
    for (int i = 0; i < last; ++i) {
7
        for (int j = last; j > i; --j) {
8
            if (arr[j] < arr[j - 1]) {
9
                my_swap(arr[j], arr[j - 1]);
10
            }
11
        }
12
    }
13
}

使用：

1
Vector<int> vi(4);
2
vi[0] = 4;
3
vi[1] = 3;
4
vi[2] = 7;
5
vi[3] = 1;
6
sort(vi); // sort(Vector<int>&)
7

8
Vector<string> vs(5);
9
vs[0] = "Fred";
10
vs[1] = "Wilma";
11
vs[2] = "Barney";
12
vs[3] = "Dino";
13
vs[4] = "Prince";
14
sort(vs); // sort(Vector<string>&)

这个 sort 对 T 有隐含要求：

T 支持 operator<，因为有 arr[j] < arr[j - 1]；
T 支持交换所需的拷贝或移动操作，因为调用了 my_swap。

这说明模板不仅参数化类型，也隐含了对类型能力的要求。

更复杂的模板参数#

多个类型参数#

模板可以有多个类型参数。

例如 hash table 需要同时参数化 key 和 value：

1
template<typename Key, typename Value>
2
class HashTable {
3
public:
4
    const Value& lookup(const Key& key) const;
5
    void insert(const Key& key, const Value& value);
6

7
private:
8
    // ...
9
};

使用：

1
HashTable<string, int> word_count;
2
HashTable<int, Student> student_table;

这里 Key 和 Value 是两个独立的类型参数。

嵌套模板参数#

模板实例本身也是类型，因此可以继续作为其他模板的参数。

1
Vector<Vector<double*>> matrix;

这里：

Vector<double*> 是一个具体类型；
它又作为外层 Vector 的元素类型。

类型参数也可以很复杂，例如函数指针：

1
Vector<int (*)(Vector<double>&, int)> funcs;

含义：

funcs 是一个 Vector；
里面存的是函数指针；
这些函数接收 Vector<double>& 和 int；
返回 int。

模板的类型系统非常强大，也因此容易写出可读性较差的复杂类型。实际代码中可以用 using 简化：

1
using Func = int (*)(Vector<double>&, int);
2
Vector<Func> funcs;

Non-type template parameters#

模板参数除了类型，也可以是编译期常量值。这叫 non-type template parameter。

常见用途：把数组长度作为模板参数。

1
#include <iostream>
2
using namespace std;
3

4
template<typename T, int N>
5
class Array {
6
public:
7
    int size() const { return N; }
8

9
    T& operator[](int i) { return m_arr[i]; }
10
    const T& operator[](int i) const { return m_arr[i]; }
11

12
private:
13
    T m_arr[N]{};
14
};
15

16
int main() {
17
    Array<int, 3> a;
18
    a[0] = 2;
19
    a[1] = 3;
20
    a[2] = 1;
21

22
    cout << a.size() << endl;
23

24
    Array<int, 3> b{};
25
    cout << b[0] << "," << b[1] << "," << b[2] << endl;
26

27
    b = a; // ok，a 和 b 类型完全相同：Array<int, 3>
28
    cout << b[0] << "," << b[1] << "," << b[2] << endl;
29
}

Array<int, 3> 中：

int 是类型参数；
3 是非类型参数；
N 必须能在编译期确定。

如果长度不同，类型也不同：

1
Array<int, 3> a;
2
Array<int, 4> b;
3

4
// b = a; // error：Array<int, 3> 和 Array<int, 4> 是不同类型

如果表达式能在编译期算出相同值，则类型相同：

1
Array<int, 3> a;
2
Array<int, 9 / 3> b;
3

4
b = a; // ok，9 / 3 在编译期等于 3

非类型参数可以有默认值：

1
template<typename T, int Bounds = 100>
2
class FixedVector {
3
public:
4
    T& operator[](int i) { return elements[i]; }
5

6
private:
7
    T elements[Bounds];
8
};
9

10
FixedVector<int, 50> v1;
11
FixedVector<int, 10 * 5> v2;
12
FixedVector<int> v3; // FixedVector<int, 100>

使用 non-type parameter 的利弊：

优点：

长度进入类型系统；
编译器知道固定大小，可能更容易优化；
可以避免原生数组传参退化成指针的问题。

缺点：

不同长度生成不同类型；
代码更复杂；
大量不同数值可能导致 code bloat。

WARNING
Array<int, 3> 和 Array<int, 4> 是不同类型。非类型参数会参与类型构造，这一点很重要。

Member templates#

跨类型 complex 构造#

Member template 指：在类或类模板内部，某个成员函数本身又是模板。

典型例子是 complex<T> 的跨类型构造。

先写一个普通的类模板：

1
#include <iostream>
2
using namespace std;
3

4
template<typename T>
5
struct MyComplex {
6
    T real;
7
    T imag;
8

9
    MyComplex(T real, T imag) : real(real), imag(imag) {}
10
};
11

12
template<typename T>
13
ostream& operator<<(ostream& out, const MyComplex<T>& c) {
14
    return out << "(" << c.real << "," << c.imag << ")";
15
}
16

17
int main() {
18
    MyComplex<double> a(3.14, -1.57);
19
    cout << a << endl;
20

21
    MyComplex<double> b = a; // ok，同类型拷贝构造
22
    cout << b << endl;
23

24
    // MyComplex<int> c = a; // error：MyComplex<double> 和 MyComplex<int> 是不同类型
25
}

编译器自动生成的 copy constructor 只处理同类型：

1
MyComplex<double> -> MyComplex<double>

它不会自动生成：

1
MyComplex<double> -> MyComplex<int>

如果希望支持跨类型初始化，就要给构造函数额外引入一个模板参数 U。

1
#include <iostream>
2
using namespace std;
3

4
template<typename T>
5
struct MyComplex {
6
    T real;
7
    T imag;
8

9
    MyComplex(T real, T imag) : real(real), imag(imag) {}
10

11
    template<typename U>
12
    MyComplex(const MyComplex<U>& other)
13
        : real(other.real), imag(other.imag) {}
14
};
15

16
template<typename T>
17
ostream& operator<<(ostream& out, const MyComplex<T>& c) {
18
    return out << "(" << c.real << "," << c.imag << ")";
19
}
20

21
int main() {
22
    MyComplex<double> a(3.14, -1.57);
23
    cout << a << endl;
24

25
    MyComplex<int> b = a; // U = double，double 转 int
26
    cout << b << endl;    // 通常输出 (3,-1)
27

28
    MyComplex<float> f(3.14f, -1.57f);
29
    MyComplex<double> d = f; // U = float，float 转 double
30
    cout << d << endl;
31
}

这里有两层模板参数：

1
template<typename T>
2
struct MyComplex {
3
    template<typename U>
4
    MyComplex(const MyComplex<U>& other);
5
};

T 是当前对象的元素类型；
U 是来源对象的元素类型。

例如：

1
MyComplex<int> b = MyComplex<double>(3.14, -1.57);

此时：

1
T = int
2
U = double

构造函数负责把 double 成员转换成 int 成员。

WARNING
从宽类型到窄类型可能损失精度，例如 double -> int 会截断小数部分。member template 只提供转换通道，不保证转换语义一定安全。

Templates and inheritance#

模板可以和继承组合。关键是看实例化之后产生了哪些具体类型。

类模板继承普通类#

1
class Base {
2
public:
3
    void common() {}
4
};
5

6
template<typename T>
7
class Derived : public Base {
8
public:
9
    T value;
10
};

实例化后：

1
Derived<int> di;
2
Derived<double> dd;
3
Derived<string> ds;

会得到多个不同的派生类类型：

1
Derived<int>
2
Derived<double>
3
Derived<string>

它们都继承自同一个 Base。

关系可以理解为：

1
Base
2
 ├── Derived<int>
3
 ├── Derived<double>
4
 └── Derived<string>

类模板继承类模板#

1
template<typename T>
2
class List {
3
    // ...
4
};
5

6
template<typename T>
7
class MyList : public List<T> {
8
    // ...
9
};

实例化后：

1
MyList<int> li;
2
MyList<double> ld;

对应继承关系是：

1
List<int>    <- MyList<int>
2
List<double> <- MyList<double>

这里的 base class 也随着 T 变化。List<int> 和 List<double> 是不同类型。

普通类继承模板实例化类型#

普通类也可以继承某个已经实例化好的模板类型。

1
class Employee {
2
    // ...
3
};
4

5
template<typename T>
6
class List {
7
    // ...
8
};
9

10
class SupervisorGroup : public List<Employee*> {
11
    // ...
12
};

这里 List<Employee*> 已经是一个具体类型，SupervisorGroup 是普通类，直接继承它。

总结：

形式	例子	含义
类模板继承普通类	`template<class T> class D : public B {}`	多个 `D<T>` 共享同一个 `B`
类模板继承类模板	`template<class T> class D : public B<T> {}`	每个 `D<T>` 对应一个 `B<T>`
普通类继承模板实例	`class D : public B<int> {}`	`B<int>` 已经是具体 base class

CRTP#

基本形式#

CRTP（Curiously Recurring Template Pattern，奇异递归模板模式） 的形式是：

1
template<typename Derived>
2
class Base {
3
    // ...
4
};
5

6
class Derived : public Base<Derived> {
7
    // ...
8
};

看起来有点奇怪：派生类继承基类模板时，把自己的类型作为模板参数传回基类。

这样基类模板就能“知道”具体派生类类型。

典型写法：

1
template<typename Derived>
2
struct Base {
3
    void interface() {
4
        static_cast<Derived*>(this)->implementation();
5
    }
6

7
    static void static_func() {
8
        Derived::static_sub_func();
9
    }
10
};
11

12
struct Derived : public Base<Derived> {
13
    void implementation() {
14
        // derived implementation
15
    }
16

17
    static void static_sub_func() {
18
        // derived static implementation
19
    }
20
};

CRTP 常用来在泛型编程中模拟类似 virtual function 的接口，但调用在编译期决定。

用普通虚函数做 Newton solver#

前面设计课里用过 Newton solver。这里先用虚函数版本回顾动态多态。

1
#include <cmath>
2
#include <iostream>
3
using namespace std;
4

5
class Problem {
6
public:
7
    virtual ~Problem() = default;
8

9
    virtual double f(double x) const = 0;
10
    virtual double df(double x) const = 0;
11
};
12

13
class Sqrt : public Problem {
14
public:
15
    double f(double x) const override {
16
        return x * x - 2.0;
17
    }
18

19
    double df(double x) const override {
20
        return 2.0 * x;
21
    }
22
};
23

24
class Whatever : public Problem {
25
public:
26
    double f(double x) const override {
27
        return cos(x) - pow(x, 3);
28
    }
29

30
    double df(double x) const override {
31
        return -sin(x) - 3.0 * pow(x, 2);
32
    }
33
};
34

35
bool is_close(double fx, double tolerance) {
36
    return fabs(fx) < tolerance;
37
}
38

39
void print_info(int k, double x, double fx) {
40
    cout << "k = " << k
41
         << ", x = " << x
42
         << ", f(x) = " << fx << endl;
43
}
44

45
double newton_solve(const Problem& p,
46
                    double x0,
47
                    double tolerance = 1e-12,
48
                    int max_iter = 30) {
49
    int k = 0;
50
    double x = x0;
51
    double fx = p.f(x);
52

53
    print_info(k, x, fx);
54

55
    while (!is_close(fx, tolerance) && k < max_iter) {
56
        double dfx = p.df(x);
57
        x = x - fx / dfx;
58

59
        fx = p.f(x);
60
        ++k;
61
        print_info(k, x, fx);
62
    }
63

64
    return x;
65
}
66

67
int main() {
68
    double x0 = 1.0;
69

70
    Sqrt sqrt_problem;
71
    Whatever whatever_problem;
72

73
    newton_solve(sqrt_problem, x0);
74
    cout << "\n-----------------------\n";
75
    newton_solve(whatever_problem, x0);
76
}

这个版本的特点：

Problem 是抽象基类；
newton_solve 接收 const Problem&；
p.f(x) 和 p.df(x) 是 virtual call；
具体调用哪个函数由对象的动态类型决定。

优点：接口明确，用户知道必须继承 Problem 并实现 f / df。

代价：通过虚函数表进行动态绑定，有运行时开销。

普通函数模板版本#

也可以不用继承，把 newton_solve 写成函数模板。

1
#include <cmath>
2
#include <iostream>
3
using namespace std;
4

5
class Sqrt {
6
public:
7
    double f(double x) const {
8
        return x * x - 2.0;
9
    }
10

11
    double df(double x) const {
12
        return 2.0 * x;
13
    }
14
};
15

16
class Whatever {
17
public:
18
    double f(double x) const {
19
        return cos(x) - pow(x, 3);
20
    }
21

22
    double df(double x) const {
23
        return -sin(x) - 3.0 * pow(x, 2);
24
    }
25
};
26

27
bool is_close(double fx, double tolerance) {
28
    return fabs(fx) < tolerance;
29
}
30

31
void print_info(int k, double x, double fx) {
32
    cout << "k = " << k
33
         << ", x = " << x
34
         << ", f(x) = " << fx << endl;
35
}
36

37
template<typename Problem>
38
double newton_solve(const Problem& p,
39
                    double x0,
40
                    double tolerance = 1e-12,
41
                    int max_iter = 30) {
42
    int k = 0;
43
    double x = x0;
44
    double fx = p.f(x);
45

46
    print_info(k, x, fx);
47

48
    while (!is_close(fx, tolerance) && k < max_iter) {
49
        double dfx = p.df(x);
50
        x = x - fx / dfx;
51

52
        fx = p.f(x);
53
        ++k;
54
        print_info(k, x, fx);
55
    }
56

57
    return x;
58
}
59

60
int main() {
61
    double x0 = 1.0;
62

63
    Sqrt sqrt_problem;
64
    Whatever whatever_problem;
65

66
    newton_solve(sqrt_problem, x0);
67
    cout << "\n-----------------------\n";
68
    newton_solve(whatever_problem, x0);
69
}

这个版本的特点：

没有抽象基类；
没有虚函数；
Problem 只要有 f(double) 和 df(double) 就能工作；
编译器为不同问题类型生成不同版本的 newton_solve。

问题在于：接口要求是隐式的。

1
template<typename Problem>
2
double newton_solve(const Problem& p, double x0, ...)

用户从函数签名上只能看到 Problem 这个模板参数，看不到 Problem 必须提供 f 和 df。如果误传一个没有 f / df 的类型，错误会在模板实例化时出现。

CRTP 版本#

CRTP 可以让接口关系更明确，同时避免虚函数调用。

1
#include <cmath>
2
#include <iostream>
3
using namespace std;
4

5
template<typename Derived>
6
class Problem {
7
public:
8
    double f(double x) const {
9
        return static_cast<const Derived*>(this)->f_impl(x);
10
    }
11

12
    double df(double x) const {
13
        return static_cast<const Derived*>(this)->df_impl(x);
14
    }
15
};
16

17
class Sqrt : public Problem<Sqrt> {
18
public:
19
    double f_impl(double x) const {
20
        return x * x - 2.0;
21
    }
22

23
    double df_impl(double x) const {
24
        return 2.0 * x;
25
    }
26
};
27

28
class Whatever : public Problem<Whatever> {
29
public:
30
    double f_impl(double x) const {
31
        return cos(x) - pow(x, 3);
32
    }
33

34
    double df_impl(double x) const {
35
        return -sin(x) - 3.0 * pow(x, 2);
36
    }
37
};
38

39
bool is_close(double fx, double tolerance) {
40
    return fabs(fx) < tolerance;
41
}
42

43
void print_info(int k, double x, double fx) {
44
    cout << "k = " << k
45
         << ", x = " << x
46
         << ", f(x) = " << fx << endl;
47
}
48

49
template<typename Derived>
50
double newton_solve(const Problem<Derived>& p,
51
                    double x0,
52
                    double tolerance = 1e-12,
53
                    int max_iter = 30) {
54
    int k = 0;
55
    double x = x0;
56
    double fx = p.f(x);
57

58
    print_info(k, x, fx);
59

60
    while (!is_close(fx, tolerance) && k < max_iter) {
61
        double dfx = p.df(x);
62
        x = x - fx / dfx;
63

64
        fx = p.f(x);
65
        ++k;
66
        print_info(k, x, fx);
67
    }
68

69
    return x;
70
}
71

72
int main() {
73
    double x0 = 1.0;
74

75
    Sqrt sqrt_problem;
76
    Whatever whatever_problem;
77

78
    newton_solve(sqrt_problem, x0);
79
    cout << "\n-----------------------\n";
80
    newton_solve(whatever_problem, x0);
81
}

核心是：

1
template<typename Derived>
2
class Problem {
3
public:
4
    double f(double x) const {
5
        return static_cast<const Derived*>(this)->f_impl(x);
6
    }
7
};
8

9
class Sqrt : public Problem<Sqrt> {
10
public:
11
    double f_impl(double x) const;
12
};

Problem<Sqrt> 内部通过：

1
static_cast<const Derived*>(this)

把当前对象当作 Derived 使用，然后调用派生类中的实现函数。

newton_solve 的接口也更明确：

1
template<typename Derived>
2
double newton_solve(const Problem<Derived>& p, double x0, ...)

这说明传入对象必须处在 Problem<Derived> 这套 CRTP 结构中。相比普通函数模板，使用者更容易看出问题类应当如何定义。

CRTP 的特点#

CRTP 可以看成一种 static polymorphism（静态多态）。

方式	调用机制	接口形式	开销	适合场景
virtual function	运行时动态绑定	抽象基类 + virtual	有虚函数开销	需要运行时多态
普通函数模板	编译期实例化	隐式要求 `f` / `df`	无虚函数开销	泛型算法，接口要求简单
CRTP	编译期静态绑定	`Derived : Base<Derived>`	无虚函数开销	想表达继承式接口，又希望静态分发

CRTP 的优点：

不需要 vtable；
调用可在编译期解析；
基类可以调用派生类实现；
接口比纯 duck typing 的函数模板更显式。

CRTP 的限制：

不能直接替代运行时多态；
不适合需要把不同派生类统一放进 vector<Base*> 的场景；
写法较绕，对初学者不直观；
报错仍可能比较长。

模板代码放在哪里#

普通类通常可以拆成：

1
.h   ：声明
2
.cpp ：实现

模板通常要把定义也放在头文件中。

原因：模板实例化发生在编译期。编译器在调用点看到：

1
my_swap<int>(a, b);

它需要拿到模板函数体，才能把 T 替换成 int 并生成真实函数。如果调用点只看到函数签名，看不到模板定义，就无法实例化。

所以模板常见写法是：

1
#ifndef MY_SWAP_HH
2
#define MY_SWAP_HH
3

4
template<typename T>
5
void my_swap(T& x, T& y) {
6
    T temp = x;
7
    x = y;
8
    y = temp;
9
}
10

11
#endif

也可以把实现写到另一个文件里，再由 header include 进来：

1
#ifndef VECTOR_HH
2
#define VECTOR_HH
3

4
template<typename T>
5
class Vector {
6
    // declaration
7
};
8

9
#include "vector_impl.hh"
10

11
#endif

重点是：使用模板的编译单元必须能看到模板定义。

TIP
模板定义放在头文件中通常不会像普通函数那样直接导致 multiple definition 问题。编译器和链接器有机制处理模板实例的合并。课堂中老师也强调：模板的东西基本都放 header file 里。

写模板的建议流程#

写模板不要一开始就泛化。更稳妥的流程：

先选一个具体类型，写出 non-template version；
建立一组测试用例；
确认非模板版本正确；
测量性能，找到需要优化的地方；
回顾实现，判断哪些类型应该被参数化；
把非参数化版本改成模板；
用原有测试用例重新测试；
再增加不同类型的测试用例。

例如先写：

1
void swap_int(int& x, int& y) {
2
    int temp = x;
3
    x = y;
4
    y = temp;
5
}

测试通过后再抽象为：

1
template<typename T>
2
void my_swap(T& x, T& y) {
3
    T temp = x;
4
    x = y;
5
    y = temp;
6
}

模板的强大来自泛化，但泛化之前要先确认普通逻辑本身正确。

概述#

目录#

Function overloading#

基本概念#

Overload and auto-cast#

Default arguments#

默认参数的含义#

默认参数必须从右往左给#

Why templates?#

问题背景#

不用模板的几种做法#

1. Clone the code#

2. Make a common base class#

3. Untyped lists#

模板的基本思想#

Function templates#

从 swap 开始#

模板语法#

实例化#

模板参数推导#

函数模板与普通函数共存#

显式给出模板参数#

Class templates#

基本概念#

Vector 示例#

类模板的成员函数定义#

类模板与函数模板组合：sort#

更复杂的模板参数#

多个类型参数#

嵌套模板参数#

Non-type template parameters#

Member templates#

跨类型 complex 构造#

Templates and inheritance#

类模板继承普通类#

类模板继承类模板#

普通类继承模板实例化类型#

CRTP#

基本形式#

用普通虚函数做 Newton solver#

普通函数模板版本#

CRTP 版本#

CRTP 的特点#

模板代码放在哪里#

写模板的建议流程#

评论