Qiming の 小屋

Qiming の 小屋

现代C++模板01 | 函数模板

C++
3
2024-12-20

函数模板不是函数，只有实例化函数模板，编译器才能生成实际的函数定义。 不过在很多时候，它看起来就像是普通函数一样。

定义模板

template<typename T>
T max(T a, T b) {
	return a > b ? a : b;
}

如果要声明一个模板函数，通常使用

template< 形参列表 > 函数声明

关键字 typename ，顾名思义，引入一个形参类型。

类型形参是 T，也可以使用其他标识符作为类型形参名（T 或 Ty 等，是约定的惯例），也可以在需要的时候自定义一些有明确意义的名字。在调用函数模板 max 时，根据传入参数，编译器可以推导出类型形参的类型，实例化函数模板。我们需要传入支持函数模板操作的类型，如 int 或 重载了 > 运算符的类。注意 max 的 return 这意味着我们的模板形参 T 还需要是可复制/移动的，以便返回。

C++17 之前，类型 T 必须是可复制或移动才能传递参数。C++17 以后，即使复制构造函数和移动构造函数都无效，因为 C++17 强制的复制消除，也可以传递临时纯右值。

因为一些历史原因，我们也可以使用 class 关键字来定义模板类型形参。所以先前的模板 max 可以等价于:

template<class T>
T max(T a,T b){
    return a > b ? a : b;
}

但是与类声明不同，在声明模板类型形参时，不能使用 struct。

使用模板

#include <iostream>

template<typename T>
T max(T a, T b) {
	return a > b ? a : b;
}

struct Test {
	int v_{};
	Test() = default;
	Test(int v) : v_(v) {}
	bool operator>(const Test& t) const {
		return this->v_ > t.v_;
	}
};

int main() {
	int a{ 1 };
	int b{ 2 };
	// ::max 中 `::`表示是本命名空间，以防止与 std 命名空间混淆
	// 虽然此时并没有使用 `using namespace std;`
	// 但是如果T是 std::string ，则可能优先找到 std::max ，从而产生歧义，导致编译错误
	std::cout << "max(a, b) : " << ::max(a, b) << '\n';

	Test t1{ 100 };
	Test t2{ 200 };
	std::cout << "max(t1, t2) : " << ::max(t1, t2).v_ << '\n';

}

上面的测试程序，编译器会实例化两个函数，也就是生成了一个参数为 int 的 max 函数，一个参数为 Test 的 max 函数。

int max(int a, int b) {
	return a > b ? a : b;
}

Test max(Test a, Test b) {
	return a > b ? a : b;
}

可以用一句通俗但不严谨的话来说：

模板，只有使用了它，才会生成实际的代码。

除了让编译器自己推导模板的形参类型以外，我们还可以自己显式的声明：

template<typename T>
T max(T a, T b) {
	return a > b ? a : b;
}

int main() {
	int a{ 1 };
	int b{ 2 };
	max(a, b);         // 函数模板 max 被推导为 max<int>
	max<double>(a, b); // 传递模板实参类型，函数模板 max 为 max<double>
}

模板参数推导

更多内容参考：模板实参推导 - cppreference.com

当使用函数模板时，模板参数可以由传入的参数推导。

如果类型 T 传递两个 int 型参数，那编译器会认为 T 是 int 类型。

然而，T 可能只是类型的 “一部分”。若声明 max() 使用 const&，

template<typename T>
T max(const T& a, const T& b) {
	return a > b ? a : b;
}

如果我们 max(1, 2) 或者说 max<int>(x,x)，T 当然会是 int，但是函数形参类型会是 const int&。

不过我们需要注意，有不少情况是没有办法进行推导的：

// 省略 max
using namespace std::string_literals;

int main(){
    max(1, 1.2);            // Error 无法确定你的 T 到底是要 int 还是 double
    max("qiming"s, "123");     // Error 无法确定你的 T 到底是要 std::string 还是 const char[N]
}

node: 字符串字面量后加字母s，是 std::string 类型。

可以显式指定模板的T类型：

max<double>(1, 1.1);
max<std::string>("qiming"s, "123");

又或者说显式类型转换：

max(static_cast<double>(1), 1.2);

但是 std::string 没有办法如此操作，我们可以显式的构造一个无名临时对象：

max("qiming"s, std::string("123"));    // Error 为什么？

此时就不是我们的 T 不明确了，而是函数模板 max 不明确，它会和标准库的 std::max 产生冲突，虽然我们没有使用 std::，但是根据 C++ 的查找规则，（实参依赖查找）ADL，依然可以查找到。

