C++STL泛型编程课件

1C++STL泛型编程

（GenericProgramming）2为什么要采用泛型编程？项目中,需要用到数组、链表、字符串、栈、队列、平衡二叉树等数据结构，以及排序、搜索等算法；若全部自行编写比较麻烦；ANSIC++中包含了C++STL(StandardTemplateLibrary,标准模板库,又称C++泛型库)，定义了常用的数据结构和算法，使用十分方便。有了STL，不必再从头写大多的标准数据结构和算法，并且可获得非常高的性能。但这不意味着我们不需要掌握基本数据结构与算法;相反,只有透彻理解了,才能更好的使用泛型!泛型程序设计由AlexanderStepanov和DavidMusser创立，于1998年被添加进C++标准.含义：编写不依赖于具体数据类型的程序.目标：将程序写得尽可能通用.将算法从特定的数据结构中抽象出来，成为通用的.C++的模板为泛型程序设计奠定了关键的基础.STL

(标准模板库,StandardTemplateLibrary)是泛型程序设计的一个范例.代码重用(reuse)!4函数模板模板函数的重载类模板堆栈类继承static成员友元模板函数模板简介5

【引例】交换2个整数和交换2个浮点数的C++程序://交换2个整数voidSwap(int&a,int&b){inttmp=0;tmp=a;a=b;b=tmp;}//交换2个浮点数voidSwap(float&a,float&b){floattmp=0.0;tmp=a;a=b;b=tmp;}intmain(){inta=10,b=20;floatc=1.2,d=2.4;cout<<"a="<<a<<"b="

<<b;cout<<"c="<<c<<"d="

<<c;

Swap(a,b);cout<<"a="<<a<<"

b="

<<b;

Swap(c,d);cout<<"

c="<<c<<"d="

<<c;return0;}

两个Swap函数实现的功能相同，只是参数类型不同，但为了实现不同类型的数据交换必须分别编写函数。造成了重复劳动。函数重载6

能否提供一种方法将两个函数合并，以节省开发成本？引例typedefintDataType;voidSwap(DataType&a,DataType&b){ DataTypetmp; tmp=a; a=b; b=tmp;}intmain(){inta=10,b=20;Swap(a,b);return0;}当需要交换两个浮点数时可以将DataType定义成float型数据即可。typedeffloatDateType;存在问题：

更改一种数据类型时，需要修改程序源代码，必须重新编译程序。如果程序中需要交换多种数据类型数据,怎么办？7引例#include<iostream>usingnamespacestd;template<classT>voidSwap(T&x,T&y){Ttmp=x;x=y;y=tmp;}voidmain(){inta=10,b=20;floatc=1.2,d=2.4;cout<<"a="<<a<<"b="<<b<<endl;cout<<"c="<<c<<"d="<<c<<endl;

Swap(a,b);cout<<"a="<<a<<"b="<<b<<endl;

Swap(c,d);cout<<"c="<<c<<"d="<<c<<endl;}模板声明定义函数模板通用的Swap!模板机制模板的概念模板是一种使用无类型参数来产生一系列函数或类的机制。模板是以一种完全通用的方法来设计函数或类而不必预先说明将被使用的每个对象的类型。通过模板可以产生类或函数的集合，使它们操作不同的数据类型，从而避免需要为每一种数据类型产生一个单独的类或函数。

8模板分类函数模板(functiontemplate)是独立于类型的函数可产生函数的特定版本类模板(classtemplate)与类相关的模板，如vector可产生类对特定类型的版本，如vector<int>9模板工作方式模板只是说明，需要实例化后才能执行或使用.10模板函数模板类模板模板类模板函数对象实例化实例化实例化函数模板(functiontemplate)定义格式：template<模板参数表>类型名函数名（参数表）{

函数体}template<classT>voidSwap(T&x,T&y){Ttmp=x;x=y;y=tmp;}11template:

函数模板定义关键字.<>中是函数的模板参数，参数可有一个或多个，逗号隔开。不能为空！

模板参数常用形式：

class标识符或者typename标识符模板参数表明函数可以接收的类型参数，可以是内部类型，也可以是自定义类型.

【例1】简单函数模板定义和应用.#include<iostream>usingnamespacestd;template<typenameT>TMax(Ta,Tb){returna>b?a:b;}intmain(){cout<<"Max(3,5)is"<<Max(3,5)<<endl;cout<<"Max('y','e')is"<<Max('y','e')<<endl;cout<<"Max(9.3,0.5)is"<<Max(9.3,0.5)<<endl;return0;}函数模板intMax(inta,intb){returna>b?a:b;}由实参类型实例化charMax(chara,charb){returna>b?a:b;}doubleMax(doublea,doubleb){returna>b?a:b;}编译器生成的模板函数函数模板实例化运行结果:Max(3,5)is5Max(‘y’,‘e’)isyMax(9.3,0.5)is9.3函数模板的原理分析：函数模板中声明了类型参数T，表示了一种抽象类型.

