C++STL泛型編程長(zhǎng)望班

1、.1 C+STL 長(zhǎng)望程序設(shè)計(jì)競(jìng)賽班.2 ACM競(jìng)賽中競(jìng)賽中,需要用到數(shù)組、鏈表、字符串、棧、需要用到數(shù)組、鏈表、字符串、棧、隊(duì)列、平衡二叉樹(shù)等數(shù)據(jù)結(jié)構(gòu)，以及排序、搜索隊(duì)列、平衡二叉樹(shù)等數(shù)據(jù)結(jié)構(gòu)，以及排序、搜索等算法；等算法； 若全部自行編寫(xiě)比較麻煩；若全部自行編寫(xiě)比較麻煩； ANSI C+中包含了中包含了C+ STL (Standard Template Library , 標(biāo)準(zhǔn)模板庫(kù)標(biāo)準(zhǔn)模板庫(kù),又稱(chēng)又稱(chēng)C+泛型泛型庫(kù)庫(kù))，定義了常用的數(shù)據(jù)結(jié)構(gòu)和算法，使用十分方，定義了常用的數(shù)據(jù)結(jié)構(gòu)和算法，使用十分方便。便。 有了有了STL，不必再?gòu)念^寫(xiě)大多的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)和，不必再?gòu)念^寫(xiě)大多的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)和

2、算法，并且可獲得非常高的性能。算法，并且可獲得非常高的性能。但這不意味著我們不但這不意味著我們不需要掌握基本數(shù)據(jù)結(jié)需要掌握基本數(shù)據(jù)結(jié)構(gòu)與算法構(gòu)與算法;相反相反,只有透只有透徹理解了徹理解了,才能更好的才能更好的使用泛型使用泛型!. 由由Alexander Stepanov和和David Musser創(chuàng)立，創(chuàng)立，于于1998年被添加進(jìn)年被添加進(jìn)C+標(biāo)準(zhǔn)標(biāo)準(zhǔn). 含義：含義：編寫(xiě)不依賴(lài)于具體數(shù)據(jù)類(lèi)型的程序編寫(xiě)不依賴(lài)于具體數(shù)據(jù)類(lèi)型的程序. 目標(biāo)：目標(biāo)：將程序?qū)懙帽M可能通用將程序?qū)懙帽M可能通用 . 將算法從特定的數(shù)據(jù)結(jié)構(gòu)中抽象出來(lái)，成為通用將算法從特定的數(shù)據(jù)結(jié)構(gòu)中抽象出來(lái)，成為通用的的. C+的模板的模

3、板為泛型程序設(shè)計(jì)奠定了關(guān)鍵的基礎(chǔ)為泛型程序設(shè)計(jì)奠定了關(guān)鍵的基礎(chǔ). STL (標(biāo)準(zhǔn)模板庫(kù)標(biāo)準(zhǔn)模板庫(kù), Standard Template Library)是泛型程序設(shè)計(jì)的一個(gè)范例是泛型程序設(shè)計(jì)的一個(gè)范例.代碼重用代碼重用(reuse)!.4 【引例引例】交換交換2個(gè)整數(shù)和交換個(gè)整數(shù)和交換2個(gè)浮點(diǎn)數(shù)的個(gè)浮點(diǎn)數(shù)的C+程序程序:/交換交換2個(gè)整數(shù)個(gè)整數(shù)void S &a , int &b) int tmp = 0; tmp = a; a = b; b = tmp;/交換交換2個(gè)浮點(diǎn)數(shù)個(gè)浮點(diǎn)數(shù)void S &a , float &b) float tmp = 0.0; t

4、mp = a; a = b; b = tmp;int main() int a = 10, b=20; float c = 1.2, d=2.4; cout a= a b= b; cout c= c d= c; S); cout a= a b= b; S); cout c= c d= c; return 0;q 兩個(gè)兩個(gè)Swap函數(shù)實(shí)現(xiàn)的函數(shù)實(shí)現(xiàn)的功能相同功能相同，只是，只是參數(shù)類(lèi)型參數(shù)類(lèi)型不同不同，但為了實(shí)現(xiàn)不同類(lèi)型的數(shù)據(jù)交換必須，但為了實(shí)現(xiàn)不同類(lèi)型的數(shù)據(jù)交換必須分別分別編寫(xiě)函數(shù)編寫(xiě)函數(shù)。造成了重復(fù)勞動(dòng)。造成了重復(fù)勞動(dòng)。函數(shù)函數(shù)重載重載.5q 能否提供一種方法能否提供一種方法將兩個(gè)函數(shù)合并將

5、兩個(gè)函數(shù)合并，以節(jié)省開(kāi)，以節(jié)省開(kāi)發(fā)成本？發(fā)成本？typedef int DataType;void S &a, DataType &b)DataType tmp ;tmp = a;a = b;b = tmp;int main() int a = 10, b=20; S); return 0;v當(dāng)需要交換兩個(gè)浮點(diǎn)數(shù)時(shí)可以將當(dāng)需要交換兩個(gè)浮點(diǎn)數(shù)時(shí)可以將DataType 定義成定義成float 型數(shù)據(jù)即可。型數(shù)據(jù)即可。typedef float DateType;存在問(wèn)題：存在問(wèn)題： 更改一種數(shù)據(jù)類(lèi)型時(shí)，需要修改程序源代碼，必須更改一種數(shù)據(jù)類(lèi)型時(shí)，需要修改程序源代碼，必須重新編譯程序

6、。重新編譯程序。 如果程序中需要交換多種數(shù)據(jù)類(lèi)型數(shù)據(jù)如果程序中需要交換多種數(shù)據(jù)類(lèi)型數(shù)據(jù), 怎么辦？怎么辦？.6#includeusing namespace std;template void Swap (T &x, T &y) T tmp = x; x = y; y = tmp;int main() int a = 10, b=20; float c = 1.2, d=2.4; cout a= a b= bendl; cout c= c d= cendl; S); cout a= a b= bendl; S); cout c= c d= cendl; return 0;模板聲

7、明模板聲明定義函數(shù)模板定義函數(shù)模板通用的通用的Swap!v能否將能否將Swap函數(shù)的形式參數(shù)，作為一種無(wú)類(lèi)型的參數(shù)，當(dāng)使用函數(shù)的形式參數(shù)，作為一種無(wú)類(lèi)型的參數(shù)，當(dāng)使用它的時(shí)候再將它用具體的參數(shù)實(shí)現(xiàn)？它的時(shí)候再將它用具體的參數(shù)實(shí)現(xiàn)？模板模板機(jī)制機(jī)制.模板的概念模板的概念 模板是一種使用無(wú)類(lèi)型參數(shù)來(lái)產(chǎn)生一系列模板是一種使用無(wú)類(lèi)型參數(shù)來(lái)產(chǎn)生一系列函數(shù)函數(shù)或或類(lèi)類(lèi)的機(jī)制。的機(jī)制。 模板是以一種完全通用的方法來(lái)設(shè)計(jì)函數(shù)或類(lèi)模板是以一種完全通用的方法來(lái)設(shè)計(jì)函數(shù)或類(lèi)而而不必預(yù)先說(shuō)明不必預(yù)先說(shuō)明將被使用的每個(gè)對(duì)象的類(lèi)型。將被使用的每個(gè)對(duì)象的類(lèi)型。 通過(guò)模板可以產(chǎn)生類(lèi)或函數(shù)的集合，使它們操通過(guò)模板可以產(chǎn)生類(lèi)或函

