C++ 第十一章課件.ppt

1、第11章標(biāo)準(zhǔn)模板庫(STL)，一個(gè)庫是程序組件的集合，可以在不同的程序中重用。圖書館功能設(shè)計(jì)的首要要求是通用性，而模板為通用性帶來了不可估量的前景。標(biāo)準(zhǔn)模板庫是ANSI/ISO C最具特色和實(shí)用性的部分之一，STL包含：容器、迭代器算法、通用算法和函數(shù)對(duì)象，使算法擺脫了對(duì)不同類型數(shù)據(jù)操作的依賴。11.1標(biāo)準(zhǔn)模板庫簡介，11.3序列容器，11.2迭代子類，11.5容器適配器，11.7 VC中的STL，11.6通用算法和函數(shù)對(duì)象，11.4關(guān)聯(lián)容器，XI標(biāo)準(zhǔn)模板庫章，11.1標(biāo)準(zhǔn)模板庫簡介，容器類是一個(gè)管理序列并保存一組對(duì)象或一組對(duì)象的類。通過容器類提供的成員函數(shù)，可以執(zhí)行向序列中插入元素、刪除元素

2、、查找元素等操作。這些成員函數(shù)通過返回迭代器來指定元素在序列中的位置。STL提供了一個(gè)標(biāo)準(zhǔn)化的模板化對(duì)象容器庫，其中包含了各種數(shù)據(jù)結(jié)構(gòu)及其算法：迭代器是面向?qū)ο蟮陌姹局羔?，它提供訪問容器或序列中每個(gè)對(duì)象的方法。這樣，該算法可以應(yīng)用于由容器管理的序列。通用算法不依賴于特定的容器，通用算法更容易擴(kuò)展。通用算法使用函數(shù)對(duì)象來介紹同一算法在不同環(huán)境下的差異。它不使用繼承和多態(tài)，避免了虛擬函數(shù)的開銷，使STL更加高效。11.1標(biāo)準(zhǔn)模板庫簡介，容器分為三類：表11.1，11.1標(biāo)準(zhǔn)模板庫簡介，順序容器和關(guān)聯(lián)容器稱為一級(jí)容器。還有四種容器被稱為近容器：c語言風(fēng)格的數(shù)組、字符串、用于操作1/0標(biāo)志值的位集和用

3、于高速數(shù)學(xué)矢量運(yùn)算的valarray。盡管它們提供了與第一類容器相似的功能，但它們并不具備所有的功能。STL還使容器能夠提供類似的接口。許多基本操作適用于所有容器，而一些操作適用于相似容器的子集。這樣，STL可以用新的類來擴(kuò)展。這些函數(shù)和操作符可以被稱為容器的接口。表11.2所有標(biāo)準(zhǔn)庫容器共有的函數(shù)，表11.3僅在第一類中的函數(shù)，表11.4標(biāo)準(zhǔn)容器庫的頭文件，和11.1標(biāo)準(zhǔn)模板庫的介紹。在討論線性表和非線性表(如數(shù)組、鏈表和二叉樹)時(shí)，如果想訪問其中一個(gè)元素(節(jié)點(diǎn))，訪問方法最終應(yīng)該歸結(jié)為獲取內(nèi)存地址(指針)，它可以抽象為面向?qū)ο蟀姹镜闹羔樀?指針)。迭代器和指針有很多相似之處，但是迭代器

4、保存了特定容器操作所需的狀態(tài)信息，從而實(shí)現(xiàn)了適合每種容器類型的迭代器。一些迭代器操作在所有容器中都是一致的。例如，運(yùn)算符總是返回容器的下一個(gè)元素的迭代器，間接引用符號(hào)*總是指示迭代器指向的容器元素。迭代器用于組合STL的所有部分。本質(zhì)上，STL提供的所有算法都是模板，我們可以通過使用自己指定的迭代器來實(shí)例化這些模板。迭代器可以包含指針，但不僅僅是指針。11.1標(biāo)準(zhǔn)模板庫簡介，STL的最大優(yōu)勢(shì)是在各種容器中提供通用算法，如插入、刪除、搜索、排序等。STL提供了大約70種標(biāo)準(zhǔn)算法。該算法僅通過迭代間接操作容器元素。算法通常返回迭代器。一個(gè)算法通?？梢杂糜谠S多不同的容器，所以它被稱為通用算法。算法分