编译器检测到程序调用函数模板Max时，用其第一个实参类型替换掉模板中的T，同时建立一个完整的函数Max，并编译该新建的函数.

本例中，针对三种数据类型，生成了三种函数.

【练习1】编写一个对具有n个元素的数组a[]求最小值的程序，要求将求最小值的函数设计成函数模板。#include<iostream>usingnamespacestd;template<classT>TMinArray(Ta[],intn){ inti; Tmina=a[0]; for(i=1;i<n;i++){ if(mina>a[i]) mina=a[i]; } returnmina;}voidmain(){intarr1[]={1,3,0,2,7,6,4,5,2};doublearr2[]={1.2,-3.4,6.8,9,8};cout<<"arr1数组的最小值为："

<<MinArray(arr1,9)<<endl;cout<<"arr2数组的最小值为："

<<MinArray(arr2,4)<<endl;}运行结果:arr1数组的最小值为：0Arr2数组的最小值为:-3.4

注意点1：实参类型与形参类型必须严格匹配.#include<iostream>usingnamespacestd;template<classT>TMax(Ta,Tb){returna>b?a:b;}intmain(){inta=3;floatb=1.5;cout<<"Max(a,b)is"<<Max(a,b)<<endl;return0;}错误！模板类型不能提供类型的隐式转换注意点2：在函数模板中允许使用多个类型参数。在template定义部分的每个模板形参前必须有关键字class或typename.#include<iostream>usingnamespacestd;template<classT1,classT2>voidmyfunc(T1x,T2y){cout<<x<<","<<y<<endl;}运行结果:100,hao3.14,10voidmain(){myfunc(100,"hao");myfunc(3.14,10L);}

注意点3：在template语句与函数模板定义语句之间不允许有别的语句。Template<classT>inti;

TMax(Tx,Ty){return(x>y)?x:y;}8//错误，不允许有别的语句模板优缺点优点:函数模板方法克服了C语言用大量不同函数名表示相似功能的弊端;克服了宏定义不能进行参数类型检查的弊端;克服了C++函数重载用相同函数名字重写几个函数的繁琐.缺点:

调试比较困难.一般先写一个特殊版本的函数运行正确后，改成模板函数1718

【练习2】编写一个函数模板，它返回两个值中的较小者，同时要求能正确处理字符串。

分析：由于C++字符串比较的方法与字符型、数值型都不同，因此函数模板不适用于字符串比较；这里设计一个函数模板template<classT>Tmin(Ta,Tb)，可以处理int、float和char等数据类型；为了能正确处理字符串，添加一个重载函数专门处理字符串比较，即char*min(char*a,char*b)。#include<iostream>#include<string.h>

template<classT>Tmin(Ta,

Tb){

return(a<b?a:b);

}

char*min(char*a,char*b)

{

return(strcmp(a,b)<0?a:b);

}voidmain(){

doublea=3.14,b=8.28;chars1[]="Bad",s2[]="Good";cout<<"输出结果:"<<endl;

cout<<min(a,b)<<endl;

cout<<min(s1,s2)<<endl;}函数模板函数重载运行结果:3.14Bad20可以显式指定（explicitlyspecify），如：i=max<int>(ia,5);d=max<double>(da,6);用函数模板求数组元素中最大值template<classGroap>Groapmax(const

Groap*r_array,intsize){

inti;

Groapmax_val=r_array[0];for(i=1;i<size;++i)if(r_array[i]>max_val)max_val=r_array[i];

returnmax_val;}可读性更好。21函数模板可以重载,形参表不同即可例,下面两个模板可以同时存在:template<classT1,classT2>voidprint(T1arg1,T2arg2){cout<<arg1<<""<<arg2<<endl;}template<classT>voidprint(Targ1,Targ2){cout<<arg1<<""<<arg2<<endl;}重载22例:函数模板调用顺序23doubleMax(doublea,doubleb){cout<<"MyMax"<<endl;return0;}template<classT>TMax(Ta,Tb){cout<<"TemplateMax1"<<endl;return0;}template<classT,classT2>TMax(Ta,T2b){cout<<"TemplateMax2"<<endl;return0;}24voidmain(){inti=4,j=5;Max(1.2,3.4);Max(i,j);Max(1.2,3);}25匹配顺序C++编译器遵循以下优先顺序:Step1:先找参数完全匹配的普通函数(非由模板实例化而得的函数)Step2:再找参数完全匹配的模板函数

