1、第七章泛型程序設(shè)計(jì)與C+標(biāo)準(zhǔn)模板庫(kù),2020/7/4,2,泛型程序設(shè)計(jì)的概念和術(shù)語(yǔ)C+標(biāo)準(zhǔn)模板庫(kù)中的容器迭代器函數(shù)對(duì)象,3,將程序?qū)懙帽M可能通用將算法從特定的數(shù)據(jù)結(jié)構(gòu)中抽象出來(lái)，成為通用的C+的模板為泛型程序設(shè)計(jì)奠定了關(guān)鍵的基礎(chǔ)STL是泛型程序設(shè)計(jì)的一個(gè)范例容器(container)迭代器(iterator)算法（algorithms）函數(shù)對(duì)象（functionobject）,泛型程序設(shè)計(jì),泛型程序設(shè)計(jì)的概念和術(shù)語(yǔ),4,容器類是容納、包含一組元素或元素集合的對(duì)象。異類容器類與同類容器類順序容器與關(guān)聯(lián)容器七種基本容器：向量（vector）、雙端隊(duì)列（deque）、列表（list）、集合（set）

2、、多重集合（multiset）、映射（map）和多重映射（multimap）,容器,泛型程序設(shè)計(jì)的概念和術(shù)語(yǔ),5,通用容器運(yùn)算符=，!=，=，=，=方法（函數(shù)）迭代方法begin()，end()，rbegin()，rend()訪問(wèn)方法size()，max_size()，swap()，empty(),泛型程序設(shè)計(jì)的概念和術(shù)語(yǔ),容器的接口,6,適配器是一種接口類為已有的類提供新的接口。目的是簡(jiǎn)化、約束、使之安全、隱藏或者改變被修改類提供的服務(wù)集合。三種類型的適配器：容器適配器用來(lái)擴(kuò)展7種基本容器，它們和順序容器相結(jié)合構(gòu)成棧、隊(duì)列和優(yōu)先隊(duì)列容器迭代器適配器函數(shù)對(duì)象適配器。,泛型程序設(shè)計(jì)的概念和術(shù)語(yǔ),

3、適配器,7,迭代器是面向?qū)ο蟀姹镜闹羔槪鼈兲峁┝嗽L問(wèn)容器、序列中每個(gè)元素的方法。,泛型程序設(shè)計(jì)的概念和術(shù)語(yǔ),迭代器,8,C+標(biāo)準(zhǔn)模板庫(kù)中包括70多個(gè)算法其中包括查找算法、排序算法、消除算法、記數(shù)算法、比較算法、變換算法、置換算法和容器管理等。這些算法的一個(gè)最重要的特性就是它們的統(tǒng)一性，并且可以廣泛用于不同的對(duì)象和內(nèi)置的數(shù)據(jù)類型。,泛型程序設(shè)計(jì)的概念和術(shù)語(yǔ),算法,9,順序容器的接口插入方法push_front()，push_back()，insert()，運(yùn)算符“=”刪除方法pop()，erase()，clear()迭代訪問(wèn)方法使用迭代器其它順序容器訪問(wèn)方法（不修改訪問(wèn)方法）front()，b

4、ack()，下標(biāo)運(yùn)算符,C+標(biāo)準(zhǔn)模板庫(kù)中的容器,順序容器,10,向量屬于順序容器，用于容納不定長(zhǎng)線性序列（即線性群體），提供對(duì)序列的快速隨機(jī)訪問(wèn)（也稱直接訪問(wèn)）向量是動(dòng)態(tài)結(jié)構(gòu)，它的大小不固定，可以在程序運(yùn)行時(shí)增加或減少。例7-1求范圍2N中的質(zhì)數(shù)，N在程序運(yùn)行時(shí)由鍵盤輸入。,C+標(biāo)準(zhǔn)模板庫(kù)中的容器,順序容器向量,11,/7_1.cpp#include#include#include/包含向量容器頭文件usingnamespacestd;intmain()vectorA(10);intn=0;intprimecount=0,i=0,j=0;cout=2asupperlimit:;cinn;Apr

