C++STL泛型編程課件

1C++STL泛型編程

（GenericProgramming）2為什么要采用泛型編程？項目中,需要用到數(shù)組、鏈表、字符串、棧、隊列、平衡二叉樹等數(shù)據(jù)結(jié)構(gòu)，以及排序、搜索等算法；若全部自行編寫比較麻煩；ANSIC++中包含了C++STL(StandardTemplateLibrary,標(biāo)準(zhǔn)模板庫,又稱C++泛型庫)，定義了常用的數(shù)據(jù)結(jié)構(gòu)和算法，使用十分方便。有了STL，不必再從頭寫大多的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)和算法，并且可獲得非常高的性能。但這不意味著我們不需要掌握基本數(shù)據(jù)結(jié)構(gòu)與算法;相反,只有透徹理解了,才能更好的使用泛型!泛型程序設(shè)計由AlexanderStepanov和DavidMusser創(chuàng)立，于1998年被添加進C++標(biāo)準(zhǔn).含義：編寫不依賴于具體數(shù)據(jù)類型的程序.目標(biāo)：將程序?qū)懙帽M可能通用.將算法從特定的數(shù)據(jù)結(jié)構(gòu)中抽象出來，成為通用的.C++的模板為泛型程序設(shè)計奠定了關(guān)鍵的基礎(chǔ).STL

(標(biāo)準(zhǔn)模板庫,StandardTemplateLibrary)是泛型程序設(shè)計的一個范例.代碼重用(reuse)!4函數(shù)模板模板函數(shù)的重載類模板堆棧類繼承static成員友元模板函數(shù)模板簡介5

【引例】交換2個整數(shù)和交換2個浮點數(shù)的C++程序://交換2個整數(shù)voidSwap(int&a,int&b){inttmp=0;tmp=a;a=b;b=tmp;}//交換2個浮點數(shù)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函數(shù)實現(xiàn)的功能相同，只是參數(shù)類型不同，但為了實現(xiàn)不同類型的數(shù)據(jù)交換必須分別編寫函數(shù)。造成了重復(fù)勞動。函數(shù)重載6

能否提供一種方法將兩個函數(shù)合并，以節(jié)省開發(fā)成本？引例typedefintDataType;voidSwap(DataType&a,DataType&b){ DataTypetmp; tmp=a; a=b; b=tmp;}intmain(){inta=10,b=20;Swap(a,b);return0;}當(dāng)需要交換兩個浮點數(shù)時可以將DataType定義成float型數(shù)據(jù)即可。typedeffloatDateType;存在問題：

更改一種數(shù)據(jù)類型時，需要修改程序源代碼，必須重新編譯程序。如果程序中需要交換多種數(shù)據(jù)類型數(shù)據(jù),怎么辦？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;}模板聲明定義函數(shù)模板通用的Swap!模板機制模板的概念模板是一種使用無類型參數(shù)來產(chǎn)生一系列函數(shù)或類的機制。模板是以一種完全通用的方法來設(shè)計函數(shù)或類而不必預(yù)先說明將被使用的每個對象的類型。通過模板可以產(chǎn)生類或函數(shù)的集合，使它們操作不同的數(shù)據(jù)類型，從而避免需要為每一種數(shù)據(jù)類型產(chǎn)生一個單獨的類或函數(shù)。

8模板分類函數(shù)模板(functiontemplate)是獨立于類型的函數(shù)可產(chǎn)生函數(shù)的特定版本類模板(classtemplate)與類相關(guān)的模板，如vector可產(chǎn)生類對特定類型的版本，如vector<int>9模板工作方式模板只是說明，需要實例化后才能執(zhí)行或使用.10模板函數(shù)模板類模板模板類模板函數(shù)對象實例化實例化實例化函數(shù)模板(functiontemplate)定義格式：template<模板參數(shù)表>類型名函數(shù)名（參數(shù)表）{

函數(shù)體}template<classT>voidSwap(T&x,T&y){Ttmp=x;x=y;y=tmp;}11template:

函數(shù)模板定義關(guān)鍵字.<>中是函數(shù)的模板參數(shù)，參數(shù)可有一個或多個，逗號隔開。不能為空！

模板參數(shù)常用形式：

class標(biāo)識符或者typename標(biāo)識符模板參數(shù)表明函數(shù)可以接收的類型參數(shù)，可以是內(nèi)部類型，也可以是自定義類型.

【例1】簡單函數(shù)模板定義和應(yīng)用.#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;}函數(shù)模板intMax(inta,intb){returna>b?a:b;}由實參類型實例化charMax(chara,charb){returna>b?a:b;}doubleMax(doublea,doubleb){returna>b?a:b;}編譯器生成的模板函數(shù)函數(shù)模板實例化運行結(jié)果:Max(3,5)is5Max(‘y’,‘e’)isyMax(9.3,0.5)is9.3函數(shù)模板的原理分析：函數(shù)模板中聲明了類型參數(shù)T，表示了一種抽象類型.

編譯器檢測到程序調(diào)用函數(shù)模板Max時，用其第一個實參類型替換掉模板中的T，同時建立一個完整的函數(shù)Max，并編譯該新建的函數(shù).

本例中，針對三種數(shù)據(jù)類型，生成了三種函數(shù).

【練習(xí)1】編寫一個對具有n個元素的數(shù)組a[]求最小值的程序，要求將求最小值的函數(shù)設(shè)計成函數(shù)模板。#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數(shù)組的最小值為："

<<MinArray(arr1,9)<<endl;cout<<"arr2數(shù)組的最小值為："

<<MinArray(arr2,4)<<endl;}運行結(jié)果:arr1數(shù)組的最小值為：0Arr2數(shù)組的最小值為:-3.4

注意點1：實參類型與形參類型必須嚴(yán)格匹配.#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;}錯誤！模板類型不能提供類型的隱式轉(zhuǎn)換注意點2：在函數(shù)模板中允許使用多個類型參數(shù)。在template定義部分的每個模板形參前必須有關(guān)鍵字class或typename.#include<iostream>usingnamespacestd;template<classT1,classT2>voidmyfunc(T1x,T2y){cout<<x<<","<<y<<endl;}運行結(jié)果:100,hao3.14,10voidmain(){myfunc(100,"hao");myfunc(3.14,10L);}

注意點3：在template語句與函數(shù)模板定義語句之間不允許有別的語句。Template<classT>inti;

TMax(Tx,Ty){return(x>y)?x:y;}8//錯誤，不允許有別的語句模板優(yōu)缺點優(yōu)點:函數(shù)模板方法克服了C語言用大量不同函數(shù)名表示相似功能的弊端;克服了宏定義不能進行參數(shù)類型檢查的弊端;克服了C++函數(shù)重載用相同函數(shù)名字重寫幾個函數(shù)的繁瑣.缺點:

調(diào)試比較困難.一般先寫一個特殊版本的函數(shù)運行正確后，改成模板函數(shù)1718

【練習(xí)2】編寫一個函數(shù)模板，它返回兩個值中的較小者，同時要求能正確處理字符串。

分析：由于C++字符串比較的方法與字符型、數(shù)值型都不同，因此函數(shù)模板不適用于字符串比較；這里設(shè)計一個函數(shù)模板template<classT>Tmin(Ta,Tb)，可以處理int、float和char等數(shù)據(jù)類型；為了能正確處理字符串，添加一個重載函數(shù)專門處理字符串比較，即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<<"輸出結(jié)果:"<<endl;

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

cout<<min(s1,s2)<<endl;}函數(shù)模板函數(shù)重載運行結(jié)果:3.14Bad20可以顯式指定（explicitlyspecify），如：i=max<int>(ia,5);d=max<double>(da,6);用函數(shù)模板求數(shù)組元素中最大值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函數(shù)模板可以重載,形參表不同即可例,下面兩個模板可以同時存在:template<classT1,classT2>voidprint(T1arg1,T2arg2){cout<<arg1<<""<<arg2<<endl;}template<classT>voidprint(Targ1,Targ2){cout<<arg1<<""<<arg2<<endl;}重載22例:函數(shù)模板調(diào)用順序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++編譯器遵循以下優(yōu)先順序:Step1:先找參數(shù)完全匹配的普通函數(shù)(非由模板實例化而得的函數(shù))Step2:再找參數(shù)完全匹配的模板函數(shù)