Step3:再找实参经过自动类型转换后能够匹配的普通函数

Step4:上面的都找不到,则报错26voidmain(){inti=4,j=5;Max(1.2,3.4);Max(i,j);Max(1.2,3);}//调用Max(double,double)函数//调用第一个TMax(Ta,Tb)模板生成的函数//调用第二个TMax(Ta,T2b)模板生成的函数运行结果:MyMaxTemplateMax1TemplateMax227可以在函数模板中使用多个类型参数,可以避免二义性template<classT1,classT2>T1myFunction(T1arg1,T2arg2){cout<<arg1<<“”<<arg2<<“\n”;returnarg1;}…myFunction(5,7);myFunction(5.8,8.4);myFunction(5,8.4);//ok：replaceT1andT2withint//ok:replaceT1andT2withdouble//ok:replaceT1withint,T2withdouble28类模板的定义C++的类模板的写法如下:template<类型参数表>class类模板名{成员函数和成员变量};类型参数表的写法就是:class类型参数1,class类型参数2,…29类模板里的成员函数,如在类模板外面定义时,template<类型参数表>返回值类型类模板名<类型参数名列表>::成员函数名(参数表){……}类模板的定义30用类模板定义对象的写法如下:类模板名<真实类型参数表>对象名(构造函数实际参数表);如果类模板有无参构造函数,那么也可以只写:类模板名<真实类型参数表>对象名;类模板的定义31Pair类模板:template<classT1,classT2>classPair{public:T1key;//关键字T2value;//值Pair(T1k,T2v):key(k),value(v){};booloperator<(constPair<T1,T2>&p)const;};template<classT1,classT2>boolPair<T1,T2>::operator<(constPair<T1,T2>&p)const//Pair的成员函数operator<{returnkey<p.key;}类模板的定义32#include<iostream>#include<string>usingnamespacestd;。。。。voidmain(){Pair<string,int>stu("Tom",19);Pair<string,int>stu2("Jack",20);if(stu.operator<(stu2))cout<<stu.key<<""<<stu.value;elsecout<<stu.key<<""<<stu2.value;}运行结果:Jack20Pair类模板的使用:33使用类模板声明对象编译器由类模板生成类的过程叫类模板的实例化

•编译器自动用具体的数据类型替换类模板中的类型参数,生成模板类的代码由类模板实例化得到的类叫模板类•为类型参数指定的数据类型不同,得到的模板类不同同一个类模板的两个模板类是不兼容的Pair<string,int>*p;Pair<string,double>a;p=&a;//wrong34#include<iostream>usingnamespacestd;template<classT>classA{public:

template<classT2>voidFunc(T2t){cout<<t;}};voidmain(){A<int>a;a.Func('K');}若函数模板改为template<classT>voidFunc(Tt){cout<<t}将报错“declarationof‘classT’shadowstemplateparm‘classT’”

程序输出:K//成员函数模板//成员函数模板Func被实例化函数模版作为类模板成员35template<classT>classA{public:template<classT2>voidFunc(T2t);};template<classT>template<classT2>voidA<T>::Func(T2t){cout<<t;}voidmain(){A<int>a;a.Func('K');}36类模板的参数声明中可以包括非类型参数

template<classT,intelementsNumber>•非类型参数:用来说明类模板中的属性•类型参数:用来说明类模板中的属性类型,成员操作的参数类型和返回值类型类模板与非类型参数37template<classT,intsize>classCArray{Tarray[size];public:voidPrint(){for(inti=0;i<size;++i)cout<<array[i]<<endl;}};类模板与非类型参数CArray<double,40>a2;CArray<int,50>a3;38CArray<double,40>a2;CArray<int,50>a3;注意:CArray<int,40>和CArray<int,50>完全是两个类这两个类的对象之间不能互相赋值类模板与非类型参数39类模板派生出类模板模板类(即类模板中类型/非类型参数实例化后的类)派生出类模板普通类派生出类模板模板类派生出普通类

类模板与继承派生

类模板类模板模板类类模板类模板类模板普通类模板类

