C++类模板与STL编程.ppt

《C++类模板与STL编程.ppt》由会员分享，可在线阅读，更多相关《C++类模板与STL编程.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第1010章章 类模板与类模板与STL编程编程C+语语言言程程序序设设计计教教程程第第10章章类类模模板板第第1010章章 类模板类模板学习目标 1.理解类模板的概念；2.掌握类模板的定义、实例化过程，会运用类模板；3.掌握栈类模板、链表类模板的使用；4.理解STL编程的基本思想；5.掌握STL容器的使用；6.熟练使用STL算法；7.理解STL函数对象；C+语语言言程程序序设设计计教教程程第第10章章类类模模板板C+语语言言程程序序设设计计教教程程第第10章章类类模模板板10.1 类模板 模板是C+语言的重要特征，它能够显著提高编程效率。利用C+的函数模板和类模板，能够快速建立具有类型安全的

2、类库集合和函数集合，进行大规模软件开发，并提高软件的通用性和灵活性。C+的标准模板库标准模板库（standard template library，简称STL）编程完全依赖模板的实现。类模板类模板是能根据不同参数建立不同类型成员的类。类模板中的数据成员、成员函数的参数、成员函数的返回值可以取不同类型，在实例化成对象时，根据传入的参数类型，实例化成具体类型的对象。类模板也称模板类。类模板定义的语法为：其中：template为模板关键字。模板参数表中的类型为参数化(parameterized)类型，也称可变类型，类型名为class(或typename)；模板参数表中的类型也可包含普通类型，普通类型

3、的参数用来为类的成员提供初值。类模板中的成员函数可以是函数模板，也可以是普通函数。C+语语言言程程序序设设计计教教程程第第10章章类类模模板板1.类模板的定义类模板的定义template class 类名类名 成员名；成员名；;例如，下面定义了一个模板类Student，为了增强类的适用性，将学号设计成参数化类型，它可以实例化成字符串、整型等；将成绩设计成参数化类型，它可以实例化成整型、浮点型、字符型(用来表示等级分)等；C+语语言言程程序序设设计计教教程程第第10章章类类模模板板1.类模板的定义类模板的定义template /TNO,TScore 为参数化类型class Student pri

4、vate:TNO StudentIDnum;/参数化类型数组，存储姓名 TScore scorenum;/参数化类型数组，存储分数 public:TNO TopStudent()/普通函数 return StudentID0;int BelowNum(TScore ascore)/函数模板 return 0;void sort()/普通函数 ;模板类的成员函数还可以在类外定义，其语法如下：其中：模板参数表与类模板的模板参数表相同。模板参数名表列出的是模板参数表中参数名，顺序与模板参数表中的顺序一致。C+语语言言程程序序设设计计教教程程第第10章章类类模模板板1.类模板的定义类模板的定义temp

5、late 类型类型 类名类名 函数名函数名(参数表参数表)函数体函数体;模板类的成员函数还可以在类外定义，其语法如下：C+语语言言程程序序设设计计教教程程第第10章章类类模模板板1.类模板的定义类模板的定义template 类型类型 类名类名 ：函数名：函数名(参数表参数表)函数体；函数体；其中：模板参数表与类模板的模板参数表相同；模板参数名表列出的是模板参数表中参数名，顺序与模板参数表中的顺序一致；例如，模板类Student的成员函数在类外实现如下：模板类Student的成员函数在类外实现如下：template class Student private:TNO StudentIDnum;T

6、Score 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;一个类模板是具体类的抽象，在使用类模板建立对象时，才根据给定的模板参数值实例化(专门化)成具体的类，然后由类建立对象。与函数模板不同，类模板实例化只能采用显式方式。类模板实例化、

7、建立对象的语法如下:C+语语言言程程序序设设计计教教程程第第10章章类类模模板板2.类模板的实例化类模板的实例化类模板名类模板名 对象对象1,对象对象2,对象对象n;其中：模板参数值表的值为类型名，类型名可以是基本数据类型名，也可以是构造数 据类型名，还可以是类类型名。模板参数值表的值还可以是常数表达式，以初始化模板参数表中普通参数。模板参数值表的值按一一对应的顺序实例化类模板的模板参数表。例如，下面对模板类Student实例化:class String public:char Str20;void main()Student S1;S1.sort();Student S2;S2.TopStu