5、為：容器修改算法，即變異序列算法，如復(fù)制()、刪除()、替換()、交換()等。不修改容器的算法，即非變異序列算法，如count()、find()等。數(shù)字算法。、11.2迭代子類，標(biāo)準(zhǔn)庫定義了迭代器的層次結(jié)構(gòu)，根據(jù)這個(gè)層次，從上到下，函數(shù)越來越強(qiáng)大。但不是遺產(chǎn)！圖11.1迭代子級(jí)，標(biāo)準(zhǔn)庫中有五個(gè)預(yù)定義的迭代器，最強(qiáng)大和靈活的是隨機(jī)訪問迭代器。表11.5迭代子類別，表11.6 STL容器支持的迭代子類別，表11.7可由各種迭代器執(zhí)行的操作，迭代器只能遍歷第一類容器。結(jié)合find()算法，討論了迭代器與遺傳算法的關(guān)系。find()的定義如下：模板輸入迭代器find(首先輸入迭代器，最后輸入迭代器，計(jì)

6、數(shù)t值)為(；首先！=最后一個(gè)。first)如果(值=*first)先返回；Return last表明通用算法不直接訪問容器的元素，與容器無關(guān)。元素的所有訪問和遍歷都是通過迭代器實(shí)現(xiàn)的。沒有必要預(yù)測(cè)容器類型。11.2迭代子類，示例11.1查找數(shù)組元素。示例11.2查找向量容器元素。11.2迭代子類，特殊迭代器：反向迭代器將一切顛倒過來。當(dāng)向前遍歷第一個(gè)類容器時(shí)，如果使用反向迭代器，實(shí)際上實(shí)現(xiàn)了反向遍歷。第一種容器支持兩對(duì)操作：begin()和end()，它們分別返回指向容器的第一個(gè)元素和最后一個(gè)元素的后續(xù)迭代器；而rbegin()和rend()支持逆變換迭代器，并返回分別指向容器的最后一個(gè)元素

