C++模板（入门）

泛型编程

以往的实现一个交换函数，需要用到函数重载

每一个类型的交换都要写一个函数

void Swap(int& left, int& right)
{
	int temp = left;
	left = right;
	right = temp;
}
void Swap(double& left, double& right)
{
	double temp = left;
	left = right;
	right = temp;
}
void Swap(char& left, char& right)
{
	char temp = left;
	left = right;
	right = temp;
}

使用函数重载虽然可以实现，但是有一下几个不好的地方：

1. 重载的函数仅仅是类型不同，代码复用率比较低，只要有新类型出现时，就需要用户自己增加对应的函数（重复同样的事情）
2. 代码的可维护性比较低，一个出错可能所有的重载均出错
   那能否告诉编译器一个模子，让编译器根据不同的类型利用该模子来生成代码呢？

在C++中，这个模子就是模板

而泛型编程，就是编写与类型无关的通用代码，是代码复用的一种手段。模板就是泛型编程的基础

C++中，模板有两种：函数模板和类模板

函数模板

函数模板的概念

函数模板代表了一个函数家族，该函数模板与类型无关，在使用时被参数化，根据实参类型产生函数的特定类型版本。

就如Swap交换函数，我们只需要写一个模板，各种类型包括自定义类型的变量都可以使用，实现交换

函数模板格式

template<typename T1, typename T2,......,typename Tn>
返回值类型 函数名(参数列表){}  

或者

template<class T1, class T2,......, typename Tn>
返回值类型 函数名(参数列表){}

• typename后的类型名字 T 可以随便取，比如T、K、V等，一般是大写字母或者单词首字母大写，一般使用T、T1，T2等

• T1、T2等 代表模板类型（虚拟类型，即需要根据实参推导的）

如Swap函数

template<typename T>
void Swap(T& left, T& right)
{
	T tmp = left;
	left = right;
	right = tmp;
}
int main()
{
	int a = 10, b = 20;
	Swap(a, b);//交换整形

	double d1 = 1.1, d2 = 2.2;
	Swap(d1, d2);//交换浮点型

	char ch1 = 'A', ch2 = 'B';
	Swap(ch1, ch2);//交换字符型
	return 0;
}

//发现上面不同类型的数据都发生了交换
//所以这就是 模板的应用

typename是用来定义模板参数的关键字，也可以利用class（不能使用struct 代替class）

需要注意的是：上面调用的并不是同一个函数，而是调用编译器根据具体的类型生成的对应的函数

最明显的地方：参数传递的大小都不同，也就是说对应的函数栈帧的大小都不同，因此肯定不是同一个函数。

函数模板的原理

函数模板就像是一个图纸，它并不是函数，是编译器用使用该方式产生特定具体类型函数的模具。所以其实模板就是将本来应该我们做的重复的事情交给了编译器。

对于函数模板，编译器会做两件事

1. 模板参数的推演：根据函数传递的参数去推演模板里面T的类型
2. 推演参数实例化：根据推演出来的类型生成对应的函数，这些函数还是多个函数，地址也不同

所以，模板的原理就是 把原本我们需要做的事情让编译器去做，我们就不需要去写重复的函数了，编译器会自动推导生成

所以模板必然会让编译的时间变长一些，因为编译器要做的事情更多了

注意，虽然都是调用一个模板，但其汇编指令其实是不同的，会根据实参的类型生成不同的汇编指令（调试的时候看上去只是进入模板，看不出调用了不同的函数）

如图：调用double和char类型的Swap函数的地址都不同

函数模板的实例化

用不同类型的参数使用函数模板时，称为函数模板的实例化。模板参数实例化分为：隐式实例化和显式实例化

隐式实例化

隐式实例化：让编译器根据实参推演模板参数的实际类型
但是分为

1. 参数是同一类型，进行隐式实例化是没有任何问题的

template<class T>
T Add(const T& left, const T& right)
{
	return left + right;
}
int main()
{
	int a1 = 10, a2 = 20;
	double d1 = 10.0, d2 = 20.0;
	Add(a1, a2);//int类型相加
	Add(d1, d2);//double类型相加
    return 0;
}

