STL入门基础(全)-ppt课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《STL入门基础(全)-ppt课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- STL 入门 基础 ppt 课件
- 资源描述:
-
1、C+模板与STL库介绍(参考北京大学单栋栋课件)1ppt课件提纲o 1. 概论o 2. 模板机制的介绍o 3. STL中的基本概念o 4. 容器概述o 5. 迭代器o 6. 算法简介ppt课件概论o C+ 语言的核心优势之一就是便于软件的重用o C+中有两个方面体现重用:n 1. 面向对象的思想:继承和多态,标准类库n 2. 泛型程序设计(generic programming) 的思想:模板机制,以及标准模板库 STL这次课的重点这次课的重点ppt课件泛型程序设计o 泛型程序设计,简单地说就是使用模板的程序设计法。n将一些常用的数据结构(比如链表,数组,二叉树)和算法(比如排序,查找)写成模
2、板,以后则不论数据结构里放的是什么对象,算法针对什么样的对象,则都不必重新实现数据结构,重新编写算法。o 标准模板库 (Standard Template Library) 就是一些常用数据结构和算法的模板的集合。主要由 Alex Stepanov 开发,于1998年被添加进C+标准o 有了STL,不必再从头写大多的标准数据结构和算法,并且可获得非常高的性能。ppt课件模板引子1.假如设计一个求两参数最大值的函数,在实践中我们可能需要定义四个函数:int max ( int a , int b ) return ( a b ) ? a , b ; long max ( long a , lon
3、g b ) return ( a b ) ? a , b ;double max ( double a , double b ) return ( a b)? a , b ; char max ( char a , char b ) return ( a b ) ? a , b ;2.这些函数几乎相同,唯一的区别就是形参类型不同3.需要事先知道有哪些类型会使用这些函数,对于未知类型这些函数不起作用ppt课件模板的概念1. 所谓模板是一种使用无类型参数来产生一系列函数或类的机制。2. 若一个程序的功能是对某种特定的数据类型进行处理,则可以将所处理的数据类型说明为参数,以便在其他数据类型的情况下使
4、用,这就是模板的由来。3. 模板是以一种完全通用的方法来设计函数或类而不必预先说明将被使用的每个对象的类型。4. 通过模板可以产生类或函数的集合,使它们操作不同的数据类型,从而避免需要为每一种数据类型产生一个单独的类或函数。 ppt课件模板分类o 函数模板(function template)n 是独立于类型的函数n 可产生函数的特定版本o 类模板(class template)n 跟类相关的模板,如vectorn 可产生类对特定类型的版本,如vector7ppt课件求最大值模板函数实现1.求两个数最大值,使用模板template T max(T a , T b)return ( a b )
5、? a , b;2.template (模板函数形参表) /函数定义体8ppt课件模板工作方式o 函数模板只是说明,不能直接执行,需要实例化为模板函数后才能执行o 在说明了一个函数模板后,当编译系统发现有一个对应的函数调用时,将根据实参中的类型来确认是否匹配函数模板中对应的形参,然后生成一个重载函数。该重载函数的定义体与函数模板的函数定义体相同,它称之为模板函数9ppt课件#include template T min(T a,int n)int i;T minv=a0;for( i = 1;i ai) minv=ai;return minv;编写一个对具有n个元素的数组a 求最小值的程序,要
6、求将求最小值的函数设计成函数模板。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; 此程序的运行结果为:a数组的最小值为:0b数组的最小值为:-3.4ppt课件模板优缺点o 函数模板方法克服了C语言解决上述问题时用大量不同函数名表示相似功能的坏习惯o 克服了宏定义不能进行参数类型检查的弊端o 克服了C+函数重载用相同函数名字重写几个函数的繁琐o 缺点,调试比较困难n 一般先写一个特殊版本的函数n
7、运行正确后,改成模板函数11ppt课件STL中的几个基本概念o 容器:可容纳各种数据类型的数据结构。o 迭代器:可依次存取容器中元素的东西o 算法:用来操作容器中的元素的函数模板。例如,STL用sort()来对一个vector中的数据进行排序,用find()来搜索一个list中的对象。n函数本身与他们操作的数据的结构和类型无关,因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。o 比如,数组int array100就是个容器,而 int * 类型的指针变量就可以作为迭代器,可以为这个容器编写一个排序的算法ppt课件容器概述o可以用于存放各种类型的数据(基本类型的变量,对象等)的数据结
8、构。o容器分为三大类:1) 顺序容器 vector:后部插入/删除,直接访问deque:前/后部插入/删除,直接访问list:双向链表,任意位置插入/删除 2)关联容器set:快速查找,无重复元素multiset :快速查找,可有重复元素map:一对一映射,无重复元素,基于关键字查找multimap :一对一映射,可有重复元素,基于关键字查找前2者合称为第一类容器 3)容器适配器stack:LIFOqueue:FIFOpriority_queue:优先级高的元素先出 ppt课件容器概述o 对象被插入容器中时,被插入的是对象的一个复制品。o 许多算法,比如排序,查找,要求对容器中的元素进行比较,
9、所以,放入容器的对象所属的类,还应该实现 = 和 运算符。ppt课件顺序容器简介1) vector 头文件 实际上就是个动态数组。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。 2) deque 头文件 也是个动态数组,随机存取任何元素都能在常数时间完成(但性能次于vector)。在两端增删元素具有较佳的性能。 3) list 头文件 双向链表,在任何位置增删元素都能在常数时间完成。不支持随机存取。 上述三种容器称为顺序容器,是因为元素的插入位置同元素的值无关,只跟插入的时机有关。ppt课件关联容器简介o 关联式容器内的元素是排序的,插入任何元素,都按相应的排序准则来确定其
10、位置。关联式容器的特点是在查找时具有非常好的性能。1) set/multiset: 头文件 set 即集合。set中不允许相同元素,multiset中允许存在相同的元素。2) map/multimap: 头文件 map与set的不同在于map中存放的是成对的key/value。 并根据key对元素进行排序,可快速地根据key来检索元素 map同multimap的不同在于是否允许多个元素有相同的key值。 上述4种容器通常以平衡二叉树方式实现,插入、查找和删除的时间都是 O(logN)ppt课件容器适配器简介1) stack :头文件 栈。是项的有限序列,并满足序列中被删除、检索和修改的项只能是
11、最近插入序列的项。即按照后进先出的原则2) queue :头文件 队列。插入只可以在尾部进行,删除、检索和修改只允许从头部进行。按照先进先出的原则。3)priority_queue :头文件 优先级队列。最高优先级元素总是第一个出列ppt课件容器的共有成员函数1) 所有标准库容器共有的成员函数:n 相当于按词典顺序比较两个容器大小的运算符: =, , , =, = , !=n empty : 判断容器中是否有元素n max_size: 容器中最多能装多少元素n size: 容器中元素个数n swap: 交换两个容器的内容ppt课件比较两个容器的例子19比较两个容器的例子:比较两个容器的例子:#
12、include #include int main()std:vector v1;std:vector v2;v1.push_back (5); v1.push_back (1);v2.push_back (1); v2.push_back (2);v2.push_back (3);std:cout (v1 v2); return 0;若两容器长度相同、所有元素相等,则两个容器就相等,否则为不等。若两容器长度不同,但较短容器中所有元素都等于较长容器中对应的元素,则较短容器小于另一个容器若两个容器均不是对方的子序列,则取决于所比较的第一个不等的元素输出:输出:0ppt课件容器的成员函数 2) 只
13、在第一类容器中的函数:begin 返回指向容器中第一个元素的迭代器end 返回指向容器中最后一个元素后面的位置的迭代器rbegin 返回指向容器中最后一个元素的迭代器rend 返回指向容器中第一个元素前面的位置的迭代器erase 从容器中删除一个或几个元素clear 从容器中删除所有元素HeadTailbeginrbeginrendendppt课件迭代器o 用于指向第一类容器中的元素。有const 和非 const两种。o 通过迭代器可以读取它指向的元素,通过非const迭代器还能修改其指向的元素。迭代器用法和指针类似。o 定义一个容器类的迭代器的方法可以是:容器类名:iterator 变量名
14、;或:容器类名:const_iterator 变量名;o 访问一个迭代器指向的元素:* 迭代器变量名ppt课件迭代器o 迭代器上可以执行 + 操作, 以指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面,则迭代器变成past-the-end值。o 使用一个past-the-end值的迭代器来访问对象是非法的,就好像使用NULL或未初始化的指针一样。ppt课件例如:#include #include using namespace std;int main() vector v; /一个存放int元素的向量,一开始里面没有元素v.push_back(1);v.push_back(
15、2); v.push_back(3); v.push_back(4);vector:const_iterator i; /常量迭代器for( i = v.begin();i != v.end();i + ) cout * i ,;cout endl;ppt课件vector:reverse_iterator r; /反向迭代器for( r = v.rbegin();r != v.rend();r+ ) cout * r ,;cout endl;vector:iterator j; /非常量迭代器for( j = v.begin();j != v.end();j + ) * j = 100;for
16、( i = v.begin();i != v.end();i+ ) cout * i ,;输出结果:1,2,3,4,4,3,2,1,100,100,100,100,ppt课件迭代器o 不同容器上支持的迭代器功能强弱有所不同。o 容器的迭代器的功能强弱,决定了该容器是否支持STL中的某种算法。n 例1:只有第一类容器能用迭代器遍历。n 例2:排序算法需要通过随机迭代器来访问容器中的元素,那么有的容器就不支持排序算法。ppt课件STL 中的迭代器o STL 中的迭代器按功能由弱到强分为5种: 1. 输入:Input iterators 提供对数据的只读访问。 1. 输出:Output iterat
17、ors 提供对数据的只写访问 2. 正向:Forward iterators 提供读写操作,并能一次一个地向前推进迭代器。 3. 双向:Bidirectional iterators提供读写操作,并能一次一个地向前和向后移动。 4. 随机访问:Random access iterators提供读写操作,并能在数据中随机移动。o 编号大的迭代器拥有编号小的迭代器的所有功能,能当作编号小的迭代器使用。ppt课件不同迭代器所能进行的操作(功能)o 所有迭代器: +p, p +o 输入迭代器: * p, p = p1, p = p1 , p!= p1o 输出迭代器: * p, p = p1o 正向迭代
18、器: 上面全部o 双向迭代器: 上面全部,-p, p -,o 随机访问迭代器: 上面全部,以及:n p+= i, p -= i, n p + i: 返回指向 p 后面的第i个元素的迭代器n p - i: 返回指向 p 前面的第i个元素的迭代器n pi: p 后面的第i个元素的引用n p p1, p p1, p= p1ppt课件容器所支持的迭代器类别容器迭代器类别vector随机deque随机list 双向set/multiset双向map/multimap双向stack不支持迭代器queue不支持迭代器priority_queue不支持迭代器ppt课件例如,vector的迭代器是随机迭代器,所
19、以遍历 vector 可以有以下几种做法:vector v(100);int i; for(i = 0;i v.size() ; i +)cout vi;vector: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; ppt课件而 list 的迭代器是双向迭代器,所以以下代码可以:list v;list:const_iterator ii;for( ii = v.begin()
20、; ii ! 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; /双向迭代器不支持 ppt课件算法简介o STL中提供能在各种容器中通用的算法,比如插入,删除,查找,排序等。大约有70种标准算法。n 算法就是一个个函数模板。n 算法通过迭代器来操纵容器中的元素。许多算法需要两个参数,一个是起始元素的迭代器,一个是终止元素的后面一个元素的迭代器。比如,排序和查找n 有的算法返回一个迭代
21、器。比如 find() 算法,在容器中查找一个元素,并返回一个指向该元素的迭代器。n 算法可以处理容器,也可以处理C语言的数组ppt课件算法分类o 变化序列算法n copy ,remove,fill,replace,random_shuffle,swap, .n 会改变容器o 非变化序列算法:n adjacent-find, equal, mismatch,find ,count, search, count_if, for_each, search_no 以上函数模板都在 中定义o 此外还有其他算法,比如中的算法ppt课件算法示例:find()templateInIt find(InIt f
22、irst, InIt last, const T& val); o first 和 last 这两个参数都是容器的迭代器,它们给出了容器中的查找区间起点和终点。n 这个区间是个左闭右开的区间,即区间的起点是位于查找范围之中的,而终点不是o val参数是要查找的元素的值o 函数返回值是一个迭代器。如果找到,则该迭代器指向被找到的元素。如果找不到,则该迭代器指向查找区间终点。ppt课件#include #include #include using namespace std;int main() int array10 = 10,20,30,40;vector v;v.push_back(1);
展开阅读全文