7、和第一個(gè)元素的前導(dǎo)元素的迭代器。向量向量。vector : reverse _ iterator r _ ITER；for(r _ ITER=veco . rbe gin()；/將r_iter指向最后一個(gè)元素r_iter！=veco . rend()；/它不等于第一個(gè)元素的前導(dǎo)ITER。/實(shí)際上正在減少。如果你想把升序改為降序，只需使用逆迭代器。逆迭代器被定義為隨機(jī)迭代器。11.2迭代子類、插入迭代器：您可以使用輸出迭代器來生成元素序列。您可以添加元素而不覆蓋它們。有三種類型的插入迭代器：back_insert_iterator是輸出迭代器，用于將生成的元素添加到類型為的容器對(duì)象的末尾。這就像

8、在字符串的末尾添加一個(gè)字符串(strcat()。front_insert_iterator是一個(gè)輸出迭代器，用于將生成的元素添加到容器的前端，也就是說，生成的元素以相反的順序在受控序列的前端結(jié)束。Insert_iterator也是一個(gè)輸出迭代器，用于將生成的元素插入到迭代器(第二個(gè)參數(shù)迭代器)指定的元素之前。相關(guān)適配器函數(shù)，11.2迭代子類，流迭代器：輸入流迭代器(istream_iterator)類支持對(duì)istream及其派生類(如ifstream)的迭代子操作。聲明方式為：istream_iterator迭代子標(biāo)識(shí)符(istream /Type為已定義輸入操作的類型，/實(shí)際參數(shù)可以是公共派

9、生istream的任何子類型對(duì)象，輸出流也由相應(yīng)的ostream_iterator類支持，聲明方式為：ostream_iterator迭代子標(biāo)識(shí)符(ostream /定義用于存儲(chǔ)整形序列的向量容器對(duì)象vi，/vector vch，用于存儲(chǔ)實(shí)序列的向量容器)；/vectorvstr，用于存儲(chǔ)字符序列的向量容器；/用于存儲(chǔ)字符串序列的向量容器。向量容器有多種構(gòu)造函數(shù)，包括用n個(gè)元素構(gòu)造一個(gè)向量。您也可以為具有相同對(duì)象的每個(gè)元素分配一個(gè)初始值。它還包括一個(gè)復(fù)制構(gòu)造函數(shù)，可以從現(xiàn)有的向量容器對(duì)象中初始化新容器的每個(gè)元素的構(gòu)造函數(shù)。這些構(gòu)造函數(shù)也可以顯式地給分配器對(duì)象。11.3順序容器，2 .列表由雙鏈

10、表組成。它有兩個(gè)指針字段，支持的迭代子類型是雙向迭代器。它類似于雙鏈表模板，但它更通用和方便使用。列表在頭文件中定義。3。deque(雙端隊(duì)列)類。Deque允許在隊(duì)列的兩端進(jìn)行操作?；谛蛄斜恚С蛛S機(jī)訪問迭代器。德克爾放松了對(duì)他訪問的限制，目標(biāo)可以從隊(duì)伍的頭，從隊(duì)伍的末端，或從任何一端進(jìn)入隊(duì)伍。支持下標(biāo)運(yùn)算符“”。增加存儲(chǔ)空間可以在內(nèi)存塊中分配出隊(duì)列的兩端。新分配的內(nèi)存空間被保存為指向這些塊的指針數(shù)組，并且可以利用不連續(xù)的內(nèi)存空間。因此，它的迭代器比向量的更智能。當(dāng)de quee被刪除時(shí)，為de quee分配的存儲(chǔ)塊被釋放。要使用deque，必須包含一個(gè)頭文件。11.4關(guān)聯(lián)容器、關(guān)聯(lián)容器可

11、以通過搜索鍵直接訪問(存儲(chǔ)和讀取元素)。四個(gè)相關(guān)的容器是：集合、多集合、映射和多映射。集合和多個(gè)集合類提供了控制數(shù)值集合的操作，其中數(shù)值是關(guān)鍵字，也就是說，不需要將另一組值與每個(gè)關(guān)鍵字相關(guān)聯(lián)。多個(gè)集合允許重復(fù)的鍵，而集合不允許。元素的順序由比較器函數(shù)對(duì)象決定。對(duì)于整數(shù)多集，只要使用比較器函數(shù)對(duì)象less來排序關(guān)鍵字，元素就可以按升序排列。多集和集合通常被實(shí)現(xiàn)為紅色和黑色的二進(jìn)制排序樹。紅黑二進(jìn)制排序樹是實(shí)現(xiàn)平衡二進(jìn)制排序樹的方法之一。示例11.4整數(shù)多集合關(guān)聯(lián)容器類、11.4關(guān)聯(lián)容器、映射和多映射類提供了操作與關(guān)鍵字關(guān)聯(lián)的映射值的方法。映射和多重映射的主要區(qū)別在于多重映射允許存儲(chǔ)與映射值相關(guān)聯(lián)

12、的重復(fù)關(guān)鍵字，而映射只允許逐個(gè)存儲(chǔ)對(duì)應(yīng)于映射值的單個(gè)關(guān)鍵字。多個(gè)映射和映射關(guān)聯(lián)容器類用于快速存儲(chǔ)和讀取關(guān)鍵字和相關(guān)值(鍵/值對(duì))。如果保存了學(xué)生的簡明信息，則需要按學(xué)生編號(hào)進(jìn)行排序，最合適的是使用映射關(guān)聯(lián)容器(因?yàn)樗粫?huì)重復(fù)編號(hào))。如果按名稱排序，因?yàn)槊Q可能重復(fù)，所以使用多個(gè)映射更合適。使用時(shí)使用頭文件。11.5容器適配器，STL提供了三個(gè)容器適配器：堆棧、隊(duì)列和優(yōu)先級(jí)隊(duì)列。所謂的適配器不是獨(dú)立的，它連接到一個(gè)順序容器。如果你想聲明一個(gè)由向量實(shí)現(xiàn)的字符堆棧，聲明如下：堆棧sk；優(yōu)先級(jí)隊(duì)列(priority_queue)適配器實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列。元素插入是按優(yōu)先級(jí)順序自動(dòng)插入的，因此優(yōu)先級(jí)最高的元

