CSTL泛型編程

1、1 c+stl 2 項目中,需要用到數(shù)組、鏈表、字符串、棧、隊列 、平衡二叉樹等數(shù)據(jù)結(jié)構(gòu)，以及排序、搜索等算 法； 若全部自行編寫比較麻煩； ansi c+中包含了c+ stl (standard template library , 標(biāo)準(zhǔn)模板庫,又稱c+泛型庫 )，定義了常用的數(shù)據(jù)結(jié)構(gòu)和算法，使用十分方便 。 有了stl，不必再從頭寫大多的標(biāo)準(zhǔn)數(shù)據(jù)結(jié)構(gòu)和算 法，并且可獲得非常高的性能。 但這不意味著我們不但這不意味著我們不 需要掌握基本數(shù)據(jù)結(jié)需要掌握基本數(shù)據(jù)結(jié) 構(gòu)與算法構(gòu)與算法;相反相反,只有只有 透徹理解了透徹理解了,才能更好才能更好 的使用泛型的使用泛型! 由alexander step

2、anov和david musser創(chuàng)立， 于1998年被添加進(jìn)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)模板庫, standard template library)是泛型程序設(shè)計的一個范例. 代碼重用代碼重用 (reuse)! 4 函數(shù)模板 模板函數(shù)的重載 類模板 堆棧類 繼承 static成員 友元 5 【引例】交換2個整數(shù)和交換2個浮點數(shù)的c+程序: /交換交換2個整數(shù)個整數(shù) void swap(int tmp = a; a = b; b

3、= tmp; /交換交換2個浮點數(shù)個浮點數(shù) void swap(float tmp = 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; swap(a,b); cout a= a b= b; swap(c,d); cout c= c d= c; return 0; q 兩個swap函數(shù)實現(xiàn)的功能相同，只是參數(shù)類型 不同，但為了實現(xiàn)不同類型的數(shù)據(jù)交換必須分別 編寫函數(shù)。造成了重復(fù)勞動。 函數(shù)函數(shù) 重載重載 6 q 能否提供一種方法將兩個函數(shù)合并

4、，以節(jié)省開發(fā) 成本？ typedef int datatype; void swap(datatype tmp = a; a = b; b = tmp; int main() int a = 10, b=20; swap(a,b); return 0; v當(dāng)需要交換兩個浮點數(shù)時可以將datatype 定義成float 型數(shù)據(jù)即可。 typedef float datetype; 存在問題：存在問題： 更改一種數(shù)據(jù)類型時，需要修改程序源代碼，必須 重新編譯程序。 如果程序中需要交換多種數(shù)據(jù)類型數(shù)據(jù), 怎么辦？ 7 #include using namespace std; template vo

5、id swap (t x = y; y = tmp; void main() int a = 10, b=20; float c = 1.2, d=2.4; cout a= a b= bendl; cout c= c d= cendl; swap(a,b); cout a= a b= bendl; swap(c,d); cout c= c d= cendl; 模板聲明 定義函數(shù)模板 通用的swap! 模板機(jī)制模板機(jī)制 模板的概念 1. 模板是一種使用無類型參數(shù)來產(chǎn)生一系列函 數(shù)或類的機(jī)制。 2. 模板是以一種完全通用的方法來設(shè)計函數(shù)或 類而不必預(yù)先說明將被使用的每個對象的類 型。 3. 通過模

6、板可以產(chǎn)生類或函數(shù)的集合，使它們 操作不同的數(shù)據(jù)類型，從而避免需要為每一 種數(shù)據(jù)類型產(chǎn)生一個單獨(dú)的類或函數(shù)。 8 模板分類 函數(shù)模板(function template) 是獨(dú)立于類型的函數(shù) 可產(chǎn)生函數(shù)的特定版本 類模板(class template) 與類相關(guān)的模板，如vector 可產(chǎn)生類對特定類型的版本，如 vector 9 模板工作方式 模板只是說明，需要實例化后才能執(zhí)行或使用. 10 模 板 函數(shù)模板 類模板 模 板 類 模板函數(shù) 對 象 實例化 實例化 實例化 (function template) 定義格式： template 類型名 函數(shù)名（參數(shù)表） 函數(shù)體 template

7、void swap (t x = y; y = tmp; 11 template: 函數(shù)模板定義關(guān)鍵字. 中是函數(shù)的模板參數(shù)，參數(shù)可有一個或多個， 逗號隔開。不能為空！ 模板參數(shù)常用形式： class 標(biāo)識符 或者 typename 標(biāo)識符 模板參數(shù)表明函數(shù)可以接收的類型參數(shù)，可以是內(nèi) 部類型，也可以是自定義類型. 【例1】簡單函數(shù)模板定義和應(yīng)用. #include using namespace std; template t max ( t a , t b ) return a b ? a : b ; int main ( ) cout max ( 3 , 5 ) is max ( 3 ,

8、 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 ; 由實參類型實例化 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ù)模板實例化 運(yùn)行結(jié)果: max(3,5) is 5 max(y, e) is y max(9.3, 0.5

9、) is 9.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 using namespace std; template t minarray(t a,int n) int i; t mina=a0; for( i = 1;i ai) mina=ai; return mina

10、; void 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; 運(yùn)行結(jié)果運(yùn)行結(jié)果: arr1數(shù)組的最小值為：數(shù)組的最小值為：0 arr2數(shù)組的最小值為數(shù)組的最小值為: -3.4 注意點1：實參類型與形參類型必須嚴(yán)格匹配. #include using namespace std; template t max ( t a , t

11、 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; 錯誤！模板類型不能 提供類型的隱式轉(zhuǎn)換 注意點2：在函數(shù)模板中允許使用多個類型參數(shù)。在 template定義部分的每個模板形參前必須有關(guān)鍵字 class或typename. #include using namespace std; template void myfunc(t1 x , t2 y) coutx, yendl; 運(yùn)行結(jié)果運(yùn)行結(jié)果: 100, hao 3.14, 10 vo

12、id main() myfunc(100, hao); myfunc(3.14, 10l); 注意點3：在template語句與函數(shù)模 板定義語句之間不允許有別的語句。 template int i; t max(t x,t y) return(xy)? x : y; 8 /錯誤，不允許有別的語句錯誤，不允許有別的語句 模板優(yōu)缺點 優(yōu)點: 函數(shù)模板方法克服了c語言用大量不同函數(shù)名表示相 似功能的弊端; 克服了宏定義不能進(jìn)行參數(shù)類型檢查的弊端; 克服了c+函數(shù)重載用相同函數(shù)名字重寫幾個函數(shù) 的繁瑣. 缺點: 調(diào)試比較困難. 一般先寫一個特殊版本的函數(shù) 運(yùn)行正確后，改成模板函數(shù) 17 18 【練習(xí)

13、2】編寫一個函數(shù)模板，它返回兩個值中的較小者， 同時要求能正確處理字符串。 分析： 由于c+字符串比較的方法與字符型、數(shù)值型都不 同，因此函數(shù)模板不適用于字符串比較； 這里設(shè)計一個函數(shù)模板template t min(t a,t b)，可以處理int、float和char 等數(shù)據(jù) 類型； 為了能正確處理字符串，添加一個重載函數(shù)專門處 理字符串比較，即char *min(char *a,char *b)。 #include #include template t min(t a, t b) return (ab?a:b); char *min(char *a,char *b) return (s

14、trcmp(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ù)重載 運(yùn)行結(jié)果: 3.14 bad 20 可以顯式指定（可以顯式指定（explicitly specify），如：），如： i=max(ia,5); d=max(da,6); 用函數(shù)模板求數(shù)組元素中最大值用函數(shù)模板求數(shù)組元素中最大值 template groap max(const groap *r_array,int s

15、ize) int i; groap max_val=r_array0; for ( i=1; i max_val ) max_val=r_arrayi; return max_val; 可讀性更好?？勺x性更好。 21 函數(shù)模板函數(shù)模板可以可以重載重載, 形參表不同即可形參表不同即可 例例, 下面兩個模板可以同時存在下面兩個模板可以同時存在: template void print(t1 arg1, t2 arg2) cout arg1 arg2endl; template void print(t arg1, t arg2) cout arg1 arg2endl; 重載重載 22 例例: 函數(shù)

16、模板調(diào)用順序函數(shù)模板調(diào)用順序 23 double max(double a, double b) cout mymax endl; return 0; template t max( t a, t b ) cout template max 1 endl; return 0; template t max( t a, t2 b ) cout template max 2 endl; return 0; 24 void main() int i=4, j=5; max( 1.2, 3.4 ); max( i, j ); max(1.2, 3); 25 匹配順序匹配順序 c+編譯編譯器遵循以下器遵

17、循以下優(yōu)先順序優(yōu)先順序: step 1: 先找參數(shù)完全匹配的先找參數(shù)完全匹配的普通函數(shù)普通函數(shù)(非由模非由模 板實例化而得的函數(shù)板實例化而得的函數(shù)) step 2: 再找參數(shù)完全匹配的再找參數(shù)完全匹配的模板函數(shù)模板函數(shù) step 3: 再找實參經(jīng)過自動類型轉(zhuǎn)換后能夠匹再找實參經(jīng)過自動類型轉(zhuǎn)換后能夠匹 配的配的普通函數(shù)普通函數(shù) step 4: 上面的都找不到上面的都找不到, 則報錯則報錯 26 void main() int i=4, j=5; max( 1.2, 3.4 ); max( i, j ); max(1.2, 3); /調(diào)用max(double, double)函數(shù) /調(diào)用第一個t

18、max(t a, t b)模板生成的函數(shù) /調(diào)用第二個t max(t a, t2 b)模板生成的函數(shù) 運(yùn)行結(jié)果: mymax template max 1 template max 2 27 l 可以在函數(shù)模板中使用可以在函數(shù)模板中使用多個類型參數(shù)多個類型參數(shù), 可以可以避免二義性避免二義性 template t1 myfunction( t1 arg1, t2 arg2) coutarg1“ ”arg2“n”; return arg1; myfunction( 5, 7 ); myfunction( 5.8, 8.4 ); myfunction( 5, 8.4 ); /ok：replace

19、t1 and t2 with int /ok: replace t1 and t2 with double /ok: replace t1 with int, t2 with double 28 類模板的定義 c+的類模板的寫法如下的類模板的寫法如下: template class 類模板名類模板名 成員函數(shù)和成員變量成員函數(shù)和成員變量 ; 類型參數(shù)表的寫法就是類型參數(shù)表的寫法就是: class 類型參數(shù)類型參數(shù)1, class 類型參數(shù)類型參數(shù)2, 29 類模板里的成員函數(shù)類模板里的成員函數(shù), 如在類模板外面定義時如在類模板外面定義時, template 返回值類型返回值類型 類模板名類模板

20、名:成員成員 函數(shù)名函數(shù)名(參數(shù)表參數(shù)表) 類模板的定義類模板的定義 30 l 用類模板定義對象的寫法用類模板定義對象的寫法如下如下: 類模板名類模板名 對象名對象名(構(gòu)造構(gòu)造 函數(shù)實際參數(shù)表函數(shù)實際參數(shù)表); l 如果類模板有如果類模板有無參構(gòu)造函數(shù)無參構(gòu)造函數(shù), 那么也可那么也可 以只寫以只寫: 類模板名類模板名 對象名對象名; 類模板的定義類模板的定義 31 pair類模板類模板: template class pair public: t1 key; /關(guān)鍵字關(guān)鍵字 t2 value; /值值 pair(t1 k,t2 v) : key(k), value(v) ; bool oper

21、ator (const pair ; template bool pair:operator( const pair 類模板的定義類模板的定義 32 #include #include using namespace std; 。 void main() pair stu(tom, 19); pair stu2(jack, 20); if (stu.operator(stu2) ) cout stu.key stu.value; else cout stu.key stu2.value; 運(yùn)行結(jié)果: jack 20 pair類模板的使用類模板的使用: 33 使用類模板聲明對象使用類模板聲明對象

22、 n 編譯器由類模板生成類的編譯器由類模板生成類的過程過程叫類模板的叫類模板的實實 例化例化 編譯器自動用編譯器自動用具體具體的數(shù)據(jù)類型的數(shù)據(jù)類型替換替換類模板中的類模板中的 類型參數(shù)類型參數(shù), 生成模板類的代碼生成模板類的代碼 n 由類模板實例化得到的類叫由類模板實例化得到的類叫模板類模板類 為類型參數(shù)指定的數(shù)據(jù)類型不同為類型參數(shù)指定的數(shù)據(jù)類型不同, 得到的模板得到的模板 類不同類不同 同一個類模板的兩個模板類是不兼容的同一個類模板的兩個模板類是不兼容的 pair * p; pair a; p = /wrong 34 #include using namespace std; templat

23、e class a public: template void func(t2 t) cout t; ; void main() a a; a.func(k); 若函數(shù)模板改為若函數(shù)模板改為 template void func(t t)coutt 將報錯將報錯 “declaration of class t shadows template parm class t ” 程序輸出程序輸出: k /成員函數(shù)模板成員函數(shù)模板 /成員函數(shù)模板成員函數(shù)模板 func被實例化被實例化 函數(shù)模版作為類模板成員函數(shù)模版作為類模板成員 35 template class a public: template

24、 void func(t2 t); ; template template void a:func(t2 t) cout t; void main() a a; a.func(k); 36 n類模板的參數(shù)聲明中可以包括類模板的參數(shù)聲明中可以包括非類型參數(shù)非類型參數(shù) template 非類型參數(shù)非類型參數(shù): 用來說明類模板中的用來說明類模板中的屬性屬性 類型參數(shù)類型參數(shù): 用來說明類模板中的用來說明類模板中的屬性類型屬性類型, 成員操作的參數(shù)類型和返回值類型成員操作的參數(shù)類型和返回值類型 類模板與非類型參數(shù) 37 template class carray t arraysize; public

25、: void print( ) for(int i = 0; i size; +i) cout array i endl; ; 類模板與非類型參數(shù)類模板與非類型參數(shù) carray a2; carray a3; 38 carray a2; carray a3; l 注意注意: carray和和carray完全是兩個完全是兩個 類類 這兩個類的對象之間這兩個類的對象之間不能互相賦值不能互相賦值 類模板與非類型參數(shù)類模板與非類型參數(shù) 39 l類模板派生出類模板類模板派生出類模板 l模板類模板類 (即類模板中類型即類模板中類型/非類型參數(shù)實例化后非類型參數(shù)實例化后 的類的類) l派生出類模板派生出類模

26、板 l普通類派生出類模板普通類派生出類模板 l模板類派生出普通類模板類派生出普通類 類模板與繼承類模板與繼承 派生派生 類模板類模板 類模板類模板 模板類模板類 類模板類模板 類模板類模板 類模板類模板 普通類普通類模板類模板類 40 (1) template class a t1 v1; t2 v2; ; template class b : public a t1 v3; t2 v4; ; template class c : public b t v5; ; void main() b obj1; c obj2; 41 void main() b obj1; c obj2; class

27、b:public a int v3; double v4; ; class a double v1; int v2; ; 42 template class a t1 v1; t2 v2; ; template class b:public a t v; ; int main() b obj1; return 0; 自動生成兩個模板類：自動生成兩個模板類：? 43 template class a t1 v1; t2 v2; ; template class b:public a t v; ; int main() b obj1; return 0; 自動生成兩個模板類：自動生成兩個模板類：

28、a和和b (2) (2) 類模板從模板類派生類模板從模板類派生 44 class a int v1; ; template class b : public a t v; ; int main() b obj1; return 0; (3) (3) 類模板從普通類派生類模板從普通類派生 45 template class a t v1; int n; ; class b : public a double v; ; int main() b obj1; return 0; 46 c+支持兩種編譯模式支持兩種編譯模式 包含模式包含模式 ( inclusion model ) 把所有的定義一起放在

29、頭文件中，在調(diào)用的把所有的定義一起放在頭文件中，在調(diào)用的cpp中，中， 包含相關(guān)的頭文件包含相關(guān)的頭文件 分離模式分離模式 ( separation model ) (好像好像vc編譯器編譯器 不支持不支持) / model.h template type tmin( type t1, type t2 ); / model.cpp export template type tmin( type t1, type t2 ); / test.cpp #include “model.h” int i, j; double d = min( i, j ); 模板編譯模式模板編譯模式 47 1. 矩陣運(yùn)

30、算：矩陣轉(zhuǎn)置與矩陣相乘函數(shù)模板。下標(biāo)作為參矩陣運(yùn)算：矩陣轉(zhuǎn)置與矩陣相乘函數(shù)模板。下標(biāo)作為參 數(shù)傳遞。數(shù)傳遞。 2.線性表線性表是數(shù)據(jù)結(jié)構(gòu)中的概念。數(shù)組中是數(shù)據(jù)結(jié)構(gòu)中的概念。數(shù)組中除第一個元素外，其他除第一個元素外，其他 元素有且僅有一個直接前驅(qū)，第一個元素沒有前驅(qū)；除最后元素有且僅有一個直接前驅(qū)，第一個元素沒有前驅(qū)；除最后 一個元素外，其他元素有且僅有一個直接后繼，最后一個元一個元素外，其他元素有且僅有一個直接后繼，最后一個元 素?zé)o后繼。這樣的特性稱為素?zé)o后繼。這樣的特性稱為線性關(guān)系線性關(guān)系。所以稱數(shù)組元素在一。所以稱數(shù)組元素在一 個線性表中。個線性表中。線性表實際包括線性表實際包括順序表順序

31、表（數(shù)組）和（數(shù)組）和鏈表鏈表。 對順序表的對順序表的典型操作典型操作包括：計算表長度，尋找變量或包括：計算表長度，尋找變量或 對象對象x（其類型與表元素相同）在表中的位置（下標(biāo)值），（其類型與表元素相同）在表中的位置（下標(biāo)值）， 判斷判斷x是否在表中，刪除是否在表中，刪除x，將，將x插入列表中第插入列表中第i個位置，尋個位置，尋 找找x的后繼，尋找的后繼，尋找x的前驅(qū)，判斷表是否空，判斷表是否滿的前驅(qū)，判斷表是否空，判斷表是否滿 （表滿不能再插入數(shù)據(jù)，否則會溢出，產(chǎn)生不可預(yù)知的錯（表滿不能再插入數(shù)據(jù)，否則會溢出，產(chǎn)生不可預(yù)知的錯 誤），取第誤），取第i個元素的值。個元素的值。 作業(yè) 48 堆

32、棧類及其模板實現(xiàn) class cstack public: cstack(int capcity = 20); cstack(); void clearstack(); bool isempty(); bool isfull(); int stacklength(); char gettop(); void push(char e); void pop(); private: char* elemarray; int top; int capcity; ; 49 函數(shù)、類、類的成員函數(shù)作為類模板函數(shù)、類、類的成員函數(shù)作為類模板 的友元的友元 函數(shù)模板作為類模板的友元函數(shù)模板作為類模板的友元 函

33、數(shù)模板作為類的友元函數(shù)模板作為類的友元 類模板作為類模板的友元類模板作為類模板的友元 50 void func1() class a ; class b public: void func() ; template class tmpl friend void func1(); friend class a; friend void b:func(); ; 51 int main() tmpl i; tmpl f; return 0; 52 #include #include using namespace std; template class pair private: t1 key; /

34、關(guān)鍵字 t2 value; /值 public: pair(t1 k,t2 v):key(k),value(v) ; bool operator ( const pair template friend ostream ; 53 template bool pair:operator ( const pair template ostream return o; 54 int main() pair student(tom,29); pair obj(12,3.14); cout student obj; return 0; 從 template ostream class a int v;

35、public: a(int n):v(n) template friend void print(const t ; template void print(const t 56 int main() a a(4); print(a); return 0; 從 template void print(const t ? 57 #include #include using namespace using namespace stdstd; ; templatetemplate class aclass a public:public: void void funcfunc( ( constco

36、nst t ; ; template template class bclass b private :private : t v; t v; public:public: b(t n):v(n) b(t n):v(n) templatetemplate friend class a; friend class a; /把類模板把類模板a a聲明為友元聲明為友元 ; 58 int main() b b(5); a b a; a.func (b); return 0; a b 類，成了類，成了b類的友元。類的友元。 從從a模版實例化出來的類，都是模版實例化出來的類，都是b實例化出來的實例化出來的

37、 類的友元類的友元 類模板作為類模板的友元類模板作為類模板的友元 /用用b替換替換a模板中的模板中的t 輸出結(jié)果： 5 59 #include using namespace std; template class a private: static int count; public: a() +count; a() - count; ; a( const a static void printcount() cout count endl; ; 60 template int a:count = 0; template int a:count = 0; int main() a ia, i

38、b; a da; ia.printcount(); ib.printcount(); da.printcount(); return 0; 輸出結(jié)果： 2 2 1 stl是一個具有工業(yè)強(qiáng)度的，高效的c+ 程序庫 包含了諸多在計算機(jī)科學(xué)領(lǐng)域里所常用的 基本數(shù)據(jù)結(jié)構(gòu)和基本算法 stl主要包含了容器、算法、迭代器 庫（library）是一系列程序組件的集合， 它們可以在不同的程序中重復(fù)使用。 63 【引例】閱讀以下程序: #include #include using namespace std; void main() vector v; int i; for (i=0;i10;i+) v.pus

39、h_back(i); for (vector:iterator it=v.begin();it!=v.end();it+) cout*it,; coutendl; vector容器容器 聲明一個整型聲明一個整型 vector容器容器 尾部元素追加尾部元素追加 用迭代器配合循環(huán)用迭代器配合循環(huán) 訪問向量元素訪問向量元素 64 容器：可容納各種數(shù)據(jù)類型的數(shù)據(jù)結(jié)構(gòu) 迭代器：可訪問容器中元素的特殊指針 算法：用來操作容器中元素的函數(shù)模板 函數(shù)對象: 是一個行為類似函數(shù)的對象，可象函數(shù) 一樣調(diào)用。 例如，向量vector就是容器， iterator是迭代器。 stl用sort()來對一個vector中的

40、數(shù)據(jù)進(jìn)行排序，用 find()來搜索一個list中的對象 最基本的最基本的 遍歷結(jié)構(gòu)遍歷結(jié)構(gòu) 對數(shù)據(jù)結(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ù)對象進(jìn)行加工的模具，可以把不同 類型的數(shù)據(jù)放到這個模具中進(jìn)行加工處理，形成具有一 定共同特性的數(shù)據(jù)結(jié)構(gòu)。 例如, 將int型、char型或者float型放到隊列容器中， 就分別生成int隊列、char型隊列或者float型隊列. 它 們都是隊列，具有隊列的基本特性，但是具體數(shù)據(jù)

41、類型 是不一樣的。 就如同現(xiàn)實生活中，就如同現(xiàn)實生活中， 人們使用容器用來裝人們使用容器用來裝 載各種物品一樣載各種物品一樣 66 c+stl容器適配器用來擴(kuò)充7種基本容器： stack：棧（lifo） queue：隊列（fifo） priority_queue：優(yōu)先級隊列 67 用于指向容器中的元素。 通過迭代器可以讀取它指向的元素。 迭代器是泛化的指針，可用“+”改變 其指向位置，可用“*”訪問內(nèi)容。 6868 c+stl包含70多個算法。 包括：查找、排序、比較、變換、置換、 容器管理等。 算法是通用的，可作用于不同的類對象和 預(yù)定義類型數(shù)據(jù)。 6969 容器 (container) 算

42、法 (algorithm) 容器 (container) 迭代器 (iterator) 函數(shù)對象 (function object) 迭代器 (iterator) c+stl將迭代器和函數(shù)對象作為算法的參數(shù)，提供了 極大靈活性。 使用 stl提供的或自定義的迭代器，配合stl算法，可 組合出各種各樣強(qiáng)大的功能。 頭文件內(nèi)容頭文件內(nèi)容 迭代器向量 輔助功能雙頭隊列 內(nèi)存管理鏈表 算法集合與多重集合 函數(shù)對象映射與多重映射 數(shù)值運(yùn)算棧 隊列與優(yōu)先隊列 容器是容納、包含一組元素或元素集合的對象。 七種基本容器： 向量（vector） 雙端隊列（deque） 列表（list） 集合（set） 多重集合

43、（multiset） 映射（map） 多重映射（multimap） c+stl的容器各有不盡相同的功能和用法。 順序容器 關(guān)聯(lián)容器 71 容器名頭文件名說 明 vector 向量，從后面快速插入和刪除，直 接訪問任何元素 list雙向鏈表 deque雙端隊列 set元素不重復(fù)的集合 multiset元素可重復(fù)的集合 map一個鍵只對于一個值的映射 multimap一個鍵可對于多個值的映射 stack堆棧，后進(jìn)先出（lifo） queue隊列，先進(jìn)先出（fifo） priority_queue優(yōu)先級隊列 sequence container r順序容器(也稱“序列式容器”)將一組具有相同 類型的

44、元素以嚴(yán)格的線性形式組織起來。 r三類順序容器： (1) vector 頭文件 實際上是動態(tài)數(shù)組。隨機(jī)存取任何元素都能在常數(shù)時間完 成。在尾端增刪元素具有較佳的性能。 (2) deque 頭文件 也是動態(tài)數(shù)組，隨機(jī)存取任何元素都能在常數(shù)時間完成(但 性能次于vector)。在兩端增刪元素具有較佳的性能。 (3) list 頭文件 雙向鏈表，在任何位置增刪元素都能在常數(shù)時間完成。不 支持隨機(jī)存取。 73 關(guān)聯(lián)容器內(nèi)的元素是排序的，插入任何元素，都按相應(yīng)的排 序準(zhǔn)則來確定其位置。 特點是在查找時具有非常好的性能。 通常以平衡二叉樹方式實現(xiàn)，插入和檢索的時間都是 o(logn) 四種關(guān)聯(lián)容器： (1

45、) set/multiset: 頭文件 set 即集合。set中不允許相同元素，multiset中允許存在相同的 元素。 (2) map/multimap: 頭文件 map與set的不同在于map中存放的是成對的key/value。 并根據(jù)key對元素進(jìn)行排序，可快速地根據(jù)key來檢索元素 map同multimap的不同在于是否允許多個元素有相同的key值。 類似于hash表 74 (1) stack :頭文件 棧。是項的有限序列，并滿足序列中被刪除、檢索和修改 的項只能是最近插入序列的項。即按照后進(jìn)先出的原則 (2) queue :頭文件 隊列。插入只可以在尾部進(jìn)行，刪除、檢索和修改只允許

46、從頭部進(jìn)行。按照先進(jìn)先出的原則。 (3) priority_queue :頭文件 優(yōu)先隊列。最高優(yōu)先級元素總是第一個出列。 容器適配器是一種接口類，為已有類提供新的接口 三種容器適配器： 75 所有容器共有的成員函數(shù)： 關(guān)系運(yùn)算： =, , , =, = , != empty() : 判斷容器中是否為空 max_size(): 容器中最多能裝多少元素 size(): 容器中元素個數(shù) s1.swap(s2)：交換兩個容器的內(nèi)容 構(gòu)造函數(shù)、拷貝構(gòu)造函數(shù)、析構(gòu)函數(shù) 76 所有順序容器和關(guān)聯(lián)容器 共有的成員函數(shù)： begin()：返回指向容器中第一個元素的迭代器 end()：返回指向容器中最后一個元素

47、后面的位置的迭 代器 rbegin(): 返回指向容器中最后一個元素的迭代器 rend(): 返回指向容器中第一個元素前面的位置的迭代 器 erase(): 從容器中刪除一個或幾個元素 clear()： 清空容器 77 headtail beginrbeginrendend 所有容器都具有的成員函數(shù) 成員函數(shù)名說 明 默認(rèn)構(gòu)造函數(shù)對容器進(jìn)行默認(rèn)初始化的構(gòu)造函數(shù)，常有多個，用于提供不同的 容器初始化方法 拷貝構(gòu)造函數(shù)用于將容器初始化為同類型的現(xiàn)有容器的副本 析構(gòu)函數(shù)執(zhí)行容器銷毀時的清理工作 empty()判斷容器是否為空，若為空返回true，否則返回false max_size()返回容器最大容

48、量，即容器能夠保存的最多元素個數(shù) size返回容器中當(dāng)前元素的個數(shù) operator= (=)將一個容器賦給另一個同類容器 operator ()如果第1個容器小于第2個容器，則返回true，否則返回false operator= ( ()如果第1個容器大于第2個容器，則返回true，否則返回false operator= (=)如果第1個容器大于等于第2個容器，則返回true，否則返回false swap交換兩個容器中的元素 順序和關(guān)聯(lián)容器共同支持的成員函數(shù) 成員函數(shù)名說 明 begin()指向第一個元素 end()指向最后一個元素的后面一個位置 rbegin()指向按反順序的第一個元素 r

49、end()指向按反順序的末端位置 erase()刪除容器中的一個或多個元素 clear()刪除容器中的所有元素 【例1】創(chuàng)建兩個整型向量容器，分別從尾端增加一些值， 輸出兩個容器的元素數(shù)、兩個容器的比較結(jié)果，交換兩個容 器后再輸出一次。 80 #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元素數(shù)元素數(shù):v1.size(),

50、v2元素數(shù)元素數(shù):v2.size()endl; if (v1=v2)coutv1=v2endl; else if (v1v2) coutv1v2endl; else coutv2endl; v1.swap(v2); cout v1元素數(shù)元素數(shù):v1.size(),v2元素數(shù)元素數(shù):v2.size()endl; if (v1=v2)coutv1=v2endl; else if (v1v2) coutv1v2endl; else coutv2endl; return 0; 聲明聲明2個向量個向量 向量賦值向量賦值 5 1 v1 1 2 3 v2 求元素數(shù)求元素數(shù) 向量內(nèi)容比較向量內(nèi)容比較 交換交換

51、2個向量個向量 實際上就是動態(tài)數(shù)組。但它比數(shù)組更靈活，當(dāng)添加數(shù)據(jù) 時，vector的大小能夠自動增加以容納新的元素。 內(nèi)存自動管理。可動態(tài)調(diào)整所占內(nèi)存。 支持隨機(jī)訪問，隨機(jī)訪問時間為常數(shù)。 所有stl算法都能對vector操作。 在尾部添加速度很快，在中間插入慢。 81 四種方式: 不指定容器的元素個數(shù)： vector 對象名； 例如： vector v; /創(chuàng)建整型向量v 指定容器大?。?vector 對象名(n)； 例如： vector v(10); /創(chuàng)建整型向量v,10個元素 注意：元素下標(biāo)09,初始化為0. 指定容器大小和元素初始值： vector 對象名(n,初值)； 例如： ve

52、ctor v(10,1); /創(chuàng)建整型向量v,10個元素,每個元素值均為1 由已有向量容器創(chuàng)建: vector 對象名(已有對象名)； 例如： vector v2(v1); /創(chuàng)建整型向量v1的副本v2 82 拷貝構(gòu)造函數(shù)拷貝構(gòu)造函數(shù) 幾種初始化vector對象的方式 vector v1;vector保存類型為t的對象。 默認(rèn)構(gòu)造函數(shù)v1為空 vector v2(v1);v2是v1的一個副本 vector v3(n, i);v3包含n個值為i的元素 vector v4(n);v4包含有值初始化元素的n個 副本 #include #include using namespace std; int

53、 main() vector v(10,1); for (vector:iterator it=v.begin();it!=v.end();it+) cout*it,; coutendl; return 0; 【例2】創(chuàng)建一個整型向量容器，輸出全部元素值。 84 可用“ ”運(yùn)算符訪問vector的元素； 【例3】用“ ”運(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,;

54、coutendl; return 0; 85 注意： 下標(biāo)操作僅能對確知已存的元素進(jìn)行賦值 和讀取操作 vector ivec; /empty vector for( int ix=0; ix 100; +ix) ivecix = ix; /ivec has no element 出錯，向量中尚沒有出錯，向量中尚沒有 元素，不能訪問！元素，不能訪問！ 如何使相同的算法能用于不同的數(shù)據(jù)結(jié)構(gòu)? - 迭代器(算法與容器的”中間人”) 87 容器類迭代器定義方法： 容器類名:iterator 變量名; 訪問一個迭代器指向的元素： * 迭代器變量名 迭代器上可執(zhí)行”+” , 指向容器中的下一個元 素。

55、如果迭代器到達(dá)了容器中的最后一個元素的后面，則迭代 器變成past-the-end值。 使用一個past-the-end值的迭代器來訪問對象是非法 的 定義迭代器的關(guān)鍵字定義迭代器的關(guān)鍵字 88 vector:iterator xhere = x.begin(); vector:iterator xend = x.end(); for (; xhere != xend; xhere+) func_name( *xhere); for (int i = 0; i x.size(); i+) func_name(x.get(i); 【例4】 #include #include using name

56、space 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; vector:reverse_iterator it2; /反向迭代器反向迭代器 for( it2 = v.rbegin();it2 != v.rend();it2+ ) cout * it2

57、 ,; cout endl; 89 vector: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; headtail beginrbeginrendend （1）const_iterator ：常量迭代器?？梢允褂眠@種類型 的迭代器來指向一個只讀的值。 （2） reverse_iterator ：反向迭代

58、器。用來反轉(zhuǎn)遍 歷vector的各元素，注意用rbegin()來代替begin()，用 rend()代替end()，而此時的“+”操作符會朝向后的方向 遍歷。 （3）iterator：隨機(jī)迭代器，可任意方向或移動任意個 位置訪問。 headtail beginrbeginrendend 有有const限制的只可讀取元限制的只可讀取元 素值，不可修改元素值素值，不可修改元素值 90 不同的容器，stl提供的迭代器功能各不相同。 vector容器的迭代器： u 可使用“+=”、“-”、“+”、“-=” 中的任何一種操作符 u 可使用“”、“”、“=” 、“=”、“!=”等比較運(yùn)算符 u 可隨機(jī)訪問

59、容器中的數(shù)據(jù)元素。 91 push_back在尾部追加元素; insert方法可在vector任意位置插入元素. 【例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容器自動分配內(nèi)存； 可對空的vector追加

60、，也可對已有元素的vector追加. 92 abcde a aabcde abcde abcdea a 在尾端增刪元素具 有較佳的性能 93 insert(iterator it,t t): 對vector容器在指定位置插入新元素 【例6】對整型向量容器插入元素，輸出全部元素值。 #include #include using namespace std; int main() vector v(3); vector:iterator it; v0=10; v1=100;v2=-20; v.insert(v.begin(),50); /在最前面插入新元素在最前面插入新元素50 v.insert