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

C C 程序设计教程 郑秋生主编 2020 2 23 2 第7章标准模板库STL介绍及应用 本章学习重点掌握内容 标准模板库STL的基本概念标准模板库STL的组成部分命名空间的概念及使用容器的概念和使用迭代器的概念和使用算法的概念和使用标准模板库STL的应用 2020 2 23 3 第7章标准模板库STL介绍及应用 7 1标准模板库STL的概念7 2容器 Container 7 3迭代器 Iterator 7 4算法 Algorithm 7 5综合应用实例 2020 2 23 4 7 1标准模板库STL的概念 STL最初是由惠普实验室开发的一系列组件 是标准C 库的重要补充之一 从逻辑层次来看 STL体现了泛型程序设计的思想 引入了多个新的名词 比如容器 算法 迭代器等 在STL中 几乎所有的代码都采用了类模板和函数模板的方式 因而 提供了更好的代码重用机会 从广义上讲 STL的代码分为三类 容器 迭代器和算法 这3类代码被组织为13个头文件 2020 2 23 5 7 1 2STL和C 标准的关系 2020 2 23 6 7 1 3STL组成部分 2020 2 23 7 4STL组成部分 容器用来容纳对象或对象组的组合 STL的容器包括向量 vector 链表 list 等2类7种 迭代器是一种面向对象的广义指针 用于指向容器中或流中的对象 提供访问方法 算法是STL的核心 是普通算法的泛化形式 算法通过迭代器的指向与容器分离 从而具有通用性 函数对象的主要作用是作为参数传递给某些通用算法 从而进一步提高算法的通用性 STL中预定义了3大类15个函数对象 用户也可根据需要自行设计 2020 2 23 8 STL对C 的影响 在STL之前 C 支持三种基本的编程样式 面向过程编程 数据抽象和面向对象编程 在STL出现之后 C 可以支持一种新的编程模式 泛型程序设计 STL并不完美 但是 它开辟了程序设计的新天地 它拥有的影响力甚至于超过了巨大的C 群体 2020 2 23 9 7 2容器 Container 7 2 1容器简介容器是能够保存其它类型的对象的类 C 的容器可以包含混合类型的对象 也就是说容器类可以包含一组相同类型或一组不同类型的对象 容器类包含相同类型的对象时 称为同类容器类 容器类包含不同类型的对象时 称为异类容器类 容器类库共包括十种容器 分为三大类 分别如下 1 顺序容器 向量 双队列 列表 2 关联容器 集合 多重集 映射和多重映射 3 容器适配器 堆栈 队列和优先队列 2020 2 23 10 7 2容器 Container 2020 2 23 11 7 2容器 Container 2020 2 23 12 7 2 2容器的结构 所有的STL容器都是定义在命名空间std中的一个模板类 由 和七个头文件给出 主要包括下面3个方面 1 常用的类型2 常用的函数3 vector和list基本结构 2020 2 23 13 7 2 2容器的结构 2020 2 23 14 7 3 2容器的结构 2020 2 23 15 7 3 2容器的结构 容器中共用的函数 2020 2 23 16 7 3 2容器的结构 2020 2 23 17 顺序容器和关联容器共用的函数 2020 2 23 18 7 3 2容器的介绍 1 向量vector是个能够存放任意类型的动态数组 但是能够自动分配内存 随机存取能在常数时间完成 像数组一样可以使用下标访问元素 小心 不要数组越界在尾端增删元素具有较佳的性能其他位置的增删操作和插入操作都不好需要把待插入元素右边的每个元素都拷贝一遍 使用vector 包含头文件 include名字空间 namespace vector属于std命名域的 usingstd vector 或者连在一起 使用全 std vectorvInts建议使用全局的名字空 usingnamespacestd 2020 2 23 19 使用vector数组 创建一个int型的vectorvectorintarray 定义一个整型数组 可以是任意类型向vector添加一个数据vector添加数据的缺省方法是push back push back 函数表示将数据添加到vector的尾部 并按需要来分配内存for inti 0 i 10 i intarray push back i 2020 2 23 20 向vector插入一个数据insert 需要从插入点开始后移所有元素 并按需分配存储空间删除vector中的数据pop back 最有位置删除一个erase iteratorfirst iteratorlast 迭代器指定位置clear 清楚所有元素 判断数据个数empty 判断vector是否为空size 返回vector的数据个数 2020 2 23 21 预先分配内存空间reserve intn reserve只是预先划分一块内存给vector使用 主要是为了提高效率 避免在不断push back的过程中 由于容量变动导致的重新分配 注意 仅是分配空间 新元素还没有构造 不能引用resize intn 是改变容器的大小 并且创建对象 可以引用注意 vector和普通数组的区别 只有调用了构造函数 才可以引用 如果析构后则不可以引用 2020 2 23 22 获得存储空间大小 size 已经包含的数组元素的个数 注意构造过的 对应于resize intn capacity 容器的存储能力 对应于reserve intn 2020 2 23 23 vector的元素访问 使用三种方法来访问vector中的数据 vector at intidx vector operator intidx 迭代器 通用方法 所有容器适用 前两者区别 operator 主要是为了与C语言进行兼容 它可以像C语言数组一样操作 容易造成越界访问 尽量少用 at 是首选 因为at 进行了边界检查 如果访问超过了vector的范围 将抛出一个例外 2020 2 23 24 vector的元素访问 利用迭代器访问vector iteratoriter 定义迭代器for iter intarry begin iter intarray end iter iter 100 类似于指针 2020 2 23 25 2020 2 23 26 7 3 2容器的结构 2 列表list定义链表结构 链表的使用和vector基本相同 只是存储结构不同 使用略微不同 算法效率不同 插入数据线性 访问数据效率不高 数据结构 2020 2 23 27 7 3 3容器的使用 使用容器就像使用一个类模板一样 只不过这个类模板是属于C 标准库的 例7 4 list容器完整的程序 本例子初始化一个list的非空实例 然后将list中的元素值打印出来 2020 2 23 28 7 4迭代器 Iterator 迭代器从作用上来说是STL最基本的部分 但理解起来比较困难 简单的说 迭代器是指针的泛化 它允许程序员以相同的方式处理不同的数据结构 容器 迭代器部分主要由头文件 和组成 iterator类的对象就成为一种指向链表结点的广义指针 它实质上是对Node类型的指针进行了封装 重载了 运算符 使得通过对该种广义指针的 运算可以指向链表的下一结点 以iterator类还对解析运算符 比较运算符 和 进行了重载 2020 2 23 29 迭代器类型 输入迭代器只用于读一个序列 可以进行自增 解析和比较操作 输出迭代器只用于写一个序列 可以进行自增和解析操作 前向迭代器可以用来读写 并能够保存迭代器的值 以便从其原先位置开始重新遍历 它能够向前推进到下一个值 但不能递减 它包含了输入和输出迭代器的所有操作 双向迭代器既可以读又可以写 支持双向移动 不但可以自增取得下一个元素 而且可以自减取前一个 2020 2 23 30 迭代器类型 补充 随机存取迭代器可以通过跳跃的方式访问容器种的任意数据 从而使数据的访问非常灵活 它除了具有双向迭代器的所有操作外 2020 2 23 31 7 5算法 Algorithm 7 5 1算法和函数对象广义上讲 算法是一个按照一组定义明确的步骤来解决某个问题的处理过程 所有算法的前两个变量都是一对迭代器 通常称为首 first 和末 last 迭代器 用来表明算法对容器进行操作的元素范围 元素范围是一个区间 fist last 它表示范围从first 包含first指向的元素 开始 到last结束 不包含last指向的元素 函数对象是函数的一般形式 实际上函数对象是一个重载了operator 的类 2020 2 23 32 7 5 2算法分类介绍 STL提供了70个算法 按照不同的分类方法可以将这些算法分成不同的类别 1 按照算法所做工作的不同 可以将算法分成8个种类 查找 排序 数值计算 比较 集合 容器管理 统计和堆操作 2 按照算法对容器的影响 可以将算法分成4个种类 非修正算法 修正算法 排序算法和数值计算算法 2020 2 23 33 7 5 2算法分类介绍 1 非修正算法非修正算法的操作不对变容器中的元素进行任何修改 这类算法包括adjacent find find find end find first count mismatch equal for each 和search 等 这些算法都包含在头文件中 例7 8 非修正算法例题 2020 2 23 34 7 5 2算法分类介绍 2 修正算法在实际应用中 经常需要对容器中的元素进行修改和写操作 这类能够对容器中元素进行修改的算法称为修正算法 修正算法包括copy copy backward fill generate partition random shuffle remove replace rotate reverse swap swap ranges transform 和unique 等 例7 9 修正算法例题 2020 2 23 35 7 5 2算法分类介绍 3 排序算法对于一个序列来说 排序是最经常进行的操作 也是最重要的操作 由于排序需要移动元素 因此排序算法用到的迭代器都是随机存取迭代器 排序算法包括sort stable sort partial sort partial sort copy nth element binary search lower bound upper bound equal range merge includes push heap pop heap make heap sort heap set union set intersection set difference set symmetric difference min min element max max element lexicographica compare next permutation 和prev permutation 等 例7 10 排序算法例题 2020 2 23 36 7 5 2算法分类介绍 4 数值计算算法数值计算算法主要是对容器中的元素进行数值计算 这类算法包括accumulate inner product partial sum adjacent difference 和一些推广的数值算法