2. 对于实参不同类型

template<typename T>
T Add(const T& left, const T& right)
{
	return left + right;
}
int main()
{
	int a1 = 10;
	double d1 = 10.0;
	Add(a1,d1);//int和double相加
    return 0;
}

该语句不能通过编译，因为在编译期间，当编译器看到该实例化时，需要推演其实参类型
通过实参a1将T推演为int，通过实参d1将T推演为double类型，但模板参数列表中只有一个T，编译器无法确定此处到底该将T确定为int 或者 double类型而报错（矛盾！）

注意：在模板中，编译器一般不会进行类型转换操作，因为一旦转化出问题，编译器就需要背黑锅，如果是函数Add(int left,int right)就可以进行类型转换（只是可能会发生数据阶段）

此时有3种处理方式：1. 用户自己来强制转化 2. 使用两个模板参数 3. 显示实例化

1. 强制转换

   Add(a1,(int)d1);
   //或者
   Add((double)a1,d1);
   

2. 两个模板参数（不推荐）

   使用两个模板参数就不会推演矛盾了
   但是两个模板参数也有其他的一些问题
   比如返回值返回哪一个？ 第一个参数还是第二个？

   template<typename T1,typename T2>
   //假设返回值设置为T1类型
   T1 Add(const T1& left, const T2& right)
   {
   	return left + right;//不同类型相加会提升（小的向大的提升）
       //然后返回时再隐式转换为T1类型 
   }
   int main()
   {
       Add(1.1,2);//这样返回的类型就是 double
       return 0;
   }
   

显示实例化

除了上面的传递参数的时候进行把参数进行强制类型转换，还有一种方法就是 不让编译器推演实参的类型了，我们直接指定告诉编译器实参是什么类型

对于上面的Add函数，可以这样解决：

//显示实例化
Add<int>(1.1, 2);//不用编译器推演，指定T是int，直接实例化一个int的
Add<double>(1.1, 2);//不用编译器推演，指定T是double，直接实例化一个double的

这样，即使 1.1 不是int 也会自动隐式转换成为int，2 不是double 也会自动隐式转换位double

但什么时候用到显示实例化呢？常见的有这两个场景

1. 类模板显式实例化

template<typename T>
class A{
	T aa[10];//存放10个T类型数据
};

//如果想构造一个存放int的A对象
A<int> obj; //显示实例化模板参数为int类型

2. 参数不是模板类型

  //模板函数的参数为int
  T* func(int n)
  {
      T* a = new T[n];
      return a;
  }
  //因为编译器是根据传递的实参进行参数推演的
  //而模板的形参并没有模板类型，这样根据传递的实参无法进行推演！
  //这里就必须使用显示实例化才能调用
  
  func<double>(5);//显示实例化参数为 double 类型

模板参数的匹配

难免会出现这种情况

//专门处理int的加法函数
int Add(int left, int right)
{
	return left + right;
}
//通用加法函数
template<class T>
T Add(const T& left, const T& right)
{
	return left + right;
}
//针对两个实参不同的加法函数
template<typename T1,typename T2>
T1 Add(const T1& left, const T2& right)
{
	return left + right;
}
int main()
{
    Add(1, 1);//调用针对int的
	Add(1.1, 2.2);//调用通用的（第二个）
    Add(1.1,2);//调用第三个
	return 0;    
}

此时会怎么调用呢？

编译器会先看又没参数匹配的，如果有匹配的就去调用现成的函数

如果模板可以产生一个具有更好匹配的函数，就根据实参和模板去实例化从而产生一个！

• Add(1,1)会直接调写好的针对int的加法函数

• Add(1.1,2.2)会去实例化一个double的加法函数然后调用。（double可以传给int的形参，但是因为模板可以产生一个更匹配的，所以此时会优先模板）

• 因为两个参数是同类型，所以不回去调用第三个。只有当两个参数是不同类型才会调用第三个！如Add(1.1,2)

类模板

为什么有类模板

C中我们使用栈存放数据，通常采用typedef 类型 STDataType

当需要更改类型的时候，只需要把typedef处的类型变一下即可

