《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) 由节点组成的红黑树,每个