C类模板与STL编程实用教案

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

1、C+语语言言程程序序设设计计(chn x sh j)教教程程第第10章章类类模模板板10.1 类模板(mbn) 模板是C+语言的重要特征，它能够显著提高编程效率。利用C+的函数模板和类模板，能够快速建立具有类型安全的类库集合和函数集合，进行大规模软件开发，并提高软件的通用性和灵活性。C+的标准模板库（standard template library，简称STL）编程完全依赖模板的实现。 类模板是能根据不同参数建立不同类型成员的类。类模板中的数据成员、成员函数的参数、成员函数的返回值可以取不同类型，在实例化成对象(duxing)时，根据传入的参数类型，实例化成具体类型的对象(duxing)。类

2、模板也称模板类。第2页/共53页第1页/共53页第一页，共54页。类模板定义(dngy)的语法为： 其中(qzhng)： template为模板关键字。 模板参数表中的类型为参数化(parameterized)类型，也称可变类型，类型名为class (或typename)；模板参数表中的类型也可包含普通类型，普通类型的参数用来为类的成员提供初值。 类模板中的成员函数可以是函数模板，也可以是普通函数。 C+语语言言程程序序设设计计教教程程(jiochng) 第第10章章类类模模板板1. 类模板的定义template class 类名类名 成员名；成员名；;第3页/共53页第2页/共53页第二页，

3、共54页。 例如，下面定义(dngy)了一个模板类Student，为了增强类的适用性，将学号设计成参数化类型，它可以实例化成字符串、整型等；将成绩设计成参数化类型，它可以实例化成整型、浮点型、字符型(用来表示等级分)等； C+语语言言(yyn)程程序序设设计计教教程程第第10章章类类模模板板1. 类模板(mbn)的定义template / TNO,TScore 为参数化类型class Student private: TNO StudentIDnum; /参数化类型数组，存储姓名 TScore scorenum; /参数化类型数组，存储分数 public: TNO TopStudent() /

4、普通函数 return StudentID0; int BelowNum(TScore ascore) /函数模板 return 0; void sort() /普通函数 ;第4页/共53页第3页/共53页第三页，共54页。模板类的成员函数(hnsh)还可以在类外定义，其语法如下：其中：模板参数(cnsh)表与类模板的模板参数(cnsh)表相同。模板参数(cnsh)名表列出的是模板参数(cnsh)表中参数(cnsh)名，顺序与模板参数(cnsh)表中的顺序一致。C+语语言言程程序序设设计计(chn x sh j)教教程程第第10章章类类模模板板1. 类模板的定义template 类型类型 类名

5、类名 函数名函数名(参数表参数表) 函数体函数体;第5页/共53页第4页/共53页第四页，共54页。 模板类的成员函数还可以在类外定义，其语法(yf)如下：C+语语言言(yyn)程程序序设设计计教教程程第第10章章类类模模板板1. 类模板(mbn)的定义template 类型类型 类名类名 ：函数名：函数名(参数表参数表) 函数体；函数体； 其中： 模板参数表与类模板的模板参数表相同； 模板参数名表列出的是模板参数表中参数名，顺序与模板参数表中的顺序一致；例如，模板类Student的成员函数在类外实现如下：模板类Student的成员函数在类外实现如下： template class Stude

6、nt private: TNO StudentIDnum; TScore scorenum; public: TNO TopStudent(); int BelowNum(TScore ascore); void sort();template int Student:BelowNum(TScore ascore) return 0;template void Student:sort()template TNO Student:TopStudent() return StudentID0;第6页/共53页第5页/共53页第五页，共54页。 一个类模板是具体类的抽象，在使用类模板建立对象时，才

7、根据给定的模板参数值实例化(专门化)成具体的类，然后由类建立对象。与函数模板不同，类模板实例化只能采用(ciyng)显式方式。 类模板实例化、建立对象的语法如下:C+语语言言程程序序设设计计(chn x sh j)教教程程第第10章章类类模模板板2. 类模板(mbn)的实例化类模板名类模板名 对象对象1, 对象对象2, , 对象对象n; 其中： 模板参数值表的值为类型名，类型名可以是基本数据类型名，也可以是构造数 据类型名，还可以是类类型名。模板参数值表的值还可以是常数表达式，以初始化模板参数表中普通参数。模板参数值表的值按一一对应的顺序实例化类模板的模板参数表。例如，下面对模板类Studen

8、t实例化: class String public:char Str20;void main() Student S1; S1.sort(); Student S2; S2.TopStudent();编译Student S1；时： String 取代 TNO float 取代 TScore 100 取代 num第7页/共53页第6页/共53页第六页，共54页。C+语语言言程程序序设设计计教教程程(jiochng) 第第10章章类类模模板板2. 类模板(mbn)的实例化template class Student private: TNO StudentIDnum; TScore scorenu

9、m; public: TNO TopStudent() int BelowNum(TScore ascore) void sort();class Student private: String StudentID100; float score100; public: String TopStudent(); int BelowNum(float ascore); void sort();将类Student实例(shl)化成：第8页/共53页第7页/共53页第七页，共54页。C+语语言言(yyn)程程序序设设计计教教程程第第10章章类类模模板板2. 默认模板(mbn)参数template c

10、lass Student private: TNO StudentIDnum; TScore scorenum; public: TNO TopStudent(); int BelowNum(TScore ascore); void sort(); 类模板的实例化过程与函数(hnsh)调用的实参与形参结合的过程相似，函数(hnsh)的形参可以采用默认值，类模板的类型参数也可以采用默认值，这样避免每次实例化时都显式给出实参。 TScore, num分别给出默认值int，10。用以下方式实例化： Student S1;class Student private: char * StudentID1