8、數(shù)的集合，使它們操作不同的數(shù)據(jù)類(lèi)型，從而作不同的數(shù)據(jù)類(lèi)型，從而避免避免需要為每一種數(shù)需要為每一種數(shù)據(jù)類(lèi)型產(chǎn)生一個(gè)單獨(dú)的類(lèi)或函數(shù)。據(jù)類(lèi)型產(chǎn)生一個(gè)單獨(dú)的類(lèi)或函數(shù)。 7.模板分類(lèi)模板分類(lèi) 函數(shù)模板函數(shù)模板(function template) 是獨(dú)立于類(lèi)型的函數(shù)是獨(dú)立于類(lèi)型的函數(shù) 可產(chǎn)生函數(shù)的特定版本可產(chǎn)生函數(shù)的特定版本 類(lèi)模板類(lèi)模板(class template) 與類(lèi)相關(guān)的模板，如與類(lèi)相關(guān)的模板，如vector 可產(chǎn)生類(lèi)對(duì)特定類(lèi)型的版本，如可產(chǎn)生類(lèi)對(duì)特定類(lèi)型的版本，如vector8.模板工作方式模板工作方式 模板只是說(shuō)明模板只是說(shuō)明，需要，需要實(shí)例化實(shí)例化后才能執(zhí)行或使用后才能執(zhí)行或使用.9 模

9、模 板板函數(shù)模板函數(shù)模板 類(lèi)模板類(lèi)模板模模 板板 類(lèi)類(lèi)模板函數(shù)模板函數(shù)對(duì)對(duì) 象象實(shí)例化實(shí)例化實(shí)例化實(shí)例化實(shí)例化實(shí)例化.(function template)定義格式：定義格式：template類(lèi)型名類(lèi)型名 函數(shù)名（參數(shù)表）函數(shù)名（參數(shù)表） 函數(shù)體函數(shù)體template void Swap (T &x, T &y) T tmp = x; x = y; y = tmp;10 template: 函數(shù)模板定義關(guān)鍵字函數(shù)模板定義關(guān)鍵字. 中中是函數(shù)的模板參數(shù)，參數(shù)可有一個(gè)或多個(gè)，逗號(hào)隔是函數(shù)的模板參數(shù)，參數(shù)可有一個(gè)或多個(gè)，逗號(hào)隔開(kāi)。開(kāi)。不能為空！不能為空！ 模板參數(shù)常用形式：模板參數(shù)常

10、用形式： class 標(biāo)識(shí)符標(biāo)識(shí)符 或者或者 typename 標(biāo)識(shí)符標(biāo)識(shí)符模板參數(shù)表明函數(shù)可以接收的類(lèi)型參數(shù)，可以是內(nèi)部類(lèi)型，模板參數(shù)表明函數(shù)可以接收的類(lèi)型參數(shù)，可以是內(nèi)部類(lèi)型，也可以是自定義類(lèi)型也可以是自定義類(lèi)型.template void Swap (T &x, T &y) T tmp = x; x = y; y = tmp;. 【例例1】簡(jiǎn)單函數(shù)模板定義和應(yīng)用簡(jiǎn)單函數(shù)模板定義和應(yīng)用.#include using namespace std;template T Max ( T a , T b ) return a b ? a : b ; int main ( ) cou

11、t 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 ) b ? a : b ; 由實(shí)參類(lèi)型實(shí)例化由實(shí)參類(lèi)型實(shí)例化char Max ( char a , char b ) return a b ? a : b ; double Max ( double a , double b ) return a b ? a : b ; 編譯器生成的編譯器生成的模板函數(shù)模板函數(shù)函數(shù)模板實(shí)例化函數(shù)模板實(shí)例化函數(shù)模板的

12、原理分析：函數(shù)模板的原理分析： 函數(shù)模板中聲明了類(lèi)型參數(shù)函數(shù)模板中聲明了類(lèi)型參數(shù)T，表示了，表示了一種抽象類(lèi)型一種抽象類(lèi)型. 編譯器檢測(cè)到程序調(diào)用函數(shù)模板編譯器檢測(cè)到程序調(diào)用函數(shù)模板Max時(shí)，用其第一個(gè)實(shí)參類(lèi)型替換掉模板中的時(shí)，用其第一個(gè)實(shí)參類(lèi)型替換掉模板中的T，同時(shí)建立一個(gè)完整的函數(shù)，同時(shí)建立一個(gè)完整的函數(shù)Max，并編，并編譯該新建的函數(shù)譯該新建的函數(shù). 本例中，針對(duì)三種數(shù)據(jù)類(lèi)型，生成了本例中，針對(duì)三種數(shù)據(jù)類(lèi)型，生成了三種函數(shù)三種函數(shù). 【練習(xí)練習(xí)1】編寫(xiě)一個(gè)對(duì)具有編寫(xiě)一個(gè)對(duì)具有n個(gè)元素的數(shù)組個(gè)元素的數(shù)組a 求最小求最小值的程序，要求值的程序，要求將求最小值的函數(shù)設(shè)計(jì)成函數(shù)模板將求最小值的函

13、數(shù)設(shè)計(jì)成函數(shù)模板。#include using namespace std;template T MinArray(T a,int n)int i;T mina=a0;for( i = 1;i ai) mina=ai;return mina;int main() int arr1=1,3,0,2,7,6,4,5,2; double arr2=1.2,-3.4,6.8,9,8; coutarr1數(shù)組的最小值為：數(shù)組的最小值為： MinArray(arr1,9) endl; coutarr2數(shù)組的最小值為：數(shù)組的最小值為： MinArray(arr2,4)endl; return 0;. 注意點(diǎn)注

