C 程序設(shè)計(jì)課件：第十一章標(biāo)準(zhǔn)模板庫(kù)（選讀）

1、第十一章 標(biāo)準(zhǔn)模板庫(kù)（選讀） 庫(kù)（library）是一系列程序組件的集合，它們可以在不同的程序中重復(fù)使用。 庫(kù)函數(shù)設(shè)計(jì)的第一位的要求就是通用性，模板（template）為通用性帶來(lái)了不可估量的前景。 標(biāo)準(zhǔn)模板庫(kù)（Standard Template Library）是ANSI/ISO C+最有特色、最實(shí)用的部分之一。STL包含:容器類（container）迭代子（iterator）算法（algorithm） 泛型算法（generic algorithm）和函數(shù)對(duì)象（function object）的概念與使用使算法擺脫了對(duì)不同類型數(shù)據(jù)個(gè)性操作的依賴。 標(biāo)準(zhǔn)模板庫(kù)的引入：11.1 標(biāo)準(zhǔn)模板庫(kù)簡(jiǎn)介

2、11.3 順序容器 11.2 迭代子類 11.6 容器適配器 11.4 泛型算法與函數(shù)對(duì)象 11.5 關(guān)聯(lián)容器 第十一章 標(biāo)準(zhǔn)模板庫(kù)（選讀）11.1 標(biāo)準(zhǔn)模板庫(kù)簡(jiǎn)介容器類（Container）容器類是管理序列的類，是容納一組對(duì)象或?qū)ο蠹念?。通過(guò)由容器類提供的成員函數(shù)，可以實(shí)現(xiàn)諸如向序列中插入元素，刪除元素，查找元素等操作，這些成員函數(shù)通過(guò)返回迭代子來(lái)指定元素在序列中的位置。容器分為三大類：順序容器（Sequence Container or Sequential Container）關(guān)聯(lián)容器（Associative Container）容器適配器（Container Adopter）參見(jiàn)表1

3、1.1。11.1 標(biāo)準(zhǔn)模板庫(kù)簡(jiǎn)介順序容器和關(guān)聯(lián)容器稱為第一類容器（first-class container）。STL也使容器提供類似的接口。許多基本操作是所有容器都適用的，可以用有類似操作的新類來(lái)擴(kuò)展STL。這些函數(shù)和運(yùn)算符可通稱為容器的接口。表11.2 所有標(biāo)準(zhǔn)庫(kù)容器共有的函數(shù)11.1 標(biāo)準(zhǔn)模板庫(kù)簡(jiǎn)介(2) 泛型算法（Generic Algorithm）：在模板中算法不依賴于具體的數(shù)據(jù)類型，而泛型算法更進(jìn)一步不依賴于具體的容器。泛型算法中采用函數(shù)對(duì)象（Function Object）引入不同情況下同一算法的差異。它沒(méi)有使用繼承和多態(tài)，避免了虛函數(shù)的開(kāi)銷，使STL效率更高。 迭代子把算法與容

4、器連接起來(lái)。注意算法只是間接通過(guò)迭代子操作容器元素，算法本身與容器無(wú)關(guān)。算法通常返回迭代子。 (3) 迭代子（Iterator）：迭代子是指針概念的泛型化，它指向容器中的元素，它能象指針一樣增減，輪流指示容器中每個(gè)元素。所以說(shuō)迭代子是面向?qū)ο蟀姹镜闹羔?。迭代子可以包括指針，但迭代子又不僅僅是一個(gè)指針。11.2 迭代子類迭代子屬性：C+標(biāo)準(zhǔn)庫(kù)中對(duì)普通類型迭代子按照基本訪問(wèn)功能分類，有五種四級(jí)（輸入/輸出為同一級(jí)）預(yù)定義迭代子，其功能最強(qiáng)最靈活的是隨機(jī)訪問(wèn)迭代子。表11.3 迭代子屬性表11.4 各種迭代子可執(zhí)行的操作【例11.1】尋找數(shù)組元素。由本例演示可見(jiàn)，泛型算法不直接訪問(wèn)容器的元素，所以與

5、容器無(wú)關(guān)。元素的全部訪問(wèn)和遍歷都通過(guò)迭代子實(shí)現(xiàn)，并不需要預(yù)知容器類型。11.3 順序容器順序容器：vector，list和deque。vector類和deque類是以數(shù)組為基礎(chǔ)的，list類是以雙向鏈表為基礎(chǔ)的。11.3.1 矢量類11.3.2 列表類11.3.3 雙端隊(duì)列類11.3. 1 矢量類矢量類的概念： 矢量（vector）類提供了具有連續(xù)內(nèi)存地址的數(shù)據(jù)結(jié)構(gòu)。它可通過(guò)下標(biāo)運(yùn)算符 直接有效地訪問(wèn)矢量的任何元素。 與數(shù)組不同，vector的內(nèi)存用盡時(shí)，vector自動(dòng)分配更大的連續(xù)內(nèi)存區(qū)，將原先的元素復(fù)制到新的內(nèi)存區(qū)，并釋放舊的內(nèi)存區(qū)。這是矢量類的優(yōu)點(diǎn)。 內(nèi)存分配由分配子（Allocato

6、r）完成。分配子也是類，它運(yùn)用了new和delete運(yùn)算符，本教材不作進(jìn)一步討論。矢量類的迭代子：每個(gè)容器都有自己所支持的迭代子類型，迭代子決定了可采用哪種算法。vector支持隨機(jī)訪問(wèn)迭代子，具有最強(qiáng)的功能。vector的迭代子通常實(shí)現(xiàn)為vector元素的指針。所謂選擇容器類，實(shí)際上很大部分是選擇所支持的迭代子。11.3. 1 矢量類矢量容器的聲明：#includevector vi; /定義存放整形序列的向量容器對(duì)象vi，長(zhǎng)度為0的空vectorvector vf;/存放實(shí)型序列的向量容器vector vch;/存放字符序列的向量容器vectorvstr; /存放字符串序列的向量容器11.