Step3:再找實參經(jīng)過自動類型轉(zhuǎn)換后能夠匹配的普通函數(shù)

Step4:上面的都找不到,則報錯26voidmain(){inti=4,j=5;Max(1.2,3.4);Max(i,j);Max(1.2,3);}//調(diào)用Max(double,double)函數(shù)//調(diào)用第一個TMax(Ta,Tb)模板生成的函數(shù)//調(diào)用第二個TMax(Ta,T2b)模板生成的函數(shù)運行結(jié)果:MyMaxTemplateMax1TemplateMax227可以在函數(shù)模板中使用多個類型參數(shù),可以避免二義性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<類型參數(shù)表>class類模板名{成員函數(shù)和成員變量};類型參數(shù)表的寫法就是:class類型參數(shù)1,class類型參數(shù)2,…29類模板里的成員函數(shù),如在類模板外面定義時,template<類型參數(shù)表>返回值類型類模板名<類型參數(shù)名列表>::成員函數(shù)名(參數(shù)表){……}類模板的定義30用類模板定義對象的寫法如下:類模板名<真實類型參數(shù)表>對象名(構(gòu)造函數(shù)實際參數(shù)表);如果類模板有無參構(gòu)造函數(shù),那么也可以只寫:類模板名<真實類型參數(shù)表>對象名;類模板的定義31Pair類模板:template<classT1,classT2>classPair{public:T1key;//關(guān)鍵字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的成員函數(shù)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;}運行結(jié)果:Jack20Pair類模板的使用:33使用類模板聲明對象編譯器由類模板生成類的過程叫類模板的實例化

?編譯器自動用具體的數(shù)據(jù)類型替換類模板中的類型參數(shù),生成模板類的代碼由類模板實例化得到的類叫模板類?為類型參數(shù)指定的數(shù)據(jù)類型不同,得到的模板類不同同一個類模板的兩個模板類是不兼容的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');}若函數(shù)模板改為template<classT>voidFunc(Tt){cout<<t}將報錯“declarationof‘classT’shadowstemplateparm‘classT’”

程序輸出:K//成員函數(shù)模板//成員函數(shù)模板Func被實例化函數(shù)模版作為類模板成員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類模板的參數(shù)聲明中可以包括非類型參數(shù)

template<classT,intelementsNumber>?非類型參數(shù):用來說明類模板中的屬性?類型參數(shù):用來說明類模板中的屬性類型,成員操作的參數(shù)類型和返回值類型類模板與非類型參數(shù)37template<classT,intsize>classCArray{Tarray[size];public:voidPrint(){for(inti=0;i<size;++i)cout<<array[i]<<endl;}};類模板與非類型參數(shù)CArray<double,40>a2;CArray<int,50>a3;38CArray<double,40>a2;CArray<int,50>a3;注意:CArray<int,40>和CArray<int,50>完全是兩個類這兩個類的對象之間不能互相賦值類模板與非類型參數(shù)39類模板派生出類模板模板類(即類模板中類型/非類型參數(shù)實例化后的類)派生出類模板普通類派生出類模板模板類派生出普通類

類模板與繼承派生

類模板類模板模板類類模板類模板類模板普通類模板類

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)

把所有的定義一起放在頭文件中，在調(diào)用的CPP中，包含相關(guān)的頭文件分離模式(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.矩陣運算：矩陣轉(zhuǎn)置與矩陣相乘函數(shù)模板。下標(biāo)作為參數(shù)傳遞。2.線性表是數(shù)據(jù)結(jié)構(gòu)中的概念。數(shù)組中除第一個元素外，其他元素有且僅有一個直接前驅(qū)，第一個元素沒有前驅(qū)；除最后一個元素外，其他元素有且僅有一個直接后繼，最后一個元素?zé)o后繼。這樣的特性稱為線性關(guān)系。所以稱數(shù)組元素在一個線性表中。線性表實際包括順序表（數(shù)組）和鏈表。

