第6章 模板

把你的引言放在这里。

<span title="这是一段极妙的引言，作者的很多书籍中“模板”一章都用了这段，这句话出现在“引言”位置，同时告诉你它可以被替换，所以这个引言本身就是一个“模板”"。>—— B. Stroustrup

6.1 导言

需要 vector 的人不太可能总是想要一个double的vector。 vector 是个泛化的概念，它本身独立于浮点数的概念存在。 因此，vector 的元素类型也应该具有独立的表现形式。模板（template） 是一种类或者函数，我们用一组类型或值去参数化它。 我们用模板表示这样一种概念： 它是某种通用的东西，我么可以通过指定参数来生成类型或函数， 至于这种参数，比方说是vector的元素类型double。

6.2 参数化类型

我们那个 承载double的vector，可以泛化成一个 承载任意类型的vector， 只要把它变成一个template，并用一个类型参数替代具体的double类型。例如：

template<typename T>
class Vector {
private:
    T* elem;        // elem指向一个数组，该数组承载sz个T类型的元素
    int sz;
public:
    explicit Vector(int s);         // 构造函数：建立不变式，申请资源
     ̃Vector() { delete[] elem; }    // 析构函数：释放资源

    // ... 复制和移动操作 ...

    T& operator[](int i);               // 为非const Vector取下标元素
    const T& operator[](int i) const;   // 为const Vector取下标元素(§4.2.1)
    int size() const { return sz; }
};

前缀template<typename T>把T作为紧跟在它后面的声明的参数。 这是数学上“对所有T”的C++版本，或者更确切的说是“对于所有类型T”。 如果你想要数学上的“对所有T，有P(T)”，那你需要 概束（concept） (§6.2.1, §7.2)。 用class引入类型参数与typename是等效的， 在旧式代码里template<class T>做前缀很常见。

成员函数可能有相似的定义：

template<typename T> Vector<T>::Vector(int s)
{
    if (s<0)
        throw Negative_size{};
    elem = new T[s];
    sz = s;
}

template<typename T>
const T& Vector<T>::operator[](int i) const
{
    if (i<0 || size()<=i)
        throw out_of_range{"Vector::operator[]"};
    return elem[i];
}

有了以上这些定义，我们可以定义如下这些 Vector：

Vector<char> vc(200);       // 承载200个字符的 vector
Vector<string> vs(17);      // 承载17个string的 vector
Vector<list<int>> vli(45);  // 承载45个int列表的的 vector

Vector<list<int>>里的>>是嵌套模板参数的结尾；并非放错地方的输入运算符。

可这样使用Vector：

void write(const Vector<string>& vs)    // Vector of some strings
{
    for (int i = 0; i!=vs.size(); ++i)
        cout << vs[i] << '\n';
}

想让我们的Vecor支持区间-for循环，就必须定义适当的begin()和end()函数：

template<typename T>
T* begin(Vector<T>& x)
{
    return x.size() ? &x[0] : nullptr;  // 指向第一个元素的指针或者nullptr
}

template<typename T>
T* end(Vector<T>& x)
{
    return x.size() ? &x[0]+x.size() : nullptr; // 指向末尾元素身后位置
}

有了以上这些，就可以这样写：

void f2(Vector<string>& vs) // 某种东西的 Vector
{
    for (auto& s : vs)
        cout << s << '\n';
}

同理，可以把list、vector、map（也就是关联数组）、 unordered map（也就是哈希表）等都定义为模板（第11章）。

模板是个编译期机制，因此使用它们跟手写的代码相比，并不会在运行时带来额外的负担。 实际上，Vector<double>生成的代码与第4章Vector版本的代码一致。 更进一步，标准库vector<double>生成的代码很可能更好 （因为实现它的时候下了更多功夫）。

模板附带一组模板参数，叫做 实例化（instantiation） 或者特化（specialization） 。 编译过程靠后的部分，在 实例化期（instantiation time） ， 程序里用到的每个实例都会被生成(§7.5)。 生成的代码会经历类型检查，以便它们与手写代码具有同样的类型安全性。 遗憾的是，此种类型检查通常处于编译过程较晚的阶段——在实例化期。