7、3.1 矢量類矢量容器的構(gòu)造函數(shù)：vector(size_t n); /構(gòu)造一個(gè)有n個(gè)元素的矢量，/每個(gè)元素都是由默認(rèn)的構(gòu)造函數(shù)所建立的vector(size_t n,T& V); /T表示矢量的基本類型，如int；/為每個(gè)元素用同一個(gè)對(duì)象V來(lái)賦初值vector(first,last);/元素的初值由區(qū)間first,last)指定的序列中的元素復(fù)制而來(lái) vector(vector& X) /復(fù)制構(gòu)造函數(shù)這些構(gòu)造函數(shù)還可以顯式給出分配子(allocator)對(duì)象?！纠?1.2】尋找vector容器元素。對(duì)矢量的操作包含了第六章在順序表中所列出的操作，甚至更豐富。每種操作都是成員函數(shù)。對(duì)用戶自定義

8、的元素類，要重載“= =”和“”等比較運(yùn)算符。11.3.1 矢量類特殊類型迭代子： *它們本身也具有五種四級(jí)迭代子屬性之一反轉(zhuǎn)型迭代子（Reverse Iterator）：它是把一切都顛倒過(guò)來(lái)。正向遍歷一個(gè)第一類容器時(shí)，如果用了反轉(zhuǎn)迭代子，實(shí)際上實(shí)現(xiàn)的是反向遍歷。begin()和end()，分別返回指向容器首元素和容器的末元素的后繼的迭代子；而rbegin()和rend()，分別返回指向容器末元素和容器的首元素的前導(dǎo)的普通迭代子。后一對(duì)操作用于支持反轉(zhuǎn)型迭代子。：vector veco;vector:reverse_iterator r_iter;for(r_iter=veco.rbegin(

9、); /將r_iter指向到末元素r_iter!=veco.rend(); /不等于首元素的前導(dǎo)r_iter+) /實(shí)際上是遞減/循環(huán)體如果需要把升序的序列改為降序的序列時(shí)，并不需要真正去逆序一個(gè)序列，只要使用反轉(zhuǎn)迭代子就可以了。反轉(zhuǎn)迭代子屬性為隨機(jī)迭代子。11.3.1 矢量類插入型迭代子（Insertion Iterator）：當(dāng)用普通輸出迭代子來(lái)產(chǎn)生一個(gè)元素序列時(shí)，一旦添加一些元素就得完全重寫。例如普通輸出迭代子可以把一個(gè)矢量a的內(nèi)容復(fù)制到另一個(gè)矢量b中，復(fù)制可以從矢量b任一元素開(kāi)始，矢量b對(duì)應(yīng)位置上的元素被覆蓋，相當(dāng)于改寫。插入迭代子則可以添加元素，復(fù)制時(shí)它可以把矢量a插入到矢量b任一位

10、置。同一個(gè)copy()算法用不同類型迭代子，結(jié)果是不同的。 有三種插入迭代子，屬性均為輸出迭代子：insert_iterator用來(lái)將新元素插入到一個(gè)由迭代子（第二個(gè)參數(shù)Iter）指定的元素的前面（所謂插在a10之前，即在a9和a10之間添加）。back_insert_iterator用來(lái)將新元素添加到類型為Type的容器對(duì)象的末端；front_insert_iterator用來(lái)將新元素添加到容器的前端（注意：新添加的元素以逆序方式結(jié)束于被控序列前端,即最后添加的元素放在最前面）。 11.3.1 矢量類插入型迭代子使用方法：標(biāo)準(zhǔn)庫(kù)定義了一組（3個(gè)）插入型迭代子適配器函數(shù)。它們返回對(duì)應(yīng)的插入迭代

11、子：Inserter(Type&,Iter)它使用容器的insert()插入操作符代替賦值操作符。inserter()函數(shù)要求兩個(gè)實(shí)參：容器本身和它的一個(gè)指示起始插入位置的迭代子。標(biāo)記起始插入位置的迭代子并不是保持不變，而是隨每個(gè)被插入的元素而遞增，這樣每個(gè)元素就能順序被插入。注意是“插入”而不是“改寫”，back_inserter(Type&)它使用容器的push_back()插入操作代替賦值操作符，將新元素添加到容器對(duì)象的末端。實(shí)參是容器本身。返回一個(gè)back_inserter迭代子。front_inserter(Type&)它使用容器的push_front()插入操作代替賦值操作符，將新

12、元素添加到容器的前端，同樣，新添加的元素以逆序方式結(jié)束于被控序列前端,即最后添加的元素放在最前面。實(shí)參也是容器本身。返回一個(gè)front_inserter迭代子。front_inserter不能用于矢量vector，因?yàn)関ector沒(méi)有成員函數(shù)push_front()。11.3.1 矢量類流迭代子(Stream Iterator)：包括輸入流迭代子（Istream_Iterator）和輸出流迭代子（Ostream_Iterator） 輸入流迭代子類支持在istream、ifstream等輸入流類上的迭代子操作。istream_iterator聲明方式為：istream_iterator迭代子標(biāo)識(shí)

13、符(istream&);/Type為已定義了輸入操作的類型,實(shí)參可以是任意公有派生的/istream的子 類型的對(duì)象輸出流也有對(duì)應(yīng)的ostream_iterator類支持，其聲明方式為：ostream_iterator迭代子標(biāo)識(shí)符(ostream&)/實(shí)參同樣可以是公有派生子類型對(duì)象ostream_iterator迭代子標(biāo)識(shí)符(ostream&,char*)/第二參數(shù)為C風(fēng)格字符串【例11.3】用istream_iterator從標(biāo)準(zhǔn)輸入讀入一個(gè)整數(shù)集到vector中。 11.3.2 列表類列表類（list）的引入：是由雙向鏈表組成的。它有兩個(gè)指針域，可以向前也可以向后進(jìn)行訪問(wèn)，但不能隨機(jī)訪問(wèn)