40类模板从类模板派生(1)template<classT1,classT2>classA{T1v1;T2v2;};template<classT1,classT2>classB:publicA<T2,T1>{T1v3;T2v4;};template<classT>classC:publicB<T,T>{Tv5;};voidmain(){B<int,double>obj1;C<int>obj2;}41voidmain(){B<int,double>obj1;C<int>obj2;}classB<int,double>:publicA<double,int>{intv3;doublev4;};classA<double,int>{doublev1;intv2;};42类模板从模板类派生template<classT1,classT2>classA{T1v1;T2v2; };template<classT>classB:publicA<int,double>{Tv; };intmain(){ B<char>obj1;return0;}自动生成两个模板类：??43template<classT1,classT2>classA{T1v1;T2v2;};template<classT>classB:publicA<int,double>{Tv;};intmain(){B<char>obj1;return0;}自动生成两个模板类：A<int,double>和B<char>(2)类模板从模板类派生44classA{intv1;};template<classT>classB:publicA{Tv;};

intmain(){B<char>obj1;return0;}(3)类模板从普通类派生45(4)普通类从模板类派生template<classT>classA{Tv1;intn;};classB:publicA<int>

{doublev; };intmain(){Bobj1; return0;}46C++支持两种编译模式包含模式(InclusionModel)

把所有的定义一起放在头文件中，在调用的CPP中，包含相关的头文件分离模式(SeparationModel)(好像VC编译器不支持)//model.h

template<typenameType>TypetMin(Typet1,Typet2);//model.cppexporttemplate<typenamType>TypetMin(Typet1,Typet2);//test.cpp#include“model.h”inti,j;doubled=min(i,j);模板编译模式471.矩阵运算：矩阵转置与矩阵相乘函数模板。下标作为参数传递。2.线性表是数据结构中的概念。数组中除第一个元素外，其他元素有且仅有一个直接前驱，第一个元素没有前驱；除最后一个元素外，其他元素有且仅有一个直接后继，最后一个元素无后继。这样的特性称为线性关系。所以称数组元素在一个线性表中。线性表实际包括顺序表（数组）和链表。

对顺序表的典型操作包括：计算表长度，寻找变量或对象x（其类型与表元素相同）在表中的位置（下标值），判断x是否在表中，删除x，将x插入列表中第i个位置，寻找x的后继，寻找x的前驱，判断表是否空，判断表是否满（表满不能再插入数据，否则会溢出，产生不可预知的错误），取第i个元素的值。作业48堆栈类及其模板实现classCStack{public:CStack(intcapcity=20);~CStack();voidClearStack();boolisEmpty();boolisFull();intStackLength();charGetTop();voidPush(chare);voidPop();private:char*elemArray;inttop;intcapcity;};49类模板与友员函数函数、类、类的成员函数作为类模板的友元函数模板作为类模板的友元函数模板作为类的友元类模板作为类模板的友元50函数、类、类的成员函数作为类模板的友元voidFunc1(){}classA{};classB{public:voidFunc(){} };template<classT>classTmpl{

friendvoidFunc1();

friendclassA;

friendvoidB::Func();};51函数、类、类的成员函数作为类模板的友元intmain(){ Tmpl<int>i; Tmpl<double>f; return0;}52函数模板作为类模板的友元#include<iostream>#include<string>usingnamespacestd;template<classT1,classT2>classPair{private:T1key;//关键字T2value;//值public:Pair(T1k,T2v):key(k),value(v){};booloperator<(constPair<T1,T2>&p)const;

template<classT3,classT4>

friendostream&operator<<(ostream&o,constPair<T3,T4>&p);};53函数模板作为类模板的友元template<classT1,classT2>boolPair<T1,T2>::operator<(constPair<T1,T2>&p)const{//"小"的意思就是关键字小returnkey<p.key;}template<classT1,classT2>ostream&operator<<(ostream&o,constPair<T1,T2>&p){o<<"("<<p.key<<","<<p.value<<")";returno;}54函数模板作为类模板的友元intmain(){ Pair<string,int>student("Tom",29); Pair<int,double>obj(12,3.14); cout<<student<<""<<obj; return0;}从template<classT1,classT2>ostream&operator<<(ostream&o,constPair<T1,T2>&p)生成的函数，都被判断为Pair摸板类的友元输出结果：(Tom,29)12,3.14)55函数模板作为类的友元#include<iostream>usingnamespacestd;classA{intv;public:A(intn):v(n){}

template<classT>

friendvoidPrint(constT&p);};template<classT>voidPrint(constT&p){ cout<<p.v;}56函数模板作为类的友元intmain(){Aa(4);Print(a);return0;}从template<classT>voidPrint(constT&p)生成的函数，都成为A的友元输出结果：4voidPrint(inta){cout<<a;}???57类模板作为类模板的友元#include<iostream>usingnamespacestd;template<classT>classA{public:voidFunc(constT&p){cout<<p.v;}};template<classT>classB{private:Tv;public:B(Tn):v(n){}

template<classT2>friendclassA;