6.2.1 受限模板参数（C++20）

绝大多数情况下，只有当模板参数符合特定条件的时候，这个模板才说得通。 例如：Vector通常提供复制操作，如果它确实提供了，就必须要求其元素是可复制的。 这样，我们就得要求Vector的模板参数不仅仅是typename，而是一个Element， 其中的“Element”规定了一个作为元素的类型所需要满足的需求：

template<Element T>
class Vector {
private:
    T* elem;    // elem指向一个数组，该数组承载sz个T类型的元素
    int sz;
    // ...
};

前缀template<Element T>就是数学中“对所有令Element(T)为真的T”的C++版本； 就是说，Element是个谓词，用来检测T，判断它是否具有Vector要求的全部属性。 这种谓词被称为 概束（concept） (§7.2)。 指定过概束的模板参数被称为 受限参数（constrained argument） ， 参数受限的模板被称为 受限模板（constrained template） 。

如果用于实例化模板的类型不满足需求，会触发一个编译期错误。例如：

Vector<int> v1;     // OK：可以复制一个int
Vector<thread> v2;  // 报错：不能复制标准线程 (§15.2)

因为在 C++20 之前，C++没有官方支持概束， 较老的代码采用了未约束模板，而把需求内容留在了文档中。

6.2.2 值模板参数

除了类型参数，模板还可以接受值参数。例如：

template<typename T, int N>
struct Buffer {
    using value_type = T;
    constexpr int size() { return N; }
    T[N];
    // ...
};

别名（value_type）和constexpr函数允许我们（只读）访问模板参数。

值参数在很多语境里都很有用。 例如：Buffer允许我们创建任意容量的缓冲区，却不使用自由存储区（动态内存）：

Buffer<char,1024> glob; // 用于字符的全局缓冲区（静态分配）

void fct() {
    Buffer<int,10> buf; // 用于整数的局部缓冲区（在栈上）
    // ...
}

值模板参数必须是常量表达式。

6.2.3 模板参数推导

考虑一下标准库模板pair的应用：

pair<int,double> p = {1,5.2};

很多人发现要指定模板参数类型很烦冗，因此标准库提供了一个函数make_pair()， 以便借助其函数参数，推导其返回的pair的模板参数。：

auto p = make_pair(1,5.2);  // p 是个 pair<int,double>

这就导致一个明显的疑问“为什么不直接通过构造函数的参数推导模板参数呢？”， 因此在C++17里，就可以了。这样：

pair p = {1,5.2};   // p 是个 pair<int,double>

这不仅是pair的问题；make_函数的应用很常见。考虑如下这个简单的例子：

template<typename T>
class Vector {
public:
    Vector(int);
    Vector(initializer_list<T>);   // 初始化列表构造函数
    // ...
};

Vector v1 {1,2,3};  // 从初始值类型推导v1的元素类型
Vector v2 = v1;     // 从v1的元素类型推导v2的元素类型

auto p = new Vector{1,2,3}; // p 指向一个 Vector<int>

Vector<int> v3(1);  // 此处，我们需要显式指定元素类型（未提及元素类型）

显然，这简化了拼写，并消除了因误拼冗余的模板参数类型而导致的烦躁。 不过，它并非万全之策。 模板参数推导可能会令人诧异（无论make_函数还是构造函数）。考虑：

Vector<string> vs1 {"Hello", "World"};  // Vector<string>
Vector vs {"Hello", "World"};           // 推导为 Vector<const char*> （诧异吗？）
Vector vs2 {"Hello"s, "World"s};        // 推导为 Vector<string>
Vector vs3 {"Hello"s, "World"};         // 报错：初始化列表类型不单一

C-风格字符串文本值的类型是const const*(§1.7.1)。 如果这不符合意图，请用一个s后缀，让它明确成为string(§9.2)。 如果初始化列表中具有不同类型，就无法推导出一个单一类型，因此会报错。