那么我们如何解决呢？很简单，进行有限定名字查找，即使用 :: 或 std:: 说明，你到底要调用 “全局作用域”的 max，还是 std 命名空间中的 max。

::max("qiming"s, std::string("123"));

万能引用与引用折叠

所谓的万能引用（又称转发引用），即 接受左值表达式那形参类型就推导为左值引用，接受右值表达式就推导为右值引用。

template<typename T>
void f(T&& t) {}

int main() {
	int a = 10;
	f(a); // a 是左值表达式，f 是 f<int&> 但它的形参类型是 int&
	f(10);// 10 是右值表达式，f 是 f<int> 但它的形参类型是 int&&
}

被推导为 f<int&> 涉及到了特殊的推导规则：如果 P 是到无 cv 限定模板形参的右值引用（也就是转发引用）且对应函数的调用实参是左值，那么将到 A 的左值引用类型用于 A 的位置进行推导。

通过模板或 typedef 中的类型操作可以构成引用的引用，此时适用引用折叠（reference collapsing）规则：

  • 右值引用的右值引用折叠成右值引用，所有其他组合均折叠成左值引用。

typedef int&  lref;
typedef int&& rref;
int n;
 
lref&  r1 = n; // r1 的类型是 int&
lref&& r2 = n; // r2 的类型是 int&
rref&  r3 = n; // r3 的类型是 int&
rref&& r4 = 1; // r4 的类型是 int&&

template <class Ty>
constexpr Ty&& forward(Ty& Arg) noexcept {
    return static_cast<Ty&&>(Arg);
}

int a = 10;            // 不重要
::forward<int>(a);     // 返回 int&& 因为 Ty 是 int，Ty&& 就是 int&&
::forward<int&>(a);    // 返回 int& 因为 Ty 是 int&，Ty&& 就是 int&
::forward<int&&>(a);   // 返回 int&& 因为 Ty 是 int&&，Ty&& 就是 int&&

有默认实参的模板类型形参

如同函数形参可以有默认值一样，模板形参也可以有默认值。

template<typename T = int>
void f();

f();         // 默认为 f<int>
f<double>(); // 显式指明为 f<double>

一个经典的例子：

using namespace std::string_literals;

template<typename T1, typename T2, typename RT = decltype(true ? T1{} : T2{})>
RT max(const T1& a, const T2& b) {
	return a > b ? a : b;
}

int main() {
	auto ret = ::max("qiming"s, "123");
	std::cout << ret << std::endl;
}

上面定义的 max 函数模板可以接受两种类型的参数（T1和T2），也就是说可以比较两种不同类型的大小。

如何确定其返回值（RT）的类型？

typename RT = decltype(true ? T1{} : T2{})

decltype 可以获取表达式的类型。

这个三目运算符的作用是获取 T1 和 T2 的可转换的公共类型。例如 int 和 double 的公共类型是double。

  1. 我们为什么要设置为 true？

    其实无所谓，设置 false 也行，true 还是 false 不会影响三目表达式的类型。这涉及到了一些复杂的规则，简单的说就是三目表达式要求第二项和第三项之间能够隐式转换，然后整个表达式的类型会是 “公共”类型。

    比如第二项是 int 第三项是 double，三目表达式当然会是 double。

     using T = decltype(true ? 1 : 1.2);
 using T2 = decltype(false ? 1 : 1.2);

    T 和 T2 都是 double 类型。

  2. 为什么需要 T1{}，T2{} 这种形式？

    没有办法，必须构造临时对象来写成这种形式，这里其实是不求值语境，我们只是为了写出这样一种形式，让 decltype 获取表达式的类型罢了。

    模板的默认实参的和函数的默认实参大部分规则相同。

    decltype(true ? T1{} : T2{}) 解决了。

    事实上上面的写法都十分的丑陋与麻烦，我们可以使用 auto 简化这一切。

    template<typename T,typename T2>