11、0; int score10; public: char * TopStudent(); int BelowNum(int ascore); void sort();第9页/共53页第8页/共53页第八页，共54页。10.2 类模板类模板(mbn)应用应用1. 栈类模板栈类模板(mbn)C+语语言言程程序序设设计计(chn x sh j)教教程程第第10章章类类模模板板 栈是一种先进后出FILO(First In Last Out)的一种结构，在程序设计中广泛使用栈，栈的基本操作有: 压栈push、出栈pop。其他操作有判空、判满、读栈顶元素等。 下图演示栈的操作： 【例10-1】将栈设计成一

12、个类模板，在栈中存放任意类型的数据。 分析：栈空间可以使用静态数组，本例中使用动态数组。使用指针top指向栈顶元素，使用成员函数push()、pop()、IsEmpty()、IsFull()分别进行压栈、出栈、判空、判满。第10页/共53页第9页/共53页第九页，共54页。1.栈类模板(mbn)891011121314151617181920212223242526272829303132/* p10_1.cpp 栈类模板template class Stack private: int size; int top;T* space; public: Stack(int=10); Stack(

13、) delete space; bool push(const T&); T pop(); bool IsEmpty() const return top=size; bool IsFull() const return top=0; ;C+语语言言程程序序设设计计(chn x sh j)教教程程第第10章章类类模模板板33343536373839404142434445464748495051525354555657585960616263646566template Stack :Stack(int size) this-size=size; space=new Tsize; top=si

14、ze;template bool Stack :push(const T& element) if(!IsFull() space-top=element; return true; return false;template T Stack :pop() return spacetop+;int main() StackS1(4); S1.push(x); S1.push(y); S1.push(z); S1.push(u); S1.push(v); while(!S1.IsEmpty() coutS1.pop()endl; return 0;运行(ynxng)(ynxng)结果: :uzy

15、x 第11页/共53页第10页/共53页第十页，共54页。2.链表类模板(mbn)C+语语言言(yyn)程程序序设设计计教教程程第第10章章类类模模板板 【例10-2】将线性链表设计成一个类模板，从而可以在链表节点中存放任意类型的数据。 分析：链表的操作见5.5.1，为了节省内存空间，将头指针与当前(dngqin)节点指针设计成static,为同类型链表所共有；为了便于操作，同样将链表的第一个节点当成头节点，不存储数据。链表的构成如下图所示：第12页/共53页第11页/共53页第十一页，共54页。2.链表类模板(mbn)C+语语言言(yyn)程程序序设设计计教教程程第第10章章类类模模板板56

16、78910111213141516171819202122232425/ p10_2.cpp * 单向链表的类模板 *#include using namespace std;template class ListNode private:TYPE data;ListNode * next; static ListNode * CurNode; static ListNode * head; public:ListNode() next=NULL; head=CurNode=this;ListNode(TYPE NewData) data=NewData; next=NULL;程序解释(jis

17、h)：第16行为不带参数的构造函数，用于建立头节点。第62行建立对象时，调用了不带参数的构造函数，建立了一个仅含头节点的链表。第20行为带数据域参数的构造函数，供函数AppendNode()动态建立节点对象时调用。第13页/共53页第12页/共53页第十二页，共54页。2.链表类模板(mbn)C+语语言言(yyn)程程序序设设计计教教程程第第10章章类类模模板板262728293031323334353637383940414243444546474849void AppendNode(TYPE NewNode);void DispList();void DelList();template

18、ListNode * ListNode:CurNode;template ListNode * ListNode:head;template Void ListNode:AppendNode(TYPE NewData)CurNode-next=new ListNode(NewData);CurNode=CurNode-next;template void ListNode:DispList()CurNode=head-next;while(CurNode!=NULL)coutdatanext;第14页/共53页第13页/共53页第十三页，共54页。2.链表类模板(mbn)C+语语言言程程序序设

19、设计计教教程程(jiochng) 第第10章章类类模模板板50515253545556575859606162template void ListNode:DelList()ListNode *q; CurNode=head-next;while(CurNode!=NULL) q=CurNode-next; delete CurNode; CurNode=q; head-next=NULL;程序解释：由于链表的非头节点为动态对象，因此，要使用(shyng)delete删除节点，以释放内存。 第15页/共53页第14页/共53页第十四页，共54页。2.链表类模板(mbn)C+语语言言程程序序设设

20、计计(chn x sh j)教教程程第第10章章类类模模板板6364656667686970717273 int main() ListNode CList; CList.AppendNode(A); CList.AppendNode(B); CList.AppendNode(C); CList.DispList(); CList.DelList(); CList.DispList();return 0; 运行(ynxng)(ynxng)结果: :ABC 从上述程序例子可见，类模板是一种安全的、高效的重用代码的方式，并可以结合类继承性和函数重载，实现更大范围类的代码重用。因此，类模板的应用在C

21、+中占有重要的地位。第16页/共53页第15页/共53页第十五页，共54页。C+语语言言程程序序设设计计教教程程(jiochng) 第第10章章类类模模板板10.3 STL编程 STL（Standard Template Library），即标准模板库，是一个高效的C+程序库。STL是ANSI/ISO C+标准函数库的一个子集，它提供了大量可扩展的类模板，包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法，类似于Microsoft Visual C+中的MFC（Microsoft Foundation Class Library）。 从逻辑结构和存储结构来看，基本数据结构的数量是有限的

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

23、ing）的思想，它提倡使用现有的模板程序代码开发应用程序，是一种代码的重用技术（reusability）。代码重用可以提高软件开发人员的劳动生产率和目标系统质量，是软件工程追求的重要目标。许多程序设计语言通过提供标准库来实现代码重用的机制。STL是一个通用组件库, 它的目标是将常用的数据结构和算法标准化、通用化，这样用户可以直接套用而不用重复开发它们，从而提高程序设计的效率。 从实现层次看，STL是一种类型(lixng)参数化（type parameterized）的程序设计方法，是一个基于模板的标准类库，称之为容器类。每种容器都是一种已经建立完成的标准数据结构。在容器中，放入任何类型(lix

24、ng)的数据，很容易建立一个存储该类型(lixng)（或类）的数据结构。 STL主要由五个部分组成，分别是容器（container）、迭代器（iterator）、适配器（adaptor）、算法（algorithm）以及函数对象（function object）。第18页/共53页第17页/共53页第十七页，共54页。C+语语言言(yyn)程程序序设设计计教教程程第第10章章类类模模板板10.3.2 STL容器(rngq) 在STL程序设计中，容器（container）就是通用的数据结构。容器用来承载不同类型的数据对象，就如同现实生活中，人们使用容器用来装载各种物品一样，但C+中的容器还存在一定

25、的“数据加工能力”，它如同一个对数据对象进行加工的模具，可以把不同类型的数据放到这个模具中进行加工处理，形成具有一定共同特性的数据结构。例如将int型、char型或者float型放到队列容器中，就分别生成int队列、char型队列或者float型队列，它们都是队列，具有队列的基本特性，但是具体数据类型是不一样的。 STL容器主要包括向量(xingling)（vector）、列表（list）、队列（deque）、集合（set/ multiset）和映射（map/multimap）等。STL用模板实现了这些最常用的数据结构，并以算法的形式提供了对这些容器类的基本操作。 STL中的所有容器都是类模板

26、，是一个已经建立完成的抽象的数据结构，因此可以使用这些容器来存储任何类型的数据，甚至是自己定义的类，而无需自己再定义数据结构。例如利用deque容器，就很容易建立一个队列。第19页/共53页第18页/共53页第十八页，共54页。C+语语言言程程序序设设计计教教程程(jiochng) 第第10章章类类模模板板10.3.2 STL容器(rngq) C+的STL中的容器是同构的，每个容器只允许存储相同类型的数据，也就是说，不能在同一个队列中同时存储int和double类型的数据元素。不过，可以分别创建两个单独的队列，一个用于存储int，另一个用来存储double。STL提供了大多数标准数据结构的实现

27、，比如前面曾经提到的向量、列表、队列、集合等都是容器，用户在进行STL编程时，不必(bb)再编写诸如链表或队列之类的数据结构。 不同的容器有不同的插入、删除和存取行为和性能特征，用户需要分析数据之间逻辑关系，为给定的任务选择最合适的容器。 在STL中，容器大致可以分为两类：顺序容器和关联容器。 第20页/共53页第19页/共53页第十九页，共54页。C+语语言言程程序序设设计计(chn x sh j)教教程程第第10章章类类模模板板10.3.3 顺序(shnx)容器 顺序容器（sequence container）以逻辑线性排列方式存储一个元素(yun s)序列，在这些容器类型中的对象在逻辑上

28、被认为是在连续的存储空间中存储的。在顺序容器中的对象有相对于容器的逻辑位置，如在容器的起始、末尾等。顺序容器可以用于存储线性表类型的数据结构。表表10-110-1 顺序容器顺序容器容器类名特性何时使用头文件vector（向量）在内存中占有一块连续的空间，存储一个元素序列。可以看作一个可自动扩充的动态数组，而且提供越界检查。可用运算符直接存取数据。需要快速查找，不在意插入/删除的速度快慢。能使用数组的地方都能使用向量。list（列表）双向链接列表，每个节点包含一个元素。列表中的每个元素均有指针指向前一个元素和下一个元素。需要快速的插入/删除，不在意查找的速度慢，就可以使用列表。deque（双端队

29、列）在内存中不占有一块连续的空间，介于向量和列表之间，更接近向量，适用于由两端存取数据。可用运算符直接存取数据。可以提供快速的元素存取。在序列中插入/删的速度除较慢。一般不需要使用双端队列，可以转而使用vector或list。第21页/共53页第20页/共53页第二十页，共54页。C+语语言言程程序序设设计计(chn x sh j)教教程程第第10章章类类模模板板10.3.3 顺序(shnx)容器 在STL中，顺序容器一共有3种 ： vector是动态数组的同义词：随着所存储(cn ch)的元素个数的变化，向量会动态的扩展和收缩。C+中的vector不是指数学意义上的向量概念。C+将数学意义上

30、的向量建模为valarray容器。 vector容器中数据元素的存储(cn ch)采用连续存储(cn ch)空间，当需要增加数据元素时，直接从vector容器尾端插入，如果vector容器发现此时存储(cn ch)空间不足，整个容器中的数据元素将会被搬到一个新的、更大的内存空间中，并将所有数据元素复制到新的内存空间中。因此，如果需要快速的存取元素，但不打算经常增加或删除元素，就应当在程序中使用vector容器。 list容器的性能特征与向量恰好相反。list容器是一个标准双向链表，每个元素都知道其前一个与下一个数据元素，其查找速度较慢，只能根据链表指针的指示逐一查找，但一旦找到相关位置，完成元

31、素的插入和删除则很快（常量时间）。 如果需要从元素序列的两端插入和删除，但仍需要快速地存取所有元素，就应当使用deque容器（双端队列）而不是向量。deque容器的特性基本上与vector容器类似，只是deque容器可以从前端以push_front()添加元素，且存储(cn ch)时不需要一块连续的内存空间。在增加数据元素时，如果deque容器内原先定义的内存空间不足，deque容器会将新增加的数据元素存储(cn ch)到另外一块内存中去。第22页/共53页第21页/共53页第二十一页，共54页。C+语语言言(yyn)程程序序设设计计教教程程第第10章章类类模模板板10.3.3 顺序(shnx

32、)容器 【例10-3】 将学生成绩转换为标准分。分析：学生的成绩一般是原始成绩，要将学生的成绩转换为标准分，必须首先比较所有学生的成绩，取得最高分，将学生原始成绩除以最高分，然后乘上100。由于程序没有给出学生人数，所以采用向量作为数据存储结构，因为向量的元素(yun s)个数可以自动的动态增长。 1234567891011/* 程序名：程序名：p10_3.cpp * 功功 能：向量容器示例能：向量容器示例 */#include#includeusing namespace std;int main() vector scorevector; /创建向量创建向量 double max,temp