如果无法从构造函数参数推导某个模板参数， 我们可以用 推导引导（deduction guide） 辅助。考虑：

template<typename T>
class Vector2 {
public:
    using value_type = T;
    // ...
    Vector2(initializer_list<T>);   // 初始化列表构造函数

    template<typename Iter>
        Vector2(Iter b, Iter e);    // [b:e) 区间构造函数
    // ...
};

Vector2 v1 {1,2,3,4,5};             // 元素类型是 int
Vector2 v2(v1.begin(),v1.begin()+2);

很明显，v2应该是个Vector2<int>，但是因为缺少辅助信息，编译器无法推导出来。 这段代码仅表明：有个构造函数接收一对同类型的值。 缺乏概束(§7.2)的语言支持，对于该类型，编译器无法假设任何情况。 如果想进行推导，可以在Vector2的声明后添加一个 推导指引（deduction guide） ：

template<typename Iter>
    Vector2(Iter,Iter) -> Vector2<typename Iter::value_type>;

意思是，如果我们看到Vector2使用一对迭代器初始化， 应该把Vector2::value_type推导为迭代器的值类型。

推导指引的效果通常很微妙，因此在设计类模板的时候，尽量别依靠它。 不过，标准库里满是（目前还）未使用concept且带有这种二义性的类， 因此它们用了不少的推导指引。

6.3 参数化操作

除了用元素类型参数化容器，模板还有很多别的用途。 具体来说，它们被广泛用于泛化标准库中的类型和算法(§11.6, §12.6)。

表示一个操作被类型或值泛化，有三种方式：

• 函数模板

• 函数对象：一个可以携带数据的对象，且像函数一样被调用

• lambda表达式：函数对象的快捷形式

6.3.1 函数模板

可以写一个元素求和函数，针对可以利用 区间-for 遍历的任意序列（也就是容器），像这样：

template<typename Sequence, typename Value>
Value sum(const Sequence& s, Value v)
{
    for (auto x : s)
        v+=x;
    return v;
}

模板参数Value和函数参数v， 允许调用者指定这个累加函数的类型和初值（累加到和里的变量）：

void user(Vector<int>& vi, list<double>& ld, vector<complex<double>>& vc)
{
    int x = sum(vi,0);                  // 承载 int 的vector的和（与 int 相加）
    double d = sum(vi,0.0);             // 承载 int 的vector的和（与 double 相加）
    double dd = sum(ld,0.0);            // 承载 double 的vector的和
    auto z = sum(vc,complex{0.0,0.0});  // 承载 complex<double>s 的vector的和
}

把int加到double上的意义在于能优雅地处理超出int上限地数值。 注意sum<Sequence,Value>从函数参数中推导模板参数的方法。 巧的是不需要显式指定它们。

这个sum()是标准库里accumulate()(§14.3)的简化版本。

函数模板可用于成员函数，但不能是virtual成员。 在一个程序里，编译器无法知晓某个模板的全部实例，因此无法生成vtbl(§4.4)。

6.3.2 函数对象

有一种特别有用的模板是 函数对象（function object） （也叫 仿函数（functor） ），用于定义可调用对象。例如：

template<typename T>
class Less_than {
    const T val;    // 参与比对的值
public:
    Less_than(const T& v) :val{v} { }
    bool operator()(const T& x) const { return x<val; } // 调用运算符
};

名为operator()的函数实现“函数调用”、“调用”或“应用”运算符()。

可以为某些参数类型定义Less_than类型的具名变量：

Less_than lti {42};                 // lti(i) 将把i用<号与42作比（i<42）
Less_than lts {"Backus"s};          // lts(s) 将把s用<号与"Backus"作比（s<"Backus"）
Less_than<string> lts2 {"Naur"};    // "Naur"是个C风格字符串，因此需要用 <string> 获取正确的 <

可以像调用函数一样调用这样的对象：

void fct(int n, const string& s)
{
    bool b1 = lti(n); // true if n<42
    bool b2 = lts(s); // true if s<"Backus"
    // ...
}