13、素首先從優(yōu)先級(jí)隊(duì)列中取出。通常使用基于向量的容器。默認(rèn)情況下，priority_queue的數(shù)據(jù)結(jié)構(gòu)基于向量。然后它可以像順序容器一樣使用。但是它沒有自己的構(gòu)造函數(shù)和析構(gòu)函數(shù)。它用它來實(shí)現(xiàn)類的構(gòu)造函數(shù)和析構(gòu)函數(shù)(比如向量)。默認(rèn)情況下，隊(duì)列基于de quee，堆?？梢曰趘ector或de quee。示例11.5優(yōu)先級(jí)隊(duì)列類演示，11.6通用算法和函數(shù)對(duì)象，算法表示為一系列函數(shù)模板。它們完全在STL頭文件中定義。用戶可以以多種方式專門化每個(gè)模板函數(shù)，這極大地提高了它作為通用程序組件的適用性。這些函數(shù)模板使用迭代器作為它們的參數(shù)和返回值來對(duì)容器(序列)執(zhí)行各種操作。本節(jié)進(jìn)一步討論算法的一般性。1

14、1.6.1功能對(duì)象、11.6.2通用算法、11.6.1功能對(duì)象。在C語言中，為了使程序更安全，使用“引用”代替指針作為函數(shù)的參數(shù)或返回值。在C語言的通用算法中，“函數(shù)對(duì)象”被類似地用來代替函數(shù)指針。函數(shù)對(duì)象是重載函數(shù)調(diào)用運(yùn)算符(運(yùn)算符()的類。這個(gè)運(yùn)算符封裝了應(yīng)該作為函數(shù)實(shí)現(xiàn)的操作。通常，函數(shù)對(duì)象作為參數(shù)傳遞給通用算法。像“引用”一樣，“功能對(duì)象”很少單獨(dú)使用。函數(shù)對(duì)象也稱為類函數(shù)對(duì)象和函子。為了消除算法的類型依賴性，可以使用函數(shù)指針作為參數(shù)，類似于第6.8節(jié)附錄中庫函數(shù)快速排序的處理方法。這種方法更適合于函數(shù)模板。11.6.1函數(shù)對(duì)象、示例11.6求和函數(shù)對(duì)象的定義和測(cè)試。函數(shù)對(duì)象作為求“數(shù)

15、值比較算法”序列中最小值的函數(shù)模板：模板常量類型示例中的Comp是比較函數(shù)對(duì)象類，不同的數(shù)據(jù)類型可以定義不同的函數(shù)對(duì)象。重載()，參數(shù)表可以有任意數(shù)量的參數(shù)。11.6.1與函數(shù)指針相比，函數(shù)對(duì)象有三個(gè)優(yōu)點(diǎn)：第一，函數(shù)指針是間接引用，不能用作內(nèi)聯(lián)函數(shù)，而函數(shù)對(duì)象可以，這更快；第二，函數(shù)對(duì)象可以有任意數(shù)量的額外數(shù)據(jù)，可以用來緩沖當(dāng)前數(shù)據(jù)和結(jié)果，提高操作質(zhì)量。當(dāng)然，在大多數(shù)情況下不一定使用它。在上例中，res是一個(gè)額外的數(shù)據(jù)；第三，在編譯時(shí)檢查函數(shù)對(duì)象的類型。函數(shù)對(duì)象1有許多來源。由標(biāo)準(zhǔn)庫預(yù)定義的一組算術(shù)、關(guān)系和邏輯函數(shù)對(duì)象；2.一組預(yù)定義的函數(shù)適配器，允許預(yù)定義函數(shù)對(duì)象的專門化或擴(kuò)展；3.自定義函數(shù)對(duì)象。11.6.1功能對(duì)象，預(yù)定義的功能對(duì)象分為算術(shù)、關(guān)系和邏輯運(yùn)算。每個(gè)對(duì)象都是一個(gè)類模板，操作數(shù)類型作為模板參數(shù)。使用時(shí)，應(yīng)包含頭文件：#包含以加法為例，討論名為加號(hào)的類模板，并使用如下整數(shù)：加號(hào)添加；int ival1=30，ival2=15int sum=intAdd(ival1，ival 2)；/相當(dāng)于：sum=ival1invar2，但函數(shù)對(duì)象主要用作泛型算法的參數(shù)，通常用于更改默認(rèn)操作。例如，在示例11.3中，有：開始()，vec。結(jié)束()、更大()；也就是說，將整數(shù)的大于關(guān)系函數(shù)對(duì)象作