33、; int i;第23页/共53页第22页/共53页第二十二页，共54页。2.链表类模板(mbn)1315161718192021222324252627282930coutInput -1 to stop:endl; coutmax; scorevector.push_back(max); for(i=1;true;i+) coutEnter the original score i+1temp;if(temp=-1) break;scorevector.push_back(temp);if(tempmax)max=temp; max/=100; C+语语言言(yyn)程程序序设设计计教教程

34、程第第10章章类类模模板板31323334353637383940coutOutput the standard scores: endl; for(i=0;iscorevector.size();i+) scorevectori/=max; coutscorevectori ; cout”来从容器中间接地返回一个值。 不同的容器，STL提供的迭代器功能各不相同。对于vector容器，可以使用“+=”、“-”、“+”、“-=”中的任何一种操作符和“”、“”、“=”、“=”、“!=”等比较运算符。list容器是一个标准双向链表，其迭代器也是双向的，但不能进行加、减运算，不像vector迭代器那样

35、能够随机访问容器中的数据元素。deque容器的迭代器与vector容器类似，但应用相对较少。第26页/共53页第25页/共53页第二十五页，共54页。C+语语言言(yyn)程程序序设设计计教教程程第第10章章类类模模板板10.3.3 顺序(shnx)容器 除了标准的迭代(di di)器外，STL中还有三种迭代(di di)器： 1）reverse_iterator ：如果想用向后的方向而不是向前的方向的迭代(di di)器来遍历除vector之外的容器中的元素，可以使用reverse_iterator 来反转遍历的方向，也可以用rbegin()来代替begin()，用rend()代替end()

