C++学习之模板

发表于 | 分类于

泛型编程

继承（公有、私有、保护）和包含，并不总能够满足重用代码的需要。

有一种概念，叫做容器（container class）。例如Stack、Queue。容器是用来设计存储各种对象和数据类型的。但之前提到的ADT中，我们把Stack设计成只能存储unsigned long 值。如果我们想建立保存double、或string对象的stack，那么要专门定义新的stack。除了保存对象的类型不同，这两种stack的其他代码应该是相同的。与其再编写一遍重复性很高的代码，不如编写一个泛型（generic）（意思是：独立于类型的）栈。对于泛型的栈，我们将具体的类型作为参数传递给这个类，这样就可以通过使用通用的代码，实现一个栈，能存储不同类型的值。

typedef 可以实现这种需求，然而，typedef有两个缺点：

  • 每次修改类型都要编辑源代码。
  • 在每个程序中只能用这种技术同时生成一种栈。即你不能让typedef同时代表两种不同的类型。

C++的类模板为生成通用的类声明提供了可靠的方法。模板提供参数化类型（parameterized），即能够将类型传递给接收方来建立类or函数。

泛型编程（Generic Programming）最初提出时的动机很简单直接：发明一种语言机制，能够帮助实现一个通用的标准容器库。所谓通用的标准容器库，就是要能够做到，比如用一个List类存放所有可能类型的对象这样的事；泛型编程让你编写完全一般化并可重复使用的算法，其效率与针对某特定数据类型而设计的算法相同。泛型即是指具有在多种数据类型上皆可操作的含义，与模板有些相似。STL巨大，而且可以扩充，它包含很多计算机基本算法和数据结构，而且将算法与数据结构完全分离，其中算法是泛型的，不与任何特定数据结构或对象类型系在一起。

类模板

定义类模板

这次的目标，就是写一个Stack模板类。定义模板时，以这样的代码开头：

1
template<class Type>

关键字template告诉编译器，将要定义一个模板。尖括号内的内容看做是一个参数列表。type是类型名称。
Type并不一定是一个类，这里表明Type是一个通用的类型说明符。较新的C++允许用不太容易混淆的关键字typename来代替。

泛型标识符——这里的Type——叫做类型参数（type parameter），意味着他们也和变量一样，但赋给他们的是类型。当模板被调用时，Type将被具体的类型值（int、string、等等）所取代。用模板成员函数替代原有类的类方法，每个函数头都要以相同的模板声明打头。此外，需要将类限定符从Stack:: 改成Stack<Type>:: 。模板的具体使用被称为实例化（instantiation）或者具体化（specialization）。不能将模板函数放在独立实现的文件中。由于模板不是函数，它们不能单独编译。模板必须与特定的模板实例化请求一起使用。

使用类模板

仅在程序包含模板时，不能生成模板类。必须请求实例化。需要声明一个类型为模板类的对象。方法是用所需的类型名替代泛型名。例如：

1
2
Stack<int> kernels;
Stack<string> colonels;

Stack<int>会用int替代模板中的所有Type，string也会如此做。

下面是Stack模板类的完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
//stack.h -- class defination for the Stack ADT
#ifndef STACK_H_
#define STACK_H_

//typedef unsigned long Item; 学泛型了，typedef guna

template <class T>
class Stack
{
private:
	enum { MAX = 100 };
	T items[MAX];
	int top;
public:
	Stack();
	bool isempty() const;
	bool isfull() const;
	bool push(const T & item);
	bool pop(T & item);
};
#endif

//stack.cpp -- Stack member functions
//#include "stack.h"
template <class T>
Stack<T>::Stack()
{
	top = 0;
}

template <class T>
bool Stack<T>::isempty()const
{
	return top == 0;
}

template <class T>
bool Stack<T>::isfull()const
{
	return top == MAX;
}

template <class T>
bool Stack<T>::push(const T & item)
{
	if (top < MAX)
	{
		items[top++] = item;
		return true;
	}
	else
		return false;
}

template <class T>
bool Stack<T>::pop(T & item)
{
	if (top > 0)
	{
		item = items[--top];
		return true;
	}
	else
		return false;
}

深入讨论模板类

可以将内置类型或类作为模板Stack<T>的类型。指针可以吗？比方说，不用string对象，用C风格字符串处理方式——char * 作为参数。答案是：可以这么创建，但如果不对程序做重大修改，将无法很好的工作。接下来介绍原因，然后介绍一个指针栈的例子。

