C++模板&STL库教程.ppt
《C++模板&STL库教程.ppt》由会员分享,可在线阅读,更多相关《C++模板&STL库教程.ppt(92页珍藏版)》请在三一办公上搜索。
1、C+模板与STL库介绍,第8章,提纲,1.概论2.模板机制的介绍3.STL中的基本概念4.容器概述5.迭代器6.算法简介,概论,C+语言的核心优势之一就是便于软件的重用C+中有两个方面体现重用:1.面向对象的思想:继承和多态,标准类库2.泛型程序设计(generic programming)的思想:模板机制,以及标准模板库 STL,这次课的重点,泛型程序设计,泛型程序设计,简单地说就是使用模板的程序设计法。将一些常用的数据结构(比如链表,数组,二叉树)和算法(比如排序,查找)写成模板,以后则不论数据结构里放的是什么对象,算法针对什么样的对象,则都不必重新实现数据结构,重新编写算法。标准模板库(
2、Standard Template Library)就是一些常用数据结构和算法的模板的集合。主要由 Alex Stepanov 开发,于1998年被添加进C+标准有了STL,不必再从头写大多的标准数据结构和算法,并且可获得非常高的性能。,模板引子,1.假如设计一个求两参数最大值的函数,在实践中我们可能需要定义四个函数:int max(int a,int b)return(a b)?a,b;long max(long a,long b)return(a b)?a,b;double max(double a,double b)return(a b)?a,b;char max(char a,char
3、 b)return(a b)?a,b;2.这些函数几乎相同,唯一的区别就是形参类型不同3.需要事先知道有哪些类型会使用这些函数,对于未知类型这些函数不起作用,int abs(int a)return a0?-a:a;double abs(double a)return a0?-a:a;,数据为int或double时的求绝对值问题,class Square1 public:Square1(int y):x(y)int fun()return x*x;private:int x;,用类实现求一个数的平方,class Square2 public:Square(double y):x(y)doubl
4、e fun()return x*x;private:double x;,样例:求最大值模板函数实现,1.求两个数最大值,使用模板template T max(T a,T b)return(a b)?a,b;2.template/模板声明格式(模板函数形参表)/函数定义体,8,模板的概念,所谓模板是一种使用无类型参数来产生一系列函数或类的机制。若一个程序的功能是对某种特定的数据类型进行处理,则可以将所处理的数据类型说明为参数,以便在其他数据类型的情况下使用,这就是模板的由来。模板是以一种完全通用的方法来设计函数或类而不必预先说明将被使用的每个对象的类型。通过模板可以产生类或函数的集合,使它们操作
5、不同的数据类型,从而避免需要为每一种数据类型产生一个单独的类或函数。,注意:,模板并非通常意义上可直接使用的函数或类,它仅仅是对一族函数或类的描述,是参数化的函数和类。模板是一种使用无类型参数来产生一族函数或类的机制。,模板分类,函数模板(function template)是独立于类型的函数可产生函数的特定版本类模板(class template)跟类相关的模板,如vector可产生类对特定类型的版本,如vector,11,模板工作方式,函数模板只是说明,不能直接执行,需要实例化为模板函数后才能执行在说明了一个函数模板后,当编译系统发现有一个对应的函数调用时,将根据实参中的类型来确认是否匹配
6、函数模板中对应的形参,然后生成一个重载函数。该重载函数的定义体与函数模板的函数定义体相同,它称之为模板函数,12,#include template T min(T a,T1 n)int i;T minv=a0;for(i=1;i ai)minv=ai;return minv;,编写一个对具有n个元素的数组a 求最小值的程序,要求将求最小值的函数设计成函数模板。,void main()ina a=1,3,0,2,7,6,4,5,2;double b=1.2,-3.4,6.8,9,8;cout”a数组的最小值为:”min(a,9)endl;cout”b数组的最小值为:”min(b,4)endl;
7、此程序的运行结果为:a数组的最小值为:0b数组的最小值为:-3.4,2、模板的实例化,模板通过参数实例化可以构建具体的函数或类,称为模板函数和模板类。,模板实例化示意图,模 板函数模板 类模板,模 板 类,模板函数,对 象,实例化,实例化,实例化,1.函数模板的定义,定义格式如下:,8.2 函数模板,函数模板只是一种说明,并不是一个具体的函数,C+编译系统不会产生任何可执行代码。当遇到具体的函数调用时,才根据调用处的具体参数类型,在参数实例化以后才生成相应的代码,此时的代码称为模板函数。,2.函数模板的使用,函数模板的实例化是在编译按系统处理函数调用时由系统自动完成。在调用函数模板时,系统首先
8、确定模板参数所对应的具体类型,并依据该类型生成一个具体函数,系统实际上是调用了这个具有确定参数类型的函数。模板函数是函数模板的一个具体实例,是模板参数实例化后的一个可执行的具体函数,只处理一种确定的数据类型。,3.模板函数的生成,#include template void myfunc(Type1 x,Type2 y)cout x y n;int main()myfunc(10,hi);myfunc(0.23,10L);return 0;,#include templateT max(T a,T b)return(ab)?a:b;templateT max(T a,T b,T c)T t;t
9、=(ab)?a:b;return(tc)?t:c;char*max(char*a,char*b)return(strcmp(a,b)0)?a:b;,#include main()int x=10,y=20,max1;double a=10.4,b=21.3,c=13.4,max2;max1=max(x,y);max2=max(a,b,c);coutThe maxinum of x and y is:max1endl;coutThe maxinum of a and b and c is:max2endl;char*c1,*c2,*c3;c1=aaaa;c2=bbbb;c3=max(c1,c2)
10、;coutThe maxinum of c1 and c2 is:c3endl;return 0;,8.3 类模板,如同函数模板一样,类模板是参数化的类,即用于实现数据类型参数化的类。应用类模板可以使类中的数据成员、成员函数的参数及成员函数的返回值,能根据模板参数匹配情况取任意数据类型。,1.类模板的定义,template class 类模板名 成员的声明;,定义格式如下:,模板类的成员函数必须是函数模板。类模板中的成员函数的定义,若放在类模板的定义之中,则与类的成员函数的定义方法相同;若在类模板之外定义,则成员函数的定义格式如下:,类模板成员函数的定义,template返回值类型 类模板名:
11、成员函数名(参数表)成员函数体,当类模板在程序中被引用时,系统根据引用处的参数匹配情况将类模板中的模板参数置换为确定的参数类型,生成一个具体的类。这种由类模板实例化生成的类称为模板类。类模板必须先实例化为相应的模板类,并定义该模板类的对象以后才可以使用。,2.类模板的使用,类模板实例化=模板类的格式如下:,类模板实例化,类模板名;,Square inta(15);,定义模板类的对象的格式,类模板名 对象名(实参表);,举 例,例8-4 类模板的应用例8-5 含有成员函数的类模板定义,模板优缺点,函数模板方法克服了C语言解决上述问题时用大量不同函数名表示相似功能的坏习惯克服了宏定义不能进行参数类
12、型检查的弊端克服了C+函数重载用相同函数名字重写几个函数的繁琐缺点,调试比较困难一般先写一个特殊版本的函数运行正确后,改成模板函数,28,STL中的几个基本概念,容器:可容纳各种数据类型的数据结构。迭代器:可依次存取容器中元素的东西算法:用来操作容器中的元素的函数模板。例如,STL用sort()来对一个vector中的数据进行排序,用find()来搜索一个list中的对象。函数本身与他们操作的数据的结构和类型无关,因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。比如,数组int array100就是个容器,而 int*类型的指针变量就可以作为迭代器,可以为这个容器编写一个排序的算法
13、,容器概述,可以用于存放各种类型的数据(基本类型的变量,对象等)的数据结构。容器分为三大类:1)顺序容器 vector:后部插入/删除,直接访问deque:前/后部插入/删除,直接访问list:双向链表,任意位置插入/删除2)关联容器set:快速查找,无重复元素multiset:快速查找,可有重复元素map:一对一映射,无重复元素,基于关键字查找multimap:一对一映射,可有重复元素,基于关键字查找前2者合称为第一类容器 3)容器适配器stack:LIFOqueue:FIFOpriority_queue:优先级高的元素先出,容器概述,对象被插入容器中时,被插入的是对象的一个复制品。许多算法
14、,比如排序,查找,要求对容器中的元素进行比较,所以,放入容器的对象所属的类,还应该实现=和 运算符。,顺序容器简介,1)vector 头文件 实际上就是个动态数组。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。2)deque 头文件 也是个动态数组,随机存取任何元素都能在常数时间完成(但性能次于vector)。在两端增删元素具有较佳的性能。3)list 头文件 双向链表,在任何位置增删元素都能在常数时间完成。不支持随机存取。上述三种容器称为顺序容器,是因为元素的插入位置同元素的值无关。,关联容器简介,关联式容器内的元素是排序的,插入任何元素,都按相应的排序准则来确定其位置。
15、关联式容器的特点是在查找时具有非常好的性能。1)set/multiset:头文件 set 即集合。set中不允许相同元素,multiset中允许存在相同的元素。2)map/multimap:头文件 map与set的不同在于map中存放的是成对的key/value。并根据key对元素进行排序,可快速地根据key来检索元素 map同multimap的不同在于是否允许多个元素有相同的key值。上述4种容器通常以平衡二叉树方式实现,插入和检索的时间都是 O(logN),容器适配器简介,1)stack:头文件 栈。是项的有限序列,并满足序列中被删除、检索和修改的项只能是最近插入序列的项。即按照后进先出的
16、原则2)queue:头文件 队列。插入只可以在尾部进行,删除、检索和修改只允许从头部进行。按照先进先出的原则。3)priority_queue:头文件 优先级队列。最高优先级元素总是第一个出列,容器的共有成员函数,1)所有标准库容器共有的成员函数:相当于按词典顺序比较两个容器大小的运算符:=,=,=,!=empty:判断容器中是否有元素max_size:容器中最多能装多少元素size:容器中元素个数swap:交换两个容器的内容,比较两个容器的例子,36,比较两个容器的例子:#include#include int main()std:vector v1;std:vector v2;v1.pus
17、h_back(5);v1.push_back(1);v2.push_back(1);v2.push_back(2);v2.push_back(3);std:cout(v1 v2);return 0;,若两容器长度相同、所有元素相等,则两个容器就相等,否则为不等。若两容器长度不同,但较短容器中所有元素都等于较长容器中对应的元素,则较短容器小于另一个容器若两个容器均不是对方的子序列,则取决于所比较的第一个不等的元素,输出:0,容器的成员函数,2)只在第一类容器中的函数:begin 返回指向容器中第一个元素的迭代器end 返回指向容器中最后一个元素后面的位置的迭代器rbegin 返回指向容器中最后一
18、个元素的迭代器rend 返回指向容器中第一个元素前面的位置的迭代器erase 从容器中删除一个或几个元素clear 从容器中删除所有元素,Head,Tail,begin,rbegin,rend,end,迭代器,用于指向第一类容器中的元素。有const 和非 const两种。通过迭代器可以读取它指向的元素,通过非const迭代器还能修改其指向的元素。迭代器用法和指针类似。定义一个容器类的迭代器的方法可以是:容器类名:iterator 变量名;或:容器类名:const_iterator 变量名;访问一个迭代器指向的元素:*迭代器变量名,迭代器,迭代器上可以执行+操作,以指向容器中的下一个元素。如果
19、迭代器到达了容器中的最后一个元素的后面,则迭代器变成past-the-end值。使用一个past-the-end值的迭代器来访问对象是非法的,就好像使用NULL或未初始化的指针一样。,例如:#include#include using namespace std;int main()vector v;/一个存放int元素的向量,一开始里面没有元素v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);vector:const_iterator i;/常量迭代器for(i=v.begin();i!=v.end();i+)cout*i
20、,;cout endl;,vector:reverse_iterator r;/反向迭代器for(r=v.rbegin();r!=v.rend();r+)cout:iterator j;/非常量迭代器for(j=v.begin();j!=v.end();j+)*j=100;for(i=v.begin();i!=v.end();i+)cout*i,;输出结果:1,2,3,4,4,3,2,1,100,100,100,100,迭代器,不同容器上支持的迭代器功能强弱有所不同。容器的迭代器的功能强弱,决定了该容器是否支持STL中的某种算法。例1:只有第一类容器能用迭代器遍历。例2:排序算法需要通过随机迭
21、代器来访问容器中的元素,那么有的容器就不支持排序算法。,STL 中的迭代器,STL 中的迭代器按功能由弱到强分为5种:1.输入:Input iterators 提供对数据的只读访问。1.输出:Output iterators 提供对数据的只写访问 2.正向:Forward iterators 提供读写操作,并能一次一个地向前推进迭代器。3.双向:Bidirectional iterators提供读写操作,并能一次一个地向前和向后移动。4.随机访问:Random access iterators提供读写操作,并能在数据中随机移动。编号大的迭代器拥有编号小的迭代器的所有功能,能当作编号小的迭代器使
22、用。,不同迭代器所能进行的操作(功能),所有迭代器:+p,p+输入迭代器:*p,p 1=p,p=p1,p!=p1输出迭代器:*p,p=p1正向迭代器:上面全部双向迭代器:上面全部,-p,p-,随机访问迭代器:上面全部,以及:p+=i,p-=i,p+i:返回指向 p 后面的第i个元素的迭代器p-i:返回指向 p 前面的第i个元素的迭代器pi:p 后面的第i个元素的引用p p1,p=p1,容器所支持的迭代器类别,容器迭代器类别vector随机deque随机list 双向set/multiset双向map/multimap双向stack不支持迭代器queue不支持迭代器priority_queue不
23、支持迭代器,例如,vector的迭代器是随机迭代器,所以遍历 vector 可以有以下几种做法:vector v(100);vector:value_type i;/等效于写 int i;(P687)for(i=0;i:const_iterator ii;for(ii=v.begin();ii!=v.end();ii+)cout*ii;/间隔一个输出:ii=v.begin();while(ii v.end()cout*ii;ii=ii+2;,而 list 的迭代器是双向迭代器,所以以下代码可以:list v;list:const_iterator ii;for(ii=v.begin();ii!
24、v.end();ii+)cout*ii;以下代码则不行:for(ii=v.begin();ii v.end();ii+)cout*ii;/双向迭代器不支持 for(int i=0;i v.size();i+)cout vi;/双向迭代器不支持,算法简介,STL中提供能在各种容器中通用的算法,比如插入,删除,查找,排序等。大约有70种标准算法。算法就是一个个函数模板。算法通过迭代器来操纵容器中的元素。许多算法需要两个参数,一个是起始元素的迭代器,一个是终止元素的后面一个元素的迭代器。比如,排序和查找有的算法返回一个迭代器。比如 find()算法,在容器中查找一个元素,并返回一个指向该元素的迭代器



- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- C+ 模板 STL 教程

链接地址:https://www.31ppt.com/p-6153968.html