//把类模板A声明为友元};58intmain(){ B<int>b(5); A<B<int>>a; a.Func(b); return0;}A<B<int>>类，成了B<int>类的友元。从A模版实例化出来的类，都是B实例化出来的类的友元类模板作为类模板的友元//用B<int>替换A模板中的T输出结果：559类模板与static成员#include<iostream>usingnamespacestd;template<classT>classA{private:

staticintcount;public: A(){++count;} ~A(){--count;}; A(constA&){++count;}

staticvoidPrintCount(){cout<<count<<endl;}};60类模板与static成员template<>intA<int>::count=0;template<>intA<double>::count=0;intmain(){A<int>ia,ib;A<double>da;ia.PrintCount();ib.PrintCount();da.PrintCount();return0;}输出结果：221C++STL一、STL概述STL是一个具有工业强度的，高效的C++程序库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法STL主要包含了容器、算法、迭代器库（library）是一系列程序组件的集合，它们可以在不同的程序中重复使用。63

【引例】阅读以下程序:#include<iostream>#include<vector>usingnamespacestd;voidmain(){

vector<int>v;inti;for(i=0;i<10;i++) v.push_back(i);for(vector<int>::iteratorit=v.begin();it!=v.end();it++) cout<<*it<<",";cout<<endl;}Vector容器声明一个整型Vector容器尾部元素追加用迭代器配合循环访问向量元素64STL中的基本概念容器：可容纳各种数据类型的数据结构迭代器：可访问容器中元素的特殊指针算法：用来操作容器中元素的函数模板函数对象:

是一个行为类似函数的对象，可象函数一样调用。例如，向量Vector就是容器，

iterator是迭代器。STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象最基本的遍历结构对数据结构的操作

C++STL是通用数据结构和算法的封装！C++STL中，容器（container）就是通用的数据结构。容器用来承载不同类型的数据对象;C++中的容器还存在一定的“数据加工能力”

它如同一个对数据对象进行加工的模具，可以把不同类型的数据放到这个模具中进行加工处理，形成具有一定共同特性的数据结构。

例如,

将int型、char型或者float型放到队列容器中，就分别生成int队列、char型队列或者float型队列.它们都是队列，具有队列的基本特性，但是具体数据类型是不一样的。概念之

容器就如同现实生活中，人们使用容器用来装载各种物品一样66概念之容器适配器C++STL容器适配器用来扩充7种基本容器：

stack：栈（LIFO）

queue：队列（FIFO）

priority_queue：优先级队列67概念之迭代器用于指向容器中的元素。通过迭代器可以读取它指向的元素。迭代器是泛化的指针，可用“++”改变其指向位置，可用“*”访问内容。6868概念之算法C++STL包含70多个算法。包括：查找、排序、比较、变换、置换、容器管理等。算法是通用的，可作用于不同的类对象和预定义类型数据。6969STL组件间的关系

容器(container)算法(algorithm)容器(container)迭代器(iterator)函数对象(function

object)迭代器(iterator)C++STL将迭代器和函数对象作为算法的参数，提供了极大灵活性。使用STL提供的或自定义的迭代器，配合STL算法，可组合出各种各样强大的功能。STL头文件一览头文件内容头文件内容<iterator>迭代器<vector>向量<utility>辅助功能<deque>双头队列<memory>内存管理<list>链表<algorithm>算法<set>集合与多重集合<functional>函数对象<map>映射与多重映射<numeric>数值运算<stack>栈<queue>队列与优先队列容器的基本功能与分类容器是容纳、包含一组元素或元素集合的对象。七种基本容器：向量（vector）双端队列（deque）列表（list）集合（set）多重集合（multiset）映射（map）多重映射（multimap）C++STL的容器各有不尽相同的功能和用法。顺序容器关联容器71二、顺序容器容器名头文件名说明vector<vector>向量，从后面快速插入和删除，直接访问任何元素list<list>双向链表deque<deque>双端队列set<set>元素不重复的集合multiset<set>元素可重复的集合map<map>一个键只对于一个值的映射multimap<map>一个键可对于多个值的映射stack<stack>堆栈，后进先出（LIFO）queue<queue>队列，先进先出（FIFO）priority_queue<queue>优先级队列顺序容器(sequencecontainer)简介顺序容器(也称“序列式容器”)将一组具有相同类型的元素以严格的线性形式组织起来。三类顺序容器：(1)vector头文件<vector>

实际上是动态数组。随机存取任何元素都能在常数时间完成。在尾端增删元素具有较佳的性能。

(2)deque头文件<deque>

也是动态数组，随机存取任何元素都能在常数时间完成(但性能次于vector)。在两端增删元素具有较佳的性能。

