第10章 类模板与STL编程课件

《第10章 类模板与STL编程课件》由会员分享，可在线阅读，更多相关《第10章 类模板与STL编程课件（54页珍藏版）》请在金锄头文库上搜索。

1、第10章 类模板与STL编程,C+语言程序设计教程 第10章 类模板,第10章 类模板,学习目标,理解类模板的概念； 掌握类模板的定义、实例化过程，会运用类模板； 掌握栈类模板、链表类模板的使用； 理解STL编程的基本思想； 掌握STL容器的使用； 熟练使用STL算法； 理解STL函数对象；,C+语言程序设计教程 第10章 类模板,C+语言程序设计教程 第10章 类模板,10.1 类模板,模板是C+语言的重要特征，它能够显著提高编程效率。利用C+的函数模板和类模板，能够快速建立具有类型安全的类库集合和函数集合，进行大规模软件开发，并提高软件的通用性和灵活性。C+的标准模板库（standard

2、template library，简称STL）编程完全依赖模板的实现。 类模板是能根据不同参数建立不同类型成员的类。类模板中的数据成员、成员函数的参数、成员函数的返回值可以取不同类型，在实例化成对象时，根据传入的参数类型，实例化成具体类型的对象。类模板也称模板类。,类模板定义的语法为：,其中： template为模板关键字。 模板参数表中的类型为参数化(parameterized)类型，也称可变类型，类型名为class (或typename)；模板参数表中的类型也可包含普通类型，普通类型的参数用来为类的成员提供初值。 类模板中的成员函数可以是函数模板，也可以是普通函数。,C+语言程序设计教程

3、第10章 类模板,1. 类模板的定义,template class 类名 成员名； ;,例如，下面定义了一个模板类Student，为了增强类的适用性，将学号设计成参数化类型，它可以实例化成字符串、整型等；将成绩设计成参数化类型，它可以实例化成整型、浮点型、字符型(用来表示等级分)等；,C+语言程序设计教程 第10章 类模板,1. 类模板的定义,模板类的成员函数还可以在类外定义，其语法如下：,其中： 模板参数表与类模板的模板参数表相同。 模板参数名表列出的是模板参数表中参数名，顺序与模板参数表中的顺序一致。,C+语言程序设计教程 第10章 类模板,1. 类模板的定义,template 类型 类名

4、 函数名(参数表) 函数体; ,模板类的成员函数还可以在类外定义，其语法如下：,C+语言程序设计教程 第10章 类模板,1. 类模板的定义,template 类型 类名 ：函数名(参数表) 函数体； ,其中： 模板参数表与类模板的模板参数表相同； 模板参数名表列出的是模板参数表中参数名，顺序与模板参数表中的顺序一致；,例如，模板类Student的成员函数在类外实现如下：,一个类模板是具体类的抽象，在使用类模板建立对象时，才根据给定的模板参数值实例化(专门化)成具体的类，然后由类建立对象。与函数模板不同，类模板实例化只能采用显式方式。 类模板实例化、建立对象的语法如下:,C+语言程序设计教程 第

5、10章 类模板,2. 类模板的实例化,类模板名 对象1, 对象2, , 对象n;,其中： 模板参数值表的值为类型名，类型名可以是基本数据类型名，也可以是构造数 据类型名，还可以是类类型名。 模板参数值表的值还可以是常数表达式，以初始化模板参数表中普通参数。 模板参数值表的值按一一对应的顺序实例化类模板的模板参数表。,例如，下面对模板类Student实例化:,编译Student S1；时：,String 取代 TNO,float 取代 TScore,100 取代 num,C+语言程序设计教程 第10章 类模板,2. 类模板的实例化,将类Student实例化成：,C+语言程序设计教程 第10章 类

6、模板,2. 默认模板参数,类模板的实例化过程与函数调用的实参与形参结合的过程相似，函数的形参可以采用默认值，类模板的类型参数也可以采用默认值，这样避免每次实例化时都显式给出实参。,TScore, num分别给出默认值int，10。 用以下方式实例化： Student S1;,10.2 类模板应用,1. 栈类模板,C+语言程序设计教程 第10章 类模板,栈是一种先进后出FILO(First In Last Out)的一种结构，在程序设计中广泛使用栈，栈的基本操作有: 压栈push、出栈pop。其他操作有判空、判满、读栈顶元素等。 下图演示栈的操作：,【例10-1】将栈设计成一个类模板，在栈中存放

7、任意类型的数据。 分析：栈空间可以使用静态数组，本例中使用动态数组。使用指针top指向栈顶元素，使用成员函数push()、pop()、IsEmpty()、IsFull()分别进行压栈、出栈、判空、判满。,1. 栈类模板,C+语言程序设计教程 第10章 类模板,运行结果:,uzyx,2.链表类模板,C+语言程序设计教程 第10章 类模板,【例10-2】将线性链表设计成一个类模板，从而可以在链表节点中存放任意类型的数据。 分析：链表的操作见5.5.1，为了节省内存空间，将头指针与当前节点指针设计成static,为同类型链表所共有；为了便于操作，同样将链表的第一个节点当成头节点，不存储数据。链表的构

8、成如下图所示：,2.链表类模板,C+语言程序设计教程 第10章 类模板,程序解释： 第16行为不带参数的构造函数，用于建立头节点。第62行建立对象时，调用了不带参数的构造函数，建立了一个仅含头节点的链表。 第20行为带数据域参数的构造函数，供函数AppendNode()动态建立节点对象时调用。,2.链表类模板,C+语言程序设计教程 第10章 类模板,2.链表类模板,C+语言程序设计教程 第10章 类模板,程序解释： 由于链表的非头节点为动态对象，因此，要使用delete删除节点，以释放内存。,2.链表类模板,C+语言程序设计教程 第10章 类模板,运行结果:,ABC,从上述程序例子可见，类模板