對順序表的典型操作包括：計算表長度，尋找變量或?qū)ο髕（其類型與表元素相同）在表中的位置（下標(biāo)值），判斷x是否在表中，刪除x，將x插入列表中第i個位置，尋找x的后繼，尋找x的前驅(qū)，判斷表是否空，判斷表是否滿（表滿不能再插入數(shù)據(jù)，否則會溢出，產(chǎn)生不可預(yù)知的錯誤），取第i個元素的值。作業(yè)48堆棧類及其模板實現(xiàn)classCStack{public:CStack(intcapcity=20);~CStack();voidClearStack();boolisEmpty();boolisFull();intStackLength();charGetTop();voidPush(chare);voidPop();private:char*elemArray;inttop;intcapcity;};49類模板與友員函數(shù)函數(shù)、類、類的成員函數(shù)作為類模板的友元函數(shù)模板作為類模板的友元函數(shù)模板作為類的友元類模板作為類模板的友元50函數(shù)、類、類的成員函數(shù)作為類模板的友元voidFunc1(){}classA{};classB{public:voidFunc(){} };template<classT>classTmpl{

friendvoidFunc1();

friendclassA;

friendvoidB::Func();};51函數(shù)、類、類的成員函數(shù)作為類模板的友元intmain(){ Tmpl<int>i; Tmpl<double>f; return0;}52函數(shù)模板作為類模板的友元#include<iostream>#include<string>usingnamespacestd;template<classT1,classT2>classPair{private:T1key;//關(guān)鍵字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函數(shù)模板作為類模板的友元template<classT1,classT2>boolPair<T1,T2>::operator<(constPair<T1,T2>&p)const{//"小"的意思就是關(guān)鍵字小returnkey<p.key;}template<classT1,classT2>ostream&operator<<(ostream&o,constPair<T1,T2>&p){o<<"("<<p.key<<","<<p.value<<")";returno;}54函數(shù)模板作為類模板的友元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)生成的函數(shù)，都被判斷為Pair摸板類的友元輸出結(jié)果：(Tom,29)12,3.14)55函數(shù)模板作為類的友元#include<iostream>usingnamespacestd;classA{intv;public:A(intn):v(n){}

template<classT>

friendvoidPrint(constT&p);};template<classT>voidPrint(constT&p){ cout<<p.v;}56函數(shù)模板作為類的友元intmain(){Aa(4);Print(a);return0;}從template<classT>voidPrint(constT&p)生成的函數(shù)，都成為A的友元輸出結(jié)果：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輸出結(jié)果：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;}輸出結(jié)果：221C++STL一、STL概述STL是一個具有工業(yè)強度的，高效的C++程序庫包含了諸多在計算機科學(xué)領(lǐng)域里所常用的基本數(shù)據(jù)結(jié)構(gòu)和基本算法STL主要包含了容器、算法、迭代器庫（library）是一系列程序組件的集合，它們可以在不同的程序中重復(fù)使用。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容器尾部元素追加用迭代器配合循環(huán)訪問向量元素64STL中的基本概念容器：可容納各種數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu)迭代器：可訪問容器中元素的特殊指針?biāo)惴ǎ河脕聿僮魅萜髦性氐暮瘮?shù)模板函數(shù)對象:

是一個行為類似函數(shù)的對象，可象函數(shù)一樣調(diào)用。例如，向量Vector就是容器，

iterator是迭代器。STL用sort()來對一個vector中的數(shù)據(jù)進行排序，用find()來搜索一個list中的對象最基本的遍歷結(jié)構(gòu)對數(shù)據(jù)結(jié)構(gòu)的操作