(3)list头文件<list>

双向链表，在任何位置增删元素都能在常数时间完成。不支持随机存取。73关联容器简介关联容器内的元素是排序的，插入任何元素，都按相应的排序准则来确定其位置。特点是在查找时具有非常好的性能。通常以平衡二叉树方式实现，插入和检索的时间都是O(logN)四种关联容器：

(1)set/multiset:头文件<set>

set即集合。set中不允许相同元素，multiset中允许存在相同的元素。(2)map/multimap:头文件<map>

map与set的不同在于map中存放的是成对的key/value。

并根据key对元素进行排序，可快速地根据key来检索元素

map同multimap的不同在于是否允许多个元素有相同的key值。类似于Hash表74容器适配器简介(1)stack:头文件<stack>

栈。是项的有限序列，并满足序列中被删除、检索和修改的项只能是最近插入序列的项。即按照后进先出的原则(2)queue:头文件<queue>

队列。插入只可以在尾部进行，删除、检索和修改只允许从头部进行。按照先进先出的原则。(3)priority_queue:头文件<queue>

优先队列。最高优先级元素总是第一个出列。容器适配器是一种接口类，为已有类提供新的接口三种容器适配器：75容器的共有成员函数提供容器的通用功能；所有容器共有的成员函数：

关系运算：

=,<,<=,>,>=,==,!=

empty()

:

判断容器中是否为空

max_size():

容器中最多能装多少元素

size():

容器中元素个数

s1.swap(s2)：交换两个容器的内容构造函数、拷贝构造函数、析构函数76容器的共有成员函数(续)所有顺序容器和关联容器共有的成员函数：begin()：返回指向容器中第一个元素的迭代器end()：返回指向容器中最后一个元素后面的位置的迭代器rbegin():

返回指向容器中最后一个元素的迭代器rend():

返回指向容器中第一个元素前面的位置的迭代器

erase():

从容器中删除一个或几个元素clear()：清空容器77HeadTailbeginrbeginrendend所有容器都具有的成员函数成员函数名说明默认构造函数对容器进行默认初始化的构造函数，常有多个，用于提供不同的容器初始化方法拷贝构造函数用于将容器初始化为同类型的现有容器的副本析构函数执行容器销毁时的清理工作empty()判断容器是否为空，若为空返回true，否则返回falsemax_size()返回容器最大容量，即容器能够保存的最多元素个数size返回容器中当前元素的个数operator=(==)将一个容器赋给另一个同类容器operator<(<)如果第1个容器小于第2个容器，则返回true，否则返回falseoperator<=(<=)如果第1个容器小于等于第2个容器，则返回true，否则返回falseoperator>(>)如果第1个容器大于第2个容器，则返回true，否则返回falseoperator>=(>=)如果第1个容器大于等于第2个容器，则返回true，否则返回falseswap交换两个容器中的元素顺序和关联容器共同支持的成员函数成员函数名说明begin()指向第一个元素end()指向最后一个元素的后面一个位置rbegin()指向按反顺序的第一个元素rend()指向按反顺序的末端位置erase()删除容器中的一个或多个元素clear()删除容器中的所有元素【例1】创建两个整型向量容器，分别从尾端增加一些值，输出两个容器的元素数、两个容器的比较结果，交换两个容器后再输出一次。80#include<iostream>#include<vector>usingnamespacestd;intmain(){vector<int>v1,v2;v1.push_back(5);v1.push_back(1);v2.push_back(1);v2.push_back(2);v2.push_back(3);cout<<"v1元素数:"<<v1.size()<<",v2元素数:"<<v2.size()<<endl;if(v1==v2)cout<<"v1==v2"<<endl;elseif(v1<v2)cout<<"v1<v2"<<endl;elsecout<<"v1>v2"<<endl;v1.swap(v2);cout<<"v1元素数:"<<v1.size()<<",v2元素数:"<<v2.size()<<endl;if(v1==v2)cout<<"v1==v2"<<endl;elseif(v1<v2)cout<<"v1<v2"<<endl;elsecout<<"v1>v2"<<endl;return0;}声明2个向量向量赋值

51

v1

123

v2求元素数向量内容比较交换2个向量1、vector向量容器实际上就是动态数组。但它比数组更灵活，当添加数据时，vector的大小能够自动增加以容纳新的元素。内存自动管理。可动态调整所占内存。支持随机访问，随机访问时间为常数。所有STL算法都能对vector操作。在尾部添加速度很快，在中间插入慢。81(1)创建vector对象四种方式:不指定容器的元素个数：vector<类型T>对象名；例如：vector<int>v;//创建整型向量v指定容器大小：vector<类型T>对象名(n)；例如：vector<int>v(10);//创建整型向量v,10个元素注意：元素下标0~9,初始化为0.指定容器大小和元素初始值：vector<类型T>对象名(n,初值)；例如：vector<int>v(10,1);

