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

C/C+程序设计教程 郑秋生 主编 *2 第7章 标准模板库STL介绍及应用 n本章学习重点掌握内容： n标准模板库STL的基本概念 n标准模板库STL的组成部分 n命名空间的概念及使用 n容器的概念和使用 n迭代器的概念和使用 n算法的概念和使用 n标准模板库STL的应用 *3 第7章 标准模板库STL介绍及应用 n7.1标准模板库STL的概念 n7.2容器（Container） n7.3迭代器（Iterator） n7.4算法（Algorithm） n7.5 综合应用实例 *4 7.1 标准模板库STL的概念 nSTL最初是由惠普实验室开发的一系列组件，是标准 C+库的重要补充之一。 n从逻辑层次来看，STL体现了泛型程序设计的思想，引 入了多个新的名词，比如容器、算法、迭代器等。 n在STL中，几乎所有的代码都采用了类模板和函数模板 的方式，因而，提供了更好的代码重用机会。 n从广义上讲，STL的代码分为三类：容器、迭代器和算 法。这3类代码被组织为13个头文件。 *5 7.1.2 STL和C+标准的关系 输入/输出 数值 诊断 通用工具 国际化 语言支持 容器 算法 迭代器 字符串 STL C+标准库 C 标 准 函 数 STL和C+标准库的关系 *6 7.1.3 STL组成部分 函数对象通用算法assist STL 容器迭代器 supports apply to access use use STL结构图 *7 4 STL组成部分 n容器用来容纳对象或对象组的组合。STL 的容器包 括向量（ vector）、链表( list)等2 类7 种。 n 迭代器是一种面向对象的广义指针，用于指向容器 中或流中的对象，提供访问方法。 n算法是STL 的核心，是普通算法的泛化形式。算法 通过迭代器的指向与容器分离，从而具有通用性。 n函数对象的主要作用是作为参数传递给某些通用算 法，从而进一步提高算法的通用性。STL 中预定义 了3 大类15个函数对象，用户也可根据需要自行设 计。 *8 STL对C+的影响 n在STL之前，C+支持三种基本的编程样式面向过程 编程、数据抽象和面向对象编程。 n在STL出现之后，C+可以支持一种新的编程模式泛 型程序设计。 nSTL并不完美，但是，它开辟了程序设计的新天地，它 拥有的影响力甚至于超过了巨大的C+群体。 *9 7.2 容器（Container） 7.2.1 容器简介 容器是能够保存其它类型的对象的类。 C+的容器可以包含混合类型的对象，也就是说容器类可以包含 一组相同类型或一组不同类型的对象。 容器类包含相同类型的对象时，称为同类容器类； 容器类包含不同类型的对象时，称为异类容器类。 容器类库共包括十种容器，分为三大类，分别如下： （1）顺序容器：向量、双队列、列表； （2）关联容器：集合、多重集、映射和多重映射； （3）容器适配器：堆栈、队列和优先队列。 *10 7.2 容器（Container） 容器名描述类型头文件 向量连续存储元素的数组。 顺序 容器 列表 由结点组成的双向链表，每个结点包含 一个元素 顺序 容器 双队列 连续存储的指向不同元素的指针所组成 的数组。 顺序 容器 集合 由节点组成的红黑树，每个节点都包含 着一个元素，节点之间以某种作用于元 素对的谓词排列，没有两个不同的元素 能够拥有相同的次序。 关联 容器 多重集合允许存在两个次序相等的元素的集合。 关联 容器 *11 容器名描述类型头文件 栈后进先出的值的排列。 容器适 配器 队列先进先出的值的排列。 容器适 配器 优先队列 元素的次序是由作用于所存储的值对 上的某种谓词决定的一种队列。 容器适 配器 映射 由键，值对组成的集合，以某种作 用于键对上的谓词排列。 关联 容器 多重映射允许键对有相等的次序的映射。 关联 容器 7.2容器（Container） *12 7.2.2 容器的结构 所有的STL容器都是定义在命名空间std中的一个模板类，由 、 和七个头文件给出。主要包括下面3个方面。 n1. 常用的类型 n2. 常用的函数 n3. vector和list基本结构 *13 类型名值的类型描述 value_type值类型容器中存放元素的类型 size_type长度 用于计算容器中项目数和检索顺序容器的 类型（不能对list检索） difference_typ e 距离 引用相同容器的两个迭代器相减结果的类 型（list和关联容器没有定义operator-） iterator迭代器指向容器中存放元素类型的迭代器 const_iterator常迭代器 指向容器中存放元素类型的常量迭代器， 只能读取容器中的元素 7.2.2 容器的结构 *14 reverse_iterat or 逆向迭 代器 指向容器中存放元素的逆向迭代器，这种 迭代器在容器中逆向迭代 const_reverse _iterator 常逆向 迭代器 指向容器中存放元素类型的常逆向迭代 器，只能读取容器中的元素 pointer指针容器中存放元素类型的指针 const_pointer常指针 容器中存放元素类型的常量指针，这种指 针只能读取容器中的元素和进行const操作 reference引用容器中存放元素类型的引用 const_referen ce 常引用 容器中存放元素类型的常量引用，这种引 用只能读取容器中的元素和进行const操作 7.3.2 容器的结构 *15 7.3.2 容器的结构 容器中共用的函数 函数名功能描述备注 默认构造函数提供容器默认初始化的构造函数 拷贝构造函数将容器初始化为现有同类容器副本的构造函数 析构函数不再需要容器时进行内存整理的析构函数 empty（）容器中没有元素时返回true,否则返回false max_size（ ） 返回容器中最大元素个数 size（）返回容器中当前元素个数 operator=将一个容器赋给另一个容器 *16 operator 如果第一个容器大于第二个容器，返回 true，否则返回false 不适用于 priority_queue operator= 如果第一个容器大于或等于第二个容 器，返回true，否则返回false 不适用于 priority_queue operator= 如果第一个容器等于第二个容器，返回 true，否则返回false 不适用于 priority_queue operator!= 如果第一个容器不等于第二个容器，返 回true，否则返回false 不适用于 priority_queue swap（b）交换两个容器的元素 7.3.2 容器的结构 *17 顺序容器和关联容器共用的函数 函数名功能描述备注 begin（） 有两个版本返回iterator或const_ iterator ， 引用容器第一个元素 不适用于 容器适配器 end（） 有两个版本返回iterator或const_ iterator, 引用容器最后一个元素后面一位 不适用于 容器适配器 rbegin（） 有两个版本返回reverse_iterator或 const_reverse_iterator,引用容器最后一个元素 不适用于 容器适配器 rend（） 有两个版本返回reverse_iterator或 const_reverse _ iterator，引用容器第一个元素前面一位 不适用于 容器适配器 erase(p, q) erase（p） 从容器中清除一个或几个元素 不适用于 容器适配器 clear（）清除容器中所有元素 不适用于容器 适配器 *18 7.3.2 容器的介绍 （1）向量vector 是个能够存放任意类型的动态数组，但是能够自动分配 内存， 随机存取能在常数时间完成，像数组一样可以使用下标 访问元素，小心，不要数组越界 在尾端增删元素具有较佳的性能 其他位置的增删操作和插入操作都不好 需要把待插入元素右边的每个元素都拷贝一遍 使用vector n包含头文件 n #include n名字空间(namespace) nvector属于std命名域的 n using std:vector; n或者连在一起，使用全 n std:vector vInts n建议使用全局的名字空 n using namespace std; *19 使用vector数组 n创建一个int型的vector nvector intarray;/ 定义一个整型数组，可 以是任意类型 n向vector添加一个数据 nvector添加数据的缺省方法是push_back() n push_back()函数表示将数据添加到vector的尾 部 并按需要来分配内存 for(int i= 0;i:iterator iter; /定义迭代器 for( iter=intarry.begin(); iter!=intarray.end(); iter+) * iter = 100；/类似于指针 *25 *26 7.3.2 容器的结构 （2）列表list定义 链表结构： 链表的使用和vector基本相同，只是存储 结构不同，使用略微不同。算法效率不同 ，插入数据线性，访问数据效率不高（数 据结构） a1 a2 . an *27 7.3.3 容器的使用 使用容器就像使用一个类模板一样，只不过这个类 模板是属于C+标准库的。 【例7.4】list容器完整的程序。本例子初始化一个 list的非空实例，然后将list中的元素值打印出来。 *28 7.4迭代器（Iterator） 迭代器从作用上来说是STL最基本的部分，但理解起来比 较困难。简单的说，迭代器是指针的泛化，它允许程序 员以相同的方式处理不同的数据结构（容器）。 迭代器部分主要由头文件、和 组成。 niterator类的对象就成为一种指向链表结点的广 义指针，它实质上是对N ode 类型的指针进行了 封装，重载了“ +”运算符，使得通过对该种广 义指针的“ +”运算可以指向链表的下一结点。 n以iterator类还对解析运算符“ *”、比较运算符“ =”和“ !=”进行了重载。 *29 迭代器类型 n输入迭代器只用于读一个序列，可以进行自增、解析 和比较操作。 n输出迭代器只用于写一个序列，可以进行自增和解析 操作。 n前向迭代器 可以用来读写，并能够保存迭代器的值， 以便从其原先位置开始重新遍历。它能够向前推进到 下一个值，但不能递减，它包含了输入和输出迭代器 的所有操作。 n双向迭代器 既可以读又可以写，支持双向移动，不但 可以自增取得下一个元素，而且可以自减取前一个 *30 迭代器类型-补充 n随机存取迭代器 可以通过跳跃的方式访问容器 种的任意数据，从而使数据的访问非常灵活。 它除了具有双向迭代器的所有操作外 随机存取迭代器双向迭代器前向迭代器 输出迭代器 输入迭代器 迭代器关系 *31 7.5算法（Algorithm） 7.5.1算法和函数对象 广义上讲，算法是一个按照一组定义明确的步骤来解决某个问 题的处理过程。 所有算法的前两个变量都是一对迭代器，通常称为首（first）和 末（last）迭代器，用来表明算法对容器进行操作的元素范围。 元素范围是一个区间fist, last)，它表示范围从first（包含 first指向的元素）开始，到last结束（不包含last指向的元素） 函数对象是函数的一般形式。实际上函数对象是一个重载了 operator()的类。 *32 7.5.2 算法分类介绍 STL提供了70个算法，按照不同的分类方法可以将这些算法分成 不同的类别： （1）按照算法所做工作的不同，可以将算法分成8个种类：查找 、排序、数值计算、比较、集合、容器管理、统计和堆操作。 （2）按照算法对容器的影响，可以将算法分成4个种类：非修正 算法、修正算法、排序算法和数值计算算法。 *33 7.5.2 算法分类介绍 1非修正算法 非修正算法的操作不对变容器中的元素进行任何修改，这类算 法包括adjacent_find()、find()、find_end()、find_first()、 count()、mismatch()、equal()、for_each()和search()等，这 些算法都包含在头文件中。 【例7.8】非修正算法例题。 *34 7.5.2 算法分类介绍 2修正算法 在实际应用中，经常需要对容器中的元素进行修改和写操作， 这类能够对容器中元素进行修改的算法称为修正算法。修正算 法包括copy()、copy_backward()、fill() 、generate()、 partition()、random_shuffle()、remove()、replace()、rotate() 、reverse()、swap()、swap_ranges()、transform()和unique() 等 【例7.9】修正算法例题。 *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()、s