C++ day27 代码重用（三）类模板（篇一：泛型编程，容器类）

ゝ一纸荒年。 2023-07-24 09:05 0阅读 0赞

前面说了公有继承私有继承保护继承和包含，以及多重继承，但这些还不是C++重用代码的全部手段，还有类模板，用泛型编程的方式编写独立于类型的类，以便生成可用于不同类型的实例类，从而重用代码，和之前的函数模板重用代码的思路一样。可以看到，模板编程或者说泛型编程本身就会起到代码重用这样一个好的副作用。

本文只是讨论类模板设计的一些基本特性，关于模板的精妙高深，不看STL是不能窥见的。

之前说过模板函数，本文的模板类和模板函数有很多相似之处。**模板都是以泛型的方式描述类或者函数**。

模板的参数，不管是类型参数还是非类型参数都是用**尖括号**传给模板，而不是一贯用于传参的圆括号。

### 文章目录 ###

*  由容器类 container class引出类模板
 *  示例 Stack类
 *   *  不用类模板
     *  用类模板
     *   *  类模板和成员函数模板都是C++编译器指令，不是定义！
         *  代码 （用类模板实现Stack类）
         *   *  出现的问题
             *  好的地方
 *  指针栈（栈中放指针类型）
 *   *  缺陷示例
     *  示例 如何正确使用指针栈
     *   *  代码
         *   *  问题

# 由容器类 container class引出类模板 #

即专门用于存储其他对象或者数据类型的类。比如Stack类，Array类， Queue类。

容器类就特别适合用类模板来实现。因为你可以定义一个专门存double类型数值的Stack类，然后再定义一个专门存string 对象的Stack类，但是这两个类的代码相似度是很大的（基本上只是保存的数据类型不一样，方法也许略有不同），如果还需要存储其他类型，难道继续写下去？显然有点不太科学。

C++对于这个问题的解答是：不写新的类声明，而是写一个泛型类，即独立于具体类型的类，然后把类型作为参数传递给这个泛型类（这叫做参数化类型，还记得吗）以生成实例类。这样一来，泛型类的代码是通用代码。

C++最初不支持模板，后来引入之后，一直在演化，如今是越来越香。C++提供了很多模板类，有一些我们已经打过照面，比如`valarray`类，`vector`类， `array`类。后面还要学习STL，即C++的标准模板库，里面有几个功能非常强大和灵活的容器类模板。

# 示例 Stack类 #

## 不用类模板 ##

第10章讲类时，写了Stack类，用于存储`unsigned long`类型的数值。类声明：

typedef unsigned long Item;
    
    class Stack
    { 
    private:
    	enum { MAX = 10};
    	Item items[MAX];
    	int top;
    public:
    	Stack();
    	bool isempty() const;
    	bool isfull() const;
    	bool push(const Item & item);
    	bool pop(Item & item);
    };

这里使用了`typedef`来使得代码有了一点点通用功能，只需要修改那一行代码就可以把这个类用于其他数据类型。但是这样子的话，每一次都要修改头文件，并且一个程序中只能有存储一种数据类型的栈类。还是远不如类模板的通用性好使。

## 用类模板 ##

使用类模板，相对于上面的代码要做的改变：

1.  把Stack类的声明改为模板定义
2.  把Stack类的所有成员函数也改为模板成员函数（每个函数头都以相同的模板声明打头）
3.  数据部分也要做点类型上的改变（用泛型名(一般比较喜欢用T或者Type)替换上面的Item）

Item items[MAX];//以前
    Type items[MAX];//现在

1.  类限定符从`Stack::`改为`Stack<Type>::`,其中Type是泛型名

### 类模板和成员函数模板都是C++编译器指令，不是定义！ ###

这些模板都只是说明和指示编译器如何生成类和成员函数的定义， 他们本身并不是定义，而是给编译器的指令。

模板的具体实现被称为实例化instantialization或者模板具体化specialization。

C++不允许把模板成员函数放在独立的实现文件中。（以前允许，现在那个关键字不让用了，所以就不允许了）