8、dent();编译Student S1；时：String 取代 TNO float 取代 TScore 100 取代 numC+语语言言程程序序设设计计教教程程第第10章章类类模模板板2.类模板的实例化类模板的实例化template class Student private:TNO StudentIDnum;TScore scorenum;public:TNO TopStudent()int BelowNum(TScore ascore)void sort();class Student private:String StudentID100;float score100;public:St

9、ring TopStudent();int BelowNum(float ascore);void sort();将类Student实例化成：C+语语言言程程序序设设计计教教程程第第10章章类类模模板板2.默认模板参数默认模板参数template class Student private:TNO StudentIDnum;TScore scorenum;public:TNO TopStudent();int BelowNum(TScore ascore);void sort();类模板的实例化过程与函数调用的实参与形参结合的过程相似，函数的形参可以采用默认值，类模板的类型参数也可以采用默认值

10、，这样避免每次实例化时都显式给出实参。TScore,num分别给出默认值int，10。用以下方式实例化：Student S1;class Student private:char*StudentID10;int score10;public:char*TopStudent();int BelowNum(int ascore);void sort();10.2 类模板应用1.栈类模板栈类模板C+语语言言程程序序设设计计教教程程第第10章章类类模模板板 栈是一种先进后出FILO(First In Last Out)的一种结构，在程序设计中广泛使用栈，栈的基本操作有:压栈push、出栈pop。其他操