auto max(const T& a, const T2& b) -> decltype(true ? a : b){
    return a > b ? a : b;
}

    这是 C++11 后置返回类型。

    这种写法与前面的 RT 是不同的。它们的返回类型是不一样的，如果函数模板的形参是类型相同 true ? a : b 表达式的类型是 const T&；如果是 max(1, 2) 调用，那么也就是 const int&；而前面的例子只是 T 即 int（前面都是用模板类型参数直接构造临时对象，而不是有实际对象，自然如此，比如 T{}）。

    假设以 max(1,1.0) 调用，那么自然返回类型不是 const T&

    max(1, 2.0); // 返回类型为 double

    写法还可以更加简化，使用 C++20 简写函数模板，我们可以直接再简化为：

    decltype(auto) max(const auto& a, const auto& b)  {
	return a > b ? a : b;
}

    效果和上面使用后置返回类型的写法完全一样；C++14 引入了两个特性：

    1. 返回类型推导（也就是函数可以直接写 auto 或 decltype(auto) 做返回类型，而不是像 C++11 那样，只是后置返回类型。

    2. decltype(auto) “如果返回类型没有使用 decltype(auto)，那么推导遵循模板实参推导的规则进行”。我们上面的 max 示例如果不使用 decltype(auto)，按照模板实参的推导规则，是不会有引用和 cv 限定的，就只能推导出返回 T 类型。

    需要注意后置返回类型和返回类型推导的区别，它们不是一种东西，后置返回类型虽然也是写的 auto ，但是它根本没推导，只是占位。

非类型模板形参

既然有”类型模板形参“，自然有非类型的，顾名思义，也就是模板不接受类型，而是接受值或对象。

template<std::size_t N>
void f() { std::cout << N << '\n'; }

f<100>();

非类型模板形参有众多的规则和要求，目前，简单认为需要参数是“常量”即可。

非类型模板形参当然也可以有默认值：

template<std::size_t N = 100>
void f() { std::cout << N << '\n'; }

f();     // 默认      f<100>
f<66>(); // 显式指明  f<66>

重载函数模板

函数模板与非模板函数可以重载。

这里会涉及到非常复杂的函数重载决议3，即选择到底调用哪个函数。

template<typename T>
void test(T) { std::puts("template"); }

void test(int) { std::puts("int"); }

test(1);        // 匹配到test(int)
test(1.2);      // 匹配到模板
test("1");      // 匹配到模板

  • 通常优先选择非模板的函数。****

可变参数模板

和其他语言一样，C++ 也是支持可变参数的，我们必须使用模板才能做到。

老式 C 语言的变长实参有众多弊端，参见。

我们提一个简单的需求：

我需要一个函数 sum，支持 sum(1,2,3.5,x,n...) 即函数 sum 支持任意类型，任意个数的参数进行调用，你应该如何实现？

首先就要引入一个东西：形参包

本节以 C++14 标准进行讲述。

模板形参包是接受零个或更多个模板实参（非类型、类型或模板）的模板形参。函数形参包是接受零个或更多个函数实参的函数形参。

template<typename...Args>
void sum(Args...args){}

这样一个函数，就可以接受任意类型的任意个数的参数调用，我们先观察一下它的语法和普通函数有什么不同。

模板中需要 typename 后跟三个点 Args，函数形参中需要用模板类型形参包后跟着三个点 再 args。

args 是函数形参包，Args 是类型形参包，它们的名字我们可以自定义。

args 里，就存储了我们传入的全部的参数，Args 中存储了我们传入的全部参数的类型。

那么问题来了，存储很简单，我们要如何把这些东西取出来使用呢？这就涉及到另一个知识：形参包展开。

void f(const char*, int, double) { puts("值"); }
void f(const char**, int*, double*) { puts("&"); }

template<typename...Args>
void sum(Args...args){  // const char * args0, int args1, double args2
    f(args...);   // 相当于 f(args0, args1, args2)
    f(&args...);  // 相当于 f(&args0, &args1, &args2)
}

int main() {
    sum("luse", 1, 1.2);
}

sum 的 Args...args 被展开为 const char * args0, int args1, double args2。

这里我们需要定义一个术语：模式。

后随省略号且其中至少有一个形参包的名字的模式会被展开 成零个或更多个逗号分隔的模式实例。

&args... 中 &args 就是模式，在展开的时候，模式，也就是省略号前面的一整个表达式，会被不停的填入对象并添加 &，然后逗号分隔。直至形参包的元素被消耗完。

那么根据这个，我们就能写出一些有意思的东西，比如一次性把它们打印出来：

template<typename...Args>
void print(const Args&...args){    // const char (&args0)[5], const int & args1, const double & args2
    int _[]{ (std::cout << args << ' ' ,0)... };
}

int main() {
    print("luse", 1, 1.2);
}

一步一步看：(std::cout << args << ' ' ,0)... 是一个包展开，那么它的模式是：(std::cout << args << ' ' ,0)，实际展开的时候是：

(std::cout << arg0 << ' ' ,0), (std::cout << arg1 << ' ' ,0),(std::cout << arg2 << ' ' ,0)

很明显是为了打印，对，但是为啥要括号里加个逗号零呢？这是因为逗号表达式是从左往右执行的，返回最右边的值作为整个逗号表达式的值，也就是说：每一个 (std::cout << arg0 << ' ' ,0) 都会返回 0，这主要是为了符合语法，用来初始化数组。我们创建了一个数组 int _[] ，最终这些 0 会用来初始化这个数组，当然，这个数组本身没有用，只是为了创造合适的包展开场所。