模板并不是函数，所以**模板不可以单独编译，必须和特定的模板实例化请求一起使用**。所以，最好把所有的模板信息（类声明和类定义，即成员函数的定义）放在一个头文件里，不要分散在不同文件。

### 代码 （用类模板实现Stack类） ###

//stacktp.h -- a stack template
    #ifndef STACKTP_H_
    #define STACKTP_H_
    #include <iostream>
    using std::cout;
    template <typename Type>//声明类模板要以这行打头
    class Stack
    { 
    private:
    	enum { MAX = 10};
    	Type items[MAX];//用数组实现栈，这样做的缺点是栈的长度不可变
    	int top;//指向栈顶，第一个可存储数据的位置
    public:
    	Stack();
    	bool isempty();
    	bool isfull();
    	bool push(const Type & item);
    	bool pop(Type & item);
    };
    
    template <typename Type>
    Stack<Type>::Stack()//Stack::Stack()报错，必须用尖括号传入参数（即具体类型）
    { 
    	top = 0;
    }
    
    template <typename Type>
    bool Stack<Type>::isempty()
    { 
    	return (top == 0);
    }
    
    template <typename Type>
    bool Stack<Type>::isfull()
    { 
    	return (top == MAX);
    }
    
    template <typename Type>
    bool Stack<Type>::push(const Type & item)
    { 
    	if (isfull())
    		return false;//不在这里输出错误提示信息，而让外部程序自己输出
    	items[top++] = item;
    	return true;
    }
    
    template <typename Type>
    bool Stack<Type>::pop(Type & item)
    { 
    	if (top == 0)
    		return false;
    	item = items[--top]; //这里极易出错，应该是--top不是top--
    	return true;
    }
    #endif

#include <iostream>
    #include <string>
    #include <cstring>
    #include <cctype>
    #include "Stacktp.h"
    using std::cout;
    using std::cin;
    void eatline();
    
    int main()
    { 
        Stack<std::string> st;//实例化，create an empty stack, a stack of string objects
        //会创建一套Stack<std::string>类的类声明和类成员函数
        char ch;
    	std::string po;
    	cout << "Please enter A to add a purchase order,\n"
    		 << "P to process a PO, or Q to quit.\n";
    	while (cin >> ch && std::toupper(ch) != 'Q')
    	{ 
    		eatline();
    		if ((!std::isalpha(ch)) || (std::strchr("AP", std::toupper(ch)) == NULL))
    		{ 
    			cout << '\a';
    			cout << "Enter A, P or Q.\n";
    			continue;
    		}
    		switch(ch)
    		{ 
    		case 'a':
    		case 'A':
    			cout << "Enter a PO number to add: ";
    			cin >> po;
    			eatline();
    			if (st.isfull())
    				cout << "Stack is already full. Push failed!\n";
                else
                    st.push(po);
    			break;
    		case 'p':
    		case 'P':
    			if (st.isempty())
    				cout << "Stack is already empty. Pop failed!\n";
                else
                { 
                    st.pop(po);
                    cout << "Purchase order " << po << " popped!\n";
                }
    
    			break;
    		}
    		cout << "Please enter A to add a purchase order,\n"
    		 << "P to process a PO, or Q to quit.\n";
    	}
    	cout << "Bye!\n";
    
        return 0;
    }
    
    void eatline()
    { 
    	while (cin.get() != '\n')
    		;
    }

其中switch语句也乐意这么写，更简短：

switch(ch)
    { 
    case 'a':
    case 'A':
    	cout << "Enter a PO number to add: ";
    	cin >> po;
    	eatline();
    	if (!st.push(po))
    		cout << "Stack is already full. Push failed!\n";
    	break;
    case 'p':
    case 'P':
    	if (!st.pop(po))
    		cout << "Stack is already empty. Pop failed!\n";
        else
            cout << "Purchase order " << po << " popped!\n";
    	break;
    }

输出

