《chap10-C++课件-清华大学》由会员分享，可在线阅读，更多相关《chap10-C++课件-清华大学（26页珍藏版）》请在金锄头文库上搜索。
1、第十章C 标准模板库 郑莉董渊张瑞丰编著清华大学出版社 C 语言程序设计 第3版 2 主要内容 泛型程序设计与标准模板库有关的概念和术语C 标准模板库中的容器迭代器标准C 库中的算法函数对象 3 泛型程序设计 将程序写得尽可能通用将算法从特定的数据结构中抽象出来 成为通用的C 的模板为泛型程序设计奠定了关键的基础STL是泛型程序设计的一个范例容器 container 迭代器 iterator 算法 algorithms 函数对象 functionobject 4 命名空间 Namespace 一个命名空间将不同的标识符集合在一个命名作用域 namedscope 内为了解决命名冲突例如 声明一个
2、命名空间NS namspaceNS classFile voidFun 则引用标识符的方式如下 NS Fileobj NS Fun 没有声明命名空间的标识符都处于无名的命名空间中 概念和术语 5 命名空间 Namespace 可以用using来指定命名空间例如 经过以下声明 usingNS File 在当前作用域中就可以直接引用Fileusingnamespacestd 命名空间std中所有标识符都可直接引用在新的C 标准程序库中 所有标识符都声明在命名空间std中 头文件都不使用扩展名 概念和术语 6 容器 容器类是容纳 包含一组元素或元素集合的对象 异类容器类与同类容器类顺序容器与关联容器
3、七种基本容器 向量 vector 双端队列 deque 列表 list 集合 set 多重集合 multiset 映射 map 和多重映射 multimap 概念和术语 7 容器的接口 通用容器运算符 方法 函数 迭代方法begin end rbegin rend 访问方法size max size swap empty 8 适配器 适配器是一种接口类为已有的类提供新的接口 目的是简化 约束 使之安全 隐藏或者改变被修改类提供的服务集合 三种类型的适配器 容器适配器用来扩展7种基本容器 它们和顺序容器相结合构成栈 队列和优先队列容器迭代器适配器函数对象适配器 概念和术语 9 迭代器 迭代器是面
4、向对象版本的指针 它们提供了访问容器 序列中每个元素的方法 概念和术语 10 算法 C 标准模板库中包括70多个算法其中包括查找算法 排序算法 消除算法 记数算法 比较算法 变换算法 置换算法和容器管理等等 这些算法的一个最重要的特性就是它们的统一性 并且可以广泛用于不同的对象和内置的数据类型 概念和术语 11 顺序容器 顺序容器的接口插入方法push front push back insert 运算符 删除方法pop erase clear 迭代访问方法使用迭代器其它顺序容器访问方法 不修改访问方法 front back 下标 运算符 容器 12 顺序容器 向量 向量属于顺序容器 用于容纳
5、不定长线性序列 即线性群体 提供对序列的快速随机访问 也称直接访问 向量是动态结构 它的大小不固定 可以在程序运行时增加或减少 例10 1求范围2 N中的质数 N在程序运行时由键盘输入 容器 10 1 cpp include include include 包含向量容器头文件usingnamespacestd intmain vectorA 10 intn intprimecount 0 i j cout 2asupperlimit cin n A primecount 2 13 for i 3 ii 2 A primecount i for i 0 i primecount i 输出质数 c
6、out setw 5 A i if i 1 10 0 每输出10个数换行一次cout endl cout endl 14 15 顺序容器 双端队列 双端队列是一种放松了访问权限的队列 元素可以从队列的两端入队和出队 也支持通过下标操作符 进行直接访问 例10 2使用双端队列容器保存双精度数值序列 容器 16 顺序容器 列表 列表主要用于存放双向链表 可以从任意一端开始遍历 列表还提供了拼接 splicing 操作 将一个序列中的元素从插入到另一个序列中 例10 3改写例9 7从键盘输入10个整数 用这些整数值作为结点数据 生成一个链表 按顺序输出链表中结点的数值 然后从键盘输入一个待查找整数
7、在链表中查找该整数 若找到则删除该整数所在的结点 如果出现多次 全部删除 然后输出删除结点以后的链表 在程序结束之前清空链表 容器 10 3 cpp include includeusingnamespacestd intmain listLink 构造一个列表用于存放整数链表inti key item for i 0 i item Link push front item cout List 输出链表 17 list iteratorp Link begin while p Link end 输出各节点数据 直到链表尾 cout key Link remove key cout List 输
8、出链表p Link begin 使P重新指向表头while p Link end cout p p 使P指向下一个节点 cout endl 18 19 容器适配器 容器适配器是用来扩展7种基本容器的栈容器使用适配器与一种基础容器相结合来实现例10 4 应用标准库中的deque顺序容器生成一个整数栈stack 队列容器使用适配器与一种基础容器相结合来实现的先进先出数据结构 例10 5 应用标准库中的deque顺序容器生成一个整数标准队列Queue 容器 20 什么是迭代器 迭代器是面向对象版本的指针指针可以指向内存中的一个地址迭代器可以指向容器中的一个位置STL的每一个容器类模版中 都定义了一组
9、对应的迭代器类 使用迭代器 算法函数可以访问容器中指定位置的元素 而无需关心元素的具体类型 迭代器 21 迭代器的类型 输入迭代器可以用来从序列中读取数据输出迭代器允许向序列中写入数据前向迭代器既是输入迭代器又是输出迭代器 并且可以对序列进行单向的遍历双向迭代器与前向迭代器相似 但是在两个方向上都可以对数据遍历随机访问迭代器也是双向迭代器 但能够在序列中的任意两个位置之间进行跳转 迭代器 22 迭代器适配器 迭代器适配器是用来扩展 或调整 迭代器功能的类 它本身也被称为迭代器 只是这种迭代器是通过改变另一个迭代器而得到的逆向迭代器通过重新定义递增运算和递减运算 使其行为正好倒置插入型迭代器将赋
10、值操作转换为插入操作 通过这种迭代器 算法可以执行插入行为而不是覆盖行为例10 6应用逆向迭代器和后插迭代器来操作向量容器中的元素 迭代器 23 迭代器相关的辅助函数 advance 函数将迭代器的位置增加 增加的幅度由参数决定Distance 函数返回迭代器之间的距离函数iter swap 交换两个迭代器所指向的元素值例10 7用三个迭代器辅助函数来操作列表容器中的元素 迭代器 24 标准C 库中的算法 算法本身是一种函数模板不可变序列算法 Non mutatingalgorithms 不直接修改所操作的容器内容的算法可变序列算法 Mutatingalgorithms 可以修改它们所操作的容
11、器的元素 排序相关算法数值算法 算法 25 算法应用举例 例10 9应用不可变序列算法对数据序列进行分析例10 10以可变序列算法对数据序列进行复制 生成 删除 替换 倒序 旋转等可变性操作 例10 11应用排序相关算法对序列进行各项操作例10 12应用数值算法对数据序列进行操作 算法 26 函数对象 一个行为类似函数的对象 它可以不需参数 也可以带有若干参数 其功能是获取一个值 或者改变操作的状态 任何普通的函数和任何重载了调用运算符operator 的类的对象都满足函数对象的特征STL中也定义了一些标准的函数对象 如果以功能划分 可以分为算术运算 关系运算 逻辑运算三大类 为了调用这些标准函数对象 需要包含头文件
