C++ 泛编程 —— 嵌套使用模板类

嵌套使用模板类

嵌套使用模板类最常见的场景
数组容器中有栈容器
栈容器中有数组容器
递归使用模板类

嵌套使用模板类最常见的场景

容器中有容器
数组的元素可以是栈，栈中的元素可以是数组。先来看一下Stack和Vector的基本代码，定长数组Array的代码也给出来，但是不会用到，代码如下：

#include <iostream>
using namespace std;// 定长数组 Array
template <class T, int len=10>
class Array {
private:T* items[len];
public:Array() {}~Array() {}T& operator[](int index) {return items[index];}const T& operator[] (int index) const {return items[index];}
};// 栈 Stack
template <class DataType>
class Stack {
private:DateType* items;int stacksize;   int top;
public:Stack(int size=3): stacksize(size), top(0) {items  = new DataType[stacksize];}~Stack() {delete [] items; items = nullptr;}bool isEmpty() {return top == 0;}bool isFull() {return top == stacksize;}bool push(const DateType& item) {if(top < stacksize) {items[top++] = item; return true;}return false;}bool pop() {if(top > 0) {item = items[--top]; return true;}return false;}
};// 动态数组 Vector
template <class T>
class Vector {
privatet:int len; // 数组元素的个数T* items; // 数组元素
public:Vector(int size=2): len(size) { // 元素个数的缺省值为 2items = new T[len];}~Vector() {delete [] items; items = nullptr;}void resize(int size) {if(size <= len) return; // 只能往更大的方向扩容T* tmp = new T[size]; // 分配更大的内存空间for(int i = 0; i < len; i++) tmp[i] = items[i]; // 复制旧数组元素到新数组delete [] items; // 释放旧数组items = tmp;len = size;}int size() {return len;}T& operator [] (int index) {if(index >= len) resize(index + 1);return items[index];}const T& operator [] (int index) const {return items[index];} // 重载操作符[]，不能修改数组中的元素。
};int main() {return 0;
}

数组容器中有栈容器

目前的代码中，Vector容器的大小缺省值是2，Stack容器的大小缺省值是3。现在演示数组容器Vector中有栈Stack容器的情况，代码如下：

#include <iostream>
using namespace std;// 栈 Stack
template <class DataType>
class Stack {
private:DataType* items;int stacksize;   int top;
public:Stack(int size=3): stacksize(size), top(0) {items  = new DataType[stacksize];}~Stack() {delete [] items; items = nullptr;}bool isEmpty() {return top == 0;}bool isFull() {return top == stacksize;}bool push(const DataType& item) {if(top < stacksize) {items[top++] = item; return true;}return false;}bool pop(DataType& item) {if(top > 0) {item = items[--top]; return true;}return false;}
};// 动态数组 Vector
template <class T>
class Vector {
private:int len; // 数组元素的个数T* items; // 数组元素
public:Vector(int size=2): len(size) { // 元素个数的缺省值为 2items = new T[len];}~Vector() {delete [] items; items = nullptr;}void resize(int size) {if(size <= len) return; // 只能往更大的方向扩容T* tmp = new T[size]; // 分配更大的内存空间for(int i = 0; i < len; i++) tmp[i] = items[i]; // 复制旧数组元素到新数组delete [] items; // 释放旧数组items = tmp;len = size;}int size() {return len;}T& operator [] (int index) {if(index >= len) resize(index + 1);return items[index];}const T& operator [] (int index) const {return items[index];} // 重载操作符[]，不能修改数组中的元素。};int main() {// 创建Vector对象vs，vs是一个Vector，Vector中存储Stack<string>类型的元素。Vector<Stack<string>> vs;// 往容器中插入数据vs[0].push("hello world!"); vs[0].push("hihihi"); vs[0].push("123456"); // vs[0]是一个栈，往vs[0]中插入数据vs[1].push("你好！"); vs[1].push("abcdef"); vs[1].push("xxxxx"); // vs[1]也是一个栈，往vs[1]中插入数据// 用嵌套循环，遍历vs中的所有元素for(int i = 0; i < vs.size(); i++) {while(vs[i].isEmpty() == false) {string item;vs[i].pop(item);cout << "pop item = " << item << endl;}}return 0;
}

运行的结果如下：

pop item = 123456
pop item = hihihi
pop item = hello world!
pop item = xxxxx
pop item = abcdef
pop item = 你好！

容器中的容器就是二维容器，但不能简单把它说成二维数组。因为不同的容器可以实现不同的数据结构。像二维数组，但不是二维数组。目前的程序，Stack是没有扩展功能的，而Vector是有resize()扩展功能的，那就往Vector容器中再多加一个元素，只入栈两个元素，其他代码不变，main()函数代码如下：

int main() {Vector<Stack<string>> vs;vs[0].push("hello world!"); vs[0].push("hihihi"); vs[0].push("123456");vs[1].push("你好！"); vs[1].push("abcdef"); vs[1].push("xxxxx");vs[2].push("Happy Everyday!"); vs[1].push("吃好喝好，身体健康！"); // 往Vector中再增加一个Stack数据for(int i = 0; i < vs.size(); i++) {while(vs[i].isEmpty() == false) {string item;vs[i].pop(item);cout << "pop item = " << item << endl;}}return 0;
}

我的电脑编译运行的结果如下，你的电脑可能编译不通过，或者编译运行的结果与我的不同，总之是不正常的：

pop item = 123456
pop item = hihihi
pop item =
pop item = xxxxx
pop item = abcdef
pop item =
pop item = Happy Everyday!
free(): double free detected in tcache 2
Aborted (core dumped)

目前这个代码异常的原因在Vector类中，具体在扩展数组内存空间的resize()函数里面。 tmp[i] = items[i];这条语句的意思是：把原数组中的数据拷贝到新数组中去。如果复制的是C++内置的数据类型，则不存在问题；如果复制的是自定义的类，并且类中使用了堆区内存，就存在浅拷贝的问题。
具体解释一下，在Stack类中，根据语句：DataType* items;可以确定items这个成员变量是指针，使用了堆区内存。这样的话，对Stack类用浅拷贝是不行的，要用深拷贝。也就是说，对于Stack这种类，一定要重写拷贝构造函数和赋值函数。在此实例中，未用到Stack类的拷贝构造函数，无需在意；但这条语句：tmp[i] = items[i];用到了Stack类的赋值函数。所以，应该为Stack类重写赋值函数，实现深拷贝。具体的做法是，在Stack类中添加如下代码：

Stack& operator = (const Stack& v) {delete [] items;stacksize = v.stacksize;items = new DataType[stacksize];for(int i = 0; i < stacksize; i++) {items[i] = v.items[i];}top = v.top;return *this;
}

再次编译运行，结果如下：

pop item = 123456
pop item = hihihi
pop item = hello world!
pop item = xxxxx
pop item = abcdef
pop item = 你好！
pop item = Happy Everyday!

栈容器中有数组容器

给Vector类也加上赋值运算符的重载函数，实现深拷贝，以便演示栈容器Stack中有数组容器Vector的情况，代码如下：

#include <iostream>
using namespace std;// 栈 Stack
template <class DataType>
class Stack {
private:DataType* items;int stacksize;   int top;
public:Stack(int size=3): stacksize(size), top(0) {items  = new DataType[stacksize];}~Stack() {delete [] items; items = nullptr;}Stack& operator = (const Stack& v) {delete [] items;stacksize = v.stacksize;items = new DataType[stacksize];for(int i = 0; i < stacksize; i++) {items[i] = v.items[i];}top = v.top;return *this;}bool isEmpty() {return top == 0;}bool isFull() {return top == stacksize;}bool push(const DataType& item) {if(top < stacksize) {items[top++] = item; return true;}return false;}bool pop(DataType& item) {if(top > 0) {item = items[--top]; return true;}return false;}
};// 动态数组 Vector
template <class T>
class Vector {
private:int len; // 数组元素的个数T* items; // 数组元素
public:Vector(int size=2): len(size) { // 元素个数的缺省值为 2items = new T[len];}~Vector() {delete [] items; items = nullptr;}Vector& operator = (const Vector& v) {delete [] items;len = v.len;items = new T[len];for(int i = 0; i < len; i++) items[i] = v.items[i];return *this;}void resize(int size) {if(size <= len) return; // 只能往更大的方向扩容T* tmp = new T[size]; // 分配更大的内存空间for(int i = 0; i < len; i++) tmp[i] = items[i]; // 复制旧数组元素到新数组delete [] items; // 释放旧数组items = tmp;len = size;}int size() {return len;}T& operator [] (int index) {if(index >= len) resize(index + 1);return items[index];}const T& operator [] (int index) const {return items[index];} // 重载操作符[]，不能修改数组中的元素。};int main() {// 创建Stack对象，sv是一个栈，栈中存储Vector<string>类型的元素。Stack<Vector<string>> sv;// 先创建Vector<string>对象，再插入到Stack中Vector<string> tmp;// 第一次把字符串数据放到临时容器tmp中，再第一次入栈。tmp[0] = "hi ~"; tmp[1] = "hello ~"; sv.push(tmp);// 第二次把字符串数据放到临时容器tmp中，再第二次入栈。tmp[0] = "666"; tmp[1] = "888"; sv.push(tmp);// 第二次把字符串数据放到临时容器tmp中，再第二次入栈。tmp[0] = "qqqqq"; tmp[1] = "324fwre"; tmp[2] = "09ji"; sv.push(tmp);// 用嵌套循环，遍历sv中的所有元素while(sv.isEmpty() == false) {sv.pop(tmp);for(int i = 0; i < tmp.size(); i++) {cout << "sv[" << i << "] = " << tmp[i] << endl;}}return 0;
}

运行结果如下：

sv[0] = qqqqq
sv[1] = 324fwre
sv[2] = 09ji
sv[0] = 666
sv[1] = 888
sv[0] = hi ~
sv[1] = hello ~

递归使用模板类

递归使用模板类，属于嵌套使用模板类的特殊情况，自己嵌套自己。对于以上代码，仅需修改main函数中的调用代码即可，参考如下：

int main() {// Vector嵌套VectorVector<Vector<string>> vv; // 递归使用模板类vv[0][0] = "hello"; vv[0][1] = "world"; vv[0][2] = "!";vv[1][0] = "你好"; vv[1][1] = "世界";vv[2][0] = "Happy"; vv[2][1] = "Everyday"; vv[2][2] = "!"; vv[2][3] = "吃好喝好";for(int i = 0; i <vv.size(); i++){for(int j = 0; j < vv[i].size(); j++) {cout << "vv[" << i << "][" << j << "] = " << vv[i][j] << endl;}}return 0;
}

运行结果如下：

vv[0][0] = hello
vv[0][1] = world
vv[0][2] = !
vv[1][0] = 你好
vv[1][1] = 世界
vv[2][0] = Happy
vv[2][1] = Everyday
vv[2][2] = !
vv[2][3] = 吃好喝好

注意，这跟二维数组不同。二维数组是一个矩阵，第二维的大小是固定的。而vv的大小不是固定的。也可以调整一下输出格式，更能直观感受vv第二维不固定的特点，代码如下：

int main() {// Vector嵌套VectorVector<Vector<string>> vv; // 递归使用模板类vv[0][0] = "hello"; vv[0][1] = "world"; vv[0][2] = "xxx";vv[1][0] = "你好"; vv[1][1] = "世界";vv[2][0] = "Happy"; vv[2][1] = "Everyday"; vv[2][2] = "qqq"; vv[2][3] = "吃好喝好";for(int i = 0; i <vv.size(); i++){for(int j = 0; j < vv[i].size(); j++) {cout << vv[i][j] << " ";}cout << endl;}return 0;
}