C++STL是通用數(shù)據(jù)結(jié)構(gòu)和算法的封裝！C++STL中，容器（container）就是通用的數(shù)據(jù)結(jié)構(gòu)。容器用來承載不同類型的數(shù)據(jù)對象;C++中的容器還存在一定的“數(shù)據(jù)加工能力”

它如同一個對數(shù)據(jù)對象進行加工的模具，可以把不同類型的數(shù)據(jù)放到這個模具中進行加工處理，形成具有一定共同特性的數(shù)據(jù)結(jié)構(gòu)。

例如,

將int型、char型或者float型放到隊列容器中，就分別生成int隊列、char型隊列或者float型隊列.它們都是隊列，具有隊列的基本特性，但是具體數(shù)據(jù)類型是不一樣的。概念之

容器就如同現(xiàn)實生活中，人們使用容器用來裝載各種物品一樣66概念之容器適配器C++STL容器適配器用來擴充7種基本容器：

stack：棧（LIFO）

queue：隊列（FIFO）

priority_queue：優(yōu)先級隊列67概念之迭代器用于指向容器中的元素。通過迭代器可以讀取它指向的元素。迭代器是泛化的指針，可用“++”改變其指向位置，可用“*”訪問內(nèi)容。6868概念之算法C++STL包含70多個算法。包括：查找、排序、比較、變換、置換、容器管理等。算法是通用的，可作用于不同的類對象和預(yù)定義類型數(shù)據(jù)。6969STL組件間的關(guān)系

容器(container)算法(algorithm)容器(container)迭代器(iterator)函數(shù)對象(function

object)迭代器(iterator)C++STL將迭代器和函數(shù)對象作為算法的參數(shù)，提供了極大靈活性。使用STL提供的或自定義的迭代器，配合STL算法，可組合出各種各樣強大的功能。STL頭文件一覽頭文件內(nèi)容頭文件內(nèi)容<iterator>迭代器<vector>向量<utility>輔助功能<deque>雙頭隊列<memory>內(nèi)存管理<list>鏈表<algorithm>算法<set>集合與多重集合<functional>函數(shù)對象<map>映射與多重映射<numeric>數(shù)值運算<stack>棧<queue>隊列與優(yōu)先隊列容器的基本功能與分類容器是容納、包含一組元素或元素集合的對象。七種基本容器：向量（vector）雙端隊列（deque）列表（list）集合（set）多重集合（multiset）映射（map）多重映射（multimap）C++STL的容器各有不盡相同的功能和用法。順序容器關(guān)聯(lián)容器71二、順序容器容器名頭文件名說明vector<vector>向量，從后面快速插入和刪除，直接訪問任何元素list<list>雙向鏈表deque<deque>雙端隊列set<set>元素不重復(fù)的集合multiset<set>元素可重復(fù)的集合map<map>一個鍵只對于一個值的映射multimap<map>一個鍵可對于多個值的映射stack<stack>堆棧，后進先出（LIFO）queue<queue>隊列，先進先出（FIFO）priority_queue<queue>優(yōu)先級隊列順序容器(sequencecontainer)簡介順序容器(也稱“序列式容器”)將一組具有相同類型的元素以嚴(yán)格的線性形式組織起來。三類順序容器：(1)vector頭文件<vector>

實際上是動態(tài)數(shù)組。隨機存取任何元素都能在常數(shù)時間完成。在尾端增刪元素具有較佳的性能。

(2)deque頭文件<deque>

也是動態(tài)數(shù)組，隨機存取任何元素都能在常數(shù)時間完成(但性能次于vector)。在兩端增刪元素具有較佳的性能。

(3)list頭文件<list>

雙向鏈表，在任何位置增刪元素都能在常數(shù)時間完成。不支持隨機存取。73關(guān)聯(lián)容器簡介關(guān)聯(lián)容器內(nèi)的元素是排序的，插入任何元素，都按相應(yīng)的排序準(zhǔn)則來確定其位置。特點是在查找時具有非常好的性能。通常以平衡二叉樹方式實現(xiàn)，插入和檢索的時間都是O(logN)四種關(guān)聯(lián)容器：

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

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

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