5、imecount+=2;,C+標(biāo)準(zhǔn)模板庫(kù)中的容器,順序容器向量,12,for(i=3;ii/2)Aprimecount+=i;for(i=0;iprimecount;i+)/輸出質(zhì)數(shù)coutsetw(5)Ai;if(i+1)%10=0)/每輸出10個(gè)數(shù)換行一次coutendl;coutendl;,C+標(biāo)準(zhǔn)模板庫(kù)中的容器,順序容器向量,13,雙端隊(duì)列是一種放松了訪問(wèn)權(quán)限的隊(duì)列。元素可以從隊(duì)列的兩端入隊(duì)和出隊(duì)，也支持通過(guò)下標(biāo)操作符“”進(jìn)行直接訪問(wèn)。例7-2使用雙端隊(duì)列容器保存雙精度數(shù)值序列,C+標(biāo)準(zhǔn)模板庫(kù)中的容器,順序容器雙端隊(duì)列,14,列表主要用于存放雙向鏈表，可以從任意一端開始遍歷。列表還提供

6、了拼接（splicing）操作，將一個(gè)序列中的元素從插入到另一個(gè)序列中。例7-3從鍵盤輸入10個(gè)整數(shù)，用這些整數(shù)值作為結(jié)點(diǎn)數(shù)據(jù)，生成一個(gè)鏈表，按順序輸出鏈表中結(jié)點(diǎn)的數(shù)值。然后從鍵盤輸入一個(gè)待查找整數(shù)，在鏈表中查找該整數(shù)，若找到則刪除該整數(shù)所在的結(jié)點(diǎn)（如果出現(xiàn)多次，全部刪除），然后輸出刪除結(jié)點(diǎn)以后的鏈表。在程序結(jié)束之前清空鏈表。,C+標(biāo)準(zhǔn)模板庫(kù)中的容器,順序容器列表,15,/7_3.cpp#include#includeusingnamespacestd;intmain()listLink;/構(gòu)造一個(gè)列表用于存放整數(shù)鏈表inti=0,key=0,item=0;for(i=0;iitem;Link

7、.push_front(item);coutList:;/輸出鏈表,C+標(biāo)準(zhǔn)模板庫(kù)中的容器,順序容器列表,16,list:iteratorp=Link.begin();while(p!=Link.end()/輸出各節(jié)點(diǎn)數(shù)據(jù)，直到鏈表尾coutkey;Link.remove(key);coutList:;/輸出鏈表p=Link.begin();/使P重新指向表頭while(p!=Link.end()cout*p;p+;/使P指向下一個(gè)節(jié)點(diǎn)coutendl;,C+標(biāo)準(zhǔn)模板庫(kù)中的容器,順序容器列表,17,容器適配器是用來(lái)擴(kuò)展7種基本容器的棧容器使用適配器與一種基礎(chǔ)容器相結(jié)合來(lái)實(shí)現(xiàn)例7-4：應(yīng)用標(biāo)準(zhǔn)庫(kù)

8、中的deque順序容器生成一個(gè)整數(shù)棧stack。隊(duì)列容器使用適配器與一種基礎(chǔ)容器相結(jié)合來(lái)實(shí)現(xiàn)的先進(jìn)先出數(shù)據(jù)結(jié)構(gòu)。例7-5：應(yīng)用標(biāo)準(zhǔn)庫(kù)中的deque順序容器生成一個(gè)整數(shù)標(biāo)準(zhǔn)隊(duì)列Queue。,C+標(biāo)準(zhǔn)模板庫(kù)中的容器,容器適配器,18,迭代器是面向?qū)ο蟀姹镜闹羔樦羔樋梢灾赶騼?nèi)存中的一個(gè)地址迭代器可以指向容器中的一個(gè)位置STL的每一個(gè)容器類模版中，都定義了一組對(duì)應(yīng)的迭代器類。使用迭代器，算法函數(shù)可以訪問(wèn)容器中指定位置的元素，而無(wú)需關(guān)心元素的具體類型。,迭代器,什么是迭代器,19,輸入迭代器可以用來(lái)從序列中讀取數(shù)據(jù)輸出迭代器允許向序列中寫入數(shù)據(jù)前向迭代器既是輸入迭代器又是輸出迭代器，并且可以對(duì)序列進(jìn)行單