14、意點(diǎn)1：實(shí)參類(lèi)型與形參類(lèi)型必須嚴(yán)格匹配實(shí)參類(lèi)型與形參類(lèi)型必須嚴(yán)格匹配.#include using namespace std;template T Max ( T a , T b ) return a b ? a : b ; int main ( ) int a=3; float b=1.5; cout Max (a,b) is Max(a,b) endl ; return 0;錯(cuò)誤！錯(cuò)誤！模板類(lèi)型不能提供模板類(lèi)型不能提供類(lèi)型的隱式轉(zhuǎn)換類(lèi)型的隱式轉(zhuǎn)換. 注意點(diǎn)注意點(diǎn)2：在函數(shù)模板中允許使用多個(gè)類(lèi)型參數(shù)。在在函數(shù)模板中允許使用多個(gè)類(lèi)型參數(shù)。在template定義部分的每個(gè)模板形參前必須有關(guān)鍵字

15、定義部分的每個(gè)模板形參前必須有關(guān)鍵字class或或typename.#includeusing namespace std;templatevoid myfunc(T1 x , T2 y) coutx, yendl; int main() myfunc(100, hao); myfunc(3.14, 10L); return 0;. 注意點(diǎn)注意點(diǎn)3：在在template語(yǔ)句與函數(shù)模板定義語(yǔ)句之間語(yǔ)句與函數(shù)模板定義語(yǔ)句之間不允許有別的語(yǔ)句。不允許有別的語(yǔ)句。Template int i; /錯(cuò)誤，不允許有別的語(yǔ)句錯(cuò)誤，不允許有別的語(yǔ)句T Max(T x,T y) return(xy)? x :

16、y;8.優(yōu)點(diǎn)優(yōu)點(diǎn):函數(shù)模板方法克服了函數(shù)模板方法克服了C語(yǔ)言用大量不同函數(shù)名表示相語(yǔ)言用大量不同函數(shù)名表示相似功能的弊端似功能的弊端;克服了宏定義不能進(jìn)行參數(shù)類(lèi)型檢查的弊端克服了宏定義不能進(jìn)行參數(shù)類(lèi)型檢查的弊端;克服了克服了C+函數(shù)重載用相同函數(shù)名字重寫(xiě)幾個(gè)函數(shù)函數(shù)重載用相同函數(shù)名字重寫(xiě)幾個(gè)函數(shù)的繁瑣的繁瑣.缺點(diǎn)缺點(diǎn): 調(diào)試比較困難調(diào)試比較困難.一般先寫(xiě)一個(gè)特殊版本的函數(shù)一般先寫(xiě)一個(gè)特殊版本的函數(shù)運(yùn)行正確后，改成模板函數(shù)運(yùn)行正確后，改成模板函數(shù)16.17 【練習(xí)練習(xí)2】編寫(xiě)一個(gè)函數(shù)模板，它返回兩個(gè)值中的較編寫(xiě)一個(gè)函數(shù)模板，它返回兩個(gè)值中的較小者，同時(shí)要求能正確處理字符串。小者，同時(shí)要求能正確處

17、理字符串。 分析：分析： 由于由于C+字符串比較的方法與字符型、數(shù)值型字符串比較的方法與字符型、數(shù)值型都不同，因此函數(shù)模板不適用于字符串比較；都不同，因此函數(shù)模板不適用于字符串比較；這里設(shè)計(jì)一個(gè)函數(shù)模板這里設(shè)計(jì)一個(gè)函數(shù)模板template T min(T a,T b)，可以處理，可以處理int、float和和char 等數(shù)據(jù)等數(shù)據(jù)類(lèi)型類(lèi)型；為了能正確處理字符串，添加一個(gè)重載函數(shù)專(zhuān)門(mén)處理為了能正確處理字符串，添加一個(gè)重載函數(shù)專(zhuān)門(mén)處理字符串比較，即字符串比較，即char *min(char *a,char *b)。 .#include #include template T min(T a,T b

18、) return (ab?a:b); char *min(char *a,char *b) return (strcmp(a,b)0?a:b); void main() double a=3.14, b=8.28; char s1=Bad,s2=Good; cout輸出結(jié)果輸出結(jié)果:endl; coutmin(a,b)endl; coutmin(s1,s2)endl; 函數(shù)模板函數(shù)模板函數(shù)重載函數(shù)重載. STL是一個(gè)具有是一個(gè)具有工業(yè)強(qiáng)度工業(yè)強(qiáng)度的，的，高效的高效的C+程序庫(kù)程序庫(kù) 包含了諸多在計(jì)算機(jī)科學(xué)領(lǐng)域里所常用的基本數(shù)包含了諸多在計(jì)算機(jī)科學(xué)領(lǐng)域里所常用的基本數(shù)據(jù)結(jié)構(gòu)和基本算法據(jù)結(jié)構(gòu)和基本

19、算法 STL主要包含了主要包含了容器容器、算法算法、迭代器迭代器 庫(kù)（庫(kù)（library）是一系列程序組件的集合，它們可是一系列程序組件的集合，它們可以在不同的程序中重復(fù)使用。以在不同的程序中重復(fù)使用。.21 【引例引例】閱讀以下程序閱讀以下程序:#include #include using namespace std;int main() vector v; int i; for (i=0;i10;i+) v.push_back(i); for (vector:iterator it=v.begin();it!=v.end();it+) cout*it,; coutendl; return

20、 0;Vector容器容器聲明一個(gè)整型聲明一個(gè)整型Vector容器容器尾部元素追加尾部元素追加用迭代器配合循環(huán)用迭代器配合循環(huán)訪(fǎng)問(wèn)向量元素訪(fǎng)問(wèn)向量元素.22 容器容器：可容納各種數(shù)據(jù)類(lèi)型的可容納各種數(shù)據(jù)類(lèi)型的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 迭代器迭代器：可可訪(fǎng)問(wèn)訪(fǎng)問(wèn)容器中元素的容器中元素的特殊指針特殊指針 算法算法：用來(lái)操作容器中元素的用來(lái)操作容器中元素的函數(shù)模板函數(shù)模板 函數(shù)對(duì)象函數(shù)對(duì)象: 是一個(gè)行為類(lèi)似函數(shù)的對(duì)象，可象函數(shù)是一個(gè)行為類(lèi)似函數(shù)的對(duì)象，可象函數(shù)一樣調(diào)用。一樣調(diào)用。 例如，向量例如，向量Vector就是就是容器容器， iterator是是迭代器迭代器。 STL用用sort()來(lái)對(duì)一個(gè)來(lái)對(duì)一個(gè)v

