C++ primer里的template用法

template 的用法     在程序设计当中经常会出现使用同种数据结构的不同实例的情况。例如:在一个程序中     可以使用多个队列、树、图等结构来组织数据。同种结构的不同实例,也许只在数据元素     的类型或数量上略有差异,如果对每个实例都重新定义,则非常麻烦且容易出错。那么能     否对同种类型数据结构仅定义一次呢?答案是肯定的,C++提供的类模板(Class Template     )就可以实现该功能。     一、类模板     类模板是C++提供的一种特殊机制,通过它我们可以定义一种特殊的类(称为模板类),在类     的定义中可以包含待定的类型参数,在声明类的实例时,系统会自动根据传递的类型生成     用户想要生成的类实例。下面是用C++实现的一个简单的模板类Clist的定义。

1  Template <class T, int I> class CList
2     {
3     public:
4     int SetItem(int Index, const T &Item);
5     int GetItem(int Index, T &Item);
6     private:
7     T Buffer;
8     }

    在这里,T是类型参数,I是整型常量参数。T和I的实际值是在声明具体类实例时指定的。     模板类的<>号内可以包括任意个类型参数和常量参数(至少要有一个参数)。类型参数和     常量参数可以是任何合法的标准类型和用户自定义类型,包括简单类型及各种结构体。同     其他类一样,类成员函数SetItem的实现可以在类定义内完成,也可以在类CList定义处实     现:

1 template<class T, int I> int CList<T, I>::SetItem(int Index, const T &Item)
2 {
3     if ( (Index<0)||(Index>I-1) )
4      return 0; // 出错
5     Buffer[Index]= Item ;
6      return 1; // 成功
7 }

    值得注意的是,在类定义外完成函数实现时,必须以关键字template和类模板定义中相同     的参数表(<>号内的)开头(上例为template<class T, int I>),并且范围分解操作符前的     类名后应跟上模板参数名清单(上例为CList<T, I>)。另外,与非模板类不同的是,必须将     函数实现包括在调用它的每个源文件中,使编译器能从函数实现产生代码。通常的做法是     将模板类的函数实现也放在定义该类的头文件中,这样只需在调用的源文件中包含该头文     件即可。     那么,如何使用生成特定的类实例呢?我们可以像使用其他类一样来使用模板类,不过必须     指定模板参数的值。例如采用如下声明:     CList <int, 100> IntList;     则使IntList成为CList类的实例,每次出现的T参数都换成int, 每次出现的I参数都换成     100。这样,IntList类中的Buffer就是一个长度为100的整型数组,SetItem和GetItem函数     参数是int值的引用。例:     IntList.SetItem(0, 5); //给数组第一个元素赋为整数5     模板类还可以像其他类一样可以定义构造函数和析构函数。下面我们以一种简单的数据     结构——堆栈为例,来说明如何用类模板来构造通用数据结构。     二、 利用类模板实现通用堆栈结构     任何抽象数据结构在计算机中的实现,归根结底都只有两种方式:顺序存储(用数组实现)     ,链式存储(用指针实现)。堆栈也不例外,按其实现方式可分为顺序栈(用数组实现)和链     栈(用指针实现)。     1. 通用顺序栈的实现     因为顺序栈中的元素在空间上连续存储,栈顶的元素位置需要注明,所以构造顺序栈的模     板类应该有这样的一些成员变量:一个待定类型和长度的数组Buffer,一个记录栈顶元素     的数组下标的整型变量top。堆栈的基本操作主要有:入栈(Push)、出栈(Pop)、置空(Se     tEmpty)、判断当前状态(IsEmpty)等,它们应用模板类的成员函数来实现。作为一个标准     的类,它还应该有自己的构造函数和析构函数。具有这些功能的模板类,就可以作为一个     通用的顺序栈来使用了。该类的定义如下:

 1 template <class T,int SIZE> class CArrayStackTemp
 2     {
 3     public:
 4     CArrayStackTemp () //缺省构造函数,构造一个空堆栈
 5     {
 6     top= -1;
 7     };
 8     ~ CArrayStackTemp (){};//析构函数
 9      void SetEmpty (); //置空堆栈
10      bool IsEmpty(); //判断堆栈是否为空
11      bool Push(T element); //入栈
12      bool Pop(T& element);//出栈
13     private:
14     T Buffer[SIZE];
15      int top;
16     };

    与堆栈的基本操作相对应的成员函数的实现如下:

 1 template <class T, int SIZE> void CArrayStackTemp<T, SIZE>:: SetEmpty ()
 2     {
 3     top= -1; //将栈顶指针赋 -1,并不实际清除数组元素
 4     }
 5     template <class T, int SIZE> bool CArrayStackTemp<T, SIZE>:: IsEmpty ()
 6     {
 7     return(top == -1);
 8     }
 9     template <class T, int SIZE> bool CArrayStackTemp<T, SIZE>:: Push (T element
10     )
11     {
12     top++;
13     if (top>SIZE-1)
14     {
15     top--;
16     return false; //堆栈已满,不能执行入栈操作
17     }
18     Buffer[top]=element;
19     return true;
20     }
21     template <class T, int SIZE> void CArrayStackTemp<T, SIZE>:: Pop (T& element
22     )
23     {
24     if (IsEmpty())
25      return false;
26     element =Buffer[top];
27     top--;
28     return true;
29     }

    根据实际需要,还可以扩充堆栈功能。例如:加入取栈顶元素、求堆栈长度等操作,其方法     如上。     2. 通用链栈的实现     模板类中允许使用指针和定义自己的结构,这就为实现链式结构提供了保证。这里采用一     个单链表来实现堆栈,栈顶指针指向链表的第一个结点,入栈和出栈均在链表的头进行。     该模板类的定义如下:

 1 template <class T> class CLinkStackTemp
 2     {
 3 
 4 public:
 5      //类的缺省构造函数,生成一个空堆栈
 6     CLinkStackTemp ()
 7     {
 8     top=NULL;
 9     };
10     ~ClinkStackTemp(){}; //析构函数
11      //定义结点结构
12      struct node
13     {
14     T
15       data; //入栈元素
16      node* next; //指向下一结点的指针
17     };
18      void SetEmpty(); //置空堆栈
19      bool IsEmpty(); //判断堆栈是否为空
20      bool Push(T element); //压入堆栈
21      bool Pop(T& element);//弹出堆栈
22     private:
23      node* top;
24     };

    该类的成员函数实现如下:

 1 template <class T> void CLinkStackTemp <T>::SetEmpty()
 2     {
 3     //释放堆栈占用的内存
 4     node* temp;
 5     while (top!=NULL)
 6     {
 7      temp=top;
 8      top=top->next;
 9      delete temp;
10     }
11     }
12     template <class T> bool CLinkStackTemp <T>::IsEmpty()
13     {
14     return (top==NULL);
15     }
16     template <class T> bool CLinkStackTemp <T>::Push(T element)
17     {
18     node* temp=new node();
19     if (temp ==NULL)
20      return false ;
21     temp->data=element;
22     temp->next=top;
23     top=temp;
24     return true;
25     }
26     template <class T> bool CLinkStackTemp <T>::Pop(T& element)
27     {
28     if ( IsEmpty())
29      return false;
30     node* q = top;
31     element = top->data;
32     top=top->next;
33     delete q;
34     return true;
35     }

    与顺序栈的实现略有不同,链栈不必指定栈的容量,其大小可以是近似"无限"的。为了程     序的使用方便,我们同样可以加入一些增强的功能。     三、 通用堆栈类的使用     通用堆栈类的使用较为简单,堆栈类的实例就是一个可以方便使用的堆栈。对堆栈的操作     都是通过类的成员函数来实现的。使用的具体步骤如下:     1. 在要使用堆栈类的程序代码的文件开头包括模板类及其成员函数的定义。     2. 类的实例化,可声明成变量,也可以声明它的指针,如:     CArrayStackTemp <int, 100> intStack; //生成一个长度为100的int型堆栈     //生成一个元素为Record型的堆栈,Record为自定义结构     CLinkStackTemp <Record>* RecordStack;     RecordStack=new CLinkStackTemp<Record>;     应注意在定义顺序栈时,必须指定栈的大小,而链栈则不必。另外在指定指针类型和执行     new操作时,必须对模板参数赋值,并且前后要一致。     3. 对堆栈进行操作,如:     intStack.Push(3); //将整数3入栈     RecordStack.SetEmpty(); //将堆栈置空     无论我们使用哪种堆栈类,对用户来讲都是透明的,操作起来并无差别。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏落影的专栏