36、，而此时的“+”操作符会朝向后的方向遍历。 2）const_iterator ：一个向前方向的迭代(di di)器，它返回一个常数值。可以使用这种类型的游标来指向一个只读的值。 3）const_reverse_iterator：一个朝反方向遍历的迭代(di di)器，它返回一个常数值。 在示例程序p10-3中，第32行开始的for循环，可以通过迭代(di di)器来实现： /采用迭代(di di)器实现 for(vector:iterator it=scorevector.begin(); it!=scorevector.end(); +it) *it/=max; cout*it ; 在上面的

37、程序的程序中，vector:iterator it定义了迭代(di di)器it，begin()返回指示容器中第一个元素的该类迭代(di di)器。 在循环体中： t!=scorevector.end(); 该语句检查迭代(di di)器是否已经访问了向量scorevector中的全部数据元素，如果完成遍历，则循环终止，否则迭代(di di)器自增，使之指向scorevector中的下一个数据元素。 语句+it;返回所指向对象的引用。 语句*it/=max;利用迭代(di di)器访问当前数据元素并修改所指向的数据元素。 第27页/共53页第26页/共53页第二十六页，共54页。C+语语言言程

38、程序序设设计计教教程程(jiochng) 第第10章章类类模模板板10.3.3 顺序(shnx)容器【例10-4】 双端队列容器示例。分析：双端队列是既可以在队头插入(ch r)和删除，也可以在队尾插入(ch r)和删除的一种特殊队列。因此，在实际应用中，双端队列比普通队列的应用范围更加广泛。1234567891011121314151617/* 程序名：程序名：p10_4.cpp * 功功 能：双端队列容器示例能：双端队列容器示例 */#include#includeusing namespace std;templatevoid print(T &deq, char *str) /显示输出

39、双端队列中的所有元素显示输出双端队列中的所有元素T:iterator it;coutThe elements of str: ;for(it=deq.begin();it!=deq.end();it+) cout*it ;coutendl;第28页/共53页第27页/共53页第二十七页，共54页。2.链表类模板(mbn)C+语语言言(yyn)程程序序设设计计教教程程第第10章章类类模模板板19202122232425262728293031323334353637383940int main() deque deque_A; /创建双端队列deque_A.push_back(c); /从队尾进

40、队列deque_A.push_back(d); deque_A.push_front(b); /从队头进队列deque_A.push_front(a);print(deque_A,deque_A); /显示队头元素coutThe first element of deque_A is deque_A.front()endl; /显示队尾元素 coutThe last element of deque_A is deque_A.back()endl; deque_A.insert(deque_A.begin(),x); /在队头插入元素 deque_A.insert(deque_A.end(),

41、z); /在队尾插入元素print(deque_A,deque_A); deque_A.pop_front(); /从队头出队列（删除元素）print(deque_A,deque_A);deque_A.pop_back(); /从队尾出队列（删除元素）print(deque_A,deque_A); return 0; 运行(ynxng)(ynxng)结果: :The elements of deque_A: a b c dThe first element of deque_A is aThe last element of deque_A is dThe elements of deque_

42、A: x a b c d zThe elements of deque_A: a b c d zThe elements of deque_A: a b c d第29页/共53页第28页/共53页第二十八页，共54页。C+语语言言程程序序设设计计教教程程(jiochng) 第第10章章类类模模板板10.3.3 顺序(shnx)容器表表表表10-4 deque10-4 deque容器中较为容器中较为容器中较为容器中较为(jio wi)(jio wi)重要的成员函重要的成员函重要的成员函重要的成员函数数数数 函 数 名功 能 说 明push_front在容器前端增加元素pop_front在容器前端

