15泛型程序设计与CSTL简介

《15泛型程序设计与CSTL简介》由会员分享，可在线阅读，更多相关《15泛型程序设计与CSTL简介（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.4.2 可变序列算法15.4.3 排序及相关算法4

2、目录（续）15.4 标准C+库中的算法简介15.4.4 数值算法15.5 函数对象15.5.1 函数对象15.5.2 函数适配器515.1.1 泛型程序设计 泛型程序设计是继面向对象程序设计之后 的又一种程序设计方法。 泛型程序设计就是让程序写得通用，能够 适用于各种数据类型与数据结构，并且并 不损失程序效率。面向对象与泛型程序设 计这两种程序设计方法并不矛盾，而是相 得益彰。 标准模板库( Standard Temp late L ibrary ，简称STL)是建立在C+中模板机制上的 泛型程序设计思想的实现。615.1.2 标准模板库相关概念和术语 容器 容器是存放其他对象的对象。比如我们

3、常见的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) 。715.1.2 标准模板库相关概念和术语 算法 算法是STL中的核心，它它包含了70多个通用算法。可 以分为四类：不可变序列算法（non-modifying sequence algorithms）、可变序列算法(mutating sequence algorithms)、排序及相关算法(sorting

5、 and related algorithms)和算术算法（numeric algorithms） 。 函数对象 函数对象是STL提供的四种组件中的一种，它是定义了 操作符【operator( )】的对象。在C+中，除了定义了 操作符operator( )的对象之外，普通函数或者函数指针 也满足函数对象的特征。结合函数模板的使用，函数 对象使得STL更加灵活和方便，同时也使得代码更为高 效。本章在15.5小节将单独介绍函数对象。815.1.2 标准模板库相关概念和术语 适配器(adapter) 适配器是一种接口类，可以认为是标准组件的改装。 通过修改其它类的接口，使适配器满足一定需求，可 分为

6、容器适配器、迭代器适配器和函数对象适配器三 种。 分配器(allocator) 分配器是STL提供的一种内存管理类模块。每种STL容 器都是用了一种分配器类，用来封装程序所用的内存 分配模式的信息。不同的内存分配模式采用不同的方 法从 操作系统中检索内存。分配器类可以封装许多方 面的信息，包括指针、常量指针、引用、常量引用、 对象大小、不同类型指针之间的差别、分配函数与释 放函数、以及一些函数的信息。分配器上的所有操作 都具有分摊常量的运行时间。915.1.2 标准模板库相关概念和术语 容器接口 STL为容器提供了一些公共接口，这些公共接口是通用 的，也可以说是泛型的。这些都是容器设计的规范，

7、 对于容器而言，定义的公共接口主要有以下几个部分 ：10通用运算说明 a=b同类容器的相等比较操作，判断是否相等，相等则 为true a!=b同类容器的不等比较操作，判断是否不等，不等则 为true ab与上同，不过ab时为true ab） a=b等同与！（a #include /使用向量容器须包含的头文件 #include using namespace std; const int n=5; int main() int arrayn=12,4,5,9,1;vector vec1;/ 构造1：定义一个空的整型向量容器vec1int i;for(i=0; i vec2(vec1); / 构造

8、2：拷贝构造vec2vector vec3(array,array+3);/ 构造3：用array到array+3的值初始化vector vec4(n,3);/构造4：用n个3初始化向量14例15-1（续）for(i=0; i #include #include #include using namespace std;void display(vector /将str至str+3之间的元素插入vec1， vec1.insert(vec1.begin(),str,str+3); vector vec2;/将vec1.begin()至vec1.end()之间的元素插入到vec2，等效于将vec1

9、复制到vec2中， vec2.insert(vec2.end(),vec1.begin(),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（续）运行结果：

10、 there are 3 elements in the 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-3：向量容器中元素的添加 和删除#include #include #include #include using

11、 namespace std; int main() int array4=2,3,5,2; vector nval; cout #include #include #include using namespace std; const int n=6; struct Evaluate /结构体， string Name;/学生的姓名 double Rank;/学生的排名 ; void display(vector i NameSet; vector rank(n,0);/初始化一个大小为n，元素都为0的向量 NameSet.insert(NameSet.begin(),name,name+n

12、);int i; for(i=0; iranki; vector Student;23例15-4（续）for(i=0; i Student2(Student);/调用向量的拷贝构造函数 cout Student3(Student2.begin(),Student2.end()-3); cout #include /使用deque需要包含的头文件 #include using namespace std; const int n=10; int main() deque de; int arrayn=10,1,3,4,5,7,2,9,8,6;int i; for(i=0; i #include

13、/使用deque需要包含的头文件 #include using namespace std; const int n=10; int main() deque de; int arrayn=10,1,3,4,5,7,2,9,8,6;int i; for(i=0; i #include /使用list需要包含的头文件 #include using namespace std; const int n=10;void display (list _list) if(!_list.empty() list:iterator it; for(it=_list.begin();it!=_list.end

14、(); it+) cout list1; list1.insert(list1.begin(),array,array+n); display(list1); list list2=list1; for(int i=0;i #include #include using namespace std; const int n=5;void display (list _list) if(!_list.empty() list:iterator it; for(it=_list.begin();it!=_list.end(); it+) cout list1; list1.insert(list1

15、.begin(),array,array+n); display(list1); list1.sort(greater();/按降序排列，greater为降序函数对象display(list1); list1.sort();/升序排列 display(list1); list list2=list1; for(int i=0;i() display(list1); display(list2); list1.reverse();/逆序 display(list1); 35例15-7（续）运行结果： 2 7 5 3 3434 7 5 3 22 3 5 7 345 7 342 3 5 5 7 7 34 34 Null list34 34 7 7 5 5 3 23615.2.2 关联容器 映射（map） 映射提供了一个键/值对，基于键的查询，迅速 查找到键相对应的所需的值。如map map_name，其建立的是一个以Type1 为索引，Type2的值的查询。 集合（set） 由节点组成的红黑树，每个