C++程序设计--对象分册(第7章).ppt

2020 2 16 1 第7章标准模板库STL介绍及应用 本章学习重点掌握内容 标准模板库STL的基本概念标准模板库STL的组成部分命名空间的概念及使用容器的概念和使用迭代器的概念和使用算法的概念和使用标准模板库STL的应用 2020 2 16 2 第7章标准模板库STL介绍及应用 7 1标准模板库STL的概念7 2命名空间7 3容器 Container 7 4迭代器 Iterator 7 5算法 Algorithm 7 6综合应用实例 2020 2 16 3 7 1标准模板库STL的概念 STL最初是由惠普实验室开发的一系列组件 是标准C 库的重要补充之一 从逻辑层次来看 STL体现了泛型程序设计的思想 引入了多个新的名词 比如容器 算法 迭代器等 在STL中 几乎所有的代码都采用了类模板和函数模板的方式 因而 提供了更好的代码重用机会 从广义上讲 STL的代码分为三类 容器 迭代器和算法 这3类代码被组织为13个头文件 2020 2 16 4 7 1 2STL和C 标准的关系 2020 2 16 5 7 1 3STL组成部分 2020 2 16 6 7 1 3STL组成部分 1 容器能够保存其它类型的对象的类 C 的容器可以包含混合类型的对象 也就是说容器类可以包含一组相同类型或一组不同类型的对象 当容器类包含相同类型的对象时 称为同类容器类 当容器类包含不同类型的对象时 称为异类容器类 2 迭代器迭代器从作用上来说是STL最基本的部分 但理解起来比较困难 简单的说 迭代器是指针的泛化 它允许程序员以相同的方式处理不同的数据结构 容器 迭代器是算法访问容器的中介 2020 2 16 7 7 1 3STL组成部分 3 算法一个按照一组定义明确的步骤来解决某个问题的处理过程 理论上 它不依赖于任何特定的计算机编程语言 STL提供了大约70个实现算法的函数模板 4 函数对象所谓函数对象是定义了函数调用操作符的对象 在使用STL时 经常需要把函数对象作为算法的输入参数或实例化一个容器 container 时的输入参数 2020 2 16 8 7 1 4STL对C 的影响 在STL之前 C 支持三种基本的编程样式 面向过程编程 数据抽象和面向对象编程 在STL出现之后 C 可以支持一种新的编程模式 泛型程序设计 STL并不完美 但是 它开辟了程序设计的新天地 它拥有的影响力甚至于超过了巨大的C 群体 2020 2 16 9 7 2命名空间 在实际开发过程中 经常需要引入对象 函数 类 类型或其它的全局实体 在同一个项目中 即使不在同一个文件中定义或声明 这些全局实体也必须有一个唯一的名字 这也意味着当程序员使用开发商提供的库时必须保证程序中的全局实体不和开发商提供的库中的全局实体名字冲突 这将是一件非常枯燥和困难的事情 为了解决名字冲突的问题 C 引入命名空间机制 2020 2 16 10 7 2 1命名空间的定义 定义命名空间的语法格式如下 namespace命名空间名 声明序列 其中 namespace是关键字 后面是命名空间名 命名空间名必须在它被定义的作用域中具有唯一的名字 否则会产生错误 在命名空间名后一对花括号 括起来的是声明序列 所有可以出现在全局作用域的定义或声明都可以放在其中 2020 2 16 11 7 2 1命名空间的定义 namespacemyNameSpace stringmyStr myStr classmyClass public myClass 类的其它部分 voidmyFunc intmyCount 0 externexFun 其它实体定义或声明 2020 2 16 12 7 2 1命名空间的定义 定义或使用命名空间需要注意下面几个方面 1 namespace只能在全局范畴定义 但它们之间可以互相嵌套 即在命名空间定义内容定义一个新的命名空间 2 在namespace定义的结尾 大括号的后面不必要跟一个分号 3 一个namespace可以在多个头文件中用一个标识符来定义 4 一个namespace的名字可以用另一个名字做它的别名 5 不能像类那样去创建一个命名空间的实例 6 可以通过多次声明和定义同一命名空间 把新的成员名称加入到已有的命名空间之中去 2020 2 16 13 7 2 2命名空间的使用 对命名空间中成员的引用 需要使用命名空间的域操作符 例7 1 使用命名空间的例子 include includeusingnamespacestd 两个在不同命名空间中定义的名字相同的变量namespacemySpace1 自定义命名空间stringmyStr myStr1 namespacemySpace2 stringmyStr myStr2 2020 2 16 14 7 2 2命名空间的使用 voidmain 用命名空间域操作符mySpace1 访问变量myStrcout Hello mySpace1 myStr goodbye endl 用命名空间域操作符mySpace2 访问变量myStrcout Hello mySpace2 myStr goodbye endl 2020 2 16 15 为了避免麻烦 可以使用C 的using编译指令来简化对命名空间中的名称的使用 语法格式为 usingnamespace命名空间名 命名空间名 中括号中的可选部分是指定命名空间中嵌套的子命名空间时使用的 有了using指令后 在编写程序时就可以使用using指令 而不用每次都使用 命名空间名 来限定要访问的实体 7 2 2命名空间的使用 2020 2 16 16 include includeusingnamespacestd namespacemyNameSpace1 stringmyStr1 myStr1 namespacemyNameSpace2 stringmyStr2 myStr2 usingnamespacemyNameSpace1 usingnamespacemyNameSpace1 myNameSpace2 voidmain cout Hello myStr1 goodbye endl cout Hello myStr2 goodbye endl 例7 2 用using指令使用命名空间的例子 2020 2 16 17 7 2 3无名空间 有时 定义的全局实体只在程序的一小段代码中使用 而在其它地方不会使用 为了保证这些全局实体不和项目其它地方的全局实体冲突 可以使用无名空间 无名空间声明的语法格式如下 namespace 声明序列 namespace后不跟命名空间名字 直接用一对 括住声明序列 就定义了一个无名空间 2020 2 16 18 7 2 3无名空间 例7 3 使用无名空间的例子 include includeusingnamespacestd namespace voidfunc1 cout 调用了func1 endl voidfunc2 cout 调用了func2 endl voidmain cout 测试无名空间的例子 endl func1 无名空间中定义的函数func2 无名空间中定义的函数 2020 2 16 19 标准C 库中的所有组件都定义在一个称为std的命名空间中 因此 std又称为标准命名空间 在编写程序时 如果需要使用标准C 的组件 在包含相应的标准C 头文件后 可以采用下面几种方法使用头文件中声明的函数对象 类模板等 1 使用域操作符std 2 使用编译指令usingnamespacestd 3 使用编译指令usingnamespacestd 进行更具体的限制 如usingnamespacestd string 7 2 3标准命名空间std 2020 2 16 20 7 3容器 Container 7 3 1容器简介容器是能够保存其它类型的对象的类 C 的容器可以包含混合类型的对象 也就是说容器类可以包含一组相同类型或一组不同类型的对象 容器类包含相同类型的对象时 称为同类容器类 容器类包含不同类型的对象时 称为异类容器类 容器类库共包括十种容器 分为三大类 分别如下 1 顺序容器 向量 双队列 列表 2 关联容器 集合 多重集 映射和多重映射 3 容器适配器 堆栈 队列和优先队列 2020 2 16 21 7 3容器 Container 根据使用迭代器的不同可以将容器分为4类 1 前向容器 一种采用前向迭代器的容器 它和容器相比没有什么区别 只是前向容器只能使用前向迭代器 2 双向容器 双向容器继承于前向容器 它除了具有前向迭代器外 还具有逆向迭代器 可以双向访问容器中的元素 3 序列容器 序列是一种长度可变的容器 向量中的元素按照线性关系排列和存储 它直接继承于前向容器 4 关联容器 关联容器也是一种长度可变的容器 它支持高效的数据查询和数据操作 它由前向容器衍生而来 2020 2 16 22 7 3容器 Container 2020 2 16 23 7 3容器 Container 2020 2 16 24 7 3 2容器的结构 所有的STL容器都是定义在命名空间std中的一个模板类 由 和七个头文件给出 主要包括下面3个方面 1 常用的类型2 常用的函数3 vector和list基本结构 2020 2 16 25 7 3 2容器的结构 顺序容器和关联容器中常用的typedef 2020 2 16 26 7 3 2容器的结构 2020 2 16 27 7 3 2容器的结构 容器中共用的函数 2020 2 16 28 7 3 2容器的结构 2020 2 16 29 顺序容器和关联容器共用的函数 2020 2 16 30 7 3 2容器的结构 1 向量vector定义 2020 2 16 31 7 3 2容器的结构 2 列表list定义 2020 2 16 32 7 3 3容器的使用 使用容器就像使用一个类模板一样 只不过这个类模板是属于C 标准库的 例7 4 list容器完整的程序 本例子初始化一个list的非空实例 然后将list中的元素值打印出来 2020 2 16 33 7 4迭代器 Iterator 迭代器从作用上来说是STL最基本的部分 但理解起来比较困难 简单的说 迭代器是指针的泛化 它允许程序员以相同的方式处理不同的数据结构 容器 迭代器部分主要由头文件 和组成 2020 2 16 34 7 4 1输入迭代器 输入迭代器只能够从一个序列中读取数值 它可以被修改 引用和进行比较 输入迭代器支持6种操作 1 i 前置自增迭代器 2 i 后置自增迭代器 3 i 引用迭代器 作为右值 4 i1 i2 将一个迭代器赋值给另一个迭代器 5 i1 i2 比较迭代器相等性 6 i1 i2 比较迭代器不等性 2020 2 16 35 7 4 1输入迭代器 2020 2 16 36 templateInputIteratorfind InputIteratorfirst InputIteratorlast constT 7 4 1输入迭代器 2020 2 16 37 输出迭代器只能够向一个序列写入数据 它可以被修改和引用 通常用于将数据从一个位置拷贝到另一个位置 除了具有输入迭代器的所有功能外 输出迭代器还具有一个操作 i 复引用迭代器 作为左值 7 4 2输出迭代器 2020 2 16 38 例7 5 一个关于输出迭代器的例题 7 4 2输出迭代器 2020 2 16 39 前向迭代器 forwarditerators 既可以用来读也可以用来写 并能够保存迭代器的值 以便从其原先位置开始重新遍历 它能够向前推进到下一个值 但不能递减 它包含了输入和输出迭代器的所有操作 7 4 3前向迭代器 2020 2 16 40 7 4 3前向迭代器 前向迭代器的例子templatevoidfill ForwardIteratorfirst ForwardIteratorlast constT上面代码使用前向迭代器将数组p的前10个元素赋值为0 后90个元素赋值为10 2020 2 16 41 7 4 4双向迭代器 双向迭代器 bidirectioniterators 既可以读又可以写 它与前向迭代器类似 除了具有前向迭代器的所有操作外 双向迭代器还具有下面两种操作 1 i 前置自减迭代器 2 i 后置自减迭代器 2020 2 16 42 7 4 5随机存取迭代器 随机存取迭代器 randomaccessiterator 可以通过跳跃的方式访问容器种的任意数据 从而使数据的访问非常灵活 它除了具有双向迭代器的所有操作外 还具有9种操作 1 i x 将迭代器i递增x位 2 i x 将迭代器i递减x位 3 i x 在i位加x位后的迭代器 4 i x 在i位减x位后的迭代器 5 i x 返回偏离i位元素x位的元素引用 6 i1 i2 如果迭代器i1小于i2 即容器中迭代器i1在迭代器i2之前 则返回true 否则返回false 2020 2 16 43 7 4 5随机存取迭代器 7 i1i2 如果迭代器1i大于i2 即容器中迭代器i1在迭代器i2之后 则返回true 否则返回false 9 i1 i2 如果迭代器i1大于或等于i2 则返回true 否则返回false 2020 2 16 44 7 4 6迭代器的使用 例7 6 从标准输入读入5个整数 使用输出迭代器输出这5个整数 然后使用STL通用算法sort 对vector中的元素排序 再输出排序后vector中元素 2020 2 16 45 7 5算法 Algorithm 7 5 1算法和函数对象广义上讲 算法是一个按照一组定义明确的步骤来解决某个问题的处理过程 所有算法的前两个变量都是一对迭代器 通常称为首 first 和末 last 迭代器 用来表明算法对容器进行操作的元素范围 元素范围是一个区间 fist last 它表示范围从first 包含first指向的元素 开始 到last结束 不包含last指向的元素 函数对象是函数的一般形式 实际上函数对象是一个重载了operator 的类 2020 2 16 46 7 5 1算法和函数对象 STL中的函数对象 2020 2 16 47 7 5 1算法和函数对象 例7 7 函数对象的使用方法例题 2020 2 16 48 7 5 2算法分类介绍 STL提供了70个算法 按照不同的分类方法可以将这些算法分成不同的类别 1 按照算法所做工作的不同 可以将算法分成8个种类 查找 排序 数值计算 比较 集合 容器管理 统计和堆操作 2 按照算法对容器的影响 可以将算法分成4个种类 非修正算法 修正算法 排序算法和数值计算算法 2020 2 16 49 7 5 2算法分类介绍 1 非修正算法非修正算法的操作不对变容器中的元素进行任何修改 这类算法包括adjacent find find find end find first count mismatch equal for each 和search 等 这些算法都包含在头文件中 例7 8 非修正算法例题 2020 2 16 50 7 5 2算法分类介绍 2 修正算法在实际应用中 经常需要对容器中的元素进行修改和写操作 这类能够对容器中元素进行修改的算法称为修正算法 修正算法包括copy copy backward fill generate partition random shuffle remove replace rotate reverse swap swap ranges transform 和unique 等 例7 9 修正算法例题 2