第九群體類精品課程建設(shè)網(wǎng)湖州師范學(xué)院

1、第十章第十章 C+標(biāo)準(zhǔn)模板庫標(biāo)準(zhǔn)模板庫清華大學(xué)清華大學(xué) 鄭鄭 莉莉C+語言程序設(shè)計(jì)C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉2主要內(nèi)容主要內(nèi)容l泛型程序設(shè)計(jì)泛型程序設(shè)計(jì)l與標(biāo)準(zhǔn)模板庫有關(guān)的概念和術(shù)語與標(biāo)準(zhǔn)模板庫有關(guān)的概念和術(shù)語lC+標(biāo)準(zhǔn)模板庫中的容器標(biāo)準(zhǔn)模板庫中的容器l迭代器迭代器l標(biāo)準(zhǔn)標(biāo)準(zhǔn)C+庫中的算法庫中的算法l函數(shù)對(duì)象函數(shù)對(duì)象 C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉3泛型程序設(shè)計(jì)泛型程序設(shè)計(jì)l將程序?qū)懙帽M可能通用將程序?qū)懙帽M可能通用 l將算法從特定的數(shù)據(jù)結(jié)構(gòu)中抽象出來，成將算法從特定的數(shù)據(jù)結(jié)構(gòu)中抽象出來，成為通用的為通用的lC+的模板為泛型程序設(shè)計(jì)奠定了關(guān)鍵的的模板為泛型程序設(shè)計(jì)奠定了關(guān)鍵的基礎(chǔ)基礎(chǔ) lST

2、L是泛型程序設(shè)計(jì)的一個(gè)范例是泛型程序設(shè)計(jì)的一個(gè)范例 容器(container) 迭代器(iterator) 算法（algorithms） 函數(shù)對(duì)象（function object）C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉4命名空間（命名空間（Namespace）l一個(gè)命名空間將不同的標(biāo)識(shí)符集合在一個(gè)一個(gè)命名空間將不同的標(biāo)識(shí)符集合在一個(gè)命名作用域（命名作用域（named scope）內(nèi)）內(nèi) 為了解決命名沖突 例如，聲明一個(gè)命名空間NS：namspace NS class File;void Fun (); 則引用標(biāo)識(shí)符的方式如下，NS: File obj;NS: Fun ();l沒有聲明命名空間的標(biāo)識(shí)符都

3、處于無名的沒有聲明命名空間的標(biāo)識(shí)符都處于無名的命名空間中命名空間中概念和術(shù)語C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉5命名空間（命名空間（Namespace）l可以用可以用using來指定命名空間來指定命名空間 例如，經(jīng)過以下聲明：using NS:File;在當(dāng)前作用域中就可以直接引用File using namespace std;命名空間std中所有標(biāo)識(shí)符都可直接引用l在新的在新的C+標(biāo)準(zhǔn)程序庫中，所有標(biāo)識(shí)標(biāo)準(zhǔn)程序庫中，所有標(biāo)識(shí)符都聲明在命名空間符都聲明在命名空間std中，頭文件中，頭文件都不使用擴(kuò)展名都不使用擴(kuò)展名概念和術(shù)語C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉6容器容器l容器類是容納、包含一組元素或元

4、素容器類是容納、包含一組元素或元素集合的對(duì)象。集合的對(duì)象。l異類容器類與同類容器類異類容器類與同類容器類l順序容器與關(guān)聯(lián)容器順序容器與關(guān)聯(lián)容器l七種基本容器：七種基本容器： 向量（vector）、雙端隊(duì)列（deque）、列表（list）、集合（set）、多重集合（multiset）、映射（map）和多重映射（multimap）概念和術(shù)語C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉7容器的接口容器的接口l通用容器運(yùn)算符通用容器運(yùn)算符 =，!=，=，=，=l方法（函數(shù)）方法（函數(shù)）迭代方法lbegin()，end()，rbegin()，rend()訪問方法lsize()，max_size()，swap()，em

