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

《C++程序设计--对象分册(第7章).ppt》由会员分享，可在线阅读，更多相关《C++程序设计--对象分册(第7章).ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第7章章 标准模板库标准模板库STL介绍及应用介绍及应用 n本章学习重点掌握内容：本章学习重点掌握内容：n标准模板库标准模板库STL的基本概念的基本概念 n标准模板库标准模板库STL的组成部分的组成部分n命名空间的概念及使用命名空间的概念及使用n容器的概念和使用容器的概念和使用 n迭代器的概念和使用迭代器的概念和使用n算法的概念和使用算法的概念和使用n标准模板库标准模板库STL的应用的应用 12/17/20221第第7章章 标准模板库标准模板库STL介绍及应用介绍及应用n7.1 标准模板库标准模板库STL的概念的概念 n7.2 命名空间命名空间 n7.3 容器（容器（Container）n7

2、.4 迭代器（迭代器（Iterator）n7.5 算法（算法（Algorithm）n7.6 综合应用实例综合应用实例 12/17/202227.1 标准模板库标准模板库STL的概念的概念 nSTL最初是由惠普实验室开发的一系列组件，是标准C+库的重要补充之一。n从逻辑层次来看，STL体现了泛型程序设计的思想，引入了多个新的名词，比如容器、算法、迭代器等。n在STL中，几乎所有的代码都采用了类模板和函数模板的方式，因而，提供了更好的代码重用机会。n从广义上讲，STL的代码分为三类：容器、迭代器和算法。这3类代码被组织为13个头文件。12/17/202237.1.2 STL和和C+标准的关系标准的

3、关系输入输入/输输出出数值数值诊断诊断通用工具通用工具国际化国际化语言支持语言支持容器容器算法算法迭代器迭代器字符串字符串STLC+标准库标准库C标标准准函函数数STL和和C+标准库的关系标准库的关系12/17/202247.1.3 STL组成部分组成部分函数对象函数对象通用算法通用算法assistSTL容器容器迭代器迭代器supportsapply toaccessuseuse STL结构图结构图12/17/202257.1.3 STL组成部分组成部分n1容器 能够保存其它类型的对象的类。C+的容器可以包含混合类型的对象，也就是说容器类可以包含一组相同类型或一组不同类型的对象。当容器类包含相

4、同类型的对象时，称为同类容器类；当容器类包含不同类型的对象时，称为异类容器类。n2迭代器 迭代器从作用上来说是STL最基本的部分，但理解起来比较困难。简单的说，迭代器是指针的泛化，它允许程序员以相同的方式处理不同的数据结构（容器）。迭代器是算法访问容器的中介。12/17/202267.1.3 STL组成部分组成部分n3算法 一个按照一组定义明确的步骤来解决某个问题的处理过程，理论上，它不依赖于任何特定的计算机编程语言。STL提供了大约70个实现算法的函数模板。n4函数对象 所谓函数对象是定义了函数调用操作符的对象。在使用STL时，经常需要把函数对象作为算法的输入参数或实例化一个容器(conta

5、iner)时的输入参数。12/17/202277.1.4 STL对对C+的影响的影响n在STL之前，C+支持三种基本的编程样式面向过程编程、数据抽象和面向对象编程。n在STL出现之后，C+可以支持一种新的编程模式泛型程序设计。nSTL并不完美，但是，它开辟了程序设计的新天地，它拥有的影响力甚至于超过了巨大的C+群体。12/17/202287.2 命名空间命名空间 n在实际开发过程中，经常需要引入对象、函数、类、类型或其它的全局实体。在同一个项目中，即使不在同一个文件中定义或声明，这些全局实体也必须有一个唯一的名字。n这也意味着当程序员使用开发商提供的库时必须保证程序中的全局实体不和开发商提供的

6、库中的全局实体名字冲突，这将是一件非常枯燥和困难的事情。n为了解决名字冲突的问题，C+引入命名空间机制。12/17/202297.2.1 命名空间的定义命名空间的定义定义命名空间的语法格式如下：namespace 命名空间名 声明序列 其中，namespace是关键字，后面是命名空间名。命名空间名必须在它被定义的作用域中具有唯一的名字，否则会产生错误。在命名空间名后一对花括号“”括起来的是声明序列。所有可以出现在全局作用域的定义或声明都可以放在其中。12/17/2022107.2.1 命名空间的定义命名空间的定义namespace myNameSpace string myStr=myStr;

