典型数据结构的模板实现

在我们初步了解编写模板类后，应当做一下代码练习。这节我们就做一个编写代码的补充，方便大家继续学习模板类的嵌套。作为新手而言，建议大家先写一个具体类，调试好后再去修改成模板类，因为调试模板类会相对复杂。

1.使用类模板实现数组结构

数组是我们常用的一种数据类型，我们今天的内容就先从编写一个数组类模板开始。数组有定长数组和边长数组的区别，我们只来实现它们的部分功能。

定长数组

首先我们先学习编写一个int类型的定长数组数组类。我们只实现查看和改写数组的元素即可。这个过程中涉及到重载[]运算符：

#define Arraysize 10
class Array
{private:int items[Arraysize]; // 声明一个数组，这里的[]不是运算符public:int sign=0; // 用于标记重载的[]运算符使用了几次Array(){memset(items,0,sizeof(items));} // 使用memset函数初始化数组，需要知道首地址、初始化值、数组元素类型所占空间int& operator[] (int ii) // 重载[]运算符，返回值类型为int的引用{this->sign++; // this指针类似于python中的self，他默认标记类地址，可以查找类内容return *(items+ii);}const int& operator[] (int ii) // 如果是const修饰的数组，上面的函数将不会被调用const{return *(items+ii);}
};

这段代码里我偷偷用了一些没有讲到的函数和知识点。包括重载运算符，初始化函数和类的this指针。当然这段代码当然没有使用this指针的必要，this->sign++直接写成sign++效果也是一样的。
写好之后我们来测试一下：

int main()
{Array a;a[0]=1;a[1]=2;a[2]=3;a[3]=4;for(int i=0;i<5;i++){cout<<a[i]<<" ";}cout<<"\n"<<a.sign<<endl;
}
// 输出为：1 2 3 4 0 
//		  9

接下来我们把它改成函数模板的样子。因为函数模板可以定义已知类型，所以我们也可以这样写：

template <class T, int Arraysize=10>
class Array
{private:T items[Arraysize]; // 声明一个数组，这里的[]不是运算符public:int sign=0; // 用于标记重载的[]运算符使用了几次Array(){memset(items,0,sizeof(items));} // 使用memset函数初始化数组，需要知道首地址、初始化值、数组元素类型所占空间T& operator[] (int ii) // 重载[]运算符，返回值类型为T的引用{this->sign++; // this指针类似于python中的self，他默认标记类地址，可以查找类内容return *(items+ii);}const T& operator[] (int ii) // 如果是const修饰的数组，上面的函数将不会被调用const{return *(items+ii);}
};

再来测试一下：

int main()
{// Array<double,5> a;Array<double> a;a[0]=1;a[1]=2;a[2]=3;a[3]=4;for(int i=0;i<10;i++){cout<<a[i]<<" ";}cout<<"\n"<<a.sign<<endl;
}
// 输出为：1 2 3 4 0 0 0 0 0 0 
//		  14

注意：非通用类型参数通常是整数型（但不绝对），这个值在函数模板实例化之后是不可以修改的。定长数组功能实现起来并不难，接下来我们试试变长数组。

可变数组

这个功能并不难实现，我们仅对上述代码实现少量改动，即当访问下标超过数组最大长度时，我们要重新分配更大的内存存储这个数组：

template <class T>
class Vector
{private:int len;T *items; // 声明一个指针变量，用于接收动态数组public:Vector(int size=5) // C++的参数也可以像python一样使用默认参数{len=size;items=new T[len];} ~Vector() // 释放动态分配的内存{delete[] items;items=nullptr;}void resize(int size) // 当数组超出容量时会重新分配内存{T* temp;if (size>len){temp=new T[size];} // 分配更大的内存else return;for(int i=0;i<len;i++) // 将旧数组拷贝到新数组{temp[i]=items[i];}delete[] items;        // 释放原数组items=temp;            // 指向新数组len=size;              // 更新数组大小}int size()const{ // 返回数组长度return len;}T& operator[] (int ii) // 重载[]运算符，返回值类型为T的引用{if (ii>=len){this->resize(len+5); // 分配多五个空间的新数组}return *(items+ii);}const T& operator[] (int ii) // 如果是const修饰的数组，上面的函数将不会被调用const{return *(items+ii);}
};

这样就完成了，大家可以自行尝试一下。

2.使用类模板实现栈结构

栈是一种先进后出的数据结构，我们主要通过类模板实现它的入栈、出栈、判空、判满功能。首先我们编写一个函数实现int类型的栈：

class Stack
{private:int *items; // 由数组结构定义的栈int stacksize; // 栈含元素数量int top; // 栈顶指针，并非指针类型，而是类似于数组下标public:// 初始化栈Stack(int size):stacksize(size),top(0){items=new int[stacksize];}// 析构函数，删除动态空间~Stack(){delete[] items;items=nullptr;}// 判空函数，即判断栈顶指针是否为0bool isempty() const // 不允许在函数内修改任何变量值{return top==0;}// 判满函数bool isfull() const{return top==stacksize;}// 压栈函数bool push(const int& item){if(!isfull()){items[top++]=item;return true;}else return false;}// 出栈函数bool pop(int &item){if(!isempty()){item=items[--top];return true;}else return false;}
};

这样我们就实现了定义一个功能简单的处理类型int栈。下面我们先来测试一下各个功能是否正常，然后再看看如何把这个具体类制作成类模板：

int main()
{Stack ss(5);cout<<ss.isempty()<<" "<<ss.isfull()<<endl;ss.push(1);ss.push(2);ss.push(3);ss.push(4);ss.push(5);cout<<ss.isempty()<<" "<<ss.isfull()<<endl;int item;while(ss.pop(item)){cout<<item<<" ";}
}
// 输出为：1 0
//		  0 1
//		  5 4 3 2 1

这样看起来，我们的功能实现的还不错。接下来我们把它定义成可以处理不同数据类型的栈类。我们可以使用

typedef *** Mydata

在星号处填入想要处理的类型，然后将与items有关的代码全都改成Mydata（或Mydata*）类。这样做的缺点是我们经常要手动去调整类所处理的数据类型。
在有了类模板之后，我们就可以更方便的解决这些问题了：

template<class T>
class Stack
{private:T *items; // 由数组结构定义的栈int stacksize; // 栈含元素数量int top; // 栈顶指针，并非指针类型，而是类似于数组下标public:// 初始化栈Stack(int size):stacksize(size),top(0){items=new T[stacksize];}// 判空和判满不需要改动// 压栈函数bool push(const T& item){if(!isfull()){items[top++]=item;return true;}else return false;}// 出栈函数bool pop(T &item){if(!isempty()){item=items[--top];return true;}else return false;}

这样我们就成功的做出了一个模板类实现栈的部分功能了。