花括号包围的初始化器：

在花括号包围的初始化器列表中，也可以出现包展开：

   template<typename... Ts>
   void func(Ts... args)
   {
	   const int size = sizeof...(args) + 2;
	   int res[size] = {1, args..., 2};
	   // 因为初始化器列表保证顺序，所以这可以用来对包的每个元素按顺序调用函数：
	   int dummy[sizeof...(Ts)] = {(std::cout << args, 0)...};
   }

  • 只有在合适的形参包展开场所才能进行形参包展开。

template<typename ...Args>
void print(const Args &...args) {
   (std::cout << args << " ")...; // 不是合适的形参包展开场所 Error！
}

先前的函数模板 print 的实现还存在一些问题，如果形参包为空呢？

也就是说，假设我如此调用：

print(); // Error!

目前这个写法在参数列表为空时会导致 _ 为非良构的 0 长度数组，在严格的模式下造成编译错误。

解决方案是在数组中添加一个元素使其长度始终为正。

 template<typename...Args>
  void print(const Args&...args){    
      int _[]{ 0, (std::cout << args << ' ' ,0)... };
  }

大家不用感到奇怪，当形参包为空的时候，也就基本相当于

int _[]{ 0, };

也就是当做直接去掉 (std::cout << args << ' ' ,0)... 即可。

这个示例其实还有修改的余地：我们的本意并非是创造一个局部的数组，我们只是想执行其中的副作用（打印）。

让这个数组对象直到函数结束生存期才结束，实在是太晚了，我们可以创造一个临时的数组对象，这样它的生存期也就是那一行罢了：

template<typename...Args>
void print(const Args&...args) {
    using Arr = int[]; // 创建临时数组，需要使用别名
    Arr{ 0, (std::cout << args << ' ' ,0)... };
}

这没问题，但是还不够，在某些编译器（clang）这会造成编译器的警告，想要解决也很简单，将它变为一个弃值表达式，也就是转换到 void。

弃值表达式 是只用来实施它的副作用的表达式。从这种表达式计算的值会被舍弃。

template<typename...Args>
void print(const Args&...args){
    using Arr = int[];
    (void)Arr{ 0, (std::cout << args << ' ' ,0)... };
}

此时编译器就开心了，不再有警告。并且也很合理，我们的确只是需要实施副作用而不需要“值”。

我们再给出一个数组的示例：

template<typename...Args>
void print(const Args&...args) {
    int _[]{ (std::cout << args << ' ' ,0)... };
}

template<typename T,std::size_t N, typename...Args>
void f(const T(&array)[N], Args...index) {
    print(array[index]...);
}