14、，即支持的迭代子類型為雙向迭代子。列表類不能使用下標(biāo)運(yùn)算符。它定義在頭文件中。列表類容器也有多種構(gòu)造函數(shù)，與矢量類形式相同?！纠?1.4】展示列表類怎樣進(jìn)行鏈表操作。在本例中建立了兩個(gè)已排序好的列表類對(duì)象，然后歸并。全部用列表類的成員函數(shù)。不能使用泛型算法sort()對(duì)無(wú)序的列表類對(duì)象排序，因?yàn)閟ort()要求隨機(jī)迭代子，list僅支持雙向迭代子。11.3.3 雙端隊(duì)列類雙端隊(duì)列（Double-Ended Queue）類的引入：雙端隊(duì)列允許在隊(duì)列的兩端進(jìn)行操作。它以順序表為基礎(chǔ)，所以能利用下標(biāo)提供有效的索引訪問(wèn)，它支持隨機(jī)訪問(wèn)迭代子。使用雙端隊(duì)列，必須包含頭文件。雙端隊(duì)列類容器也有多種構(gòu)造函數(shù)

15、，與矢量類或列表類形式相同。【例11.5】雙端隊(duì)列類與矢量類一樣，有一個(gè)成員函數(shù)insert()，注意不是插入迭代子適配器函數(shù)inserter()。本例演示該函數(shù)的使用，最后輸出字符串：“STL功能強(qiáng)使用方便?！眃eque類重載了多個(gè)成員函數(shù)insert()：insert (it,x); /在迭代子it指定元素前插入一個(gè)值為x的元素，返回指向新元素的迭代子insert (it,n,x); /在迭代子it指定元素前插入n個(gè)值為x的元素insert (it,first,last); /在迭代子it指定元素前插入由區(qū)間first,last)指定的序列11.4 泛型算法與函數(shù)對(duì)象算法表現(xiàn)為一系列的函數(shù)

16、模板。它們完整定義在STL頭文件中。使用者可以用很多方式來(lái)特化每一個(gè)模板函數(shù)，大大提高了它作為通用型程序組件的適用性。這些函數(shù)模板使用迭代子作為它的參數(shù)和返回值，以此在容器（序列）上進(jìn)行各種操作。本節(jié)進(jìn)一步討論算法的通用性。11.4.1 函數(shù)對(duì)象 11.4.2 泛型算法 11.4.1 函數(shù)對(duì)象函數(shù)對(duì)象的基本概念：每個(gè)泛型算法（Generic Algorithm）的實(shí)現(xiàn)都獨(dú)立于容器類型，它消除了算法對(duì)類型的依賴性。在STL的泛型算法中采用“函數(shù)對(duì)象”（Function Object）來(lái)解決該問(wèn)題。函數(shù)對(duì)象是一個(gè)類，通常它僅有一個(gè)成員函數(shù)，該函數(shù)重載了函數(shù)調(diào)用操作符（operator()）。該操作