Please enter A to add a purchase order,
    P to process a PO, or Q to quit.
    a
    Enter a PO number to add: 45
    Please enter A to add a purchase order,
    P to process a PO, or Q to quit.
    A
    Enter a PO number to add: 78D
    Please enter A to add a purchase order,
    P to process a PO, or Q to quit.
    as
    Enter a PO number to add: h12
    Please enter A to add a purchase order,
    P to process a PO, or Q to quit.
    p
    Purchase order h12 popped!
    Please enter A to add a purchase order,
    P to process a PO, or Q to quit.
    P
    Purchase order 78D popped!
    Please enter A to add a purchase order,
    P to process a PO, or Q to quit.
    pe
    Purchase order 45 popped!
    Please enter A to add a purchase order,
    P to process a PO, or Q to quit.
    p
    Stack is already empty. Pop failed!
    Please enter A to add a purchase order,
    P to process a PO, or Q to quit.
    q
    Bye!

#### 出现的问题 ####

*  竟然把`Type items[MAX];//用数组实现栈`写成了`Type items{MAX};`，，，，，天哪！！！然后出了一个莫名其妙地错，半天都没看懂错误是啥意思，直到浏览代码突然发现了方括号写成花括号，才解决了。
 *  写模板类的成员模板函数时，虽然都是用了`template <typename Type>`打头，但我却忘了在类名限定符中加入`<Type>`，即类名限定符本应是`Stack<Type>::`,我却写的`Stack::`
 *  总是忘记给`toupper()`和`strchr()`加`std::`

#### 好的地方 ####

*  记得使用`cstring`头文件的`strchr`方法了
 *  学习了尽量把错误提示信息用外部程序自己写，这样允许多样化的个性化的错误提示，不需要类的成员函数来写，类成员函数只需要返回`true`和`false`就好了。**职责要分清**。
 *  复习了菜单的编写，尤其是`switch`语句，每次写菜单都会有它；还有`toupper`函数在菜单中的应用；以及菜单输入的正确性检查：首先检查是否是退出，然后检查是否是字母，然后检查是否是那几个字母。

# 指针栈（栈中放指针类型） #

上面的Stack类的具体化使用了string类，那么是否可以用char指针呢？即让栈中的成员的数据类型是指针类型。答案是：可以。但是指针栈的使用需要分场合，有的地方使用指针栈非常好非常适合，有的地方则需要改动大量代码还得不到好的使用效果。所以必须要正确地使用指针栈。

## 缺陷示例 ##

就以上面的Stack类模板为基础，假设把string类型换为char 指针类型，则需要在主程序改动的代码：

首先把`Stack<std::string> st;`改为

Stack<char *> st;//create an empty stack, a stack of pointers to char

然后把`std::string po;`改为

char * po;

但是这样肯定会崩溃。因为只是创建了char指针，但是模板中并没有分配存储char类型的空间的代码。

那试试把`std::string po;`改为

char po[40];

可是模板的pop代码是

template <typename Type>
    bool Stack<Type>::pop(Type & item)
    { 
    	if (top == 0)
    		return false;
    	item = items[--top]; //这里极易出错，应该是--top不是top--
    	return true;
    }

里面的`item = items[--top];`这句代码，如果item是数组，那不就成了数组赋值，不允许的，又要崩溃

那再试试把`std::string po;`改为

char * po = new char[40];

这会和pop方法是兼容的，也给字符串分配了空间。

但是这仍然会有问题：  
看看输出吧（主程序在`cout << "Bye!\n";`前面加了一句`delete [] po;`）

Please enter A to add a purchase order,
    P to process a PO, or Q to quit.
    a
    Enter a PO number to add: 10
    Please enter A to add a purchase order,
    P to process a PO, or Q to quit.
    a
    Enter a PO number to add: 20
    Please enter A to add a purchase order,
    P to process a PO, or Q to quit.
    a
    Enter a PO number to add: 30
    Please enter A to add a purchase order,
    P to process a PO, or Q to quit.
    p
    Purchase order 30 popped!
    Please enter A to add a purchase order,
    P to process a PO, or Q to quit.
    p
    Purchase order 30 popped!
    Please enter A to add a purchase order,
    P to process a PO, or Q to quit.
    p
    Purchase order 30 popped!
    Please enter A to add a purchase order,
    P to process a PO, or Q to quit.
    p
    Stack is already empty. Pop failed!
    Please enter A to add a purchase order,
    P to process a PO, or Q to quit.
    q
    Bye!

