《C++教程教学课件 PPT 作者 郑莉 李宁 15_泛型程序设计与C++STL简介》由会员分享，可在线阅读，更多相关《C++教程教学课件 PPT 作者 郑莉 李宁 15_泛型程序设计与C++STL简介（77页珍藏版）》请在金锄头文库上搜索。
1、第十五章 泛型程序设计与C+STL简介,清华大学 郑 莉,学习目标,掌握泛型程序设计思想以及概念； 掌握STL中顺序容器的使用，了解关联容器； 掌握迭代器的使用； 了解泛型算法和函数对象。,2,目录,15.1 泛型程序设计的概念和术语 15.1.1 泛型程序设计 15.1.2 STL的相关概念和术语 15.2 C+STL中的容器 15.2.1 顺序容器 15.2.2 关联容器 15.2.3 容器适配器,3,目录（续）,15.3 迭代器 15.3.1 迭代器的分类 15.3.2 迭代器适配器 15.3.3 迭代器相关的辅助函数 15.4 标准C+库中的算法简介 15.4.1 非可变序列算法 15
2、.4.2 可变序列算法 15.4.3 排序及相关算法,4,目录（续）,15.4 标准C+库中的算法简介 15.4.4 数值算法 15.5 函数对象 15.5.1 函数对象 15.5.2 函数适配器,5,15.1.1 泛型程序设计,泛型程序设计是继面向对象程序设计之后的又一种程序设计方法。 泛型程序设计就是让程序写得通用，能够适用于各种数据类型与数据结构，并且并不损失程序效率。面向对象与泛型程序设计这两种程序设计方法并不矛盾，而是相得益彰。 标准模板库( Standard Temp late L ibrary，简称STL)是建立在C+中模板机制上的泛型程序设计思想的实现。,6,15.1 泛型程序
3、设计的概念和术语,15.1.2 标准模板库相关概念和术语,容器 容器是存放其他对象的对象。比如我们常见的C+内置数组，从广义上讲也属于一种容器。容器可以存放同一种类型的一组元素或对象，称为同类容器类（homogenous constainer）；或者存放不同类型的的元素或对象时，称为异类容器类（heterogenous constainer）。对于STL容器库，其包含了两类容器，一种为顺序容器（sequence contsainer），另一种为关联容器（associative container）。 迭代器 在C+中，我们经常使用指针。而迭代器就是相当于指针，它提供了一种一般化的方法使得C+程
4、序能够访问不同数据类型的顺序或者关联容器中的每一个元素，我们可以称它为“泛型指针”。 STL定义了五种迭代器类型，前向迭代器（forward iterator），双向迭代器(bidirectional iterator)，输入迭代器(input iterator)，输出迭代器(output iterator)，随机访问迭代器(random access iterator)。,7,15.1 泛型程序设计的概念和术语,15.1.2 标准模板库相关概念和术语,算法 算法是STL中的核心，它它包含了70多个通用算法。可以分为四类：不可变序列算法（non-modifying sequence algor
5、ithms）、可变序列算法(mutating sequence algorithms)、排序及相关算法(sorting and related algorithms)和算术算法（numeric algorithms）。 函数对象 函数对象是STL提供的四种组件中的一种，它是定义了操作符【operator( )】的对象。在C+中，除了定义了操作符operator( )的对象之外，普通函数或者函数指针也满足函数对象的特征。结合函数模板的使用，函数对象使得STL更加灵活和方便，同时也使得代码更为高效。本章在15.5小节将单独介绍函数对象。,8,15.1 泛型程序设计的概念和术语,15.1.2 标准模
6、板库相关概念和术语,适配器(adapter) 适配器是一种接口类，可以认为是标准组件的改装。通过修改其它类的接口，使适配器满足一定需求，可分为容器适配器、迭代器适配器和函数对象适配器三种。 分配器(allocator) 分配器是STL提供的一种内存管理类模块。每种STL容器都是用了一种分配器类，用来封装程序所用的内存分配模式的信息。不同的内存分配模式采用不同的方法从 操作系统中检索内存。分配器类可以封装许多方面的信息，包括指针、常量指针、引用、常量引用、对象大小、不同类型指针之间的差别、分配函数与释放函数、以及一些函数的信息。分配器上的所有操作都具有分摊常量的运行时间。,9,15.1 泛型程序
7、设计的概念和术语,15.1.2 标准模板库相关概念和术语,容器接口 STL为容器提供了一些公共接口，这些公共接口是通用的，也可以说是泛型的。这些都是容器设计的规范，对于容器而言，定义的公共接口主要有以下几个部分：,10,15.1 泛型程序设计的概念和术语,15.1.2 标准模板库相关概念和术语,容器接口 所有容器定义的迭代器访问接口,11,15.1 泛型程序设计的概念和术语,15.1.2 标准模板库相关概念和术语,容器接口 其他访问接口,12,15.1 泛型程序设计的概念和术语,15.2.1 顺序容器,顺序容器 顺序容器包含Vector，deque和list三种容器，其中vector和dequ
8、e属于直接访问容器，list属于顺序访问容器。 向量（vector） 向量相当于一个动态数组，其可以动态存储元素，并提供对容器元素的随机访问。为了提高效率，vector并不是随着每一个元素的插入而增长自己，而是当vector要增长自己的时候，他分配的空间比当前所需的空间要多一些。这多一些的内存空间使需要添加新元素的时候不必再重新分配内存。与C+的内置数组相比较，除了动态之外，向量容器支持向对象。,13,15.2 C+STL中的容器,例15-1：建立一个整型向量容器,#include #include /使用向量容器须包含的头文件 #include using namespace std; co
9、nst int n=5; int main() int arrayn=12,4,5,9,1; vector vec1; / 构造1：定义一个空的整型向量容器vec1 int i; for(i=0; i vec2(vec1); / 构造2：拷贝构造vec2 vector vec3(array,array+3);/ 构造3：用array到array+3的值初始化 vector vec4(n,3);/ 构造4：用n个3初始化向量,14,15.2 C+STL中的容器15.2.1顺序容器,例15-1（续）,for(i=0; in; i+) coutsetw(5)vec1i; coutendl; for(
10、i=0; in; i+) coutsetw(5)vec2i; coutendl; for(i=0; i3; i+) coutsetw(5)vec3i; coutendl; for(i=0; in; i+) coutsetw(5)vec4i; coutendl; ,15,15.2 C+STL中的容器15.2.1顺序容器,运行结果： 12 4 5 9 1 12 4 5 9 1 12 4 5 3 3 3 3 3,例15-1（续）,15.2 C+STL中的容器15.2.1顺序容器,16,例15-2：向量容器中元素的添加和删除,#include #include #include #include us
11、ing namespace std; void display(vector,17,15.2 C+STL中的容器15.2.1顺序容器,例15-2（续）,int main() string str3=“Hello“, “C+“, “Love“; vector vec1; /将str至str+3之间的元素插入vec1， vec1.insert(vec1.begin(),str,str+3); vector vec2; /将vec1.begin()至vec1.end()之间的元素插入到vec2，等效于将vec1复制到vec2中， vec2.insert(vec2.end(),vec1.begin()
12、,vec1.end(); vec2.insert(vec2.begin(),1,“welcom to C+“);/在vec2.begin()前插入字符串 display(vec1); display(vec2); vec1.clear();/清除整个vec1 display(vec1); vec2.erase(vec2.begin();/删除vec2的首元素 display(vec2); vec2.pop_back();/删除vec2的末尾元素 display(vec2); ,18,15.2 C+STL中的容器15.2.1顺序容器,运行结果： there are 3 elements in t
13、he vector. Hello C+ Love there are 4 elements in the vector. welcom to C+ Hello C+ Love there are 0 elements in the vector. there are 3 elements in the vector. Hello C+ Love there are 2 elements in the vector. Hello C+,例15-2（续）,15.2 C+STL中的容器15.2.1顺序容器,例15-3：向量容器中元素的添加和删除,#include #include #include
14、#include using namespace std; int main() int array4=2,3,5,2; vector nval; cout“nvals size is:“nval.size() “ and the capacity is:“nval.capacity()endl; for(int i=0; i17; i+) nval.push_back(i); if(!(i%4) cout“nvals size is:“nval.size() “ and the capacity is:“nval.capacity()endl; ,20,15.2 C+STL中的容器15.2.
15、1顺序容器,运行结果： nvals size is:0 and the capacity is:0 nvals size is:1 and the capacity is:1 nvals size is:5 and the capacity is:6 nvals size is:9 and the capacity is:9 nvals size is:13 and the capacity is:13 nvals size is:17 and the capacity is:19,例15-3（续）,15.2 C+STL中的容器15.2.1顺序容器,例15-4：复杂对象的向量容器,#include #include #include #include using namespace std; const int n=6; struct Evaluate /结构体， string Name; /学生的姓名 double Rank; /学生的排名 ; void display(vector ,22,15.2 C+STL中的容器15.2.1顺序容器,例15-4（续）,int main() string namen=“John“,“Lily“,“David“,“Jevons“,“Mike“,“Jane“; vector NameSet; vector rank(n,0);/初始化一个