7、class myClass public:myClass();/类的其它部分 ;void myFunc()int myCount=0;extern exFun();/其它实体定义或声明12/17/2022117.2.1 命名空间的定义命名空间的定义 定义或使用命名空间需要注意下面几个方面：（1）namespace只能在全局范畴定义，但它们之间可以互相嵌套，即在命名空间定义内容定义一个新的命名空间。（2）在namespace定义的结尾，大括号的后面不必要跟一个分号。（3）一个namespace可以在多个头文件中用一个标识符来定义。（4）一个namespace的名字可以用另一个名字做它的别名。（5

8、）不能像类那样去创建一个命名空间的实例。（6）可以通过多次声明和定义同一命名空间，把新的成员名称加入到已有的命名空间之中去。12/17/2022127.2.2 命名空间的使用命名空间的使用 对命名空间中成员的引用，需要使用命名空间的域操作符:。【例7.1】使用命名空间的例子。#include#include using namespace std;/两个在不同命名空间中定义的名字相同的变量namespace mySpace1/自定义命名空间 string myStr=myStr1;namespace mySpace2 string myStr=myStr2;12/17/2022137.2.2

9、命名空间的使用命名空间的使用void main()/用命名空间域操作符mySpace1:访问变量myStr coutHello,mySpace1:myStr.goodbye!endl;/用命名空间域操作符mySpace2:访问变量myStr coutHello,mySpace2:myStr.goodbye!endl;12/17/202214n为了避免麻烦，可以使用C+的using编译指令来简化对命名空间中的名称的使用。语法格式为：using namespace 命名空间名:命名空间名;中括号中的可选部分是指定命名空间中嵌套的子命名空间时使用的。有了using指令后，在编写程序时就可以使用usi

10、ng指令，而不用每次都使用“命名空间名:”来限定要访问的实体。7.2.2 命名空间的使用命名空间的使用12/17/202215#include#include using namespace std;namespace myNameSpace1 string myStr1=myStr1;namespace myNameSpace2 string myStr2=myStr2;using namespace myNameSpace1;using namespace myNameSpace1:myNameSpace2;void main()coutHello,myStr1.goodbye!endl;

11、coutHello,myStr2.goodbye!endl;【例7.2】用using指令使用命名空间的例子。12/17/2022167.2.3 无名空间无名空间 有时，定义的全局实体只在程序的一小段代码中使用，有时，定义的全局实体只在程序的一小段代码中使用，而在其它地方不会使用。为了保证这些全局实体不和而在其它地方不会使用。为了保证这些全局实体不和项目其它地方的全局实体冲突，可以使用无名空间。项目其它地方的全局实体冲突，可以使用无名空间。无名空间声明的语法格式如下：无名空间声明的语法格式如下：namespace 声明序列声明序列 namespace后不跟命名空间名字，直接用一对后不跟命名空间名

12、字，直接用一对“”括住声明序列，就定义了一个无名空间。括住声明序列，就定义了一个无名空间。12/17/2022177.2.3 无名空间无名空间 【例7.3】使用无名空间的例子。#include#include using namespace std;namespace void func1()cout调用了func1()endl;void func2()cout调用了func2()endl;void main()cout测试无名空间的例子!endl;func1();/无名空间中定义的函数 func2();/无名空间中定义的函数12/17/202218 标准C+库中的所有组件都定义在一个称为st

13、d 的命名空间中，因此，std又称为标准命名空间。在编写程序时，如果需要使用标准C+的组件，在包含相应的标准C+头文件后，可以采用下面几种方法使用头文件中声明的函数对象、类模板等。（1）使用域操作符std:（2）使用编译指令using namespace std;（3）使用编译指令using namespace std:进行更具体的限制，如using namespace std:string。7.2.3 标准命名空间标准命名空间std12/17/2022197.3 容器（容器（Container）7.3.1 容器简介 容器是能够保存其它类型的对象的类。C+的容器可以包含混合类型的对象，也就是说