int main() {
    int array[10]{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    f(array, 1, 3, 5);
}

在函数形参列表中展开。

我们复用了之前写的 print 函数，我们看新的 f 函数即可。

const T(&array)[N] 注意，这是一个数组引用，我们也使用到了非类型模板形参 N；加括号，(&array) 只是为了区分优先级。那么这里的 T 是 int，N 是 10，组成了一个数组类型。

不必感到奇怪，内建的数组类型，其 size 也是类型的一部分，这就如同 int[1] 和 int[2] 不是一个类型一样，很正常。

print(array[index]...); 其中 array[index]... 是包展开，array[index] 是模式，实际展开的时候就是：

array[arg0], array[arg1], array[arg2]

到此，如果你自己写了，理解了这两个示例，那么你应该就能正确的使用形参包展开，那就可以正确的使用基础的可变参数函数。

那么回到最初的需求，实现一个 sum：

#include <iostream>
#include <type_traits>

template<typename...Args,typename RT = std::common_type_t<Args...>>
RT sum(const Args&...args) {
    RT _[]{ static_cast<RT>(args)... };
    RT n{};
    for (int i = 0; i < sizeof...(args); ++i) {
        n += _[i];
    }
    return n;
}

int main() {
    double ret = sum(1, 2, 3, 4, 5, 6.7);
    std::cout << ret << '\n';       // 21.7
}

std::common_type_t 的作用很简单，就是确定我们传入的共用类型，说白了就是这些东西都能隐式转换到哪个，那就会返回那个类型。

RT _[]{ static_cast<RT>(args)... }; 创建一个数组，形参包在它的初始化器中展开，初始化这个数组，数组存储了我们传入的全部的参数。

因为窄化转换禁止了列表初始化中 int 到 double 的隐式转换，所以我们需要显式的转换为“公共类型” RT。

至于 sizeof... 很简单，单纯的获取形参包的元素个数。

其实也可以不写这么复杂，我们不用手动写循环，直接调用标准库的求和函数。

我们简化一下：

template<typename...Args,typename RT = std::common_type_t<Args...>>
RT sum(const Args&...args) {
    RT _[]{ args... };
    return std::accumulate(std::begin(_), std::end(_), RT{});
}

RT{} 构造一个临时无名对象，表示初始值，std::begin 和 std::end 可以获取数组的首尾地址。

当然了，非类型模板形参也可以使用形参包，我们举个例子：

template<std::size_t... N>
void f(){
    std::size_t _[]{ N... }; // 展开相当于 1UL, 2UL, 3UL, 4UL, 5UL
    std::for_each(std::begin(_), std::end(_), 
        [](std::size_t n){
            std::cout << n << ' ';
        }
    );
}
f<1, 2, 3, 4, 5>();

这很合理，无非是让模板形参存储的不再是类型形参包，而是参数形参包罢了。

模板分文件

新手经常会有一个想法就是，对模板进行分文件，写成 .h .cpp 这种形式。

这显然是不可以的，我们给出了一个项目示例。

后续会讲如何处理

在聊为什么不可以之前，我们必须先从头讲解编译链接，以及 #include 的知识，不然你将无法理解。

include 指令

先从预处理指令 #include 开始，你知道它会做什么吗？

很多人会告诉你，它就是简单的替换，的确，没有问题，但是我觉得不够明确，我给你几个示例：

array.txt

1,2,3,4,5

main.cpp

#include<iostream>

int main(){
    int arr[] = {
#include"array.txt"
    };
    for(int i = 0; i < sizeof(arr)/sizeof(int); ++i)
            std::cout<< arr[i] <<' ';
    std::cout<<'\n';
}

g++ main.cpp -o main

./main

直接编译运行，会打印出 1 2 3 4 5。

#include"array.txt" 直接被替换为了 1,2,3,4,5，所以 arr 是：

int arr[] = {1,2,3,4,5};

或者我们可以使用 gcc 的 -E 选项来查看预处理之后的文件内容：

main2.cpp

int main(){
    int arr[] = {
#include"array.txt"
    };
}

去除头文件打印之类的是因为，iostream 的内容非常庞大，不利于我们关注数组 arr。

g++ -E main2.cpp

# 0 "main2.cpp"
# 0 "<built-in>"
# 0 "<command-line>"
# 1 "main2.cpp"
int main(){
    int arr[] = {
# 1 "array.txt" 1
1,2,3,4,5
# 4 "main2.cpp" 2
    };
}

# 0 # 1 这些是 gcc 的行号更改指令。不用过多关注，不是当前的重点，明白 #include 会进行替换即可。

分文件的原理是什么？

我们通常将函数声明放在 .h 文件中，将函数定义放在 .cpp 文件中，我们只需要在需要使用的文件中 include 一个 .h 文件；我们前面也说了，include 就是复制，事实上是把函数声明复制到了我们当前的文件中。

//main.cpp
#include "test.h"

int main(){
    f();    // 非模板，OK
}

test.h 只是存放了函数声明，函数定义在 test.cpp 中，我们编译的时候是选择编译了 main.cpp 与 test.cpp 这两个文件，那么为什么程序可以成功编译运行呢？

是怎么找到函数定义的呢？明明我们的 main.cpp 其实预处理过后只有函数声明而没有函数定义。

这就是链接器做的事情，如果编译器在编译一个翻译单元（如 main.cpp）的时候，如果发现找不到函数的定义，那么就会空着一个符号地址，将它编译为目标文件。期待链接器在链接的时候去其他的翻译单元找到定义来填充符号。

我们的 test.cpp 里面存放了 f 的函数定义，并且具备外部链接，在编译成目标文件之后之后，和 main.cpp 编译的目标文件进行链接，链接器能找到函数 f 的符号。

不单单是函数，全局变量等都是这样，这是编译链接的基本原理和步骤。

类会有所不同，总而言之后续视频会单独讲解的。

那么不能模板不能分文件的原因就显而易见了

  • 模板，只有你“用”了它，才会生成实际的代码。

你单纯的放在一个 .cpp 文件中，它不会生成任何实际的代码，自然也没有函数定义，也谈不上链接器找符号了。

所以模板通常是直接放在 .h 文件中，而不会分文件。或者说用 .hpp 这种后缀，这种约定俗成的，代表这个文件里放的是模板。

#C++ 1
可计算与计算复杂度-题目
单调栈