17、符封裝了應(yīng)該被實(shí)現(xiàn)為一個(gè)函數(shù)的操作。典型情況下，函數(shù)對(duì)象被作為實(shí)參傳遞給泛型算法。和“引用”一樣，“函數(shù)對(duì)象”很少獨(dú)立使用。函數(shù)對(duì)象亦稱擬函數(shù)對(duì)象（Function_Like Object）和函子（Functor）。 11.4.1 函數(shù)對(duì)象【例11.6】求和函數(shù)對(duì)象的定義和測(cè)試。注意函數(shù)對(duì)象Sum能實(shí)例化為有限種類型，如：整型、實(shí)型、字符型等等，也能用于string類型，因?yàn)閟tring重載了operator +。函數(shù)對(duì)象的應(yīng)用：函數(shù)對(duì)象主要是作為泛型算法的實(shí)參使用，通常用來(lái)改變默認(rèn)的操作，如：sort(vec.begin(),vec.end(),greater();這就是把整數(shù)的大于關(guān)系函數(shù)

18、對(duì)象作為實(shí)參，得降序排列。如果是字符串，則有：sort(svec.begin(),svec.end(),greater();只要改一下參數(shù)就又可用于字符串的排序。greater中所包含的比較算法實(shí)際上在內(nèi)置類型int，字符串類string中定義。由此可見(jiàn)函數(shù)對(duì)象并沒(méi)有新東西，只是一個(gè)固定格式，用起來(lái)更方便。 11.4.1 函數(shù)對(duì)象例如，自定義整數(shù)類Int，其中重載了比較算法“”運(yùn)算符：class Intpublic: Int(int ival=0):_val(ival) int operator-()return -_val; /負(fù)數(shù)符號(hào)重載 int operator%(int ival)re

19、turn _val%ival; /求余符號(hào)重載 bool operator(int ival)return _valival; /大于符號(hào)重載 bool operator!()return _val=0; /邏輯非符號(hào)重載private: int _val;Int類可以作為類型參數(shù)傳遞給函數(shù)對(duì)象greater()，同時(shí)把重載的運(yùn)算符也傳遞過(guò)去了。11.4.1 函數(shù)對(duì)象 以函數(shù)對(duì)象作為求序列中最小值的函數(shù)模板的“數(shù)值比較算法”參數(shù)：templateconst Type& min(const Type*p,int size,Comp comp) int minIndex=0; /最小元素下標(biāo)初值為

20、0,即設(shè)0號(hào)元素最小 for(int i=1;isize;i+) if(comp(pi,pminIndex) minIndex=i; return pminIndex; 例中Comp為比較函數(shù)對(duì)象（類模板），對(duì)不同的數(shù)據(jù)類型，可以產(chǎn)生不同的比較函數(shù)，以實(shí)現(xiàn)泛型算法。使用函數(shù)對(duì)象實(shí)現(xiàn)泛型算法：11.4.1 函數(shù)對(duì)象函數(shù)對(duì)象與函數(shù)指針相比較有三個(gè)優(yōu)點(diǎn)：第一，函數(shù)指針是間接引用，不能作為內(nèi)聯(lián)函數(shù)，而函數(shù)對(duì)象可以，這樣速度更快；第二，函數(shù)對(duì)象可以擁有任意數(shù)量的額外數(shù)據(jù)，用這些數(shù)據(jù)可以用來(lái)緩沖當(dāng)前數(shù)據(jù)和結(jié)果，提高運(yùn)行質(zhì)量，當(dāng)然多數(shù)情況下不一定使用，上例中res就是一個(gè)額外數(shù)據(jù)；第三，編譯時(shí)對(duì)函數(shù)對(duì)象作類

21、型檢查。函數(shù)對(duì)象來(lái)源：1. 標(biāo)準(zhǔn)庫(kù)預(yù)定義的一組算術(shù)，關(guān)系和邏輯函數(shù)對(duì)象；2. 預(yù)定義的一組函數(shù)適配器，允許對(duì)預(yù)定義的函數(shù)對(duì)象進(jìn)行特殊化或擴(kuò)展；3. 自定義函數(shù)對(duì)象。函數(shù)對(duì)象的優(yōu)點(diǎn)：11.4.1 函數(shù)對(duì)象預(yù)定義函數(shù)對(duì)象及其使用方法：使用時(shí)要包含頭文件：#include 算術(shù)函數(shù)對(duì)象：加法：plus(x,y) /返回x+y,可用于string、復(fù)數(shù)和浮點(diǎn)數(shù)等減法：minus(x,y) /返回x-y,不能用串,可用于復(fù)數(shù)和浮點(diǎn)數(shù)等乘法：multiplies(x,y) /返回x*y,不能用串,可用于復(fù)數(shù)和浮點(diǎn)數(shù)等除法：divides(x,y) /返回x/y,不能用串,可用于復(fù)數(shù)和浮點(diǎn)數(shù)等求余：modu

22、lus(x,y) /返回x%y,只能用于整數(shù)取反：negate(x) /返回-x,補(bǔ)碼,只能用于整數(shù)11.4.1 函數(shù)對(duì)象邏輯函數(shù)對(duì)象：這里Type必須支持邏輯運(yùn)算，有兩個(gè)參數(shù)。邏輯與：logical_and(x,y) /對(duì)應(yīng)“&”邏輯或：logical_or(x,y) /對(duì)應(yīng)“|”邏輯非：logical_not(x) /對(duì)應(yīng)“!”關(guān)系函數(shù)對(duì)象：它們的返回值為布爾量，兩個(gè)參數(shù)，第一參數(shù)和第二參數(shù)相比：等于：equal_to(x,y) /對(duì)應(yīng)x=y不等于：not_equal_to(x,y) /對(duì)應(yīng)x!=y大于：great(x,y) /對(duì)應(yīng)xy大于等于：great_equal(x,y) /對(duì)應(yīng)x=

23、y小于：less(x,y) /對(duì)應(yīng)xy小于等于：less_equal(x,y) /對(duì)應(yīng)x=y11.4.1 函數(shù)對(duì)象返回布爾值的函數(shù)對(duì)象稱為謂詞（predicate），默認(rèn)的二進(jìn)制謂詞是小于比較操作符“”，所以默認(rèn)的排序方式都是升序排列，它采用小于比較形式。函數(shù)適配器特化或擴(kuò)展一元或二元函數(shù)對(duì)象：綁定器（Binder）：把二元函數(shù)對(duì)象中的一個(gè)參數(shù)固定（綁定），使之轉(zhuǎn)為一元函數(shù)，C+標(biāo)準(zhǔn)庫(kù)提供兩種預(yù)定義的binder適配器：bind1st和bind2nd，分別綁定了第一或第二個(gè)參數(shù)。格式：bind2st(plus(x),3.0) /返回x+3.0取反器（Negator）：把函數(shù)對(duì)象的值翻轉(zhuǎn)的適配器

24、，如原來(lái)為小于，用了它后就變成了大于。C+標(biāo)準(zhǔn)庫(kù)也提供了兩種negator適配器：not1和not2。not1用于一元預(yù)定義函數(shù)對(duì)象；not2用于二元預(yù)定義函數(shù)對(duì)象。格式同綁定器。11.4.2 泛型算法范型算法分類為：(1)修改容器的算法，即變化序列算法（mutating-sequence algorithm），如copy()、remove()、replace()、swap()等；(2)不修改容器的算法，即非變化序列算法（non-mutating-sequence algorithm），如count()、find()等；以及數(shù)字型算法。*在泛型算法中有一種習(xí)慣用語(yǔ)，不說(shuō)滿足某條件的元素，而講滿

25、足指定二進(jìn)制謂詞規(guī)則的元素，因?yàn)橹^詞是返回布爾值的函數(shù)對(duì)象，滿足則返回true，即與滿足指定條件是同樣意思。 泛型算法函數(shù)名后綴：_if表示函數(shù)采用的操作是在元素上，而不是對(duì)元素的值本身進(jìn)行操作。如find_if算法表示查找一些值滿足函數(shù)指定條件的元素，而find查找特定的值。_copy表示算法不僅操作元素的值，而且還把修改的值復(fù)制到一個(gè)目標(biāo)范圍中。reverser算法顛倒范圍中元素的排列順序，而reverse_copy算法同時(shí)把結(jié)果復(fù)制到目標(biāo)范圍中。其它的后綴從英文意思上立即可以認(rèn)出其意義。11.4.2 泛型算法泛型算法的構(gòu)造與使用方法:所有泛型算法的前兩個(gè)實(shí)參是一對(duì)iterator，通常稱

26、為first和last，它們標(biāo)出要操作的容器或內(nèi)置數(shù)組中的元素范圍。元素的范圍，包括first，但不包含last的左閉合區(qū)間。即：first,last)當(dāng)first=last成立，則范圍為空。對(duì)iterator的屬性，則要求在每個(gè)算法聲明中指出，所聲明的是最低要求。如find()最低要求為：InputIterator，可以傳遞更高級(jí)別的迭代子。如：ForwardIterator、BidirectonalIterator及RandomAccessInterator。但不能用OutputInterator。 11.4.2 泛型算法泛型算法分類：1查找算法：有13種查找算法用各種策略去判斷容器中是否

27、存在一個(gè)指定值。equal_range()、lower_bound()和upper_bound()提供對(duì)半查找形式。2排序和通用整序算法：共有14種排序（sorting）和通用整序（ordering）算法，為容器中元素的排序提供各種處理方法。所謂整序，是按一定規(guī)律分類，如分割（partition）算法把容器分為兩組，一組由滿足某條件的元素組成，另一組由不滿足某條件的元素組成。3刪除和代替算法：有15種刪除和代替算法。4排列組合算法：有2種算法。排列組合是指全排列。如：三個(gè)字符a，b，c組成的序列有6種可能的全排列：abc，acb，bac，bca，cab，cba；并且六種全排列按以上順序排列，認(rèn)

28、為abc最小，cba最大，因?yàn)閍bc是全順序（從小到大）而cba是全逆序（從大到?。?11.4.2 泛型算法5生成和改變算法：有6種，包含生成（generate），填充（fill）等等。6關(guān)系算法：有7種關(guān)系算法，為比較兩個(gè)容器提供了各種策略，包括相等（equal()），最大（max()），最?。╩in()）等等。 7集合算法：4種集合（set）算法提供了對(duì)任何容器類型的通用集合操作。包括并（union），交（intersection），差（difference）和對(duì)稱差（symmetric difference）。 8. 堆算法：有4種堆算法。堆是以數(shù)組來(lái)表示二叉樹(shù)的一種形式。標(biāo)準(zhǔn)庫(kù)提供大

