[数据结构与算法]【C++】详谈模版

泛型编程与模板

实现一个简单的Swap交换函数：

// 交换int类型数据的Swap函数
void Swap (int& left, int& right)
{
	int temp = left;
	left = right;
	right = temp;
}

很明显上面的Swap函数只能交换int类型的数据，而实际中要交换的数据类型会有许多。不过C++支持函数重载，我们可以将所有的交换数据类型的Swap函数全重载出来：

// 交换char类型数据的Swap函数
void Swap (char& left, char& right)
{...}
// 交换double类型数据的Swap函数
void Swap (double& left, double& right)
{...}
// 交换...类型数据的Swap函数

如果要实现一个通用类型的Swap函数，采用函数重载就非常不可取了：

• 重载的函数仅仅只是类型不同，代码的复用率低；
• 实际中除了要交换C++的内置类型数据，还可能交换用户自定义类型的数据，如果事先不知道这个类型是什么，如何写出该类型的交换函数？

我们常用的C++各种库函数，比如STL库（标准模板库），里面涉及的都是通用函数，这些通用函数的实现就是利用了泛型编程。

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

泛型 是指具有在多种数据类型上皆可操作的含义，与模板有些相似

STL包含了许多常用的算法和数据结构，但其内部实现均将算法与数据结构完全分离，其中算法是泛型的，不与任何特定数据结构或对象类型系在一起

==模版 != 泛型编程，模版可以做到与类型无关，不一定能做到代码通用；

但模版是泛型编程的基础，是实现泛型编程非常重要的一个环境；
模板的本质：类型参数化

为什么说模版 != 泛型编程？
举例：若要实现一个通用的查找方法find()函数

// 我们自然想到了用模版来实现：
template<typename T>
int find(const T& array[], size_t size, const T& data)
{
	for (size_t i = 0; i < size; ++i)
	{
		if (array[i] == data)
		{
			return i;
		}
	}
	return -1;
}

但这个find函数模版真的是一个泛型方法吗？

如果我们要查找的数据不是在连续的空间（如数组），而是在链表、堆或二叉树中，那么这个方法根本无法实现功能；

因此这个find只是个函数模版，而不是泛型编程代码；C++的STL（标准模版库）大都是泛型编程，用到了许多特殊的方法来实现泛型编程（迭代器…），其中数据结构就是用模版来进行封装的；

模版有哪些

1. 函数模版

概念

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

定义

• 定义模板参数列表

  定义模板关键字template；
  定义模版参数关键字typname，也可用class（早期的编译器只能用class）
  （注意这里不能用struct替换class）

  template<typename T1, typename T2,......,typename Tn>
返回值类型 函数名(参数列表){}
  （T就是一个通用类型，可替换名字）

• 定义函数模板

  函数定义时将需要替换的类型直接用通用类型即可。

例子：

1. 一个Swap函数模版的例子：（模版类型只有一个）

template<class T>  //函数模版的模版参数列表，告诉编辑器T是一个类型
void Swap (T& left, T& right)  //函数模版的实现
{...}

// 注意，上述代码只是一个函数模版（模具），并不是一个真正的函数。

2. 一个多参数模版

template<class T1, class T2, typename T3>  // class与typename等价
void Fun(T1 a, T2 b, T3 c)  //这三个参数类型可以不一样
{
	cout << a << endl;
	cout << b << endl;
	cout << c << endl;
} 

• 函数模版的注意事项：
  模版定义在主函数外；
  模版参数无特殊情况最好用引用类型（效率高）；
  函数模版并不是真正的函数，只是编译器的一种编译规则；

实例化——函数模版的使用

揭示函数模版的原理：

• 函数模版并不是真正的函数，只是编译器的一种编译规则；
• 函数模版未实例化前，编译器不会生成具体类型的函数；
• 只有当该模版使用时被，才会实例化出对应类型的函数。