5、pty()C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉8適配器適配器l適配器是一種接口類適配器是一種接口類 為已有的類提供新的接口。 目的是簡(jiǎn)化、約束、使之安全、隱藏或者改變被修改類提供的服務(wù)集合。l三種類型的適配器：三種類型的適配器： 容器適配器l用來擴(kuò)展7種基本容器，它們和順序容器相結(jié)合構(gòu)成棧、隊(duì)列和優(yōu)先隊(duì)列容器 迭代器適配器 函數(shù)對(duì)象適配器。概念和術(shù)語C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉9迭代器迭代器迭代器是面向?qū)ο蟀姹镜闹羔?，它迭代器是面向?qū)ο蟀姹镜闹羔?，它們提供了訪問容器、序列中每個(gè)元素的們提供了訪問容器、序列中每個(gè)元素的方法。方法。概念和術(shù)語C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉10算法算法lC+標(biāo)準(zhǔn)模板庫中

6、包括標(biāo)準(zhǔn)模板庫中包括70多個(gè)算法多個(gè)算法 其中包括查找算法，排序算法，消除算法，記數(shù)算法，比較算法，變換算法，置換算法和容器管理等等。l這些算法的一個(gè)最重要的特性就是它這些算法的一個(gè)最重要的特性就是它們的統(tǒng)一性，并且可以廣泛用于不同們的統(tǒng)一性，并且可以廣泛用于不同的對(duì)象和內(nèi)置的數(shù)據(jù)類型。的對(duì)象和內(nèi)置的數(shù)據(jù)類型。概念和術(shù)語C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉11順序容器順序容器l順序容器的接口順序容器的接口 插入方法lpush_front()，push_back()，insert()，運(yùn)算符“=” 刪除方法lpop() ，erase()，clear() 迭代訪問方法l使用迭代器 其它順序容器訪問方法（

7、不修改訪問方法）lfront()，back()，下標(biāo)運(yùn)算符容 器C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉12順序容器順序容器向量向量l向量屬于順序容器，用于容納不定長(zhǎng)向量屬于順序容器，用于容納不定長(zhǎng)線性序列（即線性群體），提供對(duì)序線性序列（即線性群體），提供對(duì)序列的快速隨機(jī)訪問（也稱直接訪問）列的快速隨機(jī)訪問（也稱直接訪問）l向量是動(dòng)態(tài)結(jié)構(gòu)，它的大小不固定，向量是動(dòng)態(tài)結(jié)構(gòu)，它的大小不固定，可以在程序運(yùn)行時(shí)增加或減少?？梢栽诔绦蜻\(yùn)行時(shí)增加或減少。l例例10-1 求范圍2N中的質(zhì)數(shù)，N在程序運(yùn)行時(shí)由鍵盤輸入。容 器13/10_1.cpp/10_1.cpp#include iostream#include #

8、include iomanip#include #include #include /包含向量容器頭文件包含向量容器頭文件using namespace std ;using namespace std ;intint main() main() vectorint vector A(10); A(10); int int n; n; int primecount int primecount = 0, i, j; = 0, i, j; cout cout=2 as upper limit: ;=2 as upper limit: ; cin cin n; n; Aprimecount Apr

9、imecount+ = 2;+ = 2;1314 for(ifor(i = 3; i n; i+) = 3; i n; i+) if (primecount = A.size if (primecount = A.size()() A.resize(primecount A.resize(primecount + 10); + 10); if (i % 2 = 0) if (i % 2 = 0) continue; continue; j = 3; j = 3; while (j = i/2 & i % j != 0) while (j i/2) Aprimecount if (j i

10、/2) Aprimecount+ = i;+ = i; for (i = 0; iprimecount for (i = 0; iprimecount; i+)/; i+)/輸出質(zhì)數(shù)輸出質(zhì)數(shù) coutsetw(5)Ai coutsetw(5)Ai; ; if (i+1) % 10 = 0) / if (i+1) % 10 = 0) /每輸出每輸出1010個(gè)數(shù)換行一次個(gè)數(shù)換行一次 cout endlcout endl; ; coutendl coutendl; ; 14C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉15順序容器順序容器雙端隊(duì)列雙端隊(duì)列l(wèi)雙端隊(duì)列是一種放松了訪問權(quán)限的隊(duì)雙端隊(duì)列是一種放松了訪問權(quán)限