每次pop的都是同一个值！我没有想通原因，然后调试了一下，发现，第二次add时，只是把`cin >> po;`执行了以后栈中的值就自动从10变为20了，而不是仍然为10！！！因为我们的代码，push的是引用，不是按值push,相当于是push的地址！！！而`char * po = new char[40];`只有一个地址，每一次add都是cin输入到这个地址，所以每次push的都是同一个地址，所以最终整个栈虽然top（栈顶，栈中元素数目）是在增加，但是他们实际上都是最后一次push进来的值！！之前的值早就都丢了。所以每次pop当然显示的也是一个值。这就叫体现出来`cout << "Purchase order " << po << " popped!\n";`这句提示代码的重要性了。

![在这里插入图片描述][20200412142319243.png]

到此为止，折腾了三种方法，都没能成功利用栈模板类的代码，所以这种情况下，不适合使用指针栈，还是老实点用string对象吧，和类模板的代码完全兼容。

## 示例 如何正确使用指针栈 ##

从上面的三次折腾的失败来看，外部程序（主程序或调用程序）应用提供一个**指针数组**，而不是只提供一个指针，指针数组的每一个指针指向一个字符串，这样每次push的就是不同地址了，pop自然也就是不同的字符串了。

但是指针数组的大小是外部程序员定的，有可能大于或小于`Stack<Type>`类的实现栈的数组的长度，所以我们必须保证**栈的长度是可变的**，所以这回上面的栈模板代码也要改。

那么怎么让栈的大小可变呢？答案是还是用数组，但是要用**动态数组**。怎么让类模板知道创建多长的栈数组呢？——通过类模板的构造函数，让他接受一个参数表示栈的大小。但是这会带来更多复杂性：由于构造函数要用new，所以必须自己**写析构函数**；因为栈数组的元素可能是`char*`类型，所以必须自己用**深复制定义复制构造函数和赋值运算符成员函数**。

看到了把，想要无痛使用指针栈，要做的事情还是很多的。

下面用这样一个例子看看指针栈的正确打开方式：  
![在这里插入图片描述][20200412174846715.png]

### 代码 ###

//stacktp.h -- a stack template
    #ifndef STACKTP_H_
    #define STACKTP_H_
    #include <iostream>
    using std::cout;
    
    template <typename Type>
    class Stack//这里不需要写为Stack<Type>,只是写模板函数代码时需要，在类外部也是必须使用Stack<Type>
    { 
    private:
    	int top;
    	int stacksize;
    	enum { defaultSize = 10};
    	Type * items;//在构造函数中分配空间；指针成员，所以必须自己写深复制的复制构造函数等
    public:
    	Stack(int ss = defaultSize);
    	Stack(const Stack & st);//复制构造函数（自写深复制版）
    	~Stack(){ delete [] items;}
    	bool isfull() const{ return    top == stacksize;}
    	bool isempty() const{ return top == 0;}
    	bool push(const Type & item);
    	bool pop(Type & item);
    	Stack & operator=(const Stack & st);//赋值运算符成员函数（自写深复制版）
    };
    
    template <typename Type>
    Stack<Type>::Stack(int ss):top(0),stacksize(ss)
    { 
        items = new Type[stacksize];
    }
    
    template <typename Type>
    Stack<Type>::Stack(const Stack & st)
    { 
    	stacksize = st.stacksize;
    	top = st.top;
    	items = new Type[stacksize];
    	int i;
    	for (i = 0; i < stacksize; ++i)
    	{ 
    		items[i] = st.items[i];
    	}
    }
    
    template <typename Type>
    bool Stack<Type>::push(const Type & item)
    { 
    	if (isfull())
    		return false;
    	items[top++] = item;
    	return true;
    }
    
    template <typename Type>
    bool Stack<Type>::pop(Type & item)
    { 
    	if (isempty())
    		return false;
    	item = items[--top];
    	return true;
    }
    
    //运算符成员函数的核心代码和复制构造函数一模一样
    //只是要先判断是否赋值两端是同一个对象，以及有返回值
    template <typename Type>
    Stack<Type> & Stack<Type>::operator=(const Stack<Type> & st)
    { 
    	if (this == &st)
    		return *this;
    	stacksize = st.stacksize;
    	top = st.top;
    	items = new Type[stacksize];
    	int i;
    	for (i = 0; i < stacksize; ++i)
    		items[i] = st.items[i];
    	return *this;
    }
    #endif