template<class T>  //模版类型只有一个
T Add(T a, T b)  //实现一个加法函数模版
{
	return a + b;
}
int main()
{
	// 函数模版的三种隐式实例化
	cout << Add(1, 2) << endl;
	cout << Add(1.1, 2.2) << endl;
	cout << Add('a', 'b') << endl;

	return 0;
}

通过反汇编代码查看模版的实例化情况：

函数模版实例化的分类：

1. 隐式实例化——直接调用模版

   当用户直接调用，编译器会根据实例化的结果来推演参数的类型，根据推演的结果生成具体处理该参数类型的实例化函数。
   （上面的例子已经体现了函数模版隐式实例化的具体做法）

   但是隐式实例化无法处理某些特殊情况：
   
   解决方法：用户强转类型 或 采用显示实例化模版
   

2. 显示实例化 ——函数名<类型>
   编译器不需要对实参类型进行推演，直接按照<>内类型与模版自动生成相应函数。
   

几点规则

【思考】上面实现了一个Add()函数模版，可以实现任意类型的数据相加，但是当类型为char字符时，调用该模版返回的值并不是我想要的

• 一个非模板函数可以和一个同名函数模板同时存在，且编译器优先调用已存在的非模版函数而不是模版，但该函数模板仍可以被显示实例化后调用
  
  

• 模板函数不允许自动类型转换，但普通函数可以进行自动类型转换
  

• 模版与同名函数同时存在，但使用时如果函数需类型转换，编译器会对比模版与函数，优先选择最匹配的方式
  

2. 类模版

概念

通过替换类中的类型为通用类型，让类变成模版类，这时类名就是模版类名。
类模板不同于函数模板的地方在于，编译器不能为类模板推断参数类型。

定义

• 定义模版参数列表
  同函数模版一样，使用关键字template和typename(或class)

• 定义类模版
  定义类，并将类中元素类型替换为通用类型；

  • 类模板的成员函数：
    对于类来说，其内部有成员函数和成员变量，他们定义时涉及的类型均可使用通用类型，但需特别注意成员函数：

    成员函数在类中定义：直接替换类型为通用类型即可；
    对于类模版来说，一般成员函数最好直接定义在类中；

    成员函数在类外定义：需在函数定义上方添加新的模版参数列表，其实相当于定义了一个函数模版（类模版中的成员函数模版）

  • 类模板和友元：【?】

    如果一个类模板包含一个非模板友元，则该友元可以访问该模板实例的所有成员

    如果友元也是模板，类可以授权给所有友元模板实例，也可以只授权给特定实例。

例：实现一个简单的自定义顺序表模版

// 动态顺序表类模版
template <typename T>
class SeqList
{
private:
	// 检测顺序表空间是否扩容
	void CheckCapacity()
	{
		if (_size < _capacity)
		{
			return;
		}
		// 开辟新空间（左移一位变两倍）
		T* temp = new T[_capacity << 1];
		// 拷贝原空间
		memcpy(temp, _arr, _size*sizeof(T));
		// 释放旧空间
		delete[] _arr;
		// 更新对象成员
		_arr = temp;
		_capacity *= 2;
	}
public:
	// 无参构造函数
	SeqList()
		:_arr(new T[3])
		, _size(0)
		, _capacity(3)
	{}
	// 带参构造函数
	SeqList(T* arr, size_t size)
		:_arr(new T[size])
		, _size(size)
		, _capacity(size)
	{
		for (size_t i = 0; i < size; ++i)
		{
			_arr[i] = arr[i];
		}
	}
	// 拷贝构造函数
	SeqList(const SeqList& s)
		: _arr(new T[s._size])
		, _size(s._size)
		, _capacity(s._size)
	{
		for (size_t i = 0; i < s._size; ++i)
		{
			_arr[i] = s._arr[i];
		}
	}
	// 打印顺序表
	void Print()
	{
		// 判断是否有元素
		if (_size == 0)
		{
			cout << "Print Error!" << endl;
			return;
		}
		for (int i = 0; i < _size; i++)
		{
			cout << _arr[i] << " ";
		}
		cout << endl;
	}
	// 尾插--类内仅作声明，类外定义成员函数
	void PushBack(const T& data);
	// 尾删
	void PopBack()
	{
		// 判断是否有元素
		if (_size == 0)
		{
			cout << "PopBack Error!" << endl;
			return;
		}
		// 更新对象成员
		_size--;
	}
	// 测试类外定义成员函数模版
	template<typename U>  //函数模版参数
	void Func(U a);  //类内函数声明


private:
	// 定义一个动态顺序表
	T* _arr;          // 动态数组
	size_t _size;     // 有效元素的个数
	size_t _capacity; // 表示空间总的大小
};

