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

C/C+程序设计教程郑秋生 主编1/16/20232第第7章章 标准模板库标准模板库STL介绍及应用介绍及应用n本章学习重点掌握内容：本章学习重点掌握内容：n标准模板库标准模板库STL的基本概念的基本概念n标准模板库标准模板库STL的组成部分的组成部分n命名空间的概念及使用命名空间的概念及使用n容器的概念和使用容器的概念和使用n迭代器的概念和使用迭代器的概念和使用n算法的概念和使用算法的概念和使用n标准模板库标准模板库STL的应用的应用1/16/20233第第7章章 标准模板库标准模板库STL介绍及应用介绍及应用n7.1标准模板库标准模板库STL的概念的概念n7.2容器（容器（Container）n7.3迭代器（迭代器（Iterator）n7.4算法（算法（Algorithm）n7.5 综合应用实例综合应用实例1/16/202347.1 标准模板库标准模板库STL的概念的概念 nSTL最初是由惠普实验室开发的一系列组件，是标准C+库的重要补充之一。n从逻辑层次来看，STL体现了泛型程序设计的思想，引入了多个新的名词，比如容器、算法、迭代器等。n在STL中，几乎所有的代码都采用了类模板和函数模板的方式，因而，提供了更好的代码重用机会。n从广义上讲，STL的代码分为三类：容器、迭代器和算法。这3类代码被组织为13个头文件。1/16/202357.1.2 STL和和C+标准的关系标准的关系输入输入/输输出出数值数值诊断诊断通用工具通用工具国际化国际化语言支持语言支持容器容器算法算法迭代器迭代器字符串字符串STLC+标准库标准库C标标准准函函数数STL和和C+标准库的关系标准库的关系1/16/202367.1.3 STL组成部分组成部分函数对象函数对象通用算法通用算法assistSTL容器容器迭代器迭代器supportsapply toaccessuseuse STL结构图结构图1/16/202374 STL组成部分组成部分n容器用来容纳对象或对象组的组合。STL 的容器包括向量（vector）、链表(list)等2 类7 种。n 迭代器是一种面向对象的广义指针，用于指向容器中或流中的对象，提供访问方法。n算法是STL 的核心，是普通算法的泛化形式。算法通过迭代器的指向与容器分离，从而具有通用性。n函数对象的主要作用是作为参数传递给某些通用算法，从而进一步提高算法的通用性。STL 中预定义了3 大类15个函数对象，用户也可根据需要自行设计。1/16/20238 STL对对C+的影响的影响n在STL之前，C+支持三种基本的编程样式面向过程编程、数据抽象和面向对象编程。n在STL出现之后，C+可以支持一种新的编程模式泛型程序设计。nSTL并不完美，但是，它开辟了程序设计的新天地，它拥有的影响力甚至于超过了巨大的C+群体。1/16/202397.2 容器（容器（Container）7.2.1 容器简介 容器是能够保存其它类型的对象的类。C+的容器可以包含混合类型的对象，也就是说容器类可以包含一组相同类型或一组不同类型的对象。容器类包含相同类型的对象时，称为同类容器类；容器类包含不同类型的对象时，称为异类容器类。容器类库共包括十种容器，分为三大类，分别如下：（1）顺序容器：向量、双队列、列表；（2）关联容器：集合、多重集、映射和多重映射；（3）容器适配器：堆栈、队列和优先队列。1/16/2023107.2 容器（容器（Container）容器名描述类型头文件向量连续存储元素的数组。顺序容器列表由结点组成的双向链表，每个结点包含一个元素顺序容器双队列连续存储的指向不同元素的指针所组成的数组。顺序容器集合由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元素对的谓词排列，没有两个不同的元素能够拥有相同的次序。关联容器多重集合允许存在两个次序相等的元素的集合。关联容器1/16/202311容器名描述类型头文件栈后进先出的值的排列。容器适配器队列先进先出的值的排列。容器适配器优先队列元素的次序是由作用于所存储的值对上的某种谓词决定的一种队列。容器适配器映射由键，值对组成的集合，以某种作用于键对上的谓词排列。关联容器多重映射允许键对有相等的次序的映射。关联容器7.2容器（容器（Container）1/16/2023127.2.2 容器的结构容器的结构 所有的STL容器都是定义在命名空间std中的一个模板类，由、和七个头文件给出。主要包括下面3个方面。n1.常用的类型n2.常用的函数n3.vector和list基本结构 1/16/202313类型名值的类型描述value_type值类型容器中存放元素的类型size_type长度用于计算容器中项目数和检索顺序容器的类型（不能对list检索）difference_type距离引用相同容器的两个迭代器相减结果的类型（list和关联容器没有定义operator-）iterator迭代器指向容器中存放元素类型的迭代器const_iterator常迭代器指向容器中存放元素类型的常量迭代器，只能读取容器中的元素7.2.2 容器的结构容器的结构 1/16/202314reverse_iterator逆向迭代器指向容器中存放元素的逆向迭代器，这种迭代器在容器中逆向迭代const_reverse_iterator常逆向迭代器指向容器中存放元素类型的常逆向迭代器，只能读取容器中的元素pointer指针容器中存放元素类型的指针const_pointer常指针容器中存放元素类型的常量指针，这种指针只能读取容器中的元素和进行const操作reference引用容器中存放元素类型的引用const_reference常引用容器中存放元素类型的常量引用，这种引用只能读取容器中的元素和进行const操作7.3.2 容器的结构容器的结构 1/16/2023157.3.2 容器的结构容器的结构 容器中共用的函数 函数名功能描述备注默认构造函数提供容器默认初始化的构造函数拷贝构造函数将容器初始化为现有同类容器副本的构造函数析构函数不再需要容器时进行内存整理的析构函数empty（）容器中没有元素时返回true,否则返回falsemax_size（）返回容器中最大元素个数size（）返回容器中当前元素个数operator=将一个容器赋给另一个容器1/16/202316operator如果第一个容器小于第二个容器，返回true，否则返回false不适用于priority_queueoperator如果第一个容器大于第二个容器，返回true，否则返回false不适用于priority_queueoperator=如果第一个容器大于或等于第二个容器，返回true，否则返回false不适用于priority_queueoperator=如果第一个容器等于第二个容器，返回true，否则返回false不适用于priority_queueoperator!=如果第一个容器不等于第二个容器，返回true，否则返回false不适用于priority_queueswap（b）交换两个容器的元素7.3.2 容器的结构容器的结构 1/16/202317顺序容器和关联容器共用的函数 函数名功能描述备注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（）清除容器中所有元素不适用于容器适配器1/16/2023187.3.2 容器的介绍容器的介绍（1）向量）向量vector是个能够存放任意类型的动态数组，但是能够自动分配是个能够存放任意类型的动态数组，但是能够自动分配内存，内存，随机存取能在常数时间完成，像数组一样可以使用下标随机存取能在常数时间完成，像数组一样可以使用下标访问元素，小心，不要数组越界访问元素，小心，不要数组越界在尾端增删元素具有较佳的性能在尾端增删元素具有较佳的性能其他位置的增删操作和插入操作都不好其他位置的增删操作和插入操作都不好需要把待插入元素右边的每个元素都拷贝一遍需要把待插入元素右边的每个元素都拷贝一遍使用使用vectorn包含头文件包含头文件n#include n名字空间名字空间(namespace)nvector属于属于std命名域的命名域的n using std:vector;n或者连在一起，使用全或者连在一起，使用全n std:vector vIntsn建议使用全局的名字空建议使用全局的名字空n using namespace std;1/16/202319使用使用vector数组数组n创建一个创建一个int型的型的vectornvector intarray;/定义一个整型数组，可定义一个整型数组，可以是任意类型以是任意类型n向向vector添加一个数据添加一个数据nvector添加数据的缺省方法是添加数据的缺省方法是push_back()n push_back()函数表示将数据添加到函数表示将数据添加到vector的的尾部尾部 并按需要来分配内存并按需要来分配内存for(int i=0;i10;i+)intarray.push_back(i);1/16/202320n向向vector插入一个数据插入一个数据ninsert()；/需要从插入点开始后移所有元素，并按需分配需要从插入点开始后移所有元素，并按需分配存储空间存储空间n删除删除vector中的数据中的数据npop_back();/最有位置删除一个最有位置删除一个nerase(iterator first,iterator last);/迭代器指定位置迭代器指定位置nclear()/清楚所有元素，清楚所有元素，n判断数据个数判断数据个数nempty()n 判断判断vector是否为空是否为空nsize()n 返回返回vector的数据个数的数据个数1/16/202321n预先分配内存空间预先分配内存空间nreserve(int n);/reserve只是预先划分一块内存给vector使用，主要是为了提高效率：避免在不断push_back的过程中，由于容量变动导致的重新分配,n注意：仅是分配空间，新元素还没有构造,不能引用nresize(int n);/是改变容器的大小，并且创建对象，可以引用n注意：vector和普通数组的区别，只有调用了构造函数，才可以引用，如果析构后则不可以引用1/16/202322获得存储空间大小获得存储空间大小nsize();/已经包含的数组元素的个数，注意已经包含的数组元素的个数，注意构造过的，对应于构造过的，对应于resize(int n)ncapacity();/容器的存储能力，对应于容器的存储能力，对应于reserve(int n)1/16/202323vector的元素访问的元素访问n使用三种方法来访问使用三种方法来访问vector中的数据中的数据n vector:at(int idx)n vector:operatorint idxn迭代器，通用方法，所有容器适用迭代器，通用方法，所有容器适用n 前两者区别前两者区别n operator主要是为了与主要是为了与C语言进行兼容。它可语言进行兼容。它可以像以像C语言数组一样操作。容易造成越界访问，尽语言数组一样操作。容易造成越界访问，尽量少用量少用n at()是首选，因为是首选，因为at()进行了边界检查，如果访进行了边界检查，如果访问超过了问超过了vector的范围，将抛出一个例外。的范围，将抛出一个例外。1/16/202324vector的元素访问的元素访问n利用迭代器访问利用迭代器访问vector:iterator iter;/定义迭代器for(iter=intarry.begin();iter!=intarray.end();iter+)*iter=100；/类似于指针1/16/2023251/16/2023267.3.2 容器的结构容器的结构（2）列表）列表list定义定义 链表结构：链表结构：链表的使用和链表的使用和vector基本相同，只是存储基本相同，只是存储结构不同，使用略微不同。算法效率不同，结构不同，使用略微不同。算法效率不同，插入数据线性，访问数据效率不高（数据插入数据线性，访问数据效率不高（数据结构）结构）a1 a2 .an 1/16/2023277.3.3 容器的使用容器的使用 使用容器就像使用一个类模板一样，只不过这个类模板是属于C+标准库的。【例7.4】list容器完整的程序。本例子初始化一个list的非空实例，然后将list中的元素值打印出来。1/16/2023287.4迭代器（迭代器（Iterator）迭代器从作用上来说是STL最基本的部分，但理解起来比较困难。简单的说，迭代器是指针的泛化，它允许程序员以相同的方式处理不同的数据结构（容器）。迭代器部分主要由头文件、和组成。niterator类的对象就成为一种指向链表结点的广义指针，它实质上是对N ode 类型的指针进行了封装，重载了“+”运算符，使得通过对该种广义指针的“+”运算可以指向链表的下一结点。n以iterator类还对解析运算符“*”、比较运算符“=”和“!=”进行了重载。1/16/202329迭代器类型迭代器类型n输入迭代器输入迭代器只用于读一个序列，可以进行自增、解析和比较操作。n输出迭代器输出迭代器只用于写一个序列，可以进行自增和解析操作。n前向迭代器前向迭代器 可以用来读写，并能够保存迭代器的值，以便从其原先位置开始重新遍历。它能够向前推进到下一个值，但不能递减，它包含了输入和输出迭代器的所有操作。n双向迭代器双向迭代器 既可以读又可以写，支持双向移动，不但可以自增取得下一个元素，而且可以自减取前一个1/16/202330迭代器类型迭代器类型-补充补充n随机存取迭代器随机存取迭代器 可以通过跳跃的方式访问容器种的任意数据，从而使数据的访问非常灵活。它除了具有双向迭代器的所有操作外随机存取迭代器随机存取迭代器双向迭代器双向迭代器前向迭代器前向迭代器输出迭代器输出迭代器输入迭代器输入迭代器迭代器关系迭代器关系1/16/2023317.5算法（算法（Algorithm）7.5.1算法和函数对象 广义上讲，算法是一个按照一组定义明确的步骤来解决某个问题的处理过程。所有算法的前两个变量都是一对迭代器，通常称为首（first）和末（last）迭代器，用来表明算法对容器进行操作的元素范围。元素范围是一个区间fist,last)，它表示范围从first（包含first指向的元素）开始，到last结束（不包含last指向的元素）函数对象是函数的一般形式。实际上函数对象是一个重载了operator()的类。1/16/2023327.5.2 算法分类介绍算法分类介绍 STL提供了70个算法，按照不同的分类方法可以将这些算法分成不同的类别：（1）按照算法所做工作的不同，可以将算法分成8个种类：查找、排序、数值计算、比较、集合、容器管理、统计和堆操作。（2）按照算法对容器的影响，可以将算法分成4个种类：非修正算法、修正算法、排序算法和数值计算算法。1/16/2023337.5.2 算法分类介绍算法分类介绍 1非修正算法 非修正算法的操作不对变容器中的元素进行任何修改，这类算法包括adjacent_find()、find()、find_end()、find_first()、count()、mismatch()、equal()、for_each()和search()等，这些算法都包含在头文件中。【例7.8】非修正算法例题。1/16/2023347.5.2 算法分类介绍算法分类介绍2修正算法 在实际应用中，经常需要对容器中的元素进行修改和写操作，这类能够对容器中元素进行修改的算法称为修正算法。修正算法包括copy()、copy_backward()、fill()、generate()、partition()、random_shuffle()、remove()、replace()、rotate()、reverse()、swap()、swap_ranges()、transform()和unique()等【例例7.9】修正算法例题。1/16/2023357.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】排序算法例题1/16/2023367.5.2 算法分类介绍4数值计算算法 数值计算算法主要是对容器中的元素进行数值计算。这类算法包括accumulate()、inner_product()、partial_sum()、adjacent_difference()和一些推广的数值算法。