21、ector中的數(shù)據(jù)進(jìn)行排序，用中的數(shù)據(jù)進(jìn)行排序，用find()來(lái)搜索一個(gè)來(lái)搜索一個(gè)list中的對(duì)象中的對(duì)象最基本的最基本的遍歷結(jié)構(gòu)遍歷結(jié)構(gòu)對(duì)數(shù)據(jù)結(jié)構(gòu)的操作對(duì)數(shù)據(jù)結(jié)構(gòu)的操作 C+STL是是通用通用數(shù)據(jù)結(jié)構(gòu)和算法數(shù)據(jù)結(jié)構(gòu)和算法的封裝！的封裝！. C+STL中，中，容器容器（container）就是）就是通用的數(shù)據(jù)結(jié)構(gòu)通用的數(shù)據(jù)結(jié)構(gòu)。 容器用來(lái)承載不同類(lèi)型的數(shù)據(jù)對(duì)象容器用來(lái)承載不同類(lèi)型的數(shù)據(jù)對(duì)象; C+中的容器還存在一定的中的容器還存在一定的“數(shù)據(jù)加工能力數(shù)據(jù)加工能力” 它如同一個(gè)對(duì)數(shù)據(jù)對(duì)象進(jìn)行加工的模具，可以把不同它如同一個(gè)對(duì)數(shù)據(jù)對(duì)象進(jìn)行加工的模具，可以把不同類(lèi)型的數(shù)據(jù)放到這個(gè)模具中進(jìn)行加工處理，

22、形成具有一類(lèi)型的數(shù)據(jù)放到這個(gè)模具中進(jìn)行加工處理，形成具有一定共同特性的數(shù)據(jù)結(jié)構(gòu)。定共同特性的數(shù)據(jù)結(jié)構(gòu)。 例如例如, 將將int型、型、char型或者型或者float型放到隊(duì)列容器中，型放到隊(duì)列容器中，就分別生成就分別生成int隊(duì)列、隊(duì)列、char型隊(duì)列或者型隊(duì)列或者float型隊(duì)列型隊(duì)列. 它它們都是隊(duì)列，具有隊(duì)列的基本特性，但是具體數(shù)據(jù)類(lèi)型們都是隊(duì)列，具有隊(duì)列的基本特性，但是具體數(shù)據(jù)類(lèi)型是不一樣的。是不一樣的。就如同現(xiàn)實(shí)生活中，就如同現(xiàn)實(shí)生活中，人們使用容器用來(lái)裝人們使用容器用來(lái)裝載各種物品一樣載各種物品一樣.24 C+STL容器適配器用來(lái)擴(kuò)充容器適配器用來(lái)擴(kuò)充7種基本容器：種基本容器： s

23、tack：棧（：棧（LIFO）queue：隊(duì)列（：隊(duì)列（FIFO）priority_queue：優(yōu)先級(jí)隊(duì)列：優(yōu)先級(jí)隊(duì)列.25 用于指向用于指向容器容器中的元素。中的元素。 通過(guò)迭代器可以讀取它指向的元素通過(guò)迭代器可以讀取它指向的元素。 迭代器是迭代器是泛化的指針?lè)夯闹羔槪捎?，可用?”改變改變其指向位置，可用其指向位置，可用“*”訪(fǎng)問(wèn)內(nèi)容。訪(fǎng)問(wèn)內(nèi)容。.2626 C+STL包含包含70多個(gè)算法多個(gè)算法。 包括：包括：查找、排序、比較、變換、置換查找、排序、比較、變換、置換、容器管理等。容器管理等。 算法是算法是通用通用的，可作用于不同的類(lèi)對(duì)象和的，可作用于不同的類(lèi)對(duì)象和預(yù)定義類(lèi)型數(shù)據(jù)。預(yù)定義

24、類(lèi)型數(shù)據(jù)。.2727容器容器(container)算法算法(algorithm)容器容器(container)迭代器迭代器(iterator)函數(shù)對(duì)象函數(shù)對(duì)象(functionobject)迭代器迭代器(iterator) C+STL將迭代器和函數(shù)對(duì)象作為算法的參數(shù)，提供了將迭代器和函數(shù)對(duì)象作為算法的參數(shù)，提供了極大靈活性。極大靈活性。 使用使用 STL提供的或自定義的迭代器，配合提供的或自定義的迭代器，配合STL算法，可算法，可組合出各種各樣強(qiáng)大的功能組合出各種各樣強(qiáng)大的功能。.頭文件頭文件內(nèi)容內(nèi)容頭文件頭文件內(nèi)容內(nèi)容迭代器迭代器向量向量輔助功能輔助功能雙頭隊(duì)列雙頭隊(duì)列內(nèi)存管理內(nèi)存管理鏈表鏈

25、表算法算法集合與多重集合集合與多重集合函數(shù)對(duì)象函數(shù)對(duì)象映射與多重映射映射與多重映射數(shù)值運(yùn)算數(shù)值運(yùn)算棧棧隊(duì)列與優(yōu)先隊(duì)列隊(duì)列與優(yōu)先隊(duì)列. 容器容器是容納、包含一組元素或元素集合的對(duì)象。是容納、包含一組元素或元素集合的對(duì)象。 七種基本容器七種基本容器： 向量（向量（vector） 雙端隊(duì)列（雙端隊(duì)列（deque） 列表（列表（list） 集合（集合（set） 多重集合（多重集合（multiset） 映射（映射（map） 多重映射（多重映射（multimap） C+STL的容器各有不盡相同的功能和用法。的容器各有不盡相同的功能和用法。順序容器順序容器關(guān)聯(lián)容器關(guān)聯(lián)容器29.容器名容器名頭文件名頭文件名說(shuō)

26、說(shuō) 明明vector向量，從后面快速插入和刪除，直向量，從后面快速插入和刪除，直接訪(fǎng)問(wèn)任何元素接訪(fǎng)問(wèn)任何元素list雙向鏈表雙向鏈表deque雙端隊(duì)列雙端隊(duì)列set元素不重復(fù)的集合元素不重復(fù)的集合multiset元素可重復(fù)的集合元素可重復(fù)的集合map一個(gè)鍵只對(duì)于一個(gè)值的映射一個(gè)鍵只對(duì)于一個(gè)值的映射multimap一個(gè)鍵可對(duì)于多個(gè)值的映射一個(gè)鍵可對(duì)于多個(gè)值的映射stack堆棧，后進(jìn)先出（堆棧，后進(jìn)先出（LIFO）queue隊(duì)列，先進(jìn)先出（隊(duì)列，先進(jìn)先出（FIFO）priority_queue優(yōu)先級(jí)隊(duì)列優(yōu)先級(jí)隊(duì)列.r順序容器順序容器(也稱(chēng)也稱(chēng)“序列式容器序列式容器”)將一組具有將一組具有相同相同類(lèi)