设计模板时应牢记的教训——切记盲目地使用模板。（你的代码，真的有对泛型的需求吗？）

这里用完全正确的Stack做示例：

1
Stack<char *>st; //create a stack for pointers-to-char

版本一

1
2
char * str;
cin>>str;

用char * 而不是string对象来接受键盘输入。这种方法很快就失败了，因为仅仅创建了指针，没有为保存输入字符串而开辟空间。

版本二

1
2
char str[40];
cin>>str;

这里开辟了空间，str的类型是char *，也可以放在栈中。但在栈内的操作，会与我们假设的相冲突。

1
2
3
4
5
6
7
8
9
10
11
template <class T>
bool Stack<T>::pop(T & item)
{
	if (top > 0)
	{
		item = items[--top];
		return true;
	}
	else
		return false;
}

item 要必须引用某种类型的左值，而不是数组名。

版本三

1
char *str = new char[40];

好似解决了上述问题，但又有新的问题：只有一个str 变量，而这个变量只会指向相同的内存单元。每当读取新的字符串时，内存的内容都发生改变，但执行压入操作的时候，加入到栈的地址都相同。因此，pop时弹出的都是相同的地址，结果总是最后一个输入的字符串。总之，这样的栈没有任何用途。

正确的指针栈

提供一个指针数组，每个指针指向不同的字符串，把（指向不同内存空间的）指针放到栈中是有意义的。创建不同的指针，不是栈的职责，这点要搞清楚，栈是管理指针，而不是创建指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
template <class T>
class Stack
{
private:
	enum { SIZE = 10 };
	int size;
	T *items;
	int top;
public:
	//新的构造函数，用栈大小size做参数，而且必须显示调用，有默认参数。
	explicit Stack(int ss = SIZE) { top = 0; size = ss; items = new T[size]; }

	//动态数组所需要的显示复制构造函数、析构函数、赋值运算符。
	Stack(const Stack &st);
	~Stack() { delete[]items; }
	Stack & operator=(const Stack &st);

	bool isempty() const;
	bool isfull() const;
	bool push(const T & item);
	bool pop(T & item);
};

template<class T>
Stack<T>::Stack(const Stack &st)
{
	size = st.size;
	top = st.top;
	items = new T[size];
	for (int i = 0; i < top; i++)
		items[i] = st.items[i];
}

template<class T>
Stack<T> & Stack<T>::operator=(const Stack &st)
{
	if (this == &st)
		return *this;//avoid assign to itself
	delete[] items;
	size = st.size;
	top = st.top;
	items = new T[size];
	for (int i = 0; i < top; i++)
		items[i] = st.items[i];
}


//下面的没有改变。
template <class T>
bool Stack<T>::isempty()const
{
	return top == 0;
}

template <class T>
bool Stack<T>::isfull()const
{
	return top == MAX;
}

template <class T>
bool Stack<T>::push(const T & item)
{
	if (top < MAX)
	{
		items[top++] = item;
		return true;
	}
	else
		return false;
}

template <class T>
bool Stack<T>::pop(T & item)
{
	if (top > 0)
	{
		item = items[--top];
		return true;
	}
	else
		return false;
}

简单的数组模板

模板常用作容器类，因为类型参数的概念非常适合将相同的存储方案用于不同的类型。为容器提供可重用代码是引入模板的重要动机。下面是一个允许指定数组大小的简单数组模板。C++11新增模板array就是这么做的。

这里特别关注一下模板头：
template<class T, int n>

关键字class指明T是类型参数，int指出n为一个int型的参数。这种在模板头中出现的参数（特定类型而不是泛型名）称为非类型（non-type）或者表达式参数（expression）。

表达式参数有一些限制：

  • 表达式参数可以是整型、枚举、指针、引用。因此double n是不合法的，但double *n 合法
  • 模板代码不能修改表达式参数的参数值，不能使用表达式参数的地址。也就是说在ArrayTP中不能出现如n++或者&n的表达式。
  • 实例化模板时，用作表达式参数的值必须为常量表达式。

与Stack中的构造函数相比：

stack使用的动态分配管理的堆内存，表达式参数使用的是栈内存，执行速度快一点。表达式参数的主要缺点是，每种数组大小都将生成一个类。也就是说，下面的类会生成两个类声明；

1
2
ArrayTB<double, 12> a1;
ArrayTB<double, 13> a2;

而下面的两条声明只会有一个类声明
1
2
Stack<int> s1(12);
Stack<int> s2(13);