43、删除元素push_back在容器后端增加元素pop_back在容器后端删除元素insert在容器中间插入元素erase删除容器中间的元素clear清除容器内的元素front返回容器前端元素的引用back返回容器末端元素的引用begin返回容器前端的迭代器end返回容器末端的迭代器rbegin返回容器前端的倒转迭代器rend返回容器末端的倒转迭代器max_size返回容器可存储元素的最大个数size返回当前容器中的元素个数empty若容器为空（无元素）则返回true，否则返回falsecapacity返回当前容器可以存储的最大元素个数at(n)返回第n个元素的引用swap(x)与容器x（dequ

44、e容器）互换元素operator利用运算符取出容器中的元素第30页/共53页第29页/共53页第二十九页，共54页。C+语语言言(yyn)程程序序设设计计教教程程第第10章章类类模模板板10.3.3 顺序(shnx)容器 为了更好的使用3种标准(biozhn)顺序容器，STL还设计了3种容器适配器（ container adapter） ： 队 列 （ queue） 、 优 先 队 列 （ priority queue） 和 栈（stack）。容器适配器可以将顺序容器转换为另一种容器，也就是以顺序容器为基础，将其转换为新的容器。转换后的新容器将具有新的特殊操作要求。表表10-4 10-4 容器

45、适配器容器适配器容器类名特性何时使用头文件queue（队列）在一端插入元素，在另一端取出元素，具有先进先出（first in, first out, FIFO）的特性，插入和删除都较快。需要一个FIFO结构时使用队列。priority queue（优先队列）每个元素都有一个优先级，元素按优先级的顺序从队列中删除，如果优先级相同，则仍然遵循先进先出规则。插入和删除都比一般的简单队列慢，因为必须对元素重新调整顺序，以支持按优先级排序。需要一个带优先级的FIFO结构时使用优先队列。stack（栈）在一端插入元素，在同一端删除元素，具有先进后出（first in, last out, FILO）的特性

46、。需要一个FILO结构时使用栈。第31页/共53页第30页/共53页第三十页，共54页。C+语语言言(yyn)程程序序设设计计教教程程第第10章章类类模模板板10.3.3 顺序(shnx)容器123456789101112131415161718192021/* 程序名：p10_4.cpp * 功 能：队列容器示例程序 */#include#includeusing namespace std;templatevoid print(queue &q) if(q.empty() /判断队列是否空 coutQueue is empty!endl; else int j=q.size(); for(

47、int i=0; ij;i+) coutq.front() ; q.pop(); /出队列 coutendl; 第32页/共53页第31页/共53页第三十一页，共54页。2.链表类模板(mbn)C+语语言言程程序序设设计计教教程程(jiochng) 第第10章章类类模模板板242526272829303132333435363738int main() queue q; /创建队列 q.push(1); /进队列 q.push(2); q.push(3); q.push(4); /取队头元素 coutThe first element is : q.front()endl; /取队尾元素 co

48、utThe last element is : q.back()endl; coutThe queue is : endl; print(q); return 0; 运行(ynxng)(ynxng)结果: :The first element is : 1The last element is : 4The queue is :1 2 3 4第33页/共53页第32页/共53页第三十二页，共54页。C+语语言言程程序序设设计计(chn x sh j)教教程程第第10章章类类模模板板10.3.3 顺序(shnx)容器 容器适配器也是带有类型参数的STL类模板。从技术上看，容器适配器就是将某个底层

49、顺序容器的转换为另一种容器。即以顺序容器作为数据存储结构，将其转换为一种某种特定操作特性的新容器，如queue、priority queue和stack，从而进一步扩展容器的应用。 容器适配器对顺序容器的转换形式如下： 第一个模板参数T指定要在容器中存储的类型。第二个模板参数规定适配的底层容器，变量名是利用容器适配器建立的新容器名。具体细节可参考相关专门讲述STL编程的专业书籍。 对于前面示例(shl)中的容器适配器queue（队列）而言，由于queue内数据元素要求遵循FIFO（first in, first out）的原则，因此，要转换为queue的顺序容器必须支持push_back（在容

50、器后端添加元素），又支持pop_front（在容器前端删除元素），因此只有两个内置的顺序容器可供选择：deque和list。priority queue的转换与queue类似。container adapter typename T, container 变量名;第34页/共53页第33页/共53页第三十三页，共54页。C+语语言言(yyn)程程序序设设计计教教程程第第10章章类类模模板板10.3.3 顺序(shnx)容器1234567891011121314151617/* 程序名：p10_6.cpp * 功 能：容器适配器queue示例 */#include#include#include