11、作有判空、判满、读栈顶元素等。下图演示栈的操作：【例例10-1】将栈设计成一个类模板，在栈中存放任意类型的数据。分析分析：栈空间可以使用静态数组，本例中使用动态数组。使用指针top指向栈顶元素，使用成员函数push()、pop()、IsEmpty()、IsFull()分别进行压栈、出栈、判空、判满。1.栈类模板栈类模板891011121314151617181920212223242526272829303132/*p10_1.cpp 栈类模板template class Stack private:int size;int top;T*space;public:Stack(int=10);S

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

13、ck: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;运行结果运行结果:uzyx 2.链表类模板链表类模板C+语语言言程程序序设设计计教教程程第第10章章类类模模板板 【例例1

14、0-2】将线性链表设计成一个类模板，从而可以在链表节点中存放任意类型的数据。分析：分析：链表的操作见5.5.1，为了节省内存空间，将头指针与当前节点指针设计成static,为同类型链表所共有；为了便于操作，同样将链表的第一个节点当成头节点，不存储数据。链表的构成如下图所示：2.链表类模板链表类模板C+语语言言程程序序设设计计教教程程第第10章章类类模模板板5678910111213141516171819202122232425/p10_2.cpp*单向链表的类模板*#include using namespace std;template class ListNode private:TYP

15、E data;ListNode*next;static ListNode *CurNode;static ListNode *head;public:ListNode()next=NULL;head=CurNode=this;ListNode(TYPE NewData)data=NewData;next=NULL;程序解释：程序解释：第16行为不带参数的构造函数，用于建立头节点。第62行建立对象时，调用了不带参数的构造函数，建立了一个仅含头节点的链表。第20行为带数据域参数的构造函数，供函数AppendNode()动态建立节点对象时调用。2.链表类模板链表类模板C+语语言言程程序序设设计计教教

16、程程第第10章章类类模模板板262728293031323334353637383940414243444546474849void AppendNode(TYPE NewNode);void DispList();void DelList();template ListNode*ListNode:CurNode;template ListNode*ListNode:head;template Void ListNode:AppendNode(TYPE NewData)CurNode-next=new ListNode(NewData);CurNode=CurNode-next;templat

17、e void ListNode:DispList()CurNode=head-next;while(CurNode!=NULL)coutdatanext;2.链表类模板链表类模板C+语语言言程程序序设设计计教教程程第第10章章类类模模板板50515253545556575859606162template void ListNode:DelList()ListNode*q;CurNode=head-next;while(CurNode!=NULL)q=CurNode-next;delete CurNode;CurNode=q;head-next=NULL;程序解释：程序解释：由于链表的非头节点

18、为动态对象，因此，要使用delete删除节点，以释放内存。2.链表类模板链表类模板C+语语言言程程序序设设计计教教程程第第10章章类类模模板板6364656667686970717273 int main()ListNode CList;CList.AppendNode(A);CList.AppendNode(B);CList.AppendNode(C);CList.DispList();CList.DelList();CList.DispList();return 0;运行结果运行结果:ABC 从上述程序例子可见，类模板类模板是一种安全的、高效的重用代码的方式，并可以结合类继承性和函数重载，

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

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

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

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

23、数据结构。例如将int型、char型或者float型放到队列容器中，就分别生成int队列、char型队列或者float型队列，它们都是队列，具有队列的基本特性，但是具体数据类型是不一样的。STL容器主要包括向量（向量（vector）、列表（）、列表（list）、队列（）、队列（deque）、集）、集合（合（set/multiset）和映射（）和映射（map/multimap）等。STL用模板实现了这些最常用的数据结构，并以算法的形式提供了对这些容器类的基本操作。STL中的所有容器都是类模板类模板，是一个已经建立完成的抽象的数据结构，因此可以使用这些容器来存储任何类型的数据，甚至是自己定义的类，

24、而无需自己再定义数据结构。例如利用deque容器，就很容易建立一个队列。C+语语言言程程序序设设计计教教程程第第10章章类类模模板板10.3.2 STL容器 C+的STL中的容器是同构同构的，每个容器只允许存储相同类型的数据相同类型的数据，也就是说，不能在同一个队列中同时存储int和double类型的数据元素。不过，可以分别创建两个单独的队列，一个用于存储int，另一个用来存储double。STL提供了大多数标准数据结构的实现，比如前面曾经提到的向量、列表、队列、集合等都是容器，用户在进行STL编程时，不必再编写诸如链表或队列之类的数据结构。不同的容器有不同的插入、删除和存取行为和性能特征，用

25、户需要分析数据之间逻辑关系，为给定的任务选择最合适的容器。在STL中，容器大致可以分为两类：顺序容器顺序容器和关联容器关联容器。C+语语言言程程序序设设计计教教程程第第10章章类类模模板板10.3.3 顺序容器 顺序容器（sequence container）以逻辑线性排列方式存储一个元素序列，在这些容器类型中的对象在逻辑上被认为是在连续的存储空间中存储的。在顺序容器中的对象有相对于容器的逻辑位置，如在容器的起始、末尾等。顺序容器可以用于存储线性表类型的数据结构。表表10-110-1 顺序容器顺序容器容器类名特性何时使用头文件vector（向量）在内存中占有一块连续的空间，存储一个元素序列。可

26、以看作一个可自动扩充的动态数组，而且提供越界检查。可用运算符直接存取数据。需要快速查找，不在意插入/删除的速度快慢。能使用数组的地方都能使用向量。list（列表）双向链接列表，每个节点包含一个元素。列表中的每个元素均有指针指向前一个元素和下一个元素。需要快速的插入/删除，不在意查找的速度慢，就可以使用列表。deque（双端队列）在内存中不占有一块连续的空间，介于向量和列表之间，更接近向量，适用于由两端存取数据。可用运算符直接存取数据。可以提供快速的元素存取。在序列中插入/删的速度除较慢。一般不需要使用双端队列，可以转而使用vector或list。C+语语言言程程序序设设计计教教程程第第10章章

27、类类模模板板10.3.3 顺序容器 在STL中，顺序容器一共有3种：vector是动态数组的同义词：随着所存储的元素个数的变化，向量会动态的扩展和收缩。C+中的vector不是指数学意义上的向量概念。C+将数学意义上的向量建模为valarray容器。vector容器中数据元素的存储采用连续存储空间，当需要增加数据元素时，直接从vector容器尾端插入，如果vector容器发现此时存储空间不足，整个容器中的数据元素将会被搬到一个新的、更大的内存空间中，并将所有数据元素复制到新的内存空间中。因此，如果需要快速的存取元素，但不打算经常增加或删除元素，就应当在程序中使用vector容器。list容器容

28、器的性能特征与向量恰好相反。list容器是一个标准双向链表，每个元素都知道其前一个与下一个数据元素，其查找速度较慢，只能根据链表指针的指示逐一查找，但一旦找到相关位置，完成元素的插入和删除则很快（常量时间）。如果需要从元素序列的两端插入和删除，但仍需要快速地存取所有元素，就应当使用deque容器容器（双端队列）而不是向量。deque容器的特性基本上与vector容器类似，只是deque容器可以从前端以push_front()添加元素，且存储时不需要一块连续的内存空间。在增加数据元素时，如果deque容器内原先定义的内存空间不足，deque容器会将新增加的数据元素存储到另外一块内存中去。C+语语

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

30、量创建向量 double max,temp;int i;2.链表类模板链表类模板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+语语言言程程序序设设计计教教程程第第10章章类类模模板板313233343

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

32、代器与vector容器类似，但应用相对较少。C+语语言言程程序序设设计计教教程程第第10章章类类模模板板10.3.3 顺序容器 除了标准的迭代器外，STL中还有三种迭代器：1）reverse_iterator：如果想用向后的方向而不是向前的方向的迭代器来遍历除vector之外的容器中的元素，可以使用reverse_iterator 来反转遍历的方向，也可以用rbegin()来代替begin()，用rend()代替end()，而此时的“+”操作符会朝向后的方向遍历。2）const_iterator：一个向前方向的迭代器，它返回一个常数值。可以使用这种类型的游标来指向一个只读的值。3）const_

33、reverse_iterator：一个朝反方向遍历的迭代器，它返回一个常数值。在示例程序p10-3中，第32行开始的for循环，可以通过迭代器来实现：/采用迭代器实现 for(vector:iterator it=scorevector.begin();it!=scorevector.end();+it)*it/=max;cout*it;在上面的程序的程序中，vector:iterator it定义了迭代器it，begin()返回指示容器中第一个元素的该类迭代器。在循环体中：t!=scorevector.end();该语句检查迭代器是否已经访问了向量scorevector中的全部数据元素，如果

34、完成遍历，则循环终止，否则迭代器自增，使之指向scorevector中的下一个数据元素。语句+it;返回所指向对象的引用。语句*it/=max;利用迭代器访问当前数据元素并修改所指向的数据元素。C+语语言言程程序序设设计计教教程程第第10章章类类模模板板10.3.3 顺序容器【例10-4】双端队列容器示例。分析：双端队列是既可以在队头插入和删除，也可以在队尾插入和删除的一种特殊队列。因此，在实际应用中，双端队列比普通队列的应用范围更加广泛。1234567891011121314151617/*程序名：程序名：p10_4.cpp *功功 能：双端队列容器示例能：双端队列容器示例 */#inclu