9、是一种安全的、高效的重用代码的方式，并可以结合类继承性和函数重载，实现更大范围类的代码重用。因此，类模板的应用在C+中占有重要的地位。,C+语言程序设计教程 第10章 类模板,10.3 STL编程,STL（Standard Template Library），即标准模板库，是一个高效的C+程序库。STL是ANSI/ISO C+标准函数库的一个子集，它提供了大量可扩展的类模板，包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法，类似于Microsoft Visual C+中的MFC（Microsoft Foundation Class Library）。 从逻辑结构和存储结构来看，基本数

10、据结构的数量是有限的。对于其中的数据结构，用户可能需要反复的编写一些类似的的代码，只是为了适应不同数据的类型变化而在细节上有所出入。如果能够将这些经典的数据结构，采用类型参数的形式，设计为通用的类模板和函数模板的形式，允许用户重复利用已有的数据结构构造自己特定类型下的、符合实际需要的数据结构，无疑将简化程序开发，提高软件的开发效率，这就是STL编程的基本设计思想。,C+语言程序设计教程 第10章 类模板,10.3 STL编程,从逻辑层次来看，STL中体现了泛型化程序设计（generic programming）的思想，它提倡使用现有的模板程序代码开发应用程序，是一种代码的重用技术（reusab

11、ility）。代码重用可以提高软件开发人员的劳动生产率和目标系统质量，是软件工程追求的重要目标。许多程序设计语言通过提供标准库来实现代码重用的机制。STL是一个通用组件库, 它的目标是将常用的数据结构和算法标准化、通用化，这样用户可以直接套用而不用重复开发它们，从而提高程序设计的效率。 从实现层次看，STL是一种类型参数化（type parameterized）的程序设计方法，是一个基于模板的标准类库，称之为容器类。每种容器都是一种已经建立完成的标准数据结构。在容器中，放入任何类型的数据，很容易建立一个存储该类型（或类）的数据结构。 STL主要由五个部分组成，分别是容器（container）、

12、迭代器（iterator）、适配器（adaptor）、算法（algorithm）以及函数对象（function object）。,C+语言程序设计教程 第10章 类模板,10.3.2 STL容器,在STL程序设计中，容器（container）就是通用的数据结构。容器用来承载不同类型的数据对象，就如同现实生活中，人们使用容器用来装载各种物品一样，但C+中的容器还存在一定的“数据加工能力”，它如同一个对数据对象进行加工的模具，可以把不同类型的数据放到这个模具中进行加工处理，形成具有一定共同特性的数据结构。例如将int型、char型或者float型放到队列容器中，就分别生成int队列、char型队列

13、或者float型队列，它们都是队列，具有队列的基本特性，但是具体数据类型是不一样的。 STL容器主要包括向量（vector）、列表（list）、队列（deque）、集合（set/ multiset）和映射（map/multimap）等。STL用模板实现了这些最常用的数据结构，并以算法的形式提供了对这些容器类的基本操作。 STL中的所有容器都是类模板，是一个已经建立完成的抽象的数据结构，因此可以使用这些容器来存储任何类型的数据，甚至是自己定义的类，而无需自己再定义数据结构。例如利用deque容器，就很容易建立一个队列。,C+语言程序设计教程 第10章 类模板,10.3.2 STL容器,C+的ST

14、L中的容器是同构的，每个容器只允许存储相同类型的数据，也就是说，不能在同一个队列中同时存储int和double类型的数据元素。不过，可以分别创建两个单独的队列，一个用于存储int，另一个用来存储double。 STL提供了大多数标准数据结构的实现，比如前面曾经提到的向量、列表、队列、集合等都是容器，用户在进行STL编程时，不必再编写诸如链表或队列之类的数据结构。 不同的容器有不同的插入、删除和存取行为和性能特征，用户需要分析数据之间逻辑关系，为给定的任务选择最合适的容器。 在STL中，容器大致可以分为两类：顺序容器和关联容器。,C+语言程序设计教程 第10章 类模板,10.3.3 顺序容器,顺

15、序容器（sequence container）以逻辑线性排列方式存储一个元素序列，在这些容器类型中的对象在逻辑上被认为是在连续的存储空间中存储的。在顺序容器中的对象有相对于容器的逻辑位置，如在容器的起始、末尾等。顺序容器可以用于存储线性表类型的数据结构。,表10-1 顺序容器,C+语言程序设计教程 第10章 类模板,10.3.3 顺序容器,在STL中，顺序容器一共有3种 ： vector是动态数组的同义词：随着所存储的元素个数的变化，向量会动态的扩展和收缩。C+中的vector不是指数学意义上的向量概念。C+将数学意义上的向量建模为valarray容器。 vector容器中数据元素的存储采用连

16、续存储空间，当需要增加数据元素时，直接从vector容器尾端插入，如果vector容器发现此时存储空间不足，整个容器中的数据元素将会被搬到一个新的、更大的内存空间中，并将所有数据元素复制到新的内存空间中。因此，如果需要快速的存取元素，但不打算经常增加或删除元素，就应当在程序中使用vector容器。 list容器的性能特征与向量恰好相反。list容器是一个标准双向链表，每个元素都知道其前一个与下一个数据元素，其查找速度较慢，只能根据链表指针的指示逐一查找，但一旦找到相关位置，完成元素的插入和删除则很快（常量时间）。 如果需要从元素序列的两端插入和删除，但仍需要快速地存取所有元素，就应当使用deque容器（双端队列）而不是向量。deque容器的特性基本上与vector容器类似，只是deque容器可以从前端以push_front()添加元素，且存储时不需要一块