//main.cpp
    #include <iostream>
    #include <cstdlib>
    #include <cstring>
    #include <ctime>
    #include "Stacktp.h"
    using std::cout;
    using std::cin;
    const int NUM = 10;
    
    int main()
    { 
    	//in basket
        const char * in[NUM] = { 
    		"1: Hank Gill", "2: Kiki Tshtar",
    		"3: Betty Rocker", "4: Ian Flagranti",
    		"5: Wolfgang Kibble", "6: Portia Koop",
    		"7: Joy Almondo", "8: Xaverie Paprika",
    		"9: Juan Moore", "10: Misha Mache"
    		};
    	int stacksize;
    	cout << "Enter the size of the stack (integer): ";
    	cin >> stacksize;
    	Stack<const char *> st(stacksize);//空栈
    
    	//Out basket
    	const char *out[NUM];
    
    	int processed = 0;
    	int nextin = 0;
    
    	std::srand(std::time(0));
    	while (processed < NUM)
    	{ 
    		if (st.isempty())
    			st.push(in[nextin++]);
    		else if (st.isfull())
    			st.pop(out[processed++]);//pop就是处理
    		else if (nextin < NUM && std::rand() % 2)
    			st.push(in[nextin++]);
    		else
    			st.pop(out[processed++]);
    	}
    	cout << "Processing completed!\n";
    	int i;
    	for (i = 0; i < NUM; ++i)
        { 
            cout << in[i] << ' ';
            if (i % 3 == 2)
                cout << '\n';
        }
        cout << '\n' << '\n';
        for (i = 0; i < NUM; ++i)
        { 
            cout << out[i] << ' ';
            if (i % 3 == 2)
                cout << '\n';
        }
    
        return 0;
    }

输出，由于随机性，所以处理文件的顺序是随机的

Enter the size of the stack (integer): 5
    Processing completed!
    1: Hank Gill 2: Kiki Tshtar 3: Betty Rocker
    4: Ian Flagranti 5: Wolfgang Kibble 6: Portia Koop
    7: Joy Almondo 8: Xaverie Paprika 9: Juan Moore
    10: Misha Mache
    
    2: Kiki Tshtar 1: Hank Gill 3: Betty Rocker
    4: Ian Flagranti 9: Juan Moore 8: Xaverie Paprika
    7: Joy Almondo 10: Misha Mache 6: Portia Koop
    5: Wolfgang Kibble

#### 问题 ####

*  差点忘记了复制构造函数和运算符成员函数的深复制版本了。有十多天没写代码，竟然差点忘记，有指针成员的时候要写深复制版本。
 *  竟然忘记可以把比较简短的函数写为内联版本以精简代码了。忘得太多啦。
 *  运算符成员函数的核心代码和复制构造函数一模一样。只是要先判断是否赋值两端是同一个对象，以及有返回值
 *  忘记了`cstdlib`的`rand(), srand()`
 *  把`else if (nextin < NUM && std::rand() % 2)`写为了`else if (processed < NUM && std::rand() % 2)`,于是导致nextin可能大于NUM-1，造成运行时错误。

[20200412142319243.png]: /images/20230528/59fe7e9f5e904e169d42f92ea70a9856.png
[20200412174846715.png]: /images/20230528/8b3e07e09b6c4d20afd2be7886abbafa.png