C++电子课件(下)第十一章.ppt
《C++电子课件(下)第十一章.ppt》由会员分享,可在线阅读,更多相关《C++电子课件(下)第十一章.ppt(63页珍藏版)》请在三一办公上搜索。
1、第十一章 标准模板库(选读),库(library)是一系列程序组件的集合,它们可以在不同的程序中重复使用。库函数设计的第一位的要求就是通用性,模板(template)为通用性带来了不可估量的前景。标准模板库(Standard Template Library)是ANSI/ISO C+最有特色、最实用的部分之一。STL包含:容器类(container)迭代子(iterator)算法(algorithm)泛型算法(generic algorithm)和函数对象(function object)的概念与使用使算法摆脱了对不同类型数据个性操作的依赖。,标准模板库的引入:,11.1 标准模板库简介,11
2、.3 顺序容器,11.2 迭代子类,11.6 容器适配器,11.4 泛型算法与函数对象,11.5 关联容器,第十一章 标准模板库(选读),11.1 标准模板库简介,容器类(Container)容器类是管理序列的类,是容纳一组对象或对象集的类。通过由容器类提供的成员函数,可以实现诸如向序列中插入元素,删除元素,查找元素等操作,这些成员函数通过返回迭代子来指定元素在序列中的位置。,容器分为三大类:顺序容器(Sequence Container or Sequential Container)关联容器(Associative Container)容器适配器(Container Adopter)参见表
3、11.1。,11.1 标准模板库简介,顺序容器和关联容器称为第一类容器(first-class container)。,STL也使容器提供类似的接口。许多基本操作是所有容器都适用的,可以用有类似操作的新类来扩展STL。这些函数和运算符可通称为容器的接口。,表11.2 所有标准库容器共有的函数,11.1 标准模板库简介,(2)泛型算法(Generic Algorithm):在模板中算法不依赖于具体的数据类型,而泛型算法更进一步不依赖于具体的容器。泛型算法中采用函数对象(Function Object)引入不同情况下同一算法的差异。它没有使用继承和多态,避免了虚函数的开销,使STL效率更高。,迭代
4、子把算法与容器连接起来。注意算法只是间接通过迭代子操作容器元素,算法本身与容器无关。算法通常返回迭代子。,(3)迭代子(Iterator):迭代子是指针概念的泛型化,它指向容器中的元素,它能象指针一样增减,轮流指示容器中每个元素。所以说迭代子是面向对象版本的指针。迭代子可以包括指针,但迭代子又不仅仅是一个指针。,11.2 迭代子类,迭代子属性:C+标准库中对普通类型迭代子按照基本访问功能分类,有五种四级(输入/输出为同一级)预定义迭代子,其功能最强最灵活的是随机访问迭代子。,表11.3 迭代子属性,表11.4 各种迭代子可执行的操作,【例11.1】寻找数组元素。由本例演示可见,泛型算法不直接访
5、问容器的元素,所以与容器无关。元素的全部访问和遍历都通过迭代子实现,并不需要预知容器类型。,11.3 顺序容器,顺序容器:vector,list和deque。vector类和deque类是以数组为基础的,list类是以双向链表为基础的。,11.3.1 矢量类,列表类,11.3.3 双端队列类,11.3.1 矢量类,矢量类的概念:矢量(vector)类提供了具有连续内存地址的数据结构。它可通过下标运算符 直接有效地访问矢量的任何元素。与数组不同,vector的内存用尽时,vector自动分配更大的连续内存区,将原先的元素复制到新的内存区,并释放旧的内存区。这是矢量类的优点。内存分配由分配子(Al
6、locator)完成。分配子也是类,它运用了new和delete运算符,本教材不作进一步讨论。矢量类的迭代子:每个容器都有自己所支持的迭代子类型,迭代子决定了可采用哪种算法。vector支持随机访问迭代子,具有最强的功能。vector的迭代子通常实现为vector元素的指针。所谓选择容器类,实际上很大部分是选择所支持的迭代子。,11.3.1 矢量类,矢量容器的声明:#includevector vi;/定义存放整形序列的向量容器对象vi,长度为0的空vectorvector vf;/存放实型序列的向量容器vector vch;/存放字符序列的向量容器vectorvstr;/存放字符串序列的向量
7、容器,11.3.1 矢量类,矢量容器的构造函数:vector(size_t n);/构造一个有n个元素的矢量,/每个元素都是由默认的构造函数所建立的vector(size_t n,T/元素的初值由区间first,last)指定的序列中的元素复制而来 vector(vector&X)/复制构造函数这些构造函数还可以显式给出分配子(allocator)对象。,【例11.2】寻找vector容器元素。,对矢量的操作包含了第六章在顺序表中所列出的操作,甚至更丰富。每种操作都是成员函数。对用户自定义的元素类,要重载“=”和“”等比较运算符。,11.3.1 矢量类,特殊类型迭代子:*它们本身也具有五种四级
8、迭代子属性之一反转型迭代子(Reverse Iterator):它是把一切都颠倒过来。正向遍历一个第一类容器时,如果用了反转迭代子,实际上实现的是反向遍历。,begin()和end(),分别返回指向容器首元素和容器的末元素的后继的迭代子;而rbegin()和rend(),分别返回指向容器末元素和容器的首元素的前导的普通迭代子。后一对操作用于支持反转型迭代子。:vector veco;vector:reverse_iterator r_iter;for(r_iter=veco.rbegin();/将r_iter指向到末元素r_iter!=veco.rend();/不等于首元素的前导r_iter+
9、)/实际上是递减/循环体如果需要把升序的序列改为降序的序列时,并不需要真正去逆序一个序列,只要使用反转迭代子就可以了。反转迭代子属性为随机迭代子。,11.3.1 矢量类,插入型迭代子(Insertion Iterator):当用普通输出迭代子来产生一个元素序列时,一旦添加一些元素就得完全重写。例如普通输出迭代子可以把一个矢量a的内容复制到另一个矢量b中,复制可以从矢量b任一元素开始,矢量b对应位置上的元素被覆盖,相当于改写。插入迭代子则可以添加元素,复制时它可以把矢量a插入到矢量b任一位置。同一个copy()算法用不同类型迭代子,结果是不同的。,有三种插入迭代子,属性均为输出迭代子:inser
10、t_iterator用来将新元素插入到一个由迭代子(第二个参数Iter)指定的元素的前面(所谓插在a10之前,即在a9和a10之间添加)。back_insert_iterator用来将新元素添加到类型为Type的容器对象的末端;front_insert_iterator用来将新元素添加到容器的前端(注意:新添加的元素以逆序方式结束于被控序列前端,即最后添加的元素放在最前面)。,11.3.1 矢量类,插入型迭代子使用方法:标准库定义了一组(3个)插入型迭代子适配器函数。它们返回对应的插入迭代子:Inserter(Type&,Iter)它使用容器的insert()插入操作符代替赋值操作符。inse
11、rter()函数要求两个实参:容器本身和它的一个指示起始插入位置的迭代子。标记起始插入位置的迭代子并不是保持不变,而是随每个被插入的元素而递增,这样每个元素就能顺序被插入。注意是“插入”而不是“改写”,back_inserter(Type&)它使用容器的push_back()插入操作代替赋值操作符,将新元素添加到容器对象的末端。实参是容器本身。返回一个back_inserter迭代子。front_inserter(Type&)它使用容器的push_front()插入操作代替赋值操作符,将新元素添加到容器的前端,同样,新添加的元素以逆序方式结束于被控序列前端,即最后添加的元素放在最前面。实参也是
12、容器本身。返回一个front_inserter迭代子。front_inserter不能用于矢量vector,因为vector没有成员函数push_front()。,11.3.1 矢量类,流迭代子(Stream Iterator):包括输入流迭代子(Istream_Iterator)和输出流迭代子(Ostream_Iterator),输入流迭代子类支持在istream、ifstream等输入流类上的迭代子操作。istream_iterator声明方式为:istream_iterator迭代子标识符(istream/Type为已定义了输入操作的类型,实参可以是任意公有派生的/istream的子 类
13、型的对象输出流也有对应的ostream_iterator类支持,其声明方式为:ostream_iterator迭代子标识符(ostream&)/实参同样可以是公有派生子类型对象ostream_iterator迭代子标识符(ostream&,char*)/第二参数为C风格字符串,【例11.3】用istream_iterator从标准输入读入一个整数集到vector中。,11.3.2 列表类,列表类(list)的引入:是由双向链表组成的。它有两个指针域,可以向前也可以向后进行访问,但不能随机访问,即支持的迭代子类型为双向迭代子。列表类不能使用下标运算符。它定义在头文件中。列表类容器也有多种构造函数
14、,与矢量类形式相同。,【例11.4】展示列表类怎样进行链表操作。,在本例中建立了两个已排序好的列表类对象,然后归并。全部用列表类的成员函数。不能使用泛型算法sort()对无序的列表类对象排序,因为sort()要求随机迭代子,list仅支持双向迭代子。,11.3.3 双端队列类,双端队列(Double-Ended Queue)类的引入:双端队列允许在队列的两端进行操作。它以顺序表为基础,所以能利用下标提供有效的索引访问,它支持随机访问迭代子。,使用双端队列,必须包含头文件。双端队列类容器也有多种构造函数,与矢量类或列表类形式相同。,【例11.5】双端队列类与矢量类一样,有一个成员函数insert
15、(),注意不是插入迭代子适配器函数inserter()。本例演示该函数的使用,最后输出字符串:“STL功能强使用方便。”,deque类重载了多个成员函数insert():insert(it,x);/在迭代子it指定元素前插入一个值为x的元素,返回指向新元素的迭代子insert(it,n,x);/在迭代子it指定元素前插入n个值为x的元素insert(it,first,last);/在迭代子it指定元素前插入由区间first,last)指定的序列,11.4 泛型算法与函数对象,算法表现为一系列的函数模板。它们完整定义在STL头文件中。使用者可以用很多方式来特化每一个模板函数,大大提高了它作为通用
16、型程序组件的适用性。这些函数模板使用迭代子作为它的参数和返回值,以此在容器(序列)上进行各种操作。本节进一步讨论算法的通用性。,11.4.1 函数对象,11.4.2 泛型算法,11.4.1 函数对象,函数对象的基本概念:每个泛型算法(Generic Algorithm)的实现都独立于容器类型,它消除了算法对类型的依赖性。在STL的泛型算法中采用“函数对象”(Function Object)来解决该问题。函数对象是一个类,通常它仅有一个成员函数,该函数重载了函数调用操作符(operator())。该操作符封装了应该被实现为一个函数的操作。典型情况下,函数对象被作为实参传递给泛型算法。和“引用”一
17、样,“函数对象”很少独立使用。函数对象亦称拟函数对象(Function_Like Object)和函子(Functor)。,11.4.1 函数对象,【例11.6】求和函数对象的定义和测试。注意函数对象Sum能实例化为有限种类型,如:整型、实型、字符型等等,也能用于string类型,因为string重载了operator+。,函数对象的应用:函数对象主要是作为泛型算法的实参使用,通常用来改变默认的操作,如:sort(vec.begin(),vec.end(),greater();这就是把整数的大于关系函数对象作为实参,得降序排列。如果是字符串,则有:sort(svec.begin(),svec.
18、end(),greater();只要改一下参数就又可用于字符串的排序。greater中所包含的比较算法实际上在内置类型int,字符串类string中定义。由此可见函数对象并没有新东西,只是一个固定格式,用起来更方便。,11.4.1 函数对象,例如,自定义整数类Int,其中重载了比较算法“”运算符:class Intpublic:Int(int ival=0):_val(ival)int operator-()return-_val;/负数符号重载 int operator%(int ival)return _val%ival;/求余符号重载 bool operator(int ival)ret
19、urn _valival;/大于符号重载 bool operator!()return _val=0;/逻辑非符号重载private:int _val;Int类可以作为类型参数传递给函数对象greater(),同时把重载的运算符也传递过去了。,11.4.1 函数对象,以函数对象作为求序列中最小值的函数模板的“数值比较算法”参数:templateconst Type 例中Comp为比较函数对象(类模板),对不同的数据类型,可以产生不同的比较函数,以实现泛型算法。,使用函数对象实现泛型算法:,11.4.1 函数对象,函数对象与函数指针相比较有三个优点:第一,函数指针是间接引用,不能作为内联函数,而
20、函数对象可以,这样速度更快;第二,函数对象可以拥有任意数量的额外数据,用这些数据可以用来缓冲当前数据和结果,提高运行质量,当然多数情况下不一定使用,上例中res就是一个额外数据;第三,编译时对函数对象作类型检查。,函数对象来源:1.标准库预定义的一组算术,关系和逻辑函数对象;2.预定义的一组函数适配器,允许对预定义的函数对象进行特殊化或扩展;3.自定义函数对象。,函数对象的优点:,11.4.1 函数对象,预定义函数对象及其使用方法:使用时要包含头文件:#include 算术函数对象:加法:plus(x,y)/返回x+y,可用于string、复数和浮点数等减法:minus(x,y)/返回x-y,
21、不能用串,可用于复数和浮点数等乘法:multiplies(x,y)/返回x*y,不能用串,可用于复数和浮点数等除法:divides(x,y)/返回x/y,不能用串,可用于复数和浮点数等求余:modulus(x,y)/返回x%y,只能用于整数取反:negate(x)/返回-x,补码,只能用于整数,11.4.1 函数对象,逻辑函数对象:这里Type必须支持逻辑运算,有两个参数。逻辑与:logical_and(x,y)/对应“&”逻辑或:logical_or(x,y)/对应“|”逻辑非:logical_not(x)/对应“!”,关系函数对象:它们的返回值为布尔量,两个参数,第一参数和第二参数相比:等
22、于:equal_to(x,y)/对应x=y不等于:not_equal_to(x,y)/对应x!=y大于:great(x,y)/对应xy大于等于:great_equal(x,y)/对应x=y小于:less(x,y)/对应x(x,y)/对应x=y,11.4.1 函数对象,返回布尔值的函数对象称为谓词(predicate),默认的二进制谓词是小于比较操作符“”,所以默认的排序方式都是升序排列,它采用小于比较形式。,函数适配器特化或扩展一元或二元函数对象:绑定器(Binder):把二元函数对象中的一个参数固定(绑定),使之转为一元函数,C+标准库提供两种预定义的binder适配器:bind1st和bi
23、nd2nd,分别绑定了第一或第二个参数。格式:bind2st(plus(x),3.0)/返回x+3.0取反器(Negator):把函数对象的值翻转的适配器,如原来为小于,用了它后就变成了大于。C+标准库也提供了两种negator适配器:not1和not2。not1用于一元预定义函数对象;not2用于二元预定义函数对象。格式同绑定器。,11.4.2 泛型算法,范型算法分类为:(1)修改容器的算法,即变化序列算法(mutating-sequence algorithm),如copy()、remove()、replace()、swap()等;(2)不修改容器的算法,即非变化序列算法(non-muta
24、ting-sequence algorithm),如count()、find()等;以及数字型算法。,*在泛型算法中有一种习惯用语,不说满足某条件的元素,而讲满足指定二进制谓词规则的元素,因为谓词是返回布尔值的函数对象,满足则返回true,即与满足指定条件是同样意思。,泛型算法函数名后缀:_if表示函数采用的操作是在元素上,而不是对元素的值本身进行操作。如find_if算法表示查找一些值满足函数指定条件的元素,而find查找特定的值。_copy表示算法不仅操作元素的值,而且还把修改的值复制到一个目标范围中。reverser算法颠倒范围中元素的排列顺序,而reverse_copy算法同时把结果复
25、制到目标范围中。其它的后缀从英文意思上立即可以认出其意义。,11.4.2 泛型算法,泛型算法的构造与使用方法:所有泛型算法的前两个实参是一对iterator,通常称为first和last,它们标出要操作的容器或内置数组中的元素范围。元素的范围,包括first,但不包含last的左闭合区间。即:first,last)当first=last成立,则范围为空。对iterator的属性,则要求在每个算法声明中指出,所声明的是最低要求。如find()最低要求为:InputIterator,可以传递更高级别的迭代子。如:ForwardIterator、BidirectonalIterator及Random
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- C+ 电子 课件 第十一
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-6153972.html