27、型類(lèi)型的元素以嚴(yán)格的的元素以嚴(yán)格的線(xiàn)性形式線(xiàn)性形式組織起來(lái)。組織起來(lái)。r三類(lèi)順序容器：三類(lèi)順序容器：(1) vector 頭文件頭文件 實(shí)際上是實(shí)際上是動(dòng)態(tài)數(shù)組動(dòng)態(tài)數(shù)組。隨機(jī)存取隨機(jī)存取任何元素都能在任何元素都能在常數(shù)時(shí)間常數(shù)時(shí)間完完成。在成。在尾端增刪元素尾端增刪元素具有較佳的性能。具有較佳的性能。 (2) deque 頭文件頭文件 也是也是動(dòng)態(tài)數(shù)組動(dòng)態(tài)數(shù)組，隨機(jī)存取隨機(jī)存取任何元素都能在任何元素都能在常數(shù)時(shí)間常數(shù)時(shí)間完成完成(但性能次于但性能次于vector)。在。在兩端增刪元素兩端增刪元素具有較佳的性能。具有較佳的性能。 (3) list 頭文件頭文件 雙向鏈表雙向鏈表，在，在任何位置增

28、刪元素任何位置增刪元素都能在常數(shù)時(shí)間完成。都能在常數(shù)時(shí)間完成。不不支持隨機(jī)存取支持隨機(jī)存取。31. 關(guān)聯(lián)容器內(nèi)的關(guān)聯(lián)容器內(nèi)的元素是排序的元素是排序的，插入任何元素，都按相應(yīng)的排，插入任何元素，都按相應(yīng)的排序準(zhǔn)則來(lái)確定其位置。序準(zhǔn)則來(lái)確定其位置。 特點(diǎn)是特點(diǎn)是在查找時(shí)具有非常好的性能在查找時(shí)具有非常好的性能。 通常以平衡二叉樹(shù)方式實(shí)現(xiàn)，插入和檢索的時(shí)間都是通常以平衡二叉樹(shù)方式實(shí)現(xiàn)，插入和檢索的時(shí)間都是 O(logN)四種關(guān)聯(lián)容器：四種關(guān)聯(lián)容器：(1) set/multiset: 頭文件頭文件 set 即即集合集合。set中不允許相同元素，中不允許相同元素，multiset中允許存在相同的中允許存

29、在相同的元素。元素。(2) map/multimap: 頭文件頭文件 map與與set的不同在于的不同在于map中存放的是中存放的是成對(duì)的成對(duì)的key/value。 并根據(jù)并根據(jù)key對(duì)元素進(jìn)行排序，可快速地根據(jù)對(duì)元素進(jìn)行排序，可快速地根據(jù)key來(lái)檢索元素來(lái)檢索元素 map同同multimap的不同的不同在于是否允許多個(gè)元素有相同的在于是否允許多個(gè)元素有相同的key值。值。類(lèi)似于類(lèi)似于Hash表表32.(1) stack :頭文件頭文件 棧。棧。是項(xiàng)的有限序列，并滿(mǎn)足序列中被刪除、檢索和修改是項(xiàng)的有限序列，并滿(mǎn)足序列中被刪除、檢索和修改的項(xiàng)只能是最近插入序列的項(xiàng)。即按照的項(xiàng)只能是最近插入序列的

30、項(xiàng)。即按照后進(jìn)先出后進(jìn)先出的原則的原則(2) queue :頭文件頭文件 隊(duì)列。隊(duì)列。插入只可以在尾部進(jìn)行，刪除、檢索和修改只允許插入只可以在尾部進(jìn)行，刪除、檢索和修改只允許從頭部進(jìn)行。按照從頭部進(jìn)行。按照先進(jìn)先出先進(jìn)先出的原則。的原則。(3) priority_queue :頭文件頭文件 優(yōu)先隊(duì)列。優(yōu)先隊(duì)列。最高優(yōu)先級(jí)元素總是第一個(gè)出列。最高優(yōu)先級(jí)元素總是第一個(gè)出列。 容器適配器容器適配器是一種接口類(lèi)，為已有類(lèi)提供新的接口是一種接口類(lèi)，為已有類(lèi)提供新的接口 三種容器適配器：三種容器適配器：33. 所有容器共有的成員函數(shù)：所有容器共有的成員函數(shù)：關(guān)系運(yùn)算：關(guān)系運(yùn)算： =, , , =, = ,

31、 !=empty() : 判斷容器中是否為空判斷容器中是否為空max_size(): 容器中最多能裝多少元素容器中最多能裝多少元素size(): 容器中元素個(gè)數(shù)容器中元素個(gè)數(shù)s1.s)：交換兩個(gè)容器的內(nèi)容交換兩個(gè)容器的內(nèi)容 構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、析構(gòu)函數(shù)構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、析構(gòu)函數(shù)34. 所有所有順序容器和關(guān)聯(lián)容器順序容器和關(guān)聯(lián)容器 共有的成員函數(shù)：共有的成員函數(shù)： begin()：返回指向容器中返回指向容器中第一個(gè)元素第一個(gè)元素的迭代器的迭代器 end()：返回指向容器中返回指向容器中最后一個(gè)元素后面最后一個(gè)元素后面的位置的迭的位置的迭代器代器 rbegin(): 返回指向容器中返回指

32、向容器中最后一個(gè)元素最后一個(gè)元素的迭代器的迭代器 rend(): 返回指向容器中返回指向容器中第一個(gè)元素前面第一個(gè)元素前面的位置的迭代的位置的迭代器器 erase(): 從容器中刪除一個(gè)或幾個(gè)元素從容器中刪除一個(gè)或幾個(gè)元素 clear()： 清空容器清空容器35HeadTailbeginrbeginrendend.所有容器都具有的成員函數(shù)所有容器都具有的成員函數(shù)成員函數(shù)名成員函數(shù)名說(shuō)說(shuō) 明明默認(rèn)構(gòu)造函數(shù)默認(rèn)構(gòu)造函數(shù)對(duì)容器進(jìn)行默認(rèn)初始化的構(gòu)造函數(shù)，常有多個(gè)，用于提供不同對(duì)容器進(jìn)行默認(rèn)初始化的構(gòu)造函數(shù)，常有多個(gè)，用于提供不同的容器初始化方法的容器初始化方法拷貝構(gòu)造函數(shù)拷貝構(gòu)造函數(shù)用于將容器初始化為

33、同類(lèi)型的現(xiàn)有容器的副本用于將容器初始化為同類(lèi)型的現(xiàn)有容器的副本析構(gòu)函數(shù)析構(gòu)函數(shù)執(zhí)行容器銷(xiāo)毀時(shí)的清理工作執(zhí)行容器銷(xiāo)毀時(shí)的清理工作empty()判斷容器是否為空，若為空返回判斷容器是否為空，若為空返回true，否則返回，否則返回falsemax_size()返回容器最大容量，即容器能夠保存的最多元素個(gè)數(shù)返回容器最大容量，即容器能夠保存的最多元素個(gè)數(shù)size返回容器中當(dāng)前元素的個(gè)數(shù)返回容器中當(dāng)前元素的個(gè)數(shù)operator= (=)將一個(gè)容器賦給另一個(gè)同類(lèi)容器將一個(gè)容器賦給另一個(gè)同類(lèi)容器operator ()如果第如果第1個(gè)容器小于第個(gè)容器小于第2個(gè)容器，則返回個(gè)容器，則返回true，否則返回，否則返