35、de#includeusing namespace std;templatevoid print(T&deq,char*str)/显示输出双端队列中的所有元素显示输出双端队列中的所有元素T:iterator it;coutThe elements of str:;for(it=deq.begin();it!=deq.end();it+)cout*it;coutendl;2.链表类模板链表类模板C+语语言言程程序序设设计计教教程程第第10章章类类模模板板19202122232425262728293031323334353637383940int main()deque deque_A;/创建双

36、端队列deque_A.push_back(c);/从队尾进队列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_

37、A.insert(deque_A.end(),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;运行结果运行结果: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 de

38、que_A:x a b c d zThe elements of deque_A:a b c d zThe elements of deque_A:a b c dC+语语言言程程序序设设计计教教程程第第10章章类类模模板板10.3.3 顺序容器表表表表10-410-4 dequedeque容器中较为重要的成员函数容器中较为重要的成员函数容器中较为重要的成员函数容器中较为重要的成员函数 函 数 名功 能 说 明push_front在容器前端增加元素pop_front在容器前端删除元素push_back在容器后端增加元素pop_back在容器后端删除元素insert在容器中间插入元素erase删除

39、容器中间的元素clear清除容器内的元素front返回容器前端元素的引用back返回容器末端元素的引用begin返回容器前端的迭代器end返回容器末端的迭代器rbegin返回容器前端的倒转迭代器rend返回容器末端的倒转迭代器max_size返回容器可存储元素的最大个数size返回当前容器中的元素个数empty若容器为空（无元素）则返回true，否则返回falsecapacity返回当前容器可以存储的最大元素个数at(n)返回第n个元素的引用swap(x)与容器x（deque容器）互换元素operator利用运算符取出容器中的元素C+语语言言程程序序设设计计教教程程第第10章章类类模模板板10

40、.3.3 顺序容器 为了更好的使用3种标准顺序容器，STL还设计了3种容器适配器（container adapter）：队队列列（queue）、优优先先队队列列（priority queue）和栈栈（stack）。容器适配器可以将顺序容器转换为另一种容器，也就是以顺序容器为基础，将其转换为新的容器。转换后的新容器将具有新的特殊操作要求。表表10-4 10-4 容器适配器容器适配器容器类名特性何时使用头文件queue（队列）在一端插入元素，在另一端取出元素，具有先进先出（first in,first out,FIFO）的特性，插入和删除都较快。需要一个FIFO结构时使用队列。priority q

41、ueue（优先队列）每个元素都有一个优先级，元素按优先级的顺序从队列中删除，如果优先级相同，则仍然遵循先进先出规则。插入和删除都比一般的简单队列慢，因为必须对元素重新调整顺序，以支持按优先级排序。需要一个带优先级的FIFO结构时使用优先队列。stack（栈）在一端插入元素，在同一端删除元素，具有先进后出（first in,last out,FILO）的特性。需要一个FILO结构时使用栈。C+语语言言程程序序设设计计教教程程第第10章章类类模模板板10.3.3 顺序容器123456789101112131415161718192021/*程序名：p10_4.cpp *功 能：队列容器示例程序 *

42、/#include#includeusing namespace std;templatevoid print(queue&q)if(q.empty()/判断队列是否空 coutQueue is empty!endl;else int j=q.size();for(int i=0;ij;i+)coutq.front();q.pop();/出队列 coutendl;2.链表类模板链表类模板C+语语言言程程序序设设计计教教程程第第10章章类类模模板板242526272829303132333435363738int main()queue q;/创建队列 q.push(1);/进队列 q.push

43、(2);q.push(3);q.push(4);/取队头元素 coutThe first element is:q.front()endl;/取队尾元素 coutThe last element is:q.back()endl;coutThe queue is:endl;print(q);return 0;运行结果运行结果:The first element is:1The last element is:4The queue is:1 2 3 4C+语语言言程程序序设设计计教教程程第第10章章类类模模板板10.3.3 顺序容器 容器适配器容器适配器也是带有类型参数的STL类模板。从技术上看，

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

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

46、atevoid print(T&q)while(!q.empty()coutq.front();q.pop();/出队列 coutendl;2.链表类模板链表类模板C+语语言言程程序序设设计计教教程程第第10章章类类模模板板2021222324252627282930int main()queue int,list list_q;/容器适配器转换顺序容器 for(int i=1;i=4;i+)list_q.push(i);coutThe first element is:list_q.front()endl;coutThe last element is:list_q.back()endl;c

47、outThe queue is:endl;print(list_q);return 0;运行结果运行结果:The first element is:1The last element is:4The queue is:1 2 3 4C+语语言言程程序序设设计计教教程程第第10章章类类模模板板10.3.3 顺序容器 stack（栈）（栈）是一种经典数据结构，它要求数据元素具有FILO（first in,last out）的特性，因此要转换为stack的顺序容器必须支持push_back（在容器后端添加元素），又支持pop_back（在容器后端删除元素），而顺序容器中vector、deque和li

48、st都符合这个条件，因此，它们都可以通过容器适配器转换为stack。【例10-7】容器适配器stack的示例程序1234567891011121314151617/*程序名：程序名：p10_7.cpp *功功 能：容器适配器能：容器适配器stack示例示例 */#include#include#includeusing namespace std;templatevoid output(T&stackdata)while(!stackdata.empty()coutstackdata.top();/取栈顶元素取栈顶元素 stackdata.pop();/出栈出栈 coutendl;2.链表类模

49、板链表类模板C+语语言言程程序序设设计计教教程程第第10章章类类模模板板2021222324252627282930313233int main()stack int_s;/创建栈 stack int,vector 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;运行结果运行结果:Pop from int stack:3 2

50、1 0Pop from vec_stack:3 2 1 0C+语语言言程程序序设设计计教教程程第第10章章类类模模板板10.4 关联容器 与顺序容器中的对象不同，关联容器关联容器（associate container）中的数据元素不存储在顺序的线性数据结构中，相反，它们提供了一个关键字（关键字（key）到值的关联）到值的关联映射映射。当插入数据元素到关联容器中时，各数据元素之间并不以插入的先后或位置作为顺序，而是依据数据元素的关键字按照某一顺序某一顺序进行排列。如果是数字则依照数字大小进行排列；如果是字符串则按英文字母的顺序排列。STL提供了4个关联容器：set、multiset、map和m