这种函数对象广泛用做算法的参数。例如，可以统计使特定谓词为true的值的数量：

template<typename C, typename P>
    // requires Sequence<C> && Callable<P,Value_type<P>>
int count(const C& c, P pred)
{
    int cnt = 0;
    for (const auto& x : c)
        if (pred(x))
            ++cnt;
    return cnt;
}

谓词（predicate） 是调用后能返回true或false的东西。例如：

void f(const Vector<int>& vec, const list<string>& lst, int x, const string& s)
{
    cout << "number of values less than " << x << ": " << count(vec,Less_than{x}) << '\n';
    cout << "number of values less than " << s << ": " << count(lst,Less_than{s}) << '\n';
}

此处，Less_than{x}构造一个Less_than<int>类型的对象， 它的调用运算符会与名为x的int进行比较；Less_than{s}会构造一个对象，与名为s的string进行比较。 这些函数对象的妙处在于，它们随身携带参与比较的值。 我们无需为每个值（以及每种类型）写一个单独的函数， 也无需引入一个恼人的全局变量去持有这个值。 还有，类似于Less_than这种函数对象易于内联， 因此调用Less_than远比间接的函数调用高效。 携带数据的能力再加上高效性，使函数对象作为算法参数特别有用。

用在通用算法中的函数对象，可指明其关键运算的意义 （例如Less_than之于count()），通常被称为 策略对象（policy object） 。

6.3.3 Lambda表达式

在 §6.3.2 中，我们把Less_than的定义和它的应用拆开了。这样不太方便。 你猜怎么着，还有个隐式生成函数对象的写法：

void f(const Vector<int>& vec, const list<string>& lst, int x, const string& s)
{
    cout << "number of values less than " << x
        << ": " << count(vec,[&](int a){ return a<x; })
        << '\n';

    cout << "number of values less than " << s
        << ": " << count(lst,[&](const string& a){ return a<s; })
        << '\n';
}

[&](int a){return a<x;}这个写法叫 lambda表达式（lambda expression） 。 它跟Less_than<int>{x}一样会生成函数对象。 此处的[&]是一个 抓取列表（capture list） ， 表明lambda函数体内用到的所有局部名称，将以引用的形式访问。 如果我们仅想“抓取”x，应该这么写：[&x]。 如果我们把x的副本传给生成的对象，就应该这么写：[=x]。 不抓取任何东西写[ ]，以引用方式抓取所有局部名称写[&]， 以传值方式抓取所有局部名称写：[=]。

使用lambda表达式方便、简略，但也略晦涩些。 对于繁复的操作（比方说超出一个表达式的内容）， 我倾向于为它命名，以便明确用途，并让它可以在程序中多处访问。

在 §4.5.3 中，我们遇到了一个困扰， 就是在使用元素类型为指针或unique_ptr的vector时， 要写很多针对其元素的操作，比方说draw_all()和rotate_all()。 函数对象（确切的说是lambda表达式）有助于把容器遍历和针对每个元素的操作分离开。

首先，我们需要一个函数，操作指针容器中元素指向的对象：

template<typename C, typename Oper>
void for_all(C& c, Oper op) // 假定C是个承载指针的容器
    // 要求 Sequence<C> && Callable<Oper,Value_type<C>> (see §7.2.1)
{
    for (auto& x : c)
        op(x);  // 把每个元素指向的对象传引用给 op()
}

现在，针对 §4.5 中的 user()，可以写个不需要一堆_all函数的版本了：

void user2()
{
    vector<unique_ptr<Shape>> v;
    while (cin)
        v.push_back(read_shape(cin));
    for_all(v,[](unique_ptr<Shape>& ps){ ps->draw(); });        // draw_all()
    for_all(v,[](unique_ptr<Shape>& ps){ ps->rotate(45); });    // rotate_all(45)
}

我把unique_ptr<Shape>&传给lambda表达式， 这样for_all()就无需关心对象存储的方式了。 确切的说，这些for_all()函数不影响传入的Shape生命期， lambda表达式的函数体使用参数时，就像用旧式的指针一样。