14、容器类可以包含一组相同类型或一组不同类型的对象。容器类包含相同类型的对象时，称为同类容器类；容器类包含不同类型的对象时，称为异类容器类。容器类库共包括十种容器，分为三大类，分别如下：（1）顺序容器：向量、双队列、列表；（2）关联容器：集合、多重集、映射和多重映射；（3）容器适配器：堆栈、队列和优先队列。12/17/2022207.3 容器（容器（Container）根据使用迭代器的不同可以将容器分为4类：（1）前向容器：一种采用前向迭代器的容器，它和容器相比没有什么区别，只是前向容器只能使用前向迭代器。（2）双向容器：双向容器继承于前向容器，它除了具有前向迭代器外，还具有逆向迭代器。可以双向访

15、问容器中的元素。（3）序列容器：序列是一种长度可变的容器，向量中的元素按照线性关系排列和存储。它直接继承于前向容器。（4）关联容器：关联容器也是一种长度可变的容器，它支持高效的数据查询和数据操作。它由前向容器衍生而来。12/17/2022217.3 容器（容器（Container）容器名描述类型头文件向量连续存储元素的数组。顺序容器列表由结点组成的双向链表，每个结点包含一个元素顺序容器双队列连续存储的指向不同元素的指针所组成的数组。顺序容器集合由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元素对的谓词排列，没有两个不同的元素能够拥有相同的次序。关联容器多重集合允许存在两个次

16、序相等的元素的集合。关联容器12/17/202222容器名描述类型头文件栈后进先出的值的排列。容器适配器队列先进先出的值的排列。容器适配器优先队列元素的次序是由作用于所存储的值对上的某种谓词决定的一种队列。容器适配器映射由键，值对组成的集合，以某种作用于键对上的谓词排列。关联容器多重映射允许键对有相等的次序的映射。关联容器7.3容器（容器（Container）12/17/2022237.3.2 容器的结构容器的结构 所有的STL容器都是定义在命名空间std中的一个模板类，由、和七个头文件给出。主要包括下面3个方面。n1.常用的类型n2.常用的函数n3.vector和list基本结构 12/17

17、/202224类型名值的类型描述value_type值类型容器中存放元素的类型size_type长度用于计算容器中项目数和检索顺序容器的类型（不能对list检索）difference_type距离引用相同容器的两个迭代器相减结果的类型（list和关联容器没有定义operator-）iterator迭代器指向容器中存放元素类型的迭代器const_iterator常迭代器指向容器中存放元素类型的常量迭代器，只能读取容器中的元素7.3.2 容器的结构容器的结构 顺序容器和关联容器中常用的typedef 12/17/202225reverse_iterator逆向迭代器指向容器中存放元素的逆向迭代器，

18、这种迭代器在容器中逆向迭代const_reverse_iterator常逆向迭代器指向容器中存放元素类型的常逆向迭代器，只能读取容器中的元素pointer指针容器中存放元素类型的指针const_pointer常指针容器中存放元素类型的常量指针，这种指针只能读取容器中的元素和进行const操作reference引用容器中存放元素类型的引用const_reference常引用容器中存放元素类型的常量引用，这种引用只能读取容器中的元素和进行const操作7.3.2 容器的结构容器的结构 12/17/2022267.3.2 容器的结构容器的结构 容器中共用的函数 函数名功能描述备注默认构造函数提供容器

19、默认初始化的构造函数拷贝构造函数将容器初始化为现有同类容器副本的构造函数析构函数不再需要容器时进行内存整理的析构函数empty（）容器中没有元素时返回true,否则返回falsemax_size（）返回容器中最大元素个数size（）返回容器中当前元素个数operator=将一个容器赋给另一个容器12/17/202227operator如果第一个容器小于第二个容器，返回true，否则返回false不适用于priority_queueoperator如果第一个容器大于第二个容器，返回true，否则返回false不适用于priority_queueoperator=如果第一个容器大于或等于第二个容器

20、，返回true，否则返回false不适用于priority_queueoperator=如果第一个容器等于第二个容器，返回true，否则返回false不适用于priority_queueoperator!=如果第一个容器不等于第二个容器，返回true，否则返回false不适用于priority_queueswap（b）交换两个容器的元素7.3.2 容器的结构容器的结构 12/17/202228顺序容器和关联容器共用的函数 函数名功能描述备注begin（）有两个版本返回iterator或const_ iterator，引用容器第一个元素不适用于容器适配器end（）有两个版本返回iterator或

