泛型程序设计与C STL简介

泛型程序设计与C++STL简介本章主要内容泛型程序设计及概念和术语C++STL中的容器迭代器标准C++库中的算法简介函数对象2泛型程序设计及概念和术语泛型程序设计泛型程序设计是继面向对象程序设计之后的又一种程序设计方法。泛型程序设计就是让程序写得通用，能够适用于各种数据类型与数据结构，并且并不损失程序效率。面向对象与泛型程序设计这两种程序设计方法并不矛盾，而是相得益彰。标准模板库(StandardTemplateLibrary，简称STL)是建立在C++中模板机制上的泛型程序设计思想的实现。34标准模板库相关概念和术语容器容器是存放其他对象的对象。比如我们常见的C++内置数组，从广义上讲也属于一种容器。容器可以存放同一种类型的一组元素或对象，称为同类容器类（homogenousconstainer）；或者存放不同类型的的元素或对象时，称为异类容器类（heterogenousconstainer）。对于STL容器库，其包含了两类容器，一种为顺序容器（sequencecontsainer），另一种为关联容器（associativecontainer）。迭代器在C++中，我们经常使用指针。而迭代器就是相当于指针，它提供了一种一般化的方法使得C++程序能够访问不同数据类型的顺序或者关联容器中的每一个元素，我们可以称它为“泛型指针”。STL定义了五种迭代器类型，前向迭代器（forwarditerator），双向迭代器(bidirectionaliterator)，输入迭代器(inputiterator)，输出迭代器(outputiterator)，随机访问迭代器(randomaccessiterator)。泛型程序设计及概念和术语5标准模板库相关概念和术语算法算法是STL中的核心，它它包含了70多个通用算法。可以分为四类：不可变序列算法（non-modifyingsequencealgorithms）、可变序列算法(mutatingsequencealgorithms)、排序及相关算法(sortingandrelatedalgorithms)和算术算法（numericalgorithms）。函数对象函数对象是STL提供的四种组件中的一种，它是定义了操作符【operator()】的对象。在C++中，除了定义了操作符operator()的对象之外，普通函数或者函数指针也满足函数对象的特征。结合函数模板的使用，函数对象使得STL更加灵活和方便，同时也使得代码更为高效。本章在15.5小节将单独介绍函数对象。泛型程序设计及概念和术语6标准模板库相关概念和术语适配器(adapter)适配器是一种接口类，可以认为是标准组件的改装。通过修改其它类的接口，使适配器满足一定需求，可分为容器适配器、迭代器适配器和函数对象适配器三种。分配器(allocator)分配器是STL提供的一种内存管理类模块。每种STL容器都是用了一种分配器类，用来封装程序所用的内存分配模式的信息。不同的内存分配模式采用不同的方法从操作系统中检索内存。分配器类可以封装许多方面的信息，包括指针、常量指针、引用、常量引用、对象大小、不同类型指针之间的差别、分配函数与释放函数、以及一些函数的信息。分配器上的所有操作都具有分摊常量的运行时间。泛型程序设计及概念和术语7标准模板库相关概念和术语容器接口STL为容器提供了一些公共接口，这些公共接口是通用的，也可以说是泛型的。这些都是容器设计的规范，对于容器而言，定义的公共接口主要有以下几个部分：泛型程序设计及概念和术语通用运算说明a==b同类容器的相等比较操作，判断是否相等，相等则为truea!=b同类容器的不等比较操作，判断是否不等，不等则为trueab两个容器大小判断，首先判断size，接着判断元素值，ab则trueab与上同，不过ab时为truea=b等同于！（ab）a=b等同与！（ab）r=b赋值操作8容器接口泛型程序设计及概念和术语迭代方法说明begin（）返回一个指向容器第一个元素的迭代器end（）返回一个指向容器末尾元素的迭代器rbegin（）返回一个逆向迭代器，指向反序后的首元素rend（）返回一个逆向迭代器，指向反序后的末尾元素所有容器定义的迭代器访问接口9容器接口泛型程序设计及概念和术语其他访问接口操作说明Size()返回容器元素个数Max_size()返回容器最大的规模Empty()判断容器是否为空，是，则返回trueSwap（）交换两个容器的所有元素10顺序容器顺序容器顺序容器包含Vector，deque和list三种容器，其中vector和deque属于直接访问容器，list属于顺序访问容器。向量（vector）向量相当于一个动态数组，其可以动态存储元素，并提供对容器元素的随机访问。为了提高效率，vector并不是随着每一个元素的插入而增长自己，而是当vector要增长自己的时候，他分配的空间比当前所需的空间要多一些。这多一些的内存空间使需要添加新元素的时候不必再重新分配内存。与C++的内置数组相比较，除了动态之外，向量容器支持向对象。C++STL中的容器11例15-1：建立一个整型向量容器#includeiostream#includevector//使用向量容器须包含的头文件#includeiomanipusingnamespacestd;constintn=5;intmain(){intarray[n]={12,4,5,9,1};vectorintvec1;//构造1：定义一个空的整型向量容器vec1inti;for(i=0;in;i++)//赋值{//vec1[i]=array[i];//错误,因为vec1还没有分配内存空间vec1.push_back(array[i]);//压入向量尾部}vectorintvec2(vec1);//构造2：拷贝构造vec2vectorintvec3(array,array+3);//构造3：用array到array+3的值初始化vectorintvec4(n,3);//构造4：用n个3初始化向量C++STL中的容器12例1：建立一个整型向量容器for(i=0;in;i++){coutsetw(5)vec1[i];}coutendl;for(i=0;in;i++){coutsetw(5)vec2[i];}coutendl;for(i=0;i3;i++){coutsetw(5)vec3[i];}coutendl;for(i=0;in;i++){coutsetw(5)vec4[i];}coutendl;}C++STL中的容器124591124591124533333运行结果：C++STL中的容器1314例2：向量容器中元素的添加和删除#includeiostream#includevector#includeiomanip#includestringusingnamespacestd;voiddisplay(vectorstring&_str){//向量元素显示函数coutthereare_str.size()elementsinthevector.endl;for(inti=0;i_str.size();i++)coutsetw(15)_str[i];//逐个显示元素coutendl;};C++STL中的容器15例2：向量容器中元素的添加和删除intmain(){stringstr[3]={Hello,C++,Love};vectorstringvec1;//将str至str+3之间的元素插入vec1，vec1.insert(vec1.begin(),str,str+3);vectorstringvec2;//将vec1.begin()至vec1.end()之间的元素插入到vec2，等效于将vec1复制到vec2中，vec2.insert(vec2.end(),vec1.begin(),vec1.end());vec2.insert(vec2.begin(),1,welcomtoC++);//在vec2.begin()前插入字符串display(vec1);display(vec2);vec1.clear();//清除整个vec1display(vec1);vec2.erase(vec2.begin());//删除vec2的首元素display(vec2);vec2.pop_back();//删除vec2的末尾元素display(vec2);}C++STL中的容器thereare3elementsinthevector.HelloC++Lovethereare4elementsinthevector.welcomtoC++HelloC++Lovethereare0elementsinthevector.thereare3elementsinthevector.HelloC++Lovethereare2elementsinthevector.HelloC++运行结果：C++STL中的容器1617例3：向量容器中元素的添加和删除#includeiostream#includevector#includeiomanip#includestringusingnamespacestd;intmain(){intarray[4]={2,3,5,2};vectorintnval;coutnval'ssizeis:nval.size()andthecapacityis:nval.capacity()endl;for(inti=0;i17;i++){nval.push_back(i);if(!(i%4)){coutnval'ssizeis:nval.size()andthecapacityis:nval.capacity()endl;}}}C++STL中的容器nval'ssizeis:0andthecapacityis:0nval'ssizeis:1andthecapacityis:1nval'ssizeis:5andthecapacityis:6nval'ssizeis:9andthecapacityis:9nval'ssizeis:13andthecapacityis:13nval'ssizeis:17andthecapacityis:19运行结果：C++STL中的容器1819例4：复杂对象的向量容器#includeiostream#includestring#includevector#includeiomanipusingnamespacestd;constintn=6;structEvaluate{//结构体，stringName;//学生的姓名doubleRank;//学生的排名};voiddisplay(vectorEvaluate&_student)//显示排名情况{if(!_student.empty()){//如果不空则显示for(inti=0;i_student.size();i++)cout_student[i].Name'srankissetw(5)_student[i].Rankendl;}}C++STL中的容器20例4：复杂对象的向量容器intmain(){stringname[n]={John,Lily,David,Jevons,Mike,Jane};vectorstringNameSet;vectorintrank(n,0);//初始化一个大小为n，元素都为0的向量NameSet.insert(NameSet.begin(),name,name+n);inti;for(i=0;in;i++){coutPleaseenterNameSet[i