跟函数一样，lambda表达式也可以泛型。例如：

template<class S>
void rotate_and_draw(vector<S>& v, int r)
{
    for_all(v,[](auto& s){ s->rotate(r); s->draw(); });
}

此处的auto，像变量声明里那样， 意思是初始值（在调用中，实参初始化形参）接受任何类型。 这让带有auto的lambda表达式成了模板，一个 泛型lambda（generic lambda） 。 由于标准委员会政策方面的疏漏，此种auto的应用，目前无法用于函数参数。

可以用任意容器调用这个泛型的rotate_and_draw()， 只要该容器内的对象能执行draw()和rotate()。例如：

void user4()
{
    vector<unique_ptr<Shape>> v1;
    vector<Shape*> v2;
    // ...
    rotate_and_draw(v1,45);
    rotate_and_draw(v2,90);
}

利用lambda表达式，可以把任何语句变成表达式。 其主要用途是，把用于求值的运算当作参数值传递，但它的能力是通用的。 考虑以下这个复杂的初始化：

enum class Init_mode { zero, seq, cpy, patrn }; // 各种初始化方式

// 乱糟糟的代码：

// int n, Init_mode m, vector<int>& arg, 和 iterators p 以及 q 在别处定义

vector<int> v;

switch (m) {
case zero:
    v = vector<int>(n); // n个初始化为0的元素
    break;
case cpy:
    v = arg;
    break;
};

// ...

if (m == seq)
    v.assign(p,q);      // 从序列[p:q)复制

// ...

这是个风格化明显的例子，但不幸的是这种情况并不罕见。 我们要在一组初始化方法中进行选择， 去初始化一个数据结构（此处是v），并为不同方法做不同的运算。 这种代码通常一塌糊涂，声称“为了高效”必不可少，还是bug之源：

• 变量可能在获得合适的值之前被使用

• “初始化代码”跟其它代码混杂在一起，以至于难以理解

• 在“初始化代码”与其它代码混杂的时候，很容易缺失某个case

• 这不是初始化，而是赋值

取而代之，可以把它转化为一个lambda表达式，用作初值：

// int n, Init_mode m, vector<int>& arg, 和 iterators p 以及 q 在别处定义

vector<int> v = [&] {
    switch (m) {
    case zero:
        return vector<int>(n);      // n个初始化为0的元素
    case seq:
        return vector<int>{p,q};    // 从序列[p:q)复制
    case cpy:
        return arg;
    }
}();
// ...

我仍然“忘掉”了一个case，不过现在这就不难察觉了。

6.4 模板机制

要定义出好的模板，我们需要一些辅助的语言构造：

• 依赖于类型的值： 变量模板（variable template） (§6.4.1)。

• 针对类型和模板的别名： 别名模板（alias template） (§6.4.2)。

• 编译期选择机制：if constexpr(§6.4.3)。

• 针对类型和表达式属性的编译期查询机制：requires表达式(§7.2.3)。

另外，constexpr函数(§1.6)和static_asserts(§3.5.5) 也经常参与模板设计和应用。

对于构建通用、基本的抽象，这些基础机制是主要工具。

6.4.1 变量模板

在使用某个类型时，经常会需要该类型的常量和值。 这理所当然也发生在我们使用类模板的的时候： 当我们定义了C<T>，通常会需要类型T以及依赖T的其它类型的常量和变量。 以下示例出自一个流体力学模拟[Garcia,2015]：

template <class T>
    constexpr T viscosity = 0.4;

template <class T>
    constexpr space_vector<T> external_acceleration = { T{}, T{-9.8}, T{} };
auto vis2 = 2*viscosity<double>;
auto acc = external_acceleration<float>;

此处的space_vector是个三维向量。

显然，可以用适当类型的任意表达式作为初始值。考虑：

template<typename T, typename T2>
    constexpr bool Assignable = 
        is_assignable<T&,T2>::value; // is_assignable 是个类型 trait (§13.9.1)