typedef int STDataType;
class Stack
{
private:
	STDataType* _a;
    int top;
    int capacity;
}

但是这并不是泛型编程，因为还是针对的某一具体类型

如果有这样的要求：同时定义一个整形栈int和一个字符栈char怎么办？如果真的要做就需要定义一个Stack_int和一个Stack_char，太挫了！

所以需要模板来做这件事

类模板的定义格式

template<class T1, class T2, ..., class Tn>
class 类模板名
{
// 类内成员定义
};

以Stack为例,下面就是一个Stack类的模板，模板参数为T

template<typename T>
class Stack
{
public:
	Stack(size_t capacity = 0)
		:_a(nullptr)
		, _top(0)
		, _capacity(capacity)
	{
		if (_capacity > 0)
		{
			_a = new T[_capacity];
		}
	}
private:
	T* _a;
	size_t _top;
	size_t _capacity;
};

类模板的实例化

不同于函数模板，函数可以传递实参从而可以推演出模板参数的实际类型。但是定义一个对象Stack st的时候是没有参数传递的，所以无法推导处模板参数的实际类型，必须采用显式实例化！

类模板实例化需要在类模板名字后跟<>，然后将实例化的类型放在<>中即可，类模板名字不是真正的类，而实例化的结果才是真正的类

//Stack是类名， Stack<int>是一个类型
Stack<int> st1;//int      
Stack<char> st2;//char

类模板的原理

虽然都是用了一个类模板，其实Stack<int>和Stack<char>都不是一个类型，就相当于编译器根据类模板实例化出了两个类（虽然我们看不到）

Stack模板类的简单实现（不涉及深拷贝）

//类模板
template<typename T>
class Stack
{
public:
	Stack(size_t capacity = 0)
		:_a(nullptr)
		, _top(0)
		, _capacity(capacity)
	{
		if (_capacity > 0)
		{
			_a = new T[_capacity];
		}
	}
	~Stack()
	{
		delete[] _a;
		_a = nullptr;
		_top = _capacity = 0;
	}
	void Push(const T& x)
	{
		//检查扩容
		if (_top == _capacity)
		{
			size_t newCapacity = _capacity == 0 ? 4 : 2 * _capacity;
			//1. 开新空间
			//2. 拷贝数据
			//3. 删旧空间
			T* tmp = new T[newCapacity];
			//如果a不为空  防止数组为空导致memcpy崩溃
			if (_a)
			{
				memcpy(tmp, _a, sizeof(T) * newCapacity);
				delete[] _a;
			}
			_a = tmp;
			_capacity = newCapacity;
		}
		//插入数据
		_a[_top] = x;
		++_top;
	}
	void Pop()
	{
		assert(_top > 0);
		--_top;
	}
	const T& Top()
	{
		assert(_top > 0);
		return _a[_top - 1];
	}
	bool Empty()
	{
		return _top == 0;
	}
private:
	T* _a;
	size_t _top;
	size_t _capacity;

};

注意问题：new的扩容需要自己写，new/delete不具有realloc的扩容功能

步骤：

1. new一个新空间
2. 把原空间内容拷贝到新空间
3. delete原空间

模板的注意问题

模板不支持分离编译

1. 模板不支持分离编译，即不支持声明放在.h，定义放在.cpp

2. 但是模板支持在同一个.cpp或者.h文件中声明和定义分离，但是需要先声明模板参数。并且指定类域需要Stack<类型>::

   template<typename T>
   class Stack()
   {
       /*...*/
       void Push(const T& x);
   }
   
   //Push的定义
   template<typename T>  //声明模板参数，否则后面不认识T
   void Stack<int>::Push(const T& x)
   {
       /***/
   }
   

因此有时候把模板定义和声明都写在同一个.h文件，这时候.h文件也叫做.hpp,即 hplusplus(不止是声明)

模板的缺省参数

写一个函数可以有缺省参数，该参数是一个值

模板也可以有一个缺省参数，该参数是一个类型

template<typename T = int>
class Stack
{
    /**/
}
int main()
{
    Stack st;//error
    Stack<> st;//不传递模板参数，但必须写<> 默认是缺省参数
    return 0;
}