34、回falseoperator= ( ()如果第如果第1個(gè)容器大于第個(gè)容器大于第2個(gè)容器，則返回個(gè)容器，則返回true，否則返回，否則返回falseoperator= (=)如果第如果第1個(gè)容器大于等于第個(gè)容器大于等于第2個(gè)容器，則返回個(gè)容器，則返回true，否則返回，否則返回falseswap交換兩個(gè)容器中的元素交換兩個(gè)容器中的元素.順序和關(guān)聯(lián)容器共同支持的成員函數(shù)順序和關(guān)聯(lián)容器共同支持的成員函數(shù)成員函數(shù)名成員函數(shù)名說(shuō)說(shuō) 明明begin()指向第一個(gè)元素指向第一個(gè)元素end()指向最后一個(gè)元素指向最后一個(gè)元素rbegin()指向按反順序的第一個(gè)元素指向按反順序的第一個(gè)元素rend()指向按反順

35、序的末端位置指向按反順序的末端位置erase()刪除容器中的一個(gè)或多個(gè)元素刪除容器中的一個(gè)或多個(gè)元素clear()刪除容器中的所有元素刪除容器中的所有元素.38#include #include using namespace std;int main() vector v1,v2; v1.push_back (5); v1.push_back (1); v2.push_back (1); v2.push_back (2); v2.push_back (3); cout v1元素?cái)?shù)元素?cái)?shù):v1.size(),v2元素?cái)?shù)元素?cái)?shù):v2.size()endl; if (v1=v2)coutv1=v2

36、endl; else if (v1v2) coutv1v2endl; else coutv2endl; v1.s); cout v1元素?cái)?shù)元素?cái)?shù):v1.size(),v2元素?cái)?shù)元素?cái)?shù):v2.size()endl; if (v1=v2)coutv1=v2endl; else if (v1v2) coutv1v2endl; else coutv2endl; return 0;聲明聲明2個(gè)向量個(gè)向量向量賦值向量賦值 5 1 v1 1 2 3 v2求元素?cái)?shù)求元素?cái)?shù)向量?jī)?nèi)容比較向量?jī)?nèi)容比較交換交換2個(gè)向量個(gè)向量.實(shí)際上就是實(shí)際上就是動(dòng)態(tài)數(shù)組動(dòng)態(tài)數(shù)組。但它比數(shù)組更靈活，當(dāng)添加數(shù)據(jù)但它比數(shù)組更靈活，當(dāng)添加數(shù)

37、據(jù)時(shí)，時(shí)，vector的大小能夠自動(dòng)增加以容納新的元素。的大小能夠自動(dòng)增加以容納新的元素。內(nèi)存自動(dòng)管理內(nèi)存自動(dòng)管理。可動(dòng)態(tài)調(diào)整所占內(nèi)存?？蓜?dòng)態(tài)調(diào)整所占內(nèi)存。支持隨機(jī)訪(fǎng)問(wèn)，支持隨機(jī)訪(fǎng)問(wèn)，隨機(jī)訪(fǎng)問(wèn)隨機(jī)訪(fǎng)問(wèn)時(shí)間為常數(shù)。時(shí)間為常數(shù)。所有所有STL算法都能對(duì)算法都能對(duì)vector操作操作。在尾部添加速度很快，在中間插入慢。在尾部添加速度很快，在中間插入慢。39.四種方式四種方式:不指定容器的元素個(gè)數(shù)：不指定容器的元素個(gè)數(shù)：vector 對(duì)象名；對(duì)象名；例如：例如： vector v; /創(chuàng)建整型向量創(chuàng)建整型向量v指定容器大?。褐付ㄈ萜鞔笮。簐ector 對(duì)象名對(duì)象名(n)；例如：例如： vector v

38、(10); /創(chuàng)建整型向量創(chuàng)建整型向量v,10個(gè)元素個(gè)元素注意：注意：元素下標(biāo)元素下標(biāo)09,初始化為初始化為0.指定容器大小和元素初始值：指定容器大小和元素初始值：vector 對(duì)象名對(duì)象名(n,初值初值)；例如：例如： vector v(10,1); /創(chuàng)建整型向量創(chuàng)建整型向量v,10個(gè)元素個(gè)元素,每個(gè)元素值均為每個(gè)元素值均為1由已有向量容器創(chuàng)建由已有向量容器創(chuàng)建: vector 對(duì)象名對(duì)象名(已有對(duì)象名已有對(duì)象名)；例如：例如： vector v2(v1); /創(chuàng)建整型向量創(chuàng)建整型向量v1的副本的副本v240拷貝構(gòu)造函數(shù)拷貝構(gòu)造函數(shù).幾種初始化幾種初始化vector對(duì)象的方式對(duì)象的方式ve

39、ctor v1;vector保存類(lèi)型為保存類(lèi)型為T(mén)的對(duì)象。的對(duì)象。默認(rèn)構(gòu)造函數(shù)默認(rèn)構(gòu)造函數(shù)v1為空為空vector v2(v1);v2是是v1的一個(gè)副本的一個(gè)副本vector v3(n, i);v3包含包含n個(gè)值為個(gè)值為i的元素的元素vector v4(n);v4包含有值初始化元素的包含有值初始化元素的n個(gè)個(gè)副本副本.#include #include using namespace std;int main() vector v(10,1); for (vector:iterator it=v.begin();it!=v.end();it+) cout*it,; coutendl; retu

40、rn 0;【例例2】創(chuàng)建創(chuàng)建一一個(gè)整型向量容器，個(gè)整型向量容器，輸出全部元素值。輸出全部元素值。42.可用可用“ ”運(yùn)算符訪(fǎng)問(wèn)運(yùn)算符訪(fǎng)問(wèn)vector的元素的元素；【例例3】用用“ ”運(yùn)算符為運(yùn)算符為整型向量容器整型向量容器元素賦值元素賦值，輸出全部輸出全部元素值。元素值。#include #include using namespace std;int main() vector v(3); v0=10; v1=100;v2=-20; for (int i=0;i3;i+) coutvi,; coutendl; return 0;43.注意：注意： 下標(biāo)操作僅能對(duì)確知已存的元素進(jìn)行賦值下標(biāo)操作