template<typename T>
void testing()
{
    static_assert(Assignable<T&,double>, "can't assign a double");
    static_assert(Assignable<T&,string>, "can't assign a string");
}

经历一些大刀阔斧的变动，这个点子成了概束定义(§7.2)的关键。

6.4.2 别名

出人意料的是，为类型或者模板引入一个同义词很有用。 例如，标准库头文件<cstddef>包含一个size_t的别名，可能是这样：

using size_t = unsigned int;

用于命名size_t的实际类型是实现相关的， 因此在另一个实现里size_t可能是unsigned long。 有了别名size_t的存在，就让程序员能够写出可移植的代码。

对参数化类型来说，为模板参数相关的类型提供别名是很常见的。例如：

template<typename T>
class Vector {
public:
    using value_type = T;
    // ...
};

实际上，每个标准库容器都提供了value_type作为其值类型的名称（第11章）。 对于所有遵循此惯例的容器，我们都能写出可行的代码。例如：

template<typename C>
using Value_type = typename C::value_type;  // C 的元素的类型

template<typename Container>
void algo(Container& c)
{
    Vector<Value_type<Container>> vec;      // 结果保存在这里
    // ...
}

通过绑定部分或全部模板参数，可以用别名机制定义一个新模板。例如：

template<typename Key, typename Value>
class Map {
    // ...
};

template<typename Value>
using String_map = Map<string,Value>;

String_map<int> m;  // m 是个 Map<string,int>

6.4.3 编译期if

思考编写这样一个操作，它在slow_and_safe(T)和simple_and_fast(T)里二选一。 这种问题充斥在基础代码中——那些通用性和性能优化都重要的场合。 传统的解决方案是写一对重载的函数，并基于 trait(§13.9.1) 选出最适宜的那个， 比方说标准库里的is_pod。 如果涉及类体系，slow_and_safe(T)可提供通用操作， 而某个继承类可以用simple_and_fast(T)的实现去重载它。

在 C++17 里，可以利用一个编译期if：

template<typename T> void update(T& target)
{
    // ...
    if constexpr(is_pod<T>::value)
        simple_and_fast(target);    // 针对“简单旧式的数据”
    else
        slow_and_safe(target);
    // ...
}

is_pod<T>是个类型trait (§13.9.1)，它辨别某个类型可否低成本复制。

仅被选定的if constexpr分支被实例化。 此方案即提供了性能优化，又实现了优化的局部性。

重要的是，if constexpr并非文本处理机制， 不会破坏语法、类型和作用域的常见规则。例如：

template<typename T>
void bad(T arg)
{
    if constexpr(Something<T>::value)
        try {                           // 语法错误

    g(arg);

    if constexpr(Something<T>::value)
        } catch(...) { /* ... */ }      // 语法错误
}

如果允许类似的文本操作，会严重破坏代码的可靠性，而且对依赖于新型程序表示技术 （比方说“抽象语法树（abstract syntax tree）”）的工具，会造成问题。

6.5 忠告

• [1] 可应用于很多参数类型的算法，请用模板去表达；§6.1; [CG: T.2]。

• [2] 请用模板去表达容器；§6.2; [CG: T.3]。

• [3] 请用模板提升代码的抽象层级；§6.2; [CG: T.1]。

• [4] 模板是类型安全的，但它的类型检查略有些迟滞；§6.2。

• [5] 让构造函数或者函数模板去推导模板参数类型；§6.2.3。

• [6] 使用算法的时候，请用函数对象作参数；§6.3.2; [CG: T.40]‘

• [7] 如果需要简单的一次性函数对象，采用lambda表达式；§6.3.2。

• [8] 虚成员函数无法作为模板成员函数；§6.3.1。

• [9] 用模板别名简化符号表示，并隐藏实现细节；§6.4.2。

• [10] 使用模板时，确保其定义（不仅仅是声明）在作用域内；§7.5。

• [11] 模板提供编译期的“鸭子类型（duck typing）”；§7.5。

• [12] 模板不支持分离编译：把模板定义#include进每个用到它的编译单元。