//创建整型向量v,10个元素,每个元素值均为1由已有向量容器创建:

vector<类型T>对象名(已有对象名)；例如：vector<int>v2(v1);//创建整型向量v1的副本v282拷贝构造函数创建vector向量几种初始化vector对象的方式vector<T>v1;vector保存类型为T的对象。默认构造函数v1为空vector<T>v2(v1);v2是v1的一个副本vector<T>v3(n,i);v3包含n个值为i的元素vector<T>v4(n);v4包含有值初始化元素的n个副本#include<iostream>#include<vector>usingnamespacestd;intmain(){

vector<int>v(10,1);for(vector<int>::iteratorit=v.begin();it!=v.end();it++) cout<<*it<<",";cout<<endl;return0;}【例2】创建一个整型向量容器，输出全部元素值。84(2)下标方式访问vector元素可用“[

]”运算符访问vector的元素；【例3】用“[]”运算符为整型向量容器元素赋值，输出全部元素值。#include<iostream>#include<vector>usingnamespacestd;intmain(){vector<int>v(3);

v[0]=10;v[1]=100;v[2]=-20;for(inti=0;i<3;i++) cout<<v[i]<<",";cout<<endl;return0;}85vector(向量)下标访问元素注意：下标操作仅能对确知已存的元素进行赋值和读取操作vector<int>ivec;//emptyvectorfor(intix=0;ix<100;++ix){ivec[ix]=ix;//ivechasnoelement}出错，向量中尚没有元素，不能访问！(3)用迭代器访问vector元素

如何使相同的算法能用于不同的数据结构?

--迭代器(算法与容器的”中间人”)87

容器类迭代器定义方法：

容器类名::iterator变量名;访问一个迭代器指向的元素：

*迭代器变量名迭代器上可执行”++”,指向容器中的下一个元素。如果迭代器到达了容器中的最后一个元素的后面，则迭代器变成past-the-end值。使用一个past-the-end值的迭代器来访问对象是非法的定义迭代器的关键字88对照理解vector<int>::iteratorxHere=x.Begin();vector<int>::iteratorxEnd=x.End();for(;xHere!=xEnd;xHere++)func_name(*xHere);for(inti=0;i<x.Size();i++)

func_name(x.Get(i));【例4】#include<vector>#include<iostream>usingnamespacestd;intmain(){vector<int>v;v.push_back(1); v.push_back(2);v.push_back(3);v.push_back(4);

vector<int>::const_iteratorit1;

//常量迭代器for(it1=v.begin();it1!=v.end();it1++) cout<<*it1<<",";cout<<endl;

vector<int>::reverse_iteratorit2;

//反向迭代器for(it2=v.rbegin();it2!=v.rend();it2++) cout<<*it2<<",";cout<<endl;89

vector<int>::iteratorit3;

//非常量迭代器

for(it3=v.begin();it3!=v.end();it3++) *it3=100;//重置向量 for(it3=v.begin();it3!=v.end();it3++) cout<<*it3<<","; cout<<endl; return0;}HeadTailbeginrbeginrendend（1）const_iterator：常量迭代器。可以使用这种类型的迭代器来指向一个只读的值。

（2）

reverse_iterator

：反向迭代器。用来反转遍历vector的各元素，注意用rbegin()来代替begin()，用rend()代替end()，而此时的“++”操作符会朝向后的方向遍历。

（3）iterator：随机迭代器，可任意方向或移动任意个位置访问。vector的迭代器HeadTailbeginrbeginrendend有const限制的只可读取元素值，不可修改元素值90

不同的容器，STL提供的迭代器功能各不相同。

vector容器的迭代器：

可使用“+=”、“--”、“++”、“-=”中的任何一种操作符

可使用“<”、“<=”、“>”、“>=”、“==”、“!=”等比较运算符

可随机访问容器中的数据元素。vector的迭代器91(4)元素插入push_back在尾部追加元素;insert方法可在vector任意位置插入元素.【例5】向整型向量容器追加元素，输出全部元素值。

#include<iostream>#include<vector>usingnamespacestd;intmain(){

vector<int>v(10,1);

v.push_back(100);v.psuh_back(-200);for(vector<int>::iteratorit=v.begin();it!=v.end();it++) cout<<*it<<",";cout<<endl;return0;}