41、僅能對(duì)確知已存的元素進(jìn)行賦值和讀取操作和讀取操作vector ivec; /empty vectorfor( int ix=0; ix 100; +ix) ivecix = ix; /ivec has no element出錯(cuò)，向量中尚沒(méi)有出錯(cuò)，向量中尚沒(méi)有元素，不能訪(fǎng)問(wèn)！元素，不能訪(fǎng)問(wèn)！. 如何使相同的算法能用于不同的數(shù)據(jù)結(jié)構(gòu)如何使相同的算法能用于不同的數(shù)據(jù)結(jié)構(gòu)? - 迭代器迭代器(算法與容器的算法與容器的”中間人中間人”)45 容器類(lèi)迭代器定義方法：容器類(lèi)迭代器定義方法： 容器類(lèi)名容器類(lèi)名:iterator 變量名變量名; 訪(fǎng)問(wèn)一個(gè)迭代器指向的元素：訪(fǎng)問(wèn)一個(gè)迭代器指向的元素： * 迭代器變

42、量名迭代器變量名 迭代器上可執(zhí)行迭代器上可執(zhí)行”+” , 指向容器中的下一個(gè)元指向容器中的下一個(gè)元素。素。 如果迭代器到達(dá)了容器中的最后一個(gè)元素的后面，則迭代如果迭代器到達(dá)了容器中的最后一個(gè)元素的后面，則迭代器變成器變成past-the-end值。值。 使用一個(gè)使用一個(gè)past-the-end值的迭代器來(lái)訪(fǎng)問(wèn)對(duì)象是非法值的迭代器來(lái)訪(fǎng)問(wèn)對(duì)象是非法的的定義迭代器的關(guān)鍵字定義迭代器的關(guān)鍵字.46vector:iterator xHere = x.Begin();vector:iterator xEnd = x.End();for (; xHere != xEnd; xHere+) func_name

43、( *xHere);for (int i = 0; i x.Size(); i+) func_name(x.Get(i);.【例例4】#include #include using namespace std;int main() vector v; v.push_back(1); v.push_back(2); v.push_back(3); v.push_back(4); vector:const_iterator it1; /常量迭代器常量迭代器 for( it1 = v.begin();it1 != v.end();it1 + ) cout * it1 ,; cout endl; ve

44、ctor:reverse_iterator it2; /反向迭代器反向迭代器 for( it2 = v.rbegin();it2 != v.rend();it2+ ) cout * it2 ,; cout endl;47vector:iterator it3; /非常量迭代器非常量迭代器for( it3 = v.begin();it3 != v.end();it3 + ) * it3 = 100; /重置向量重置向量for( it3 = v.begin();it3!= v.end();it3+ ) cout * it3 ,;cout endl;return 0;HeadTailbeginrbe

45、ginrendend. （1）const_iterator ：常量迭代器常量迭代器?？梢允褂眠@種類(lèi)型?？梢允褂眠@種類(lèi)型的迭代器來(lái)指向一個(gè)的迭代器來(lái)指向一個(gè)只讀只讀的值。的值。 （2） reverse_iterator ：反向迭代器。反向迭代器。用來(lái)反轉(zhuǎn)遍用來(lái)反轉(zhuǎn)遍歷歷vector的各元素，注意用的各元素，注意用rbegin()來(lái)代替來(lái)代替begin()，用，用rend()代替代替end()，而此時(shí)的，而此時(shí)的“+”操作符會(huì)朝向后的方向操作符會(huì)朝向后的方向遍歷。遍歷。 （3）iterator：隨機(jī)迭代器，隨機(jī)迭代器，可任意方向或移動(dòng)任意個(gè)可任意方向或移動(dòng)任意個(gè)位置訪(fǎng)問(wèn)。位置訪(fǎng)問(wèn)。HeadTail

46、beginrbeginrendend有有const限制的只可讀取元限制的只可讀取元素值，不可修改元素值素值，不可修改元素值48. 不同的容器，不同的容器，STL提供的提供的迭代器功能迭代器功能各不相同。各不相同。 vector容器的迭代器：容器的迭代器：u 可使用可使用“+=”、“-”、“+”、“-=”中的任何一種操作符中的任何一種操作符u 可使用可使用“”、“”、“=”、“=”、“!=”等比較運(yùn)算符等比較運(yùn)算符u 可可隨機(jī)訪(fǎng)問(wèn)隨機(jī)訪(fǎng)問(wèn)容器中的數(shù)據(jù)元素。容器中的數(shù)據(jù)元素。49. push_back在尾部追加元素在尾部追加元素; insert方法方法可在可在vector任意位置插入元素任意位置插

47、入元素.【例例5】向向整型向量容器整型向量容器追加元素追加元素，輸出全部元素值。輸出全部元素值。 #include #include using namespace std;int main() vector v(10,1); v.push_back(100);v.psuh_back(-200); for (vector:iterator it=v.begin();it!=v.end();it+) cout*it,; coutendl; return 0; 尾部追加元素，尾部追加元素，vector容器自動(dòng)分配內(nèi)存；容器自動(dòng)分配內(nèi)存； 可對(duì)空的可對(duì)空的vector追加，也可對(duì)已有元素的追加，也可

48、對(duì)已有元素的vector追加追加.50.ABCDEaaABCDEABCDEABCDEaa在尾端增刪元素具在尾端增刪元素具有較佳的性能有較佳的性能51.insert(iterator it,T t): 對(duì)對(duì)vector容器在指定位置插入新元素容器在指定位置插入新元素【例例6】對(duì)對(duì)整型向量容器整型向量容器插入元素插入元素，輸出全部元素值。輸出全部元素值。#include #include using namespace std;int main() vector v(3); vector:iterator it; v0=10; v1=100;v2=-20; v.insert(v.begin(),5

49、0); /在最前面插入新元素在最前面插入新元素50 v.insert(v.begin()+2,8); /在第在第2個(gè)元素之前插入新元素個(gè)元素之前插入新元素8 v.insert(v.end(),9); /在末尾插入新元素在末尾插入新元素8 for (it=v.begin();it!=v.end();it+) cout*it,; coutendl; return 0; 注意：注意：insert方法要求插入的位置，是迭代器位方法要求插入的位置，是迭代器位置，而不是下標(biāo)！置，而不是下標(biāo)！52通過(guò)迭代器隨機(jī)通過(guò)迭代器隨機(jī)訪(fǎng)問(wèn)元素訪(fǎng)問(wèn)元素.pop_back刪除向量最后一個(gè)元素；刪除向量最后一個(gè)元素；era

50、se刪除指定位置或一段區(qū)間的元素刪除指定位置或一段區(qū)間的元素;clear方法刪除所有方法刪除所有元素元素.【例例7】向量容器向量容器刪除元素方法示例。刪除元素方法示例。 #include #include using namespace std;int main() vector v(10); vector:iterator it; for(int i=0;i10;i+) vi=i; v.erase(v.begin()+3); /刪除第刪除第3個(gè)元素，從個(gè)元素，從0開(kāi)始計(jì)數(shù)開(kāi)始計(jì)數(shù) for (it=v.begin();it!=v.end();it+) cout*it,; coutendl; v