// 类模板成员函数类外定义，需要加上类的模板参数列表
template<typename T>
void SeqList<T>::PushBack(const T& data)
{
	// 检测是否需扩容
	CheckCapacity();
	// 尾部直接添加
	_array[_size] = data;
	// 更新对象成员
	_size++;
}

// 类外定义成员函数，就相当与定义了一个函数模版
// 成员函数的模版参数可以与类模版不同
// 测试：（该函数无实际意义）
template<typename T>   //类模版的模版参数列表
template<typename U>   //函数模版的模版参数列表
					   //注意这两个模版不能写到一起			
void SeqList<T>::Func(U a)
{
	cout << a << endl;
}

实例化

类模版只有显示实例化一种方法
例：实例上面的顺序表类模版

int main()
{
	// 定义一个类对象
	// SeqList<int>相当于一个类名
	SeqList<int> s1;
	// 后面方法与正常类使用无异
	s1.PushBack(1);
	s1.PushBack(2);
	s1.PopBack();

	// 使用成员函数模版
	s1.Func<double>(1.1);

	return 0;
}

注意事项

• 类模板名是一个模版名，并不是类型，不能用来实例化对象。要实例化对象需要用类模板名<具体类型>（相当于一个类）来进行实例化

  元素可以为内置类型，比如：
  SeqList<int>是一个元素为int的顺序表类、
  SeqList<double>是一个元素为double的顺序表类、
  …

  元素也可以是自定义类型：SeqList<Data>是一个元素为Data对象的顺序表类；

• 类外定义成员函数或成员函数模版，记得添加类模版和函数模版的参数列表

• 类模板是一个类家族，模板类是通过类模板实例化的具体类

非类型模版参数

模版的实质就是类型参数化，对于函数模版或类模版的定义，第一步都是定义模版参数列表；

模板参数种类

上述的参数列表可以有两种模版参数：

1. 类型形参：跟在class或typename后的参数类型名称，可以是内置类型或自定义类型；
2. 非类型形参（非类型模版参数）：用一个常量作为类(函数)模板的一个参数，在类(函数)模板中可将该参数当成常量来使用
   例：一个函数模版采用非类型参数
   

注意事项

1. 类模版和函数模版均可采用非类型模版参数；

2. 非类型模版参数可以设为缺省参数；

3. 非类型模版参数本质是常量，函数内不可当成左值修改内容；
   

4. 浮点数、类对象以及字符串是不允许作为非类型模板参数；
   

5. 非类型的模板参数必须在编译期就能确认结果；
   
   

模版的特化

为什么要特化？

这是一个很简单的Max()函数模版：

// 实现一个返回两值中的最大值
template <typename T>
T Max(T left, T right)
{
	return left > right ? left : right;
}

使用该模版的实例化：

通常情况下，使用模板可以实现一些与类型无关的代码，但对于一些特殊类型的使用模版的实例化代码无法达到目的，出现结果错误。

为了解决这种问题，C++提供了模版特化这样的机制，函数模版和类模版都可以特化。

模版特化种类

1. 函数模版特化（不推荐使用）