下面是简单的数组模板代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<iostream>
#include<cstdlib>

template<class T, int n>
class ArrayTP {
private:
	T ar[n];
public:
	ArrayTP() {};
	explicit ArrayTP(const T &v);
	virtual T & operator[](int i);
	virtual T operator[](int i);
};

template<class T, int n>
ArrayTP<T, n>::ArrayTP(const T &v)
{
	for (int i = 0; i < n; i++)
		ar[i] = v;
}

template<class T, int n>
T & ArrayTP<T, n>::operator[](int i)
{
	if (i <= 0 || i >= n)
	{
		std::cerr << "Error in array limits: " << i 
			<< " is out of range\n";
		std::exit(EXIT_FAILURE);
	}
	return ar[i];
}


template<class T, int n>
T ArrayTP<T, n>::operator[](int i)const
{
	if (i <= 0 || i >= n)
	{
		std::cerr << "Error in array limits: " << i 
			<< " is out of range\n";
		std::exit(EXIT_FAILURE);
	}
	return ar[i];
}

多功能的模板

模板能作为基类、组件类、作为其他模板的类型参数

模板类用作基类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <class T>
class Array
{
private:
	T entry;
	...
};

template <class T>
class GrowArray : public Array<T>{...};//作为基类

template <class Tp>
class Stack
{
	Array<Tp> ar; //作为组件
}

递归使用模板

1
ArrayTP< ArrayTP<int, 5> , 10> a;

a是一个包含10个元素的数组，每个元素是一个包含5个int元素的数组

等价于 int a[10][5];。模板语法中，维的顺序与等价的二位数组相反。

使用多个类型参数。希望模板可以保持两种（或多种）类型

1
2
3
4
5
6
7
8
9
10
11
template<class T1, class T2>
class Pair
{
private:
	T1 a;
	T2 b;
public:
	T1 & first();
	T2 & second();
	....
}

Pair类可以保存两个不同的值。STL有类似的模板，名叫pair

默认类型模板参数

1
2
template <class T1, class T2 = int>
class XXX{...};

这样，如果在传参数时省略T2，将默认使用int

1
2
XXX<double,double>m1; //double double
XXX<double>m2;        //double int

STL经常使用该特性。

不可以为函数模板提供参数默认值。可以为非类型参数提供默认值。

成员

模板可用作结构、类、模板类的成员。STL的实现必须使用这项特性

将模板作为参数

模板可包含类型参数（class T）、非类型参数（int n），模板还可以包含本身就是模板的参数。

1
2
3
4
5
6
7
8
template<template <class T> class Thing>
class Crab
{
private:
	Thing<int> s1;
	Thing<double> s2;
...
};

template里面有一个类型参数。这里的类型参数为template <class T> class Thing 。参数中template <class T> class是类型，表示传进来的是一个模板类。Thing是模板类名字。

例如如下的声明：

1
Crab<King> legs;

这种声明要生效，模板参数King必须是一个模板类。
1
2
template<class T>
class King{...};

Crab中的两个私有对象，由King<double>和King<int>替代。

C++代码重用总结

C++提供几种代码重用的手段。

代码重用机制是为了让程序员能够重用经过测试的代码，而不用手工复制它们。这样可以简化编程工作，提供程序的可靠性。

公有继承建立is-a关系，派生类可以重用基类的代码。

私有继承和保护继承建立的是has-a关系，基类的公有接口都将成为派生类的内部接口。这被称为继承，但不继承接口，因此派生类对象不能显示使用基类接口。因此不能像公有继承那样将派生类对象看成是一种基类对象。在不进行显示类型转换的情况下，基类指针或引用将不能指向派生类对象。

包含是一种比较常用的实现has-a关系的手段，与私有继承和保护继承相比，更加容易使用。

私有继承和保护继承有一些不同的功能。例如继承允许派生类访问基类的保护成员。还允许派生类重新定义从基类那儿继承的虚函数。包含是不能使用这些功能的。

多重继承。私有MI和保护MI建立has-a关系，公有MI建立is-a关系。MI会带来一些问题：多次定义同一个名称、继承多个基类对象。可以用类限定符来解决名称二义性的问题，可以用虚基类来避免继承多个基类对象的问题。但使用虚基类后，要编写新的构造函数初始化列表以解决二义性问题。

类模板是一种典型的泛型编程例子。模板要以一句template打头，告诉编译器要定义一个模板。涉及到的知识点：类型参数、表达式参数、实例化、默认参数、模板做参数、成员……等等