资源预览内容
第1页 / 共26页
第2页 / 共26页
第3页 / 共26页
第4页 / 共26页
第5页 / 共26页
第6页 / 共26页
第7页 / 共26页
第8页 / 共26页
第9页 / 共26页
第10页 / 共26页
亲,该文档总共26页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
第十章 C+标准模板库 清华大学 郑 莉 C+语言程序设计 1 C+语言程序设计清华大学 郑莉 主要内容 l泛型程序设计 l与标准模板库有关的概念和术语 lC+标准模板库中的容器 l迭代器 l标准C+库中的算法 l函数对象 2 C+语言程序设计清华大学 郑莉 泛型程序设计 l将程序写得尽可能通用 l将算法从特定的数据结构中抽象出来, 成为通用的 lC+的模板为泛型程序设计奠定了关键 的基础 lSTL是泛型程序设计的一个范例 容器(container) 迭代器(iterator) 算法(algorithms) 函数对象(function object) 3 C+语言程序设计清华大学 郑莉 命名空间(Namespace) l一个命名空间将不同的标识符集合在一 个命名作用域(named scope)内 为了解决命名冲突 例如,声明一个命名空间NS: namspace NS class File; void Fun (); 则引用标识符的方式如下, NS: File obj; NS: Fun (); l没有声明命名空间的标识符都处于无名 的命名空间中 概念和术语 4 C+语言程序设计清华大学 郑莉 命名空间(Namespace) l可以用using来指定命名空间 例如,经过以下声明: using NS:File; 在当前作用域中就可以直接引用File using namespace std; 命名空间std中所有标识符都可直接 引用 l在新的C+标准程序库中,所有标 识符都声明在命名空间std中,头文件 都不使用扩展名 概念和术语 5 C+语言程序设计清华大学 郑莉 容器 l容器类是容纳、包含一组元素或元 素集合的对象。 l异类容器类与同类容器类 l顺序容器与关联容器 l七种基本容器: 向量(vector)、双端队列( deque)、列表(list)、集合(set )、多重集合(multiset)、映射( map)和多重映射(multimap) 概念和术语 6 C+语言程序设计清华大学 郑莉 容器的接口 l通用容器运算符 =,!=,=,=,= l方法(函数) 迭代方法 lbegin(),end(),rbegin(), rend() 访问方法 lsize(),max_size(),swap() ,empty() 7 C+语言程序设计清华大学 郑莉 适配器 l适配器是一种接口类 为已有的类提供新的接口。 目的是简化、约束、使之安全 、隐藏或者改变被修改类提供的服务 集合。 l三种类型的适配器: 容器适配器 l用来扩展7种基本容器,它们 和顺序容器相结合构成栈、队列和优先 队列容器 迭代器适配器 函数对象适配器。 概念和术语 8 C+语言程序设计清华大学 郑莉 迭代器 迭代器是面向对象版本的指针,它 们提供了访问容器、序列中每个元素的 方法。 概念和术语 9 C+语言程序设计清华大学 郑莉 算法 lC+标准模板库中包括70多个算法 其中包括查找算法,排序算法 ,消除算法,记数算法,比较算法, 变换算法,置换算法和容器管理等等 。 l这些算法的一个最重要的特性就是 它们的统一性,并且可以广泛用于不同 的对象和内置的数据类型。 概念和术语 10 C+语言程序设计清华大学 郑莉 顺序容器 l顺序容器的接口 插入方法 lpush_front(),push_back(), insert(),运算符“=” 删除方法 lpop() ,erase(),clear() 迭代访问方法 l使用迭代器 其它顺序容器访问方法(不修改访 问方法) lfront(),back(),下标运算符 容 器 11 C+语言程序设计清华大学 郑莉 顺序容器向量 l向量属于顺序容器,用于容纳不定 长线性序列(即线性群体),提供对序 列的快速随机访问(也称直接访问) l向量是动态结构,它的大小不固定 ,可以在程序运行时增加或减少。 l例10-1 求范围2N中的质数,N在程序 运行时由键盘输入。 容 器 12 /10_1.cpp #include #include #include /包含向量容器头文件 using namespace std ; void main(void) vector A(10); int n; int primecount = 0, i, j; cout n; Aprimecount+ = 2; 1313 for(i = 3; i n; i+) if (primecount = A.size() A.resize(primecount + 10); if (i % 2 = 0) continue; j = 3; while (j i/2) Aprimecount+ = i; for (i = 0; iprimecount; i+)/输出质数 coutsetw(5)Ai; if (i+1) % 10 = 0) /每输出10个数换行一 次 cout endl; coutitem; Link.push_front(item); coutList: ; / 输出链表 1717 list:iterator p=Link.begin(); while(p!=Link.end()/输出各节点数据,直到 链表尾 cout *p ; p+; /使P指向下一个节点 cout endl; cout key; Link.remove(key); cout List: ; / 输出链表 p=Link.begin();/ 使P重新指向表头 while(p!=Link.end() cout *p ; p+; / 使P指向下一个节点 cout endl; 1818 C+语言程序设计清华大学 郑莉 容器适配器 l容器适配器是用来扩展7种基本容器的 l栈容器 使用适配器与一种基础容器相结合来 实现 例10-4:应用标准库中的deque顺序 容器生成一个整数栈stack。 l队列容器 使用适配器与一种基础容器相结合来 实现的先进先出数据结构。 例10-5:应用标准库中的deque顺序 容器生成一个整数标准队列Queue。 容 器 19 C+语言程序设计清华大学 郑莉 什么是迭代器 l迭代器是面向对象版本的指针 指针可以指向内存中的一个地 址 迭代器可以指向容器中的一个 位置 lSTL的每一个容器类模版中,都定 义了一组对应的迭代器类。使用迭代器 ,算法函数可以访问容器中指定位置的 元素,而无需关心元素的具体类型。 迭代器 20 C+语言程序设计清华大学 郑莉 迭代器的类型 l输入迭代器 可以用来从序列中读取数据 l输出迭代器 允许向序列中写入数据 l前向迭代器 既是输入迭代器又是输出迭代器,并且可以 对序列进行单向的遍历 l双向迭代器 与前向迭代器相似,但是在两个方向上都可 以对数据遍历 l随机访问迭代器 也是双向迭代器,但能够在序列中的任意两 个位置之间进行跳转。 迭代器 21 C+语言程序设计清华大学 郑莉 迭代器适配器 l迭代器适配器是用来扩展(或调整)迭代器功 能的类。它本身也被称为迭代器,只是这种迭代器是 通过改变另一个迭代器而得到的 l逆向迭代器 通过重新定义递增运算和递减运算,使其行 为正好倒置 l插入型迭代器 将赋值操作转换为插入操作。通过这种迭代 器,算法可以执行插入行为而不是覆盖行为 l例10-6 应用逆向迭代器和后插迭代器来操作向量容 器中的元素 迭代器 22 C+语言程序设计清华大学 郑莉 迭代器相关的辅助函数 ladvance()函数 将迭代器的位置增加,增加的幅度 由参数决定 lDistance()函数 返回迭代器之间的距离 l函数iter_swap() 交换两个迭代器所指向的元素值 l例10-7 用三个迭代器辅助函数来操作列表 容器中的元素。 迭代器 23 C+语言程序设计清华大学 郑莉 标准C+库中的算法 l算法本身是一种函数模板 l不可变序列算法(Non-mutating algorithms) 不直接修改所操作的容器内容 的算法 l可变序列算法(Mutating algorithms ) 可以修改它们所操作的容器的 元素。 l排序相关算法 l数值算法 算 法 24 C+语言程序设计清华大学 郑莉 算法应用举例 l例10-9 应用不可变序列算法对数据序列进行 分析 l例10-10 以可变序列算法对数据序列进行复制 ,生成,删除,替换,倒序,旋转等可变性 操作。 l例10-11 应用排序相关算法对序列进行各项操 作 l例10-12 应用数值算法对数据序列进行操作 算 法 25 C+语言程序设计清华大学 郑莉 函数对象 l一个行为类似函数的对象,它可以不需 参数,也可以带有若干参数,其功能是获取 一个值,或者改变操作的状态。 l任何普通的函数和任何重载了调用运算 符operator()的类的对象都满足函数对象的特 征 lSTL中也定义了一些标准的函数对象, 如果以功能划分,可以分为算术运算、关系 运算、逻辑运算三大类。为了调用这些标准 函数对象,需要包含头文件。 26
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号