11、的隊(duì)列。元素可以從隊(duì)列的兩端入隊(duì)和出列。元素可以從隊(duì)列的兩端入隊(duì)和出隊(duì)，也支持通過下標(biāo)操作符隊(duì)，也支持通過下標(biāo)操作符“”進(jìn)行進(jìn)行直接訪問。直接訪問。l例例10-2 使用雙端隊(duì)列容器保存雙精度數(shù)值序列容 器C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉16順序容器順序容器列表列表l列表主要用于存放雙向鏈表，可以從任意列表主要用于存放雙向鏈表，可以從任意一端開始遍歷。列表還提供了拼接一端開始遍歷。列表還提供了拼接（splicing）操作，將一個(gè)序列中的元素從）操作，將一個(gè)序列中的元素從插入到另一個(gè)序列中。插入到另一個(gè)序列中。l例例10-3 改寫例改寫例9-7 從鍵盤輸入10個(gè)整數(shù)，用這些整數(shù)值作為結(jié)點(diǎn)數(shù)據(jù)，生成一

12、個(gè)鏈表，按順序輸出鏈表中結(jié)點(diǎn)的數(shù)值。然后從鍵盤輸入一個(gè)待查找整數(shù)，在鏈表中查找該整數(shù)，若找到則刪除該整數(shù)所在的結(jié)點(diǎn)（如果出現(xiàn)多次，全部刪除），然后輸出刪除結(jié)點(diǎn)以后的鏈表。在程序結(jié)束之前清空鏈表。容 器17/10_3.cpp/10_3.cpp#include iostream#include #include #include using namespace std ;using namespace std ;intint main() main() listint list Link; Link;/構(gòu)造一個(gè)列表用于存放整數(shù)鏈表構(gòu)造一個(gè)列表用于存放整數(shù)鏈表 intint i, key, item