程序员进阶之算法练习(三十二)LeetCode专场

题目链接 题目大意: 给出一个链表RandomListNode *next, *random; 每个节点有int值,有两个指针,一个指向下一个节点,一个指...

892
来自专栏ios 技术积累

Swif Array

使用加法赋值运算符(+=)也可以直接在数组后面添加一个或多个拥有相同类型的数据项:

983
来自专栏LinkedBear的个人空间

唠唠SE的集合-00——概述 原

                        由于是数组实现,在增和删的时候会牵扯到数组增容、以及拷贝元素,所以慢。

892
来自专栏大闲人柴毛毛

Java基础全面解析——Java语言基础

高级编程语言的组成:关键字、标识符、注释、常量与变量、语句、函数、数组,下面一一介绍各个组成元素。 a)  关键字 i.  定义:关键字是一些英文单词,但在ja...

2977
来自专栏决胜机器学习

PHP数据结构(二十一) ——希尔排序

PHP数据结构(二十一)——希尔排序 (原创内容,转载请注明来源,谢谢) 一、概述 希尔排序,又称缩小增量排序,也属于插入排序类方法,时间上有较大改进。前面...

3447
来自专栏cs

python数据类型2

刚刚提到列表是序列,所有 序列都有几种基本的操作。 >>> st=[1,2,'dflx']; >>> len(st); 3 >>> df=[6,8,"great...

34710
来自专栏WD学习记录

Python数据结构与算法笔记(2)

栈、队列、deques、列表是一类数据的容器,它们数据项之间的顺序由添加或删除的顺序决定。一旦一个数据项被添加,它相对于前后元素一直保持该位置不变。诸如此类的数...

1011
来自专栏决胜机器学习

PHP数据结构(二十六) ——基数排序实现36进制数排序

PHP数据结构(二十六)——基数排序实现36进制数排序 (原创内容,转载请注明来源,谢谢) 一、概述 插入排序、选择排序、快速排序等,都是通过关键字之间的比...

40211
来自专栏恰同学骚年

《C#图解教程》读书笔记之三:方法

    不为形参在栈上分配内存,形参的参数名作为实参变量的别名指向同一位置,必须使用ref关键字,并且事先需要被赋值;

812
来自专栏javathings

什么是 default 方法

Java 设计者希望能在 List 上提供一个 forEach 方法,例如可以 list.forEach(System.out::println) 而 L...

1662

扫码关注云+社区

领取腾讯云代金券