并根據(jù)key對元素進行排序，可快速地根據(jù)key來檢索元素

map同multimap的不同在于是否允許多個元素有相同的key值。類似于Hash表74容器適配器簡介(1)stack:頭文件<stack>

棧。是項的有限序列，并滿足序列中被刪除、檢索和修改的項只能是最近插入序列的項。即按照后進先出的原則(2)queue:頭文件<queue>

隊列。插入只可以在尾部進行，刪除、檢索和修改只允許從頭部進行。按照先進先出的原則。(3)priority_queue:頭文件<queue>

優(yōu)先隊列。最高優(yōu)先級元素總是第一個出列。容器適配器是一種接口類，為已有類提供新的接口三種容器適配器：75容器的共有成員函數(shù)提供容器的通用功能；所有容器共有的成員函數(shù)：

關(guān)系運算：

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

empty()

:

判斷容器中是否為空

max_size():

容器中最多能裝多少元素

size():

容器中元素個數(shù)

s1.swap(s2)：交換兩個容器的內(nèi)容構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、析構(gòu)函數(shù)76容器的共有成員函數(shù)(續(xù))所有順序容器和關(guān)聯(lián)容器共有的成員函數(shù)：begin()：返回指向容器中第一個元素的迭代器end()：返回指向容器中最后一個元素后面的位置的迭代器rbegin():

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

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

erase():

從容器中刪除一個或幾個元素clear()：清空容器77HeadTailbeginrbeginrendend所有容器都具有的成員函數(shù)成員函數(shù)名說明默認(rèn)構(gòu)造函數(shù)對容器進行默認(rèn)初始化的構(gòu)造函數(shù)，常有多個，用于提供不同的容器初始化方法拷貝構(gòu)造函數(shù)用于將容器初始化為同類型的現(xiàn)有容器的副本析構(gòu)函數(shù)執(zhí)行容器銷毀時的清理工作empty()判斷容器是否為空，若為空返回true，否則返回falsemax_size()返回容器最大容量，即容器能夠保存的最多元素個數(shù)size返回容器中當(dāng)前元素的個數(shù)operator=(==)將一個容器賦給另一個同類容器operator<(<)如果第1個容器小于第2個容器，則返回true，否則返回falseoperator<=(<=)如果第1個容器小于等于第2個容器，則返回true，否則返回falseoperator>(>)如果第1個容器大于第2個容器，則返回true，否則返回falseoperator>=(>=)如果第1個容器大于等于第2個容器，則返回true，否則返回falseswap交換兩個容器中的元素順序和關(guān)聯(lián)容器共同支持的成員函數(shù)成員函數(shù)名說明begin()指向第一個元素end()指向最后一個元素的后面一個位置rbegin()指向按反順序的第一個元素rend()指向按反順序的末端位置erase()刪除容器中的一個或多個元素clear()刪除容器中的所有元素【例1】創(chuàng)建兩個整型向量容器，分別從尾端增加一些值，輸出兩個容器的元素數(shù)、兩個容器的比較結(jié)果，交換兩個容器后再輸出一次。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元素數(shù):"<<v1.size()<<",v2元素數(shù):"<<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元素數(shù):"<<v1.size()<<",v2元素數(shù):"<<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求元素數(shù)向量內(nèi)容比較交換2個向量1、vector向量容器實際上就是動態(tài)數(shù)組。但它比數(shù)組更靈活，當(dāng)添加數(shù)據(jù)時，vector的大小能夠自動增加以容納新的元素。內(nèi)存自動管理?？蓜討B(tài)調(diào)整所占內(nèi)存。支持隨機訪問，隨機訪問時間為常數(shù)。所有STL算法都能對vector操作。在尾部添加速度很快，在中間插入慢。81(1)創(chuàng)建vector對象四種方式:不指定容器的元素個數(shù)：vector<類型T>對象名；例如：vector<int>v;//創(chuàng)建整型向量v指定容器大?。簐ector<類型T>對象名(n)；例如：vector<int>v(10);//創(chuàng)建整型向量v,10個元素注意：元素下標(biāo)0~9,初始化為0.指定容器大小和元素初始值：vector<類型T>對象名(n,初值)；例如：vector<int>v(10,1);