13、; i, key, item; for(i for(i=0;i 10;i+)/ =0;i item;item; Link.push_front(item Link.push_front(item);); cout coutList: ; / List: ; / 輸出鏈表輸出鏈表1718 list:iterator p=Link.begin list:iterator p=Link.begin(); (); while(p!=Link.end while(p!=Link.end()/()/輸出各節(jié)點(diǎn)數(shù)據(jù)，直到鏈表尾輸出各節(jié)點(diǎn)數(shù)據(jù)，直到鏈表尾 cout cout * *p ;p ; p+; / p

14、+; /使使P P指向下一個(gè)節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn) cout endl cout endl; ; cout cout key; key; Link.remove(key Link.remove(key); ); cout cout List: ; / List: ; / 輸出鏈表輸出鏈表 p=Link.beginp=Link.begin();();/ / 使使P P重新指向表頭重新指向表頭 while(p!=Link.endwhile(p!=Link.end()() cout cout * *p ;p ; p+; / p+; / 使使P P指向下一個(gè)節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn) cout endl cout

15、 endl; ; 18C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉19容器適配器容器適配器l容器適配器是用來擴(kuò)展容器適配器是用來擴(kuò)展7種基本容器的種基本容器的l棧容器棧容器 使用適配器與一種基礎(chǔ)容器相結(jié)合來實(shí)現(xiàn) 例10-4：應(yīng)用標(biāo)準(zhǔn)庫中的deque順序容器生成一個(gè)整數(shù)棧stack。l隊(duì)列容器隊(duì)列容器 使用適配器與一種基礎(chǔ)容器相結(jié)合來實(shí)現(xiàn)的先進(jìn)先出數(shù)據(jù)結(jié)構(gòu)。 例10-5：應(yīng)用標(biāo)準(zhǔn)庫中的deque順序容器生成一個(gè)整數(shù)標(biāo)準(zhǔn)隊(duì)列Queue。容 器C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉20什么是迭代器什么是迭代器l迭代器是面向?qū)ο蟀姹镜闹羔樀魇敲嫦驅(qū)ο蟀姹镜闹羔?指針可以指向內(nèi)存中的一個(gè)地址 迭代器可以指向容器中的一個(gè)位

16、置lSTL的每一個(gè)容器類模版中，都定義的每一個(gè)容器類模版中，都定義了一組對(duì)應(yīng)的迭代器類。使用迭代器，了一組對(duì)應(yīng)的迭代器類。使用迭代器，算法函數(shù)可以訪問容器中指定位置的算法函數(shù)可以訪問容器中指定位置的元素，而無需關(guān)心元素的具體類型。元素，而無需關(guān)心元素的具體類型。迭代器C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉21迭代器的類型迭代器的類型l輸入迭代器輸入迭代器 可以用來從序列中讀取數(shù)據(jù)l輸出迭代器輸出迭代器 允許向序列中寫入數(shù)據(jù)l前向迭代器前向迭代器 既是輸入迭代器又是輸出迭代器，并且可以對(duì)序列進(jìn)行單向的遍歷l雙向迭代器雙向迭代器 與前向迭代器相似，但是在兩個(gè)方向上都可以對(duì)數(shù)據(jù)遍歷l隨機(jī)訪問迭代器隨機(jī)訪問迭

17、代器 也是雙向迭代器，但能夠在序列中的任意兩個(gè)位置之間進(jìn)行跳轉(zhuǎn)。迭代器C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉22迭代器適配器迭代器適配器l迭代器適配器是用來擴(kuò)展（或調(diào)整）迭代器功能迭代器適配器是用來擴(kuò)展（或調(diào)整）迭代器功能的類。它本身也被稱為迭代器，只是這種迭代器的類。它本身也被稱為迭代器，只是這種迭代器是通過改變另一個(gè)迭代器而得到的是通過改變另一個(gè)迭代器而得到的l逆向迭代器逆向迭代器 通過重新定義遞增運(yùn)算和遞減運(yùn)算，使其行為正好倒置l插入型迭代器插入型迭代器 將賦值操作轉(zhuǎn)換為插入操作。通過這種迭代器，算法可以執(zhí)行插入行為而不是覆蓋行為l例例10-6 應(yīng)用逆向迭代器和后插迭代器來操作向量容器中的元素迭

18、代器C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉23迭代器相關(guān)的輔助函數(shù)迭代器相關(guān)的輔助函數(shù)ladvance()函數(shù)函數(shù) 將迭代器的位置增加，增加的幅度由參數(shù)決定lDistance()函數(shù)函數(shù) 返回迭代器之間的距離l函數(shù)函數(shù)iter_swap() 交換兩個(gè)迭代器所指向的元素值l例例10-7 用三個(gè)迭代器輔助函數(shù)來操作列表容器中的元素。迭代器C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉24標(biāo)準(zhǔn)標(biāo)準(zhǔn)C+庫中的算法庫中的算法l算法本身是一種函數(shù)模板算法本身是一種函數(shù)模板l不可變序列算法不可變序列算法（Non-mutating algorithmsNon-mutating algorithms）不直接修改所操作的容器內(nèi)容的算法l可變序列算法可變序列算法（Mutating algorithmsMutating algorithms）可以修改它們所操作的容器的元素。l排序相關(guān)算法排序相關(guān)算法l數(shù)值算法數(shù)值算法算 法C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉25算法應(yīng)用舉例算法應(yīng)用舉例l例例10-9 應(yīng)用不可變序列算法對(duì)數(shù)據(jù)序列進(jìn)行分析l例例10-10 以可變序列算法對(duì)數(shù)據(jù)序列進(jìn)行復(fù)制，生成，刪除，替換，倒序，旋轉(zhuǎn)等可變性操作。l例例10-11 應(yīng)用排序相關(guān)算法對(duì)序列進(jìn)行各項(xiàng)操作l例例10-12 應(yīng)用數(shù)值算法對(duì)數(shù)據(jù)序列進(jìn)行操作算 法C+語言程序設(shè)計(jì)清華大學(xué) 鄭莉26函數(shù)對(duì)象函數(shù)對(duì)象l一個(gè)行為類似函數(shù)的對(duì)象，它