29、根堆（max_heap），它的每個(gè)結(jié)點(diǎn)的關(guān)鍵字大于其子結(jié)點(diǎn)的關(guān)鍵字。9. 算術(shù)算法：該類算法有4種，使用時(shí)要求包含頭文件。11.5 關(guān)聯(lián)容器關(guān)聯(lián)容器(associative container)的引入：它們能通過(guò)關(guān)鍵字（search key）直接訪問(wèn)(存儲(chǔ)和讀取元素)。四個(gè)關(guān)聯(lián)容器為：集合（set），多重集合（multiset），映射（map）和多重映射（multimap）。11.5.1 集合和多重集合類11.5.2 映射和多重映射類11.5.1 集合和多重集合類集合和多重集合類引入：它們提供了控制數(shù)值集合的操作，其中數(shù)值是關(guān)鍵字，即不必另有一組值與每個(gè)關(guān)鍵字相關(guān)聯(lián)。集合與多重集合類的主要差別

30、在于多重集合允許重復(fù)的關(guān)鍵字，而集合不允許重復(fù)的關(guān)鍵字。 集合和多重集合類提供了控制數(shù)值集合的操作，其中數(shù)值是關(guān)鍵字，即不必另有一組值與每個(gè)關(guān)鍵字相關(guān)聯(lián)。 多重集合允許重復(fù)的關(guān)鍵字（key），而集合不允許。 元素的順序由比較器函數(shù)對(duì)象（comparator function object）確定。如對(duì)整型multiset，只要用比較器函數(shù)對(duì)象less排序關(guān)鍵字，元素即可按升序排列。set類模板聲明為：templatetypename Key, typename Pred = less, typename A = allocator class set; /模板參數(shù)表中的非類型參數(shù)同樣可有默認(rèn)值1

31、1.5.1 集合和多重集合類set容器的構(gòu)造函數(shù)：set (); /構(gòu)造一個(gè)空的按默認(rèn)次序排列的集合set (pr); /構(gòu)造一個(gè)空的按函數(shù)對(duì)象pr排序的集合set (first,last); /構(gòu)造一個(gè)默認(rèn)次序排列的集合， /元素值由區(qū)間first,last)指定的序列復(fù)制set (first,last,pr); /同上，但按函數(shù)對(duì)象pr排序這些構(gòu)造函數(shù)還可以顯式給出分配子(Allocator)對(duì)象。集合和多重集合類支持雙向迭代子。 multiset和set通常實(shí)現(xiàn)為紅黑二叉排序樹(shù)。紅黑二叉排序樹(shù)是實(shí)現(xiàn)平衡二叉排序樹(shù)的方法之一。 【例11.7】整型多重集合關(guān)聯(lián)容器類11.5.2 映射和多重映

32、射類映射和多重映射類引入： 它們提供了操作與關(guān)鍵字相關(guān)聯(lián)的映射值（mapped value）的方法。映射和多重映射的主要差別在于多重映射允許存放與映射值相關(guān)聯(lián)的重復(fù)關(guān)鍵字，而映射只允許存放與映射值一一對(duì)應(yīng)的單一關(guān)鍵字。 多重映射和映射關(guān)聯(lián)容器類用于快速存儲(chǔ)和讀取關(guān)鍵字與相關(guān)值（關(guān)鍵字/數(shù)值對(duì)，key/value pair）。如果保存學(xué)生的簡(jiǎn)明資料，要求按學(xué)號(hào)排序，使用映射關(guān)聯(lián)容器（因?yàn)椴粫?huì)重號(hào)）是最合適的。如用姓名排序，因姓名可能重復(fù)，使用多重映射更為合適。使用時(shí)要用頭文件。 11.5.2 映射和多重映射類map類模板聲明：templatetypename Key,typename T,typ

33、ename Pred = less, typename A = allocatorpair class map; map容器有多種構(gòu)造函數(shù)：map (); /構(gòu)造一個(gè)空的按默認(rèn)次序排列的映射map (pr); /構(gòu)造一個(gè)空的按函數(shù)對(duì)象pr排序的映射map (first,last); /構(gòu)造按默認(rèn)次序排列的映射， /元素值由區(qū)間first,last)指定的有序序列復(fù)制map (first,last,pr); /同上，但按函數(shù)對(duì)象pr排序這些構(gòu)造函數(shù)還可以顯式給出分配子(allocator)對(duì)象。11.5.2 映射和多重映射類映射的使用：映射和多重映射類支持雙向迭代子。映射定義了成員操作符：T&