//創(chuàng)建整型向量v,10個元素,每個元素值均為1由已有向量容器創(chuàng)建:

vector<類型T>對象名(已有對象名)；例如：vector<int>v2(v1);//創(chuàng)建整型向量v1的副本v282拷貝構(gòu)造函數(shù)創(chuàng)建vector向量幾種初始化vector對象的方式vector<T>v1;vector保存類型為T的對象。默認(rèn)構(gòu)造函數(shù)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】創(chuàng)建一個整型向量容器，輸出全部元素值。84(2)下標(biāo)方式訪問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(向量)下標(biāo)訪問元素注意：下標(biāo)操作僅能對確知已存的元素進行賦值和讀取操作vector<int>ivec;//emptyvectorfor(intix=0;ix<100;++ix){ivec[ix]=ix;//ivechasnoelement}出錯，向量中尚沒有元素，不能訪問！(3)用迭代器訪問vector元素

如何使相同的算法能用于不同的數(shù)據(jù)結(jié)構(gòu)?

--迭代器(算法與容器的”中間人”)87

容器類迭代器定義方法：

容器類名::iterator變量名;訪問一個迭代器指向的元素：

*迭代器變量名迭代器上可執(zhí)行”++”,指向容器中的下一個元素。如果迭代器到達了容器中的最后一個元素的后面，則迭代器變成past-the-end值。使用一個past-the-end值的迭代器來訪問對象是非法的定義迭代器的關(guān)鍵字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

：反向迭代器。用來反轉(zhuǎn)遍歷vector的各元素，注意用rbegin()來代替begin()，用rend()代替end()，而此時的“++”操作符會朝向后的方向遍歷。

（3）iterator：隨機迭代器，可任意方向或移動任意個位置訪問。vector的迭代器HeadTailbeginrbeginrendend有const限制的只可讀取元素值，不可修改元素值90

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

vector容器的迭代器：

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

可使用“<”、“<=”、“>”、“>=”、“==”、“!=”等比較運算符

可隨機訪問容器中的數(shù)據(jù)元素。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容器自動分配內(nèi)存；可對空的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方法要求插入的位置，是迭代器位置，而不是下標(biāo)！94通過迭代器隨機訪問元素(5)元素刪除pop_back刪除向量最后一個元素；erase刪除指定位置或一段區(qū)間的元素;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開始計數(shù)

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中元素數(shù)："<<v.size()<<endl;

v.clear();//清空向量cout<<endl<<"向量V中元素數(shù)："<<v.size()<<endl;return0;}區(qū)間刪除95(6)向量大小的有關(guān)操作向量大小有關(guān)操作列表v.size();返回向量的大小v.max_size();返回向量可容納的最大個數(shù)v.empty();返回向量是否為空v.resize(n);調(diào)整向量的大小，使其可以容納n個元素，如果n<v.size(),則刪除多出來的元素;v.resize(n,t);調(diào)整向量的大小，使其可以容納n個元素，所有新添加的元素初始化為tv.capacity();獲取向量的容量，再分配內(nèi)存空間之前所能容納的元素個數(shù)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()返回向量中元素的個數(shù)

max_size()返回向量中最多可容納的元素個數(shù)

capacity()獲取向量的容量，再分配內(nèi)存空間之前所能容納的元素個數(shù),當(dāng)元素個數(shù)等于capacity返回的元素個數(shù)時，vector自動分配一段空間用于存儲輸入的新元素012…23……vec.size()vec.capacity()向量的大小systemmemorymax_sizemax_size是系統(tǒng)最大可分配的容量,并非實際分配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作為函數(shù)參數(shù)#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】向量作為函數(shù)參數(shù)示例。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