9、向的遍歷。雙向迭代器與前向迭代器相似，但是在兩個(gè)方向上都可以對(duì)數(shù)據(jù)遍歷。隨機(jī)訪問(wèn)迭代器也是雙向迭代器，但能夠在序列中的任意兩個(gè)位置之間進(jìn)行跳轉(zhuǎn)。,迭代器,迭代器的類型,20,迭代器適配器是用來(lái)擴(kuò)展（或調(diào)整）迭代器功能的類。它本身也被稱為迭代器，只是這種迭代器是通過(guò)改變另一個(gè)迭代器而得到的逆向迭代器通過(guò)重新定義遞增運(yùn)算和遞減運(yùn)算，使其行為正好倒置插入型迭代器將賦值操作轉(zhuǎn)換為插入操作。通過(guò)這種迭代器，算法可以執(zhí)行插入行為而不是覆蓋行為例7-6應(yīng)用逆向迭代器和后插迭代器來(lái)操作向量容器中的元素,迭代器,迭代器適配器,21,advance()函數(shù)將迭代器的位置增加，增加的幅度由參數(shù)決定Distance(

10、)函數(shù)返回迭代器之間的距離函數(shù)iter_swap()交換兩個(gè)迭代器所指向的元素值例7-7用三個(gè)迭代器輔助函數(shù)來(lái)操作列表容器中的元素,迭代器,迭代器相關(guān)的輔助函數(shù),22,算法本身是一種函數(shù)模板不可變序列算法（Non-mutatingalgorithms）不直接修改所操作的容器內(nèi)容的算法可變序列算法（Mutatingalgorithms）可以修改它們所操作的容器的元素排序相關(guān)算法數(shù)值算法,算法,標(biāo)準(zhǔn)C+庫(kù)中的算法,23,例7-9應(yīng)用不可變序列算法對(duì)數(shù)據(jù)序列進(jìn)行分析例7-10以可變序列算法對(duì)數(shù)據(jù)序列進(jìn)行復(fù)制，生成，刪除，替換，倒序，旋轉(zhuǎn)等可變性操作。例7-11應(yīng)用排序相關(guān)算法對(duì)序列進(jìn)行各項(xiàng)操作例7-

11、12應(yīng)用數(shù)值算法對(duì)數(shù)據(jù)序列進(jìn)行操作,算法,算法應(yīng)用舉例,一個(gè)行為類似函數(shù)的對(duì)象，它可以不需參數(shù)，也可以帶有若干參數(shù)，其功能是獲取一個(gè)值，或者改變操作的狀態(tài)。任何普通的函數(shù)和任何重載了調(diào)用運(yùn)算符operator()的類的對(duì)象都滿足函數(shù)對(duì)象的特征STL中也定義了一些標(biāo)準(zhǔn)的函數(shù)對(duì)象，如果以功能劃分，可以分為算術(shù)運(yùn)算、關(guān)系運(yùn)算、邏輯運(yùn)算三大類。為了調(diào)用這些標(biāo)準(zhǔn)函數(shù)對(duì)象，需要包含頭文件。,函數(shù)對(duì)象,函數(shù)對(duì)象,24/26,2020/7/4,25,本節(jié)課主要介紹了如下內(nèi)容：1、與C+標(biāo)準(zhǔn)模板庫(kù)有關(guān)的概念和術(shù)語(yǔ)容器、容器適配器、迭代器、迭代器適配器、通用算法、函數(shù)對(duì)象、函數(shù)適配器2、用于處理線性群體的容器向量、雙端隊(duì)列