尾部追加元素，vector容器自动分配内存；可对空的vector追加，也可对已有元素的vector追加.尾部元素追加92vector(向量)--添加ABCDEaaABCDEABCDEABCDEaa在尾端增删元素具有较佳的性能93指定位置插入元素insert(iteratorit,Tt):对vector容器在指定位置插入新元素【例6】对整型向量容器插入元素，输出全部元素值。#include<iostream>#include<vector>usingnamespacestd;intmain(){

vector<int>v(3);vector<int>::iteratorit;v[0]=10;v[1]=100;v[2]=-20;

v.insert(v.begin(),50);//在最前面插入新元素50

v.insert(v.begin()+2,8);//在第2个元素之前插入新元素8

v.insert(v.end(),9);//在末尾插入新元素9for(it=v.begin();it!=v.end();it++) cout<<*it<<",";cout<<endl;return0;}

注意：insert方法要求插入的位置，是迭代器位置，而不是下标！94通过迭代器随机访问元素(5)元素删除pop_back删除向量最后一个元素；erase删除指定位置或一段区间的元素;clear方法删除所有元素.【例7】向量容器删除元素方法示例。#include<iostream>#include<vector>usingnamespacestd;intmain(){vector<int>v(10);vector<int>::iteratorit;for(inti=0;i<10;i++)v[i]=i;

v.erase(v.begin()+3);//删除第3个元素，从0开始计数

for(it=v.begin();it!=v.end();it++)cout<<*it<<",";cout<<endl;

v.erase(v.begin()+1,v.begin()+3);//删除第1~3个元素for(it=v.begin();it!=v.end();it++)cout<<*it<<",";cout<<endl<<"向量V中元素数："<<v.size()<<endl;

v.clear();//清空向量cout<<endl<<"向量V中元素数："<<v.size()<<endl;return0;}区间删除95(6)向量大小的有关操作向量大小有关操作列表v.size();返回向量的大小v.max_size();返回向量可容纳的最大个数v.empty();返回向量是否为空v.resize(n);调整向量的大小，使其可以容纳n个元素，如果n<v.size(),则删除多出来的元素;v.resize(n,t);调整向量的大小，使其可以容纳n个元素，所有新添加的元素初始化为tv.capacity();获取向量的容量，再分配内存空间之前所能容纳的元素个数96向量的大小size()和resize()vector<int>vec(10,42);//10int,eachhasvalue42cout<<vec.size()<<endl;vec.resize(15);//adds5elementsofvalue0tothebackofthevectorcout<<vec.size()<<endl;vec.resize(25,-1);//adds10elementsofvalue-1tothebackofthevectorcout<<vec.size()<<endl;新增元素初始化为-197size(),max_size()和capacity()vector<int>v1;cout<<v1.size()<<""<<v1.max_size()<<""<<v1.capacity()<<endl;vector<int>v2(100,-1);cout<<v2.size()<<""<<v2.max_size()<<""<<v2.capacity()<<endl;

size()返回向量中元素的个数

max_size()返回向量中最多可容纳的元素个数

capacity()获取向量的容量，再分配内存空间之前所能容纳的元素个数,当元素个数等于capacity返回的元素个数时，vector自动分配一段空间用于存储输入的新元素012…23……vec.size()vec.capacity()向量的大小systemmemorymax_sizemax_size是系统最大可分配的容量,并非实际分配98(7)在向量上使用算法C++STL很多算法都可以在向量上使用;使用算法需要包含头文件<algorithm>.【例8】在整型向量容器上使用排序算法。#include<iostream>#include<vector>#include<algorithm>usingnamespacestd;intmain(){vector<int>v;vector<int>::iteratorit;for(inti=0;i<10;i++)v.push_back(10-i);for(it=v.begin();it!=v.end();it++)cout<<*it<<",";cout<<endl;

sort(v.begin(),v.end());//对向量排序

for(it=v.begin();it!=v.end();it++)cout<<*it<<",";cout<<endl;return0;}99(8)vector作为函数参数#include<iostream>#include<vector>usingnamespacestd;voidprint(vector<int>v){for(vector<int>::iteratorit=v.begin();it!=v.end();it++)cout<<*it<<endl;}intmain(){vector<int>vec;vec.push_back(1);vec.push_back(2);vec.push_back(3);

print(vec);return0;}【例9】向量作为函数参数示例。100#include<iostream>#include<vector>usingnamespacestd;constintKVectSize=5;intmain(){vector<int>vec;inti;for(i=0;i!=KVectSize;i++){vec.push_back(i);cout<<vec.size()<<","<<vec.capacity()<<endl;}vector<int>*p=newvector<int>(vec);cout<<p->size()<<","<<p->capacity()<<en