特化步骤：

例：上述Max()函数模版对于字符串类型的特化

// 实现一个返回两值中的最大值
template <typename T>
T Max(T left, T right)
{
	return left > right ? left : right;
}
// Max()模版的特化
template<>  
char* Max<char*>(char* left, char* right)  
//注意模版中所有的通用类型都必须用<>内的数据类型替换
{
	return strcmp(left, right) > 0 ? left : right;
}

为什么不推荐使用函数模版特化？

对于刚才的Max()函数模版，我们不希望函数内部修改参数，为了代码的安全与高效，将其修改为：

// 实现一个返回两值中的最大值
template <typename T>
const T& Max(const T& left, const T& right)  //&引用类型更高效、const更安全
{
	return left > right ? left : right;
}

修改了函数模版，其特化理所当然也要改变，但是并不容易正确使用

而前面我们在函数模版的匹配规则说过，C++支持与函数模版同名的函数存在，使用模版同名函数也能处理上述问题，而且简单不易出错。因此我们推荐使用模版同名函数，而不是为函数模版提供特化

实际例子展示：注意那个特殊的特化函数模版的例子

#include<iostream>
using namespace std;

// 本体函数模版
template<typename Type>
const Type Max(const Type &a, const Type &b)
{
	cout << "This is Max<Type>" << endl;
	return a > b ? a : b;
}

// 函数模版的特化
// 特化1
template<>
const int Max<int>(const int &a, const int &b)
{
	cout << "This is Max<int>" << endl;
	return a > b ? a : b;
}

// 特化2
template<>
const char Max<char>(const char &a, const char &b)
{
	cout << "This is Max<char>" << endl;
	return a > b ? a : b;
}

// 特化3
// 一个特殊易错的例子：中间必须是const char*&
template<>
const char*& Max<const char*&>(const char* &a, const char* &b)
{
	cout << "This is Max<char>" << endl;
	return a > b ? a : b;
}

// 同名函数
int Max(const int &a, const int &b)
{
	cout << "This is Max" << endl;
	return a > b ? a : b;
}

int main()

{
	Max(10, 20);        //优先调用同名函数
	Max(12.34, 23.45);  //调用本体模版
	Max('A', 'B');      //调用特化模版2
	Max<int>(20, 30);   //调用特化模版1  
	return 0;
}

2. 类模版特化

特化步骤：大体与函数特化步骤相同

类模版特化分为：

全特化：将模板参数列表中所有的参数都确定化

// 类模版特化
// 测试类模版
template<class T1, class T2>
class Test
{
public:
	Data() 
	{ 
		cout << "调用Test类模版" << endl; 
	}
private:
	T1 _d1;
	T2 _d2;
};

// 全特化
template<>
class Test<int, char>
{
public:
	Test()
	{
		cout << "调用类模版特化" << endl;
	}
private:
	int _d1;
	char _d2;
};

偏特化（两种）：

• 部分特化：将模板参数类表中的一部分参数特化

// 偏特化
// 形式1：部分特化
template<class T1>
class Test<T1, char>
{
public:
	Test()
	{
		cout << "调用偏特化" << endl;
	}
private:
	int _d1;
	char _d2;
};

• 对参数限制：偏特化并不仅仅是指特化部分参数，而是针对模板参数更进一步的条件限制所设计出来的一个特化版本

// 形式2：参数限制
template<class T1, class T2>
class Test<T1*, T2*>
{
public:
	Test()
	{
		cout << "偏特化：参数限制" << endl;
	}
private:
	T1* _d1;
	T2* _d2;
};

了解一下

类模版特化用途之一：类型萃取（仅作了解）
类型萃取了解
C++之类型萃取

模版优缺点

模版还有一个很重要的概念：分离编译！这个概念对于自定义实现模版真的非常重要，详细内容可参考下一篇博客：【C++】模版的分离编译与多文件编程

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