51、.erase(v.begin()+1,v.begin()+3); /刪除第刪除第13個(gè)元素個(gè)元素 for (it=v.begin();it!=v.end();it+) cout*it,; coutendl向量向量V中元素?cái)?shù)：中元素?cái)?shù)：v.size()endl; v.clear(); /清空向量清空向量 coutendl向量向量V中元素?cái)?shù)：中元素?cái)?shù)：v.size()endl; return 0;區(qū)間刪除區(qū)間刪除53.向量大小有關(guān)操作列表向量大小有關(guān)操作列表v.size();返回向量的大小返回向量的大小v.max_size();返回向量可容納的最大個(gè)數(shù)返回向量可容納的最大個(gè)數(shù)v.empty();返

52、回向量是否為空返回向量是否為空v.resize(n);調(diào)整向量的大小，使其可以容納調(diào)整向量的大小，使其可以容納n個(gè)元素，個(gè)元素，如果如果nv.size(),則刪除多出來(lái)的元素則刪除多出來(lái)的元素;v.resize(n,t);調(diào)整向量的大小，使其可以容納調(diào)整向量的大小，使其可以容納n個(gè)元素，個(gè)元素，所有所有新添加的元素新添加的元素初始化為初始化為tv.capacity();獲取向量的容量，再分配內(nèi)存空間之前所能獲取向量的容量，再分配內(nèi)存空間之前所能容納的元素個(gè)數(shù)容納的元素個(gè)數(shù)54. size() 和和 resize()vector vec(10, 42); /10 int, each has va

53、lue 42cout vec.size() endl;vec.resize(15); /adds 5 elements of value 0 to the back of the vectorcout vec.size() endl;vec.resize(25, -1); / adds 10 elements of value -1 to the back of the vectorcout vec.size() endl;新增元素初始化新增元素初始化為為-155. size(),max_size()和和capacity()vector v1;coutv1.size() v1.max_size

54、()v1.capacity()endl;vector v2( 100, -1 );coutv2.size() v2.max_size() v2.capacity()endl; size()返回向量中元素的個(gè)數(shù)返回向量中元素的個(gè)數(shù) max_size()返回向量中返回向量中最多最多可容納的元素個(gè)數(shù)可容納的元素個(gè)數(shù) capacity()獲取向量的容量，再分配內(nèi)存空間之前所能容納的元素個(gè)數(shù)獲取向量的容量，再分配內(nèi)存空間之前所能容納的元素個(gè)數(shù),當(dāng)元素個(gè)數(shù)等于當(dāng)元素個(gè)數(shù)等于capacity返回的元素個(gè)數(shù)時(shí)，返回的元素個(gè)數(shù)時(shí)，vector自動(dòng)分配一段空間用自動(dòng)分配一段空間用于存儲(chǔ)輸入的新元素于存儲(chǔ)輸入的新元

55、素01223vec.size()vec.capacity()system memorymax_sizemax_size是是系統(tǒng)最大可分系統(tǒng)最大可分配的容量配的容量,并并非實(shí)際分配非實(shí)際分配56. C+STL很多算法都可以在向量上使用很多算法都可以在向量上使用; 使用算法需要包含頭文件使用算法需要包含頭文件.【例例8】在整型在整型向量容器向量容器上使用排序算法。上使用排序算法。 #include #include #include using namespace std;int main() vector v; vector:iterator it; for(int i=0;i10;i+) v.

56、push_back(10-i); for (it=v.begin();it!=v.end();it+) cout*it,; coutendl; sort(v.begin(),v.end(); /對(duì)向量排序?qū)ο蛄颗判?for (it=v.begin();it!=v.end();it+) cout*it,; coutendl; return 0;57.#include #include using namespace std;void print( vector v ) for(vector:iterator it=v.begin(); it!= v.end(); it+) cout *it en

57、dl;int main() vector vec; vec.push_back( 1 ); vec.push_back( 2 ); vec.push_back( 3 ); print( vec ); return 0;【例例9】向量向量作為函數(shù)參數(shù)示例。作為函數(shù)參數(shù)示例。 58.#include #include using namespace std;const int KVectSize = 5;int main() vector vec; int i; for(i=0;i!=KVectSize; i+) vec.push_back(i); coutvec.size() , vec.cap

58、acity() endl; vector *p = new vector(vec); coutsize() , capacity() size(); i+) (*p)i = 0; p-clear(); coutsize() , capacity()endl; delete p; return 0; 【練習(xí)練習(xí)】 閱讀程序閱讀程序59.【練習(xí)練習(xí)】 學(xué)生成績(jī)標(biāo)準(zhǔn)分的計(jì)算方法為：學(xué)生成績(jī)標(biāo)準(zhǔn)分的計(jì)算方法為： 成績(jī)成績(jī)/最高成績(jī)最高成績(jī)*100； 編寫(xiě)程序，使用向量作為存儲(chǔ)結(jié)構(gòu)，輸入學(xué)生原始成績(jī)編寫(xiě)程序，使用向量作為存儲(chǔ)結(jié)構(gòu)，輸入學(xué)生原始成績(jī)（以輸入（以輸入-1為結(jié)束），將學(xué)生成績(jī)轉(zhuǎn)換為標(biāo)準(zhǔn)分輸出，

59、每行為結(jié)束），將學(xué)生成績(jī)轉(zhuǎn)換為標(biāo)準(zhǔn)分輸出，每行一個(gè)。一個(gè)。 Sample Input769258958772-1 輸入結(jié)束輸入結(jié)束 Sample Output8096.842161.052610091.578975.789560.分析：分析：首先須比較所有學(xué)生的成績(jī)，取得最高分，將學(xué)生原首先須比較所有學(xué)生的成績(jī)，取得最高分，將學(xué)生原始成績(jī)除以最高分，然后乘上始成績(jī)除以最高分，然后乘上100。由于程序沒(méi)有給出學(xué)生人數(shù)，所以采用向量作為數(shù)據(jù)存儲(chǔ)結(jié)由于程序沒(méi)有給出學(xué)生人數(shù)，所以采用向量作為數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，因?yàn)橄蛄康脑貍€(gè)數(shù)可以自動(dòng)的動(dòng)態(tài)增長(zhǎng)。構(gòu)，因?yàn)橄蛄康脑貍€(gè)數(shù)可以自動(dòng)的動(dòng)態(tài)增長(zhǎng)。 #include

60、#includeusing namespace std;int main() vector score; /創(chuàng)建向量創(chuàng)建向量 vector:iterator it; double max,temp; cinmax; score.push_back(max); while (true) cintemp; if(temp=-1) break; score.push_back(temp); if(tempmax) max=temp; for (it=score.begin();it!=score.end();it+) *it/=max; cout*itendl; return 0;61.對(duì)比代碼：對(duì)比代碼： #include#includeusing namespace std;int