51、using namespace std;templatevoid print(T &q) while(!q.empty() coutq.front() ; q.pop(); /出队列 coutendl;第35页/共53页第34页/共53页第三十四页，共54页。2.链表类模板(mbn)C+语语言言程程序序设设计计教教程程(jiochng) 第第10章章类类模模板板2021222324252627282930int main() queue int,list list_q; /容器适配器转换顺序容器 for(int i=1;i=4;i+) list_q.push(i); coutThe first

52、 element is : list_q.front()endl; coutThe last element is : list_q.back()endl; coutThe queue is : endl; print(list_q); return 0; 运行(ynxng)(ynxng)结果: :The first element is : 1The last element is : 4The queue is :1 2 3 4第36页/共53页第35页/共53页第三十五页，共54页。C+语语言言(yyn)程程序序设设计计教教程程第第10章章类类模模板板10.3.3 顺序(shnx)容器

53、stack（栈）是一种经典数据结构，它要求数据元素具有FILO（first in, last out）的特性，因此要转换为stack的顺序容器必须支持push_back（在容器后端添加元素），又支持pop_back（在容器后端删除元素），而顺序容器中vector、deque和list都符合(fh)这个条件，因此，它们都可以通过容器适配器转换为stack。【例10-7】 容器适配器stack的示例程序1234567891011121314151617/* 程序名：程序名：p10_7.cpp * 功功 能：容器适配器能：容器适配器stack示例示例 */#include#include#inclu

54、deusing namespace std;templatevoid output(T &stackdata) while(!stackdata.empty() coutstackdata.top() ; /取栈顶元素取栈顶元素 stackdata.pop(); /出栈出栈 coutendl;第37页/共53页第36页/共53页第三十六页，共54页。2.链表类模板(mbn)C+语语言言程程序序设设计计(chn x sh j)教教程程第第10章章类类模模板板2021222324252627282930313233int main() stack int_s; /创建栈 stack int,vec

55、tor vec_stack; for(int i=0;i4;i+) int_s.push (i); /进栈vec_stack.push(i); coutPop from int stack:endl; output(int_s); coutPop from vec_stack:endl; output(vec_stack); return 0; 运行(ynxng)(ynxng)结果: :Pop from int stack:3 2 1 0Pop from vec_stack:3 2 1 0第38页/共53页第37页/共53页第三十七页，共54页。C+语语言言程程序序设设计计(chn x sh

56、j)教教程程第第10章章类类模模板板10.4 关联(gunlin)容器 与顺序容器中的对象不同，关联容器（associate container）中的数据元素不存储在顺序的线性数据结构中，相反，它们提供了一个关键字（key）到值的关联映射。当插入数据元素到关联容器中时，各数据元素之间并不以插入的先后或位置作为(zuwi)顺序，而是依据数据元素的关键字按照某一顺序进行排列。如果是数字则依照数字大小进行排列；如果是字符串则按英文字母的顺序排列。 STL提供了4个关联容器：set、multiset、map和multimap，这些容器都将数据元素存储在一个有序的、类似于树的数据结构中。数据元素的存储和

57、检索是基于关键字和该数据元素与其他数据元素之间的关系。 第39页/共53页第38页/共53页第三十八页，共54页。C+语语言言程程序序设设计计(chn x sh j)教教程程第第10章章类类模模板板10.4 关联(gunlin)容器 STL中的集合（set）就是一个元素集合（collection）。尽管集合的数学定义指出它是无序的，但STL中的集合会按有序的方式存储元素，因而能够提供相当快的查找、插入和删除。事实上，集合的插入、删除和查找等操作的时间复杂度都是O(log(N)，其底层实现往往(wngwng)是一个平衡二叉树。表表10-510-5 关联容器关联容器容器类名特性何时使用头文件set

58、（集合）/multiset（多集）set是一个元素集合。集合中的元素按有序的方式存储。set中没有重复的元素，但multiset中允许有重复的元素。需要使用元素集合，而且对元素的查找、插入和删除操作都较为频繁时，就可以使用set/multiset。map（映射）/multimap（多映射）map是键(key)，值对的组成的集合。集合中的元素按键排列。multimap是允许键/值对有重复的集合。map和multimap的关系如同set和multiset之间的关系如果希望将键/与值相关联就可以使用map/muitimap。表表10-510-5 关联容器关联容器第40页/共53页第39页/共53页第

59、三十九页，共54页。C+语语言言程程序序设设计计教教程程(jiochng) 第第10章章类类模模板板10.4 关联(gunlin)容器12345678910111213141516171819202122/* 程序名：p10_8.cpp * 功 能：关联容器set示例 */#include#include#includeusing namespace std;templatevoid print(set &set_con) /输出set中所有元素 if(set_con.empty() coutContainer is empty!endl; else set:iterator it; /定义迭

60、代器for(it=set_con.begin(); it!=set_con.end();it+) cout*it ; coutendl; 第41页/共53页第40页/共53页第四十页，共54页。2.链表类模板(mbn)C+语语言言程程序序设设计计(chn x sh j)教教程程第第10章章类类模模板板242526272829303132333435363738394041424344454647int main() string stu_name=ChenHailing,LiuNa,CuiPeng; set str_set(stu_name,stu_name+3); coutAll stude

61、nt:endl; print(str_set); coutAfter insert:endl; str_set.insert(DingLong); /插入数据元素 print(str_set); coutAfter erase:endl; str_set.erase(ChenHailing); /删除数据元素 print(str_set); string search; set:iterator it; coutPlease input the student name for searching:search; it=str_set.find(search); /查找数据元素 if(it=s

62、tr_set.end() coutThe search did not find!endl; else coutThe search find!endl; return 0; 运行(ynxng)(ynxng)结果: :All students:ChenHailing CuiPeng LiuNaAfter insert:ChenHailing CuiPeng DingLong LiuNaAfter erase:CuiPeng DingLong LiuNaPlease input the student name for searching:DingLongThe DingLong find!第4

63、2页/共53页第41页/共53页第四十一页，共54页。C+语语言言程程序序设设计计(chn x sh j)教教程程第第10章章类类模模板板10.4 关联(gunlin)容器 在set容器中，数据元素不存在键/值对，因为数据元素的值是唯一的，所以数据元素的值就是键（key）。集合中的数据元素按一定的顺序排列，并被作为集合中的实例。如果需要一个键/值对（pair）来存储数据，map是一个更好的选择。map中的数据元素是由关键字和数据两部分组成。例如：在银行管理系统中，每个用户都有一个对应的帐号。 multimap与map基本相同，但允许键/值对有重复的集合。 例如：大多数在线聊天程序中允许用户有一

64、个“好友列表”。聊天程序会对“好友列表”中列出的用户授予一些特权，如允许他们向用户发送主动信息。程序实现可以采用multimap容器来实现，一个multimap可以存储所有用户的“好友列表”，每个数据元素表示(biosh)一个用户，键（key）是用户名，值是好友名。multimap允许同一个键有多个值，因此，一个用户就可以有多个好友。第43页/共53页第42页/共53页第四十二页，共54页。C+语语言言(yyn)程程序序设设计计教教程程第第10章章类类模模板板10.5 STL算法(sun f) 算法（algorithm）就是一些常用的数据处理方法，如向容器中插入、删除容器中的元素、查找容器中的

65、元素、对容器中的元素排序、复制容易中的元素等等，这些数据处理方法是以函数模板的形式实现的实现的。 算法之美就在于(ziy)它们不仅独立于底层元素的类型，而且也独立于所操作的容器，利用这些已经定义的算法和迭代器，程序设计人员可以方便灵活地地存取容器中存储的各种数据元素。 在STL中，算法的“神奇之处”在于(ziy)：算法并非容器的一部分，而是工作在迭代器基础之上，通过迭代器这个“中间人”存取容器中的元素，算法并没有和特定的容器进行绑定。 在传统的软件开发方法中，算法与数据类型、数据结构紧密耦合，缺乏通用性。而STL 倡导泛型编程风格，即以通用的方式来编写程序。STL采用C+模板机制实现了算法与数

66、据类型的无关性。实际上，为了支持通用程序设计，STL实现了算法与容器（数据结构）的分离。这样，同一算法适用于不同的容器和数据类型，成为通用性算法，可以最大限度地节省源代码。因此STL比传统的函数库或类库具有更好的代码重用性。 第44页/共53页第43页/共53页第四十三页，共54页。2.链表类模板(mbn)C+语语言言程程序序设设计计教教程程(jiochng) 第第10章章类类模模板板12345678910111213141516171819202122232425/* 程序名：p10_9.cpp * 功 能：算法（algorithm）示例 */#include#include#include

67、using namespace std;templatevoid print(T &con) /输出容器中所有元素 if(con.empty() coutContainer is empty!endl; else T:iterator it; /设置迭代器 for(it=con.begin(); it!=con.end();it+) cout*it ; coutendl; 第45页/共53页第44页/共53页第四十四页，共54页。2.链表类模板(mbn)C+语语言言程程序序设设计计教教程程(jiochng) 第第10章章类类模模板板2627282930313233343536373839404

68、14243444546474849int main() int num; vector vec_A(8); /定义容器vec_A coutFill vec_A with A:endl; fill(vec_A.begin(),vec_A.end(),A); /填充数据元素 print(vec_A); coutCopy element of vector to vec_A:endl; char array_B=B,B,B,B,; vector vec_B(array_B,array_B+4); /定义容器vec_A,并初始化 copy(vec_B.begin(),vec_B.end(),vec_A

69、.begin()+2); /复制数据元素 print(vec_A); coutRemove A from vec_A:endl; vector:iterator it; it=remove(vec_A.begin(),vec_A.end(),A); /移除数据元素 vec_A.erase(it,vec_A.end(); /删除数据元素 print(vec_A); coutRepalce B with C:endl; replace(vec_A.begin(),vec_A.begin()+2,B,C); /替换数据元素 replace(vec_B.begin(),vec_B.end(),B,X)

70、; print(vec_A);第46页/共53页第45页/共53页第四十五页，共54页。2.链表类模板(mbn)C+语语言言(yyn)程程序序设设计计教教程程第第10章章类类模模板板525354555657585960616263646566676869 coutInserting:endl; vec_A.insert(vec_A.begin(),D); /插入数据元素插入数据元素 vec_A.insert(vec_A.end(),A); print(vec_A); coutSorting:endl; sort(vec_A.begin(),vec_A.end(); /排序排序 print(ve

71、c_A); vector vec_C(vec_A.size()+vec_B.size(); coutMerge vec_A and vec_B:endl; merge(vec_A.begin(),vec_A.end(),vec_B.begin(),vec_B.end(), vec_C.begin(); /合并合并 print(vec_C); num=count(vec_C.begin(),vec_C.end(),B); /统计数据元素统计数据元素 coutCounting the number of B in vec_C:endl; coutnumendl; return 0; 运行(ynxn

72、g)(ynxng)结果: :Fill vec_A with A:A A A A A A A ACopy element of vector to vec_A:A A B B B B A ARemove A from vec_A:B B B BRepalce B with C:C C B BInserting:D C C B B ASorting:A B B C C DMerge vec_A and vec_B:A B B C C D X X X XCounting the number of B in vec_C:2第47页/共53页第46页/共53页第四十六页，共54页。C+语语言言程程序序

73、设设计计(chn x sh j)教教程程第第10章章类类模模板板10.3.6 函数(hnsh)对象 在C+中, 把函数名后的括号()称为函数调用运算符。函数调用运算符也可以像其他运算符一样进行重载。如果某个类重载了函数调用运算符，则该类的实例就是一个函数对象(duxing)（function object）。 例如： class Add double operator () (double x, double y) return x+ y; ; 类Add 的实例就是函数对象(duxing)。下面是创建并使用该类函数对象(duxing)的代码: Add plus; coutplus (12. 6

74、, 2. 4) ; coutAdd () (13. 9, 26. 8) ; 当编译器处理表达式plus (12. 6, 2. 4) 时, 将它解释为plus.operator () (12. 6, 2. 4)。表达式Add () 将创建一个临时对象(duxing)，然后按与对象(duxing)一样的方法使用它。由此可以看到，如果一个类重载了函数调用运算符，则创建一个该类的实例，并以函数的调用形式来引用该实例的话，其实就是在调用operator () 这个成员函数。第48页/共53页第47页/共53页第四十七页，共54页。C+语语言言(yyn)程程序序设设计计教教程程第第10章章类类模模板板10

75、.3.6 函数(hnsh)对象 一个函数对象通常是完成特定的简单操作的很小的类对象。函数对象本身并不是很有用，但它们使得算法中函数操作的参数化策略成为可能，使通用性算法变得更加通用。函数对象在STL中被广泛使用，如同算法的得力助手，大大增强了算法和其它组件的能力，使STL 形成为一个具有强大威力的泛型库。 在STL中，函数对象是由模板类产生的对象，产生函数对象的模板类只有一个用于重载的operator()函数，所以在使用STL中的函数对象时，必须传入数据类型。 例如： vector vec_total; /对scorevector内的数据元素进行排序 sort(vec_total.begin(

76、),vec_total.end(),greater(); 由于(yuy)vec_total是一个容纳int类型数据的vector容器，因此使用函数对象greater时，所传入的数据类型也必须是double类型。算法sort()的第三个模板参数greater表示函数对象greater的模板类使用了double数据类型。STL中包含许多预定义的函数对象，大致上分为3类： （1）算术操作：plus, minus, multiplies, divides, modulus, 和 negate （2）比较操作：equal_to, not_equal_to, greater, less, greater_

77、equal, 和 less_equal （3）逻辑操作：logical_and, logical_or, 和 logical_not 在STL编程中，直接使用函数对象的方式并无多大意义, 但如果把函数对象作为参数传递给其它函数, 则其它函数就具有了通用性。第49页/共53页第48页/共53页第四十八页，共54页。C+语语言言(yyn)程程序序设设计计教教程程第第10章章类类模模板板10.3.6 函数(hnsh)对象123456789101112/* 程序名：p10_10.cpp * 功 能：函数对象（function objector）示例程序 */#include#include#inclu

78、de#includeusing namespace std;void print(double i) couti ; 【例10-10】 利用函数对象计算学生总成绩并排序后输出。分析：学生的成绩包括(boku)考试成绩、实验成绩和总评成绩，学生总评成绩由考试成绩（占60%）、实验成绩（占40%）这两部分之和组成。第50页/共53页第49页/共53页第四十九页，共54页。2.链表类模板(mbn)C+语语言言程程序序设设计计教教程程(jiochng) 第第10章章类类模模板板141516171819202122232425262728293031int main() double test_scor

79、e=76,92,84,65,96; double exp_score=88,96,90,72,98;vector vec_test(test_score,test_score+5); vector vec_exp(exp_score,exp_score+5);vector vec_total(vec_test.size(); coutTest score: ;for_each(vec_test.begin(),vec_test.end(),print); coutendl; coutExperiment score: ; for_each(vec_exp.begin(),vec_exp.end

80、(),print); coutendl;for(int i=0;i=4;i+) vec_testi=vec_testi*0.6; /考试成绩占60% vec_expi=vec_expi*0.4; /实验成绩占40%第51页/共53页第50页/共53页第五十页，共54页。2.链表类模板(mbn)C+语语言言程程序序设设计计(chn x sh j)教教程程第第10章章类类模模板板333435363738394041424344 coutTotal score: ;transform(vec_test.begin(),vec_test.end(),vec_exp.begin(), vec_total

81、.begin(),plus();for_each(vec_total.begin(),vec_total.end(),print);coutendl; coutAfter sorting: ;sort(vec_total.begin(),vec_total.end(),greater(); for_each(vec_total.begin(),vec_total.end(),print);coutendl; return 0; 运行(ynxng)(ynxng)结果: :Test score: 76 92 84 65 96Experiment score: 88 96 90 72 98Total

82、 score: 80.8 93.6 86.4 67.8 96.8After sorting: 96.8 93.6 86.4 80.8 67.8第52页/共53页第51页/共53页第五十一页，共54页。10.4 本章本章(bn zhn)小结小结 类模板是能根据不同参数建立不同类型对象的类，类模板中的数据成员、成员 函数的参数、成员函数的返回值可以取参数化类型。 类模板实例化是在建立对象时，根据传入的参数类型，将类模板实例化成具 体类，然后再建立对象。 栈是一种先进后出FILO（First In Last Out）的一种结构，在程序设计中广 泛使用栈，将栈设计成一个类模板，就可以在栈中存放任意类型

83、的数据。 动态链表的插入与删除节点的性能优于静态数组，在程序设计中广泛使用链 表，将链表设计成一个类模板，就可以在链表节点中存放任意类型的数据。 STL（Standard Template Library）是C+提供的标准模板库，它可以实现高 效的泛型程序设计。 STL容器包括顺序容器和关联容器，利用容器适配器可以将顺序容器转换为新 的容器。 在STL中，算法独立(dl)于所操作的容器，利用已经定义的算法和迭代器，用户可 以方便灵活地地存取容器中存储的各种数据元素。 在STL中，函数对象是由模板类产生的对象，函数对象在STL中被广泛用作算 法中子操作的参数，使算法变得更加通用。C+语语言言(y

84、yn)程程序序设设计计教教程程第第10章章类类模模板板第53页/共53页第52页/共53页第五十二页，共54页。感谢您的欣赏(xnshng)！第53页/共53页第五十三页，共54页。内容(nirng)总结C+语言程序设计教程。【例10-1】将栈设计成一个类模板，在栈中存放任意(rny)类型的数据。uzyx。【例10-2】将线性链表设计成一个类模板，从而可以在链表节点中存放任意(rny)类型的数据。ABC。若容器为空（无元素）则返回true，否则返回false。除了标准的迭代器外，STL中还有三种迭代器：。priority queue的转换与queue类似。如果需要一个键/值对（pair）来存储数据，map是一个更好的选择第五十四页，共54页。