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

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