34、operatorconst Key& key這樣映射的使用是非常方便的，就如同一個(gè)數(shù)組，關(guān)鍵字作為下標(biāo)，相關(guān)值作為元素值?！纠?1.8】我國(guó)部分省份與面積映射關(guān)聯(lián)容器類的演示。 11.6 容器適配器容器適配器（container adapter）：棧，隊(duì)列和優(yōu)先級(jí)隊(duì)。所謂適配器并不獨(dú)立，它依附在一個(gè)順序容器上。如要聲明一個(gè)用矢量實(shí)現(xiàn)的字符型堆棧，聲明如下： stackvector sk;然后它可以象順序容器一樣使用。但它沒(méi)有自己的構(gòu)造和析構(gòu)函數(shù)，它使用其實(shí)現(xiàn)類（如vector）的構(gòu)造和析構(gòu)函數(shù)。隊(duì)列（queue）默認(rèn)用deque為基礎(chǔ)，棧（stack）可用vector或deque為基礎(chǔ)。11.

35、5.1 棧類 11.5.2 隊(duì)列類11.5.3 優(yōu)先級(jí)隊(duì)列類11.5.1 棧類 棧并不獨(dú)立，它依附在一個(gè)順序容器上。棧（stack）可用vector或deque為基礎(chǔ)。聲明一個(gè)用矢量實(shí)現(xiàn)的字符型堆棧，格式如下： stackvector sk;【例11.9】演示堆棧的壓入和彈出。棧類的引入：11.5.2 隊(duì)列類隊(duì)列（queue）： 默認(rèn)以deque為基礎(chǔ)【例11.10】演示隊(duì)列的入隊(duì)和出隊(duì)。11.5.3 優(yōu)先級(jí)隊(duì)列類優(yōu)先級(jí)隊(duì)列（priority_queue）適配器：用以實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列。元素插入是自動(dòng)按優(yōu)先級(jí)順序插入，使最高優(yōu)先級(jí)元素首先從優(yōu)先級(jí)隊(duì)列中取出。常用矢量為基礎(chǔ)容器。默認(rèn)時(shí)priorit

36、y_queue用vector為基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。 【例11.11】 優(yōu)先級(jí)隊(duì)列類演示，頭文件用，優(yōu)先級(jí)用數(shù)表示，數(shù)值越大優(yōu)先級(jí)越高。第十一章 標(biāo)準(zhǔn)模板庫(kù)（選讀）課程全部結(jié)束祝同學(xué)們有一個(gè)好成績(jī)！表11.1 標(biāo)準(zhǔn)庫(kù)容器類標(biāo)準(zhǔn)庫(kù)容器類說(shuō)明順序容器vector（參量）deque（雙端隊(duì)列）list（列表）從后面快速插入與刪除，直接訪問(wèn)任何元素從前面或后面快速插入與刪除，直接訪問(wèn)任何元素從任何地方快速插入與刪除，雙鏈表關(guān)聯(lián)容器set（集合）multiset（多重集合）map（映射）multimap（多重映射）快速查找，不允許重復(fù)值快速查找，允許重復(fù)值一對(duì)一映射，基于關(guān)鍵字快速查找，不允許重復(fù)值一對(duì)多映射，

37、基于關(guān)鍵字快速查找，允許重復(fù)值容器適配器stack（棧）queue（隊(duì)列）priority_queue（優(yōu)先級(jí)隊(duì)列）后進(jìn)先出（LIFO）先進(jìn)先出（FIFO）最高優(yōu)先級(jí)元素總是第一個(gè)出列表11.2 所有標(biāo)準(zhǔn)庫(kù)容器共有的函數(shù)（1）提供容器默認(rèn)初始化的構(gòu)造函數(shù)。通常每個(gè)容器都有幾個(gè)不同的構(gòu)造函數(shù)，提供容器不同的初始化方法將容器初始化為現(xiàn)有同類容器副本的構(gòu)造函數(shù)撤消容器時(shí)，進(jìn)行內(nèi)存處理判容器是否為空，空返回true,不空返回false返回容器中最多允許的元素量返回容器當(dāng)前元素量默認(rèn)構(gòu)造函數(shù)復(fù)制構(gòu)造函數(shù)析構(gòu)函數(shù)empty()max_size()size()說(shuō)明標(biāo)準(zhǔn)庫(kù)容器共有的函數(shù)將一個(gè)容器賦值復(fù)制給另一

38、個(gè)同類容器交換兩個(gè)容器的元素如果前面的容器小于后面的容器，則返回true，否則返回false，不適用于priority_queue如果前面的容器小于等于后面的容器，則返回true，否則返回false，不適用于priority_queue如果前面的容器大于后面的容器，則返回true，否則返回false，不適用于priority_queue如果前面的容器大于等于后面的容器，則返回true，否則返回false，不適用于priority_queue如果前面的容器等于后面的容器，則返回true，否則返回false，不適用于priority_queue如果前面的容器不等于后面的容器，則返回true，否則返

39、回false，不適用于priority_queueoperator=swap()operatoroperatoroperator=operator=operator!=說(shuō)明標(biāo)準(zhǔn)庫(kù)容器共有的函數(shù)表11.2 所有標(biāo)準(zhǔn)庫(kù)容器共有的函數(shù)（2）表11.2 所有標(biāo)準(zhǔn)庫(kù)容器共有的函數(shù)（3）獲得指向被控序列開(kāi)始處的迭代子，引用容器第一個(gè)元素獲得指向被控序列末端的迭代子，引用容器最后一個(gè)元素的后繼位置獲得指向被控序列末端的反轉(zhuǎn)型迭代子，引用容器最后一個(gè)元素。實(shí)際上這是該容器前后反轉(zhuǎn)之后的begin()獲得指向被控序列開(kāi)始處的反轉(zhuǎn)型迭代子，引用容器第一個(gè)元素的前導(dǎo)位置。實(shí)際上這是該容器前后反轉(zhuǎn)之后的end()從容

40、器中清除一個(gè)或幾個(gè)元素從容器中清除所有元素begin()end()rbegin()rend()erase()clear()說(shuō)明只在第一類容器中的函數(shù)表11.3 迭代子屬性標(biāo)準(zhǔn)庫(kù)迭代子類型說(shuō)明輸入InputIterator輸出OutputIterator正向ForwardIterator雙向Bidirectional Iterator隨機(jī)訪問(wèn) RandomAccessIterator從容器中讀取元素。輸入迭代子只能一次一個(gè)元素地正向移動(dòng)（即從容器開(kāi)頭到容器末尾，后移）。要重讀必須從頭開(kāi)始。向容器寫入元素。輸出迭代子只能一次一個(gè)元素地正向移動(dòng)。輸出迭代子要重寫，必須從頭開(kāi)始。組合輸入迭代子和輸出迭

41、代子的功能，并保留在容器中的位置（作為狀態(tài)信息），所以重新讀寫不必從頭開(kāi)始。組合正向迭代子功能與逆向移動(dòng)功能（即從容器序列末尾到容器序列開(kāi)頭）。組合雙向迭代子的功能，并能直接訪問(wèn)容器中的任意元素，即可向前或向后跳過(guò)任意個(gè)元素。包含正向迭代子所有功能，再增加先- -后執(zhí)行，前置自減迭代子先執(zhí)行后- - ，后置自減迭代子雙向迭代子-pp-提供輸入和輸出迭代子的所有功能正向迭代子間接引用迭代子，作為左值將一個(gè)迭代子賦給另一個(gè)迭代子輸出迭代子*pp=p1間接引用迭代子，作為右值將一個(gè)迭代子賦給另一個(gè)迭代子比較迭代子的相等性比較迭代子的不等性輸入迭代子*pp=p1p=p1p!=p1前置自增迭代子，先+后

42、執(zhí)行后置自增迭代子，執(zhí)行后再+所有迭代子+pp+說(shuō)明迭代操作表11. 4 各種迭代子可執(zhí)行的操作（1）包含雙向迭代子所有功能，再增加迭代子p遞增i位（后移i位）（p本身變）迭代子p遞減i位（前移i位）（p本身變）在p所在位置后移i位后的迭代子（迭代子p本身不變）在p所在位置前移i位后的迭代子（迭代子p本身不變）返回與p所在位置后移i位的元素引用如迭代子p小于p1，返回true，所謂小，即p在p1之前如迭代子p小于等于p1，返回true，否則返回false如迭代子p大于等于p1，返回true，所謂大即p在p1之后如迭代子p大于迭代子p1，返回true，否則返回false隨機(jī)訪問(wèn)迭代子p+=ip-

43、=ip+ip-ipipp1p=p1pp1說(shuō)明迭代操作表11. 4 各種迭代子可執(zhí)行的操作（2）【例11.1】尋找數(shù)組元素int main() int search_value,ia9=47,29,37,23,11,7,5,31,41; cout請(qǐng)輸入需搜索的數(shù)：search_value; int* presult=find(&ia0,&ia9,search_value); cout數(shù)值search_value (presult=&ia9 ?不存在:存在)endl; return 0;這里a9數(shù)組元素并不存在，但內(nèi)存地址單元存在。find()定義 ：templateInputIteratorfi

44、nd(InputIterator first, InputIterator last,const T value ) for(;first!=last;+first) if(value=*first) return first; return last;【例11.2】尋找vector容器元素int main() int i,search_value,ia9=47,29,37,23,11,7,5,31,41; vector vec(ia,ia+9); /數(shù)據(jù)填入vector vector:iterator iter; /iter是vector用的迭代子，自動(dòng)建為隨機(jī)訪問(wèn)迭代子 for(i=0;i

45、vec.size();i+) coutvecit; /size()返回元素?cái)?shù)量 coutendl; vec.push_back(13); /容器末尾插入新元素，vector只能在尾部處理 for(iter=vec.begin();iter!=vec.end();iter+) cout*itert; /標(biāo)準(zhǔn)輸出方法 coutn請(qǐng)輸入需搜索的數(shù)：search_value; iter=find(vec.begin(),vec.end(),search_value); /使用vector成員函數(shù)賦迭代子初值 cout數(shù)值search_value ( iter=vec.end() ?不存在:存在)end

46、l; return 0;【例11.3】標(biāo)準(zhǔn)輸入#include#include#include#include#includeusing namespace std;int main() istream_iterator input(cin); istream_iterator end_of_stream; vector vec; copy(input,end_of_stream,inserter(vec,vec.begin(); /輸入Z結(jié)束流 sort(vec.begin(),vec.end(),greater(); /降序排列 ostream_iteratoroutput(cout, )

47、; unique_copy(vec.begin(),vec.end(),output); coutendl; return 0;【例11.3】標(biāo)準(zhǔn)輸入首先，用一個(gè)istream_iterator迭代子input（其實(shí)參為cin，即標(biāo)準(zhǔn)輸入）讀入一個(gè)整數(shù)集到一個(gè)矢量類對(duì)象中，出現(xiàn)光標(biāo)后，可輸入：41 3 9 5 7 23 17 19 13 11 37 31 23 29 41 39 Z例中泛型算法copy()定義如下：templateOutputIterator copy(InputIterator first,InputIterator last,OutputInterator x) for(;

48、first!=last;+x,+first) *x=*first return (x); 實(shí)參end_of_stream是指示文件（流）的結(jié)束位置，輸入時(shí)必須在最后一個(gè)數(shù)字后加分隔符，然后加Ctrl-Z結(jié)束。復(fù)制算法要求提供一對(duì)iterator來(lái)指示文件（流）內(nèi)部的開(kāi)始和結(jié)束位置。第三個(gè)參數(shù)是標(biāo)準(zhǔn)函數(shù)inserter()返回的插入迭代子，它把流插入vec?！纠?1.3】標(biāo)準(zhǔn)輸入泛型算法sort()為升序排序算法，聲明如下templatevoid sort(RandomAccessIterator first, RandomAccessInterator last, Pr p);/第三參數(shù)為排序

49、方式，greater()是預(yù)定義的“大于”函數(shù)對(duì)象，排序時(shí)用它來(lái)比較數(shù)值大小。默認(rèn)時(shí)為“小于”，即升序排序。例中用輸出迭代子output來(lái)輸出。其第二個(gè)參數(shù) 表示用空格分隔各數(shù)字。泛型算法unique_copy（），復(fù)制一個(gè)序列，并刪除序列中所有重復(fù)元素。本例中，復(fù)制到output迭代子，并用空格分隔各整數(shù)的標(biāo)準(zhǔn)輸出。輸出為：41 39 37 31 29 23 19 17 13 11 9 7 5 3 【例11.4】列表類的鏈表操作int main() int i; list list1,list2; list:iterator iter; /iter是list用的迭代子，自動(dòng)建為雙向訪問(wèn)迭代子

50、 int arr1=5,7,17,19,23,43; int arr2=3,9,13,29,41; for(i=0;i6;i+) list1.push_back(arr1i); for(i=0;i5;i+) list2.push_front(arr2i); for(iter=list1.begin();iter!=list1.end();iter+) cout*itert; /輸出5,7,17,19,23,43 coutendl; for(iter=list2.begin();iter!=list2.end();iter+) cout*itert; /輸出41,29,13,9,3 couten

51、dl; list2.reverse(); /反轉(zhuǎn)為3,9,13,29,41 list1.merge(list2); /list2歸并到list1,方式默認(rèn)為升序 while(!list1.empty() /表空結(jié)束 coutlist1.front()t; /讀第一項(xiàng)，輸出3,5,7,9,13,17,19,23,29,41,43 list1.pop_front(); /從鏈表首刪去一項(xiàng) coutendl; return 0;【例11.5】雙端隊(duì)列類成員函數(shù)insert() 操作void print_string(char_deque deq)ostream_iteratoroutput(cout

52、);cout生成的字符串是：;copy(deq.begin(),deq.end(),output);int main()char arr1=功能強(qiáng),arr2=使用方便。;char_deque chdeq(arr1,arr1+6);print_string(chdeq);coutendl;chdeq.insert(chdeq.begin(),L); /逆序chdeq.insert(chdeq.begin(),T);chdeq.insert(chdeq.begin(),S);print_string(chdeq);coutendl;chdeq.insert(chdeq.end(),arr2,arr

53、2+10);print_string(chdeq);coutendl;return 0;【例11.6】求和函數(shù)對(duì)象的定義和測(cè)試templateclass Sum T res;public: Sum(T i=0):res(i) /構(gòu)造函數(shù),即Sum(T i=0)res=i; T operator()(T x) /累加，重載的調(diào)用操作符() res+=x; return res; ;templateT Func1(FuncObject fob,const T &val) /函數(shù)對(duì)象作為參數(shù) return fob(val); /調(diào)用重載的()，實(shí)現(xiàn)加法 templateT Func2(FuncObj

54、ect &fob,const T &val) /參數(shù)為引用，建議用此方式 return fob(val); 【例11.6】求和函數(shù)對(duì)象的定義和測(cè)試int main() Sum sum(10); /調(diào)用構(gòu)造函數(shù)建立sum。res值為10 int i=5,j=10; coutsum(j)tsum(i)endl; /調(diào)用重載的()，實(shí)現(xiàn)累加，輸出：20 25 coutFunc1(sum,i)t; /Func1參數(shù)傳值，sum:res保持25，在一份副本上完成sum+i，輸出：30 coutFunc1(sum,j)endl; /在副本上完成sum+j，未累加，輸出：35 coutFunc2(sum,i

55、)t; /Func2參數(shù)為引用，在原sum上完成sum=sum+i，實(shí)現(xiàn)累加，輸出：30 coutFunc2(sum,j)endl; /完成sum=sum+j，實(shí)現(xiàn)累加，輸出：40 /以下為函數(shù)對(duì)象標(biāo)準(zhǔn)用法，每次新建函數(shù)對(duì)象，F(xiàn)unc1和Func2結(jié)果無(wú)差別 coutFunc1(Sum(5),i)t; / 5+i，輸出：10 coutFunc2(Sum(),j)endl; / 0+j，輸出：10 return 0;輸出：2025 303535 304050 101010 101010【例11.7】整型多重集合關(guān)聯(lián)容器類多重集合關(guān)聯(lián)容器類，類模板聲明:templatetypename Key,

56、typename Pred = less, typename A = allocator class multiset; /模板參數(shù)表中的非類型參數(shù)同樣可有默認(rèn)值 #include#include /包含集合頭文件#include/包含算法頭文件using namespace std; /C+標(biāo)準(zhǔn)庫(kù)名字空間域typedef multisetINTMS; /特例取名INTMS，整型多重集合按升序排列【例11.7】整型多重集合關(guān)聯(lián)容器類int main() const int size=16; int asize=17,11,29,89,73,53,61,37,41,29,3,47,31,59,5,2; INTMS intMultiset(a,a+size);/用a來(lái)初始化INTMS容器實(shí)例 ostream_iterator output(cout, ); /整型輸出迭代子output，可通過(guò)cout輸出用空格分隔的整數(shù) cout這里原來(lái)有intMultiset.count(17) 個(gè)數(shù)值17endl; /查找有幾個(gè)關(guān)鍵字17 intMultiset.insert(17); /插入一個(gè)重復(fù)的數(shù)17 cout輸入后這里有intMultiset.count(17) 個(gè)數(shù)值17endl; INTMS:const_iterator result; /const_iterator使程序