21、const_ iterator,引用容器最后一个元素后面一位不适用于容器适配器rbegin（）有两个版本返回reverse_iterator或const_reverse_iterator,引用容器最后一个元素不适用于容器适配器rend（）有两个版本返回reverse_iterator或const_reverse_ iterator，引用容器第一个元素前面一位不适用于容器适配器erase(p,q)erase（p）从容器中清除一个或几个元素不适用于容器适配器clear（）清除容器中所有元素不适用于容器适配器12/17/2022297.3.2 容器的结构容器的结构（1）向量）向量vector定义定义

22、12/17/2022307.3.2 容器的结构容器的结构（2）列表）列表list定义定义12/17/2022317.3.3 容器的使用容器的使用 使用容器就像使用一个类模板一样，只不过这个类模板是属于C+标准库的。【例7.4】list容器完整的程序。本例子初始化一个list的非空实例，然后将list中的元素值打印出来。12/17/2022327.4迭代器（迭代器（Iterator）迭代器从作用上来说是STL最基本的部分，但理解起来比较困难。简单的说，迭代器是指针的泛化，它允许程序员以相同的方式处理不同的数据结构（容器）。迭代器部分主要由头文件、和组成。随机存取迭代器随机存取迭代器双向迭代器双向

23、迭代器前向迭代器前向迭代器输出迭代器输出迭代器输入迭代器输入迭代器迭代器关系迭代器关系12/17/2022337.4.1 输入迭代器输入迭代器输入迭代器只能够从一个序列中读取数值，它可以被修改、引用和进行比较。输入迭代器支持6种操作。（1）+i：前置自增迭代器。（2）i+：后置自增迭代器。（3）*i：引用迭代器，作为右值。（4）i1=i2：将一个迭代器赋值给另一个迭代器。（5）i1=i2：比较迭代器相等性。（6）i1!=i2：比较迭代器不等性。12/17/202234元素元素n元素n1 元素n2 元素n3 元素n4输入迭代器工作原理输入迭代器工作原理i+7.4.1 输入迭代器输入迭代器12/1

24、7/202235template InputIterator find(InputIterator first,InputIterator last,const T&value)while(first!=last&*first!=value)+first;return first;7.4.1 输入迭代器输入迭代器12/17/202236 输出迭代器只能够向一个序列写入数据，它可以被修改和引用。通常用于将数据从一个位置拷贝到另一个位置。除了具有输入迭代器的所有功能外，输出迭代器还具有一个操作*i：复引用迭代器，作为左值。7.4.2 输出迭代器元素n元素元素n1元素元素n2元素元素n3元素n4输出

25、迭代器工作原理输出迭代器工作原理i+12/17/202237【例7.5】一个关于输出迭代器的例题。7.4.2 输出迭代器12/17/202238 前向迭代器（forward iterators）既可以用来读也可以用来写，并能够保存迭代器的值，以便从其原先位置开始重新遍历。它能够向前推进到下一个值，但不能递减，它包含了输入和输出迭代器的所有操作。7.4.3 前向迭代器前向迭代器 元素元素n元素元素n1元素元素n2元素元素n3元素元素n4前向迭代器工作原理前向迭代器工作原理i+12/17/2022397.4.3 前向迭代器前向迭代器前向迭代器的例子template void fill(Forwar

26、dIterator first,ForwardIterator last,const T&x);long*p=new int100;fill(p,p+10,0);fill(p+11,p+100,10);上面代码使用前向迭代器将数组p的前10个元素赋值为0，后90个元素赋值为10。12/17/2022407.4.4 双向迭代器 双向迭代器（bidirection iterators）既可以读又可以写，它与前向迭代器类似，除了具有前向迭代器的所有操作外，双向迭代器还具有下面两种操作。（1）-i：前置自减迭代器；（2）i-：后置自减迭代器。元素元素n元素元素n1元素元素n2元素元素n3元素元素n4双

27、向迭代器工作原理双向迭代器工作原理i+i-12/17/2022417.4.5 随机存取迭代器 随机存取迭代器（random access iterator）可以通过跳跃的方式访问容器种的任意数据，从而使数据的访问非常灵活。它除了具有双向迭代器的所有操作外，还具有9种操作：（1）i+=x：将迭代器i递增x位；（2）i-=x：将迭代器i递减x位；（3）i+x：在i位加x位后的迭代器；（4）i-x：在i位减x位后的迭代器；（5）ix：返回偏离i位元素x位的元素引用；（6）i1i2：如果迭代器i1小于i2（即容器中迭代器i1在迭代器i2之前），则返回true，否则返回false；12/17/20224

28、27.4.5 随机存取迭代器随机存取迭代器（7）i1i2：如果迭代器1i大于i2（即容器中迭代器i1在迭代器i2之后），则返回true，否则返回false；（9）i1=i2：如果迭代器i1大于或等于i2，则返回true，否则返回false；元素元素n元素元素n1元素元素n2元素元素n3 元素元素n4随机存取迭代器工作原理随机存取迭代器工作原理i+=xi-=x12/17/2022437.4.6 迭代器的使用迭代器的使用 【例7.6】从标准输入读入5个整数，使用输出迭代器输出这5个整数。然后使用STL通用算法sort()对vector中的元素排序，再输出排序后vector中元素。12/17/202

29、2447.5算法（算法（Algorithm）7.5.1算法和函数对象 广义上讲，算法是一个按照一组定义明确的步骤来解决某个问题的处理过程。所有算法的前两个变量都是一对迭代器，通常称为首（first）和末（last）迭代器，用来表明算法对容器进行操作的元素范围。元素范围是一个区间fist,last)，它表示范围从first（包含first指向的元素）开始，到last结束（不包含last指向的元素）函数对象是函数的一般形式。实际上函数对象是一个重载了operator()的类。12/17/2022457.5.1 算法和函数对象算法和函数对象函数对象函数对象类型类型函数对象函数对象类型类型函数对象函数

30、对象类型类型divides算术算术less_equal关系关系modulus算术算术equal_to关系关系logical_and逻辑逻辑negate算术算术greater关系关系logical_not逻辑逻辑not_equal_to关系关系greater_equal关系关系logical_or逻辑逻辑plus算术算术less关系关系minus算术算术multiplies算术算术STL中的函数对象中的函数对象 12/17/2022467.5.1 算法和函数对象算法和函数对象 【例例7.7】函数对象的使用方法例题。函数对象的使用方法例题。12/17/2022477.5.2 算法分类介绍算法分类介

31、绍 STL提供了70个算法，按照不同的分类方法可以将这些算法分成不同的类别：（1）按照算法所做工作的不同，可以将算法分成8个种类：查找、排序、数值计算、比较、集合、容器管理、统计和堆操作。（2）按照算法对容器的影响，可以将算法分成4个种类：非修正算法、修正算法、排序算法和数值计算算法。12/17/2022487.5.2 算法分类介绍算法分类介绍 1非修正算法 非修正算法的操作不对变容器中的元素进行任何修改，这类算法包括adjacent_find()、find()、find_end()、find_first()、count()、mismatch()、equal()、for_each()和sear

32、ch()等，这些算法都包含在头文件中。【例7.8】非修正算法例题。12/17/2022497.5.2 算法分类介绍算法分类介绍2修正算法 在实际应用中，经常需要对容器中的元素进行修改和写操作，这类能够对容器中元素进行修改的算法称为修正算法。修正算法包括copy()、copy_backward()、fill()、generate()、partition()、random_shuffle()、remove()、replace()、rotate()、reverse()、swap()、swap_ranges()、transform()和unique()等【例例7.9】修正算法例题。12/17/2022

33、507.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_i

34、ntersection()、set_difference()、set_symmetric_difference()、min()、min_element()、max()、max_element()、lexicographica;_compare()、next_permutation()和prev_permutation()等。12/17/202251【例7.10】排序算法例题7.5.2 算法分类介绍12/17/2022527.5.2 算法分类介绍4数值计算算法 数值计算算法主要是对容器中的元素进行数值计算。这类算法包括accumulate()、inner_product()、partial_sum()、adjacent_difference()和一些推广的数值算法。12/17/2022537.6 综合应用实例综合应用实例【实例一实例一】排序基本实现算法例题。排序基本实现算法例题。12/17/2022547.6 综合应用实例综合应用实例【实例二实例二】部分使用部分使用STL容器和算法实现容器和算法实现的排序例题的排序例题 12/17/2022557.6 综合应用实例综合应用实例【实例三实例三】全部使用全部使用STL容器和算法实现容器和算法实现的排序例题。的排序例题。12/17/202256