標(biāo)準(zhǔn)模板庫STL課件

第十一章標(biāo)準(zhǔn)模板庫（STL）

庫（library）是一系列程序組件的集合，它們可以在不同的程序中重復(fù)使用。庫函數(shù)設(shè)計的第一位的要求就是通用性，為程序員提供大量實用的庫是C++的又一特色。標(biāo)準(zhǔn)模板庫（StandardTemplateLibrary）是ANSI/ISOC++最有特色、最實用的部分之一。STL包含了容器類（container）、迭代子（iterator）和算法（algorithm）三個部分。第十一章標(biāo)準(zhǔn)模板庫（STL）庫（library）是一系1第十一章標(biāo)準(zhǔn)模板庫（STL）11.1標(biāo)準(zhǔn)模板庫簡介

11.3順序容器

11.2迭代子類

11.5容器適配器

11.7VC++中的STL

11.6泛型算法與函數(shù)對象

11.4關(guān)聯(lián)容器

第十一章標(biāo)準(zhǔn)模板庫（STL）11.1標(biāo)準(zhǔn)模板庫簡介211.1

標(biāo)準(zhǔn)模板庫簡介

STL提供了一個標(biāo)準(zhǔn)化的模板化的對象容器庫，包含多種數(shù)據(jù)結(jié)構(gòu)及其算法，可以節(jié)省大量的時間和精力，而且程序是高質(zhì)量的。

容器類是管理序列的類，是容納一組對象或?qū)ο蠹膶ο?，甚至可以包含混合的對象，包含一組不同類型的對象，稱為異類容器（heterogeneouscontainer），一組相同類型的對象，稱為同類容器(homogenouscontainer)。通過由容器類提供的成員函數(shù)，可以實現(xiàn)諸如向序列中插入元素，刪除元素，查找元素等操作，這些成員函數(shù)通過返回迭代子來指定元素在序列中的位置。迭代子是面向?qū)ο蟀姹镜闹羔?，它提供了訪問容器或序列中每個對象的方法。這樣就可以把算法用于容器所管理的序列。

11.1標(biāo)準(zhǔn)模板庫簡介STL提供了一個標(biāo)準(zhǔn)化的模板化的對311.1

標(biāo)準(zhǔn)模板庫簡介容器分為三大類：順序容器（sequencecontainerorsequentialcontainer）關(guān)聯(lián)容器（associativecontainer）容器適配器（containeradopter）

順序容器和關(guān)聯(lián)容器稱為第一類容器（first-classcontainer）。另外有四種容器稱為近容器（nearcontainer）：C語言風(fēng)格數(shù)組、字符串string、操作1/0標(biāo)志值的bitset和進(jìn)行高速數(shù)學(xué)矢量運算的valarray。

11.1標(biāo)準(zhǔn)模板庫簡介容器分為三大類：411.1

標(biāo)準(zhǔn)模板庫簡介標(biāo)準(zhǔn)庫容器類說明順序容器vector（參量）deque（雙端隊列）list（列表）

從后面快速插入與刪除，直接訪問任何元素從前面或后面快速插入與刪除，直接訪問任何元素從任何地方快速插入與刪除，雙鏈表關(guān)聯(lián)容器set（集合）multiset（多重集合）map（映射）multimap（多重映射）

快速查找，不允許重復(fù)值快速查找，允許重復(fù)值一對一映射，基于關(guān)鍵字快速查找，不允許重復(fù)值一對多映射，基于關(guān)鍵字快速查找，允許重復(fù)值容器適配器stack（棧）queue（隊列）priority_queue（優(yōu)先級隊列）

后進(jìn)先出（LIFO）先進(jìn)先出（FIFO）最高優(yōu)先級元素總是第一個出列表11.1標(biāo)準(zhǔn)庫容器類

11.1標(biāo)準(zhǔn)模板庫簡介標(biāo)準(zhǔn)庫容器類說明順序容器

關(guān)聯(lián)容器

511.1

標(biāo)準(zhǔn)模板庫簡介

STL也使容器提供接口。許多基本操作是所有容器都適用的，而有些操作則適用于類似容器的子集?？梢杂眯碌念悂頂U(kuò)展STL。參見表11.2。這些函數(shù)和運算符可通稱為容器的接口。各容器具體接口參見附錄C。使用STL容器或容器適配器，要包含定義該容器模板類頭文件。參見表11.3。這些頭文件的內(nèi)容都在std名字空間域（namespacestd）中，程序中必須加以說明。

11.1標(biāo)準(zhǔn)模板庫簡介STL也使容器提供接口。許多基本611.1

標(biāo)準(zhǔn)模板庫簡介

在有關(guān)數(shù)組、鏈表和二叉樹等線性表和非線性表的討論中，若要訪問其中一個元素（結(jié)點），我們可以用下標(biāo)或者指針去訪問，而下標(biāo)實際上也是一種指針即地址，訪問時取地址的方式還有很多，一系列的訪問方法都可以抽象為迭代子（iterator）。訪問方法最終要歸于內(nèi)存地址的獲得，所以說迭代子是面向?qū)ο蟀姹镜闹羔槨?/p>

迭代子與指針有許多相同之處，但迭代子保存所操作的特定容器需要的狀態(tài)信息，從而實現(xiàn)與每種容器類型相適應(yīng)的迭代子。而且有些迭代子操作在所有容器中是一致的，如++運算符總是返回容器下一個元素的迭代子，間接引用符“*”，總是表示迭代子指向的容器元素。

迭代子用來將STL的各部分結(jié)合在一起。從本質(zhì)上說，STL提供的所有算法都是模板，我們可以通過使用自己指定的迭代子來對這些模板實例化。迭代子可以包括指針，但又不僅是一個指針。

11.1標(biāo)準(zhǔn)模板庫簡介在有關(guān)數(shù)組、鏈表和二叉樹等線性表711.1

標(biāo)準(zhǔn)模板庫簡介

STL最大的優(yōu)點是提供能在各種容器中通用的算法，例如插入、刪除、查找、排序等等。STL提供70種左右的標(biāo)準(zhǔn)算法。算法只是間接通過迭代子操作容器元素。算法通常返回迭代子。一個算法通?？捎糜诙鄠€不同的容器，所以稱為泛型算法（genericalgorithm）。算法分為：１．修改容器的算法，即變化序列算法（mutating-sequencealgorithm），如copy()、remove()、replace()、swap()等。２．不修改容器的算法，即非變化序列算法（non-mutating-sequencealgorithm），如count()、find()等。３．?dāng)?shù)字型算法。

11.1標(biāo)準(zhǔn)模板庫簡介STL最大的優(yōu)點是提供能在各種容811.2迭代子類

C++標(biāo)準(zhǔn)庫中有五種預(yù)定義迭代子，其功能最強(qiáng)最靈活的是隨機(jī)訪問迭代子。

標(biāo)準(zhǔn)庫定義迭代子類型說明輸入（InputIterator）

輸出（OutputIterator）

正向（ForwardIterator）

雙向（BidirectionalIterator）

隨機(jī)訪問（RandomAccessIterator）從容器中讀取元素。輸入迭代子只能一次一個元素地向前移動（即從容器開頭到容器末尾）。要重讀必須從頭開始。向容器寫入元素。輸出迭代子只能一次一個元素地向前移動。輸出迭代子要重寫，必須從頭開始。組合輸入迭代子和輸出迭代子的功能，并保留在容器中的位置（作為狀態(tài)信息），所以重新讀寫不必從頭開始。組合正向迭代子功能與逆向移動功能（即從容器序列末尾到容器序列開頭）。組合雙向迭代子的功能，并能直接訪問容器中的任意元素，即可向前或向后跳過任意個元素。表11.4迭代子類別

11.2迭代子類C++標(biāo)準(zhǔn)庫中有五種預(yù)定義迭代子，911.2迭代子類

標(biāo)準(zhǔn)庫定義迭代子的層次結(jié)構(gòu)，按這個層次，從上到下，功能越來越強(qiáng)。但不是繼承！inputoutputforwardbidirectionalrandomaccess圖11.1迭代子層次

11.2迭代子類標(biāo)準(zhǔn)庫定義迭代子的層次結(jié)構(gòu)，按這個1011.2迭代子類

只有第一類容器能用迭代子遍歷。表11.5給出各種不同容器所支持的迭代子類別。標(biāo)準(zhǔn)庫定義的各種迭代子可進(jìn)行的操作參見表11.6，

容器支持的迭代子類別順序容器vectordequelist

隨機(jī)訪問（randomaccess）隨機(jī)訪問（randomaccess）雙向（bidirection）關(guān)聯(lián)容器setmultisetmapmultimap

雙向（bidirection）雙向（bidirection）雙向（bidirection）雙向（bidirection）容器適配器stackqueuepriority_queue

不支持迭代子不支持迭代子不支持迭代子11.2迭代子類只有第一類容器能用迭代子遍歷。表11111.2迭代子類

下面結(jié)合find()算法討論迭代子與泛型算法的關(guān)系。find()定義如下：

template<typenameInputIterator,typenameT>InputIteratorfind(InputIteratorfirst,InputIteratorlast,countTvalue){for(;first!=last;++first)if(value==*first)returnfirst;returnlast}可見，泛型算法不直接訪問容器的元素，與容器無關(guān)。元素的全部訪問和遍歷都通過迭代子實現(xiàn)。并不需要預(yù)知容器類型。find()算法也支持系統(tǒng)內(nèi)置的數(shù)組類型：

11.2迭代子類下面結(jié)合find()算法討論迭代子與1211.2迭代子類【例11.1】尋找數(shù)組元素。#include<algorithm>#include<iostream>usingnamespacestd;

voidmain(){ intsearch_value,ia[9]={47,29,37,23,11,7,5,31,41}; cout<<"請輸入需搜索的數(shù)："<<endl; cin>>search_value; int*presult=find(&ia[0],&ia[9],search_value); cout<<"數(shù)值"<<search_value<<(presult==&ia[9]?"不存在":"存在")<<endl;}這里a[9]數(shù)組元素并不存在，但內(nèi)存地址單元存在。

11.2迭代子類【例11.1】尋找數(shù)組元素。1311.2迭代子類【例11.2】尋找vector容器元素。#include<algorithm>#include<vector>#include<iostream>usingnamespacestd;

voidmain(){ intsearch_value,ia[9]={47,29,37,23,11,7,5,31,41}; vector<int>vec(ia,ia+9);//數(shù)據(jù)填入vector cout<<"請輸入需搜索的數(shù)："<<endl; cin>>search_value; vector<int>::iteratorpresult;//定義迭代子 presult=find(vec.begin(),vec.end(),search_value); cout<<"數(shù)值"<<search_value<<(presult==vec.end()?"不存在":"存在")<<endl;}11.2迭代子類【例11.2】尋找vector容器元素1411.2迭代子類在<iterator>頭文件中還定義了一些專用迭代子：反轉(zhuǎn)迭代子(reverseiterator)；插入型迭代子(insertioniterator)；流迭代子(streamiterator)；流緩沖迭代子(streambufferiterator)；11.2迭代子類在<iterator>頭文件中還定義了1511.2迭代子類１．反轉(zhuǎn)型迭代子（reverseiterator）把一切都顛倒過來

vector<int>veco;vector<int>::reverse_iteratorr_iter;for(r_iter=veco.rbegin();//將r_iter指向到末元素 r_iter!=veco.rend();//不等于首元素的前導(dǎo) r_iter++){//實際是上是遞減 //循環(huán)體}如果要把升序的序列改為降序的序列，只要使用反轉(zhuǎn)迭代子就可以了。反轉(zhuǎn)迭代子定義為隨機(jī)迭代子。

11.2迭代子類１．反轉(zhuǎn)型迭代子（reverseit1611.2迭代子類２．插入型迭代子（insertioniterator）：可以用輸出迭代子來產(chǎn)生一個元素序列?？梢蕴砑釉囟槐刂貙?。有三種插入迭代子：back_insert_iterator<Type>是輸出迭代子，用來將產(chǎn)生的元素添加到類型為Type的容器對象的末端。就象在一個字符串末尾加一個串（strcat()）。front_insert_iterator<Type>是輸出迭代子，用來將產(chǎn)生的元素添加到容器的前端，就是，產(chǎn)生出來的元素以逆序方式結(jié)束于被控序列前端。insert_iterator<Type,Iter>也是輸出迭代子，它用來將產(chǎn)生的元素插入到一個由迭代子（第二個參數(shù)Iter）指定的元素的前面。

與之對應(yīng)的也有三個相關(guān)的適配器函數(shù)，它們返回特定的插入迭代子：back_inserter(Type&)：它使用容器的push_back()插入操作代替賦值操作符，實參是容器自己。返回一個back_inserter迭代子。front_insertor(Type&)：使用容器的push_front()插入操作代替賦值操作符，實參也是容器本身。返回一個front_inserter迭代子。inserter（Type&,Iter）：用容器的insert()插入操作符代替賦值操作符。inserter()要求兩個實參：容器本身和它的一個迭代子指示起始插入的位置。標(biāo)記起始插入位置的迭代子并不保持不變，而是隨每個被插入的元素而遞增，這樣每個元素就能順序被插入。

11.2迭代子類２．插入型迭代子（insertion1711.2迭代子類３．流迭代子有輸入流迭代子（istream_iterator）和輸出流迭代子（ostream_iterator）。在<iostream.h>、<fstream.h>等頭文件中定義了流類庫，在STL中為輸入/輸出流iostream提供了迭代子，它們可以與標(biāo)準(zhǔn)庫容器類型和泛型算法結(jié)合起來工作。使用這兩個迭代子必須包含頭文件<iterator>。

輸入流迭代子（istream_iterator）類支持在istream及其派生類（如ifstream）上的迭代子操作。istream_iterator聲明方式為：istream_iterator<Type>迭代子標(biāo)識符(istream&);//Type為已定義了輸入操作的類型,實參可以是任意公有派生的istream的子類型的對象

輸出流也有對應(yīng)的ostream_iterator類支持，其聲明方式為：ostream_iterator<Type>迭代子標(biāo)識符(ostream&)//實參同樣可以是公有派生子類型對象ostream_iterator<Type>迭代子標(biāo)識符(ostream&,char*)//第二參數(shù)為C風(fēng)格字符串

11.2迭代子類３．流迭代子有輸入流迭代子（istre1811.2迭代子類下面結(jié)合copy算法和sort算法來介紹istreamiterator和ostream_iterator?！纠?1.3】用istreamiterator從標(biāo)準(zhǔn)輸入讀入一個整數(shù)集到vector中。#include<iostream>#include<iterator>#include<algorithm>#include<vector>#include<functional>usingnamespacestd;

voidmain(){istream_iterator<int>input(cin); istream_iterator<int>end_of_stream; vector<int>vec; copy(input,end_of_stream,inserter(vec,vec.begin()));//輸入^Z結(jié)束流 sort(vec.begin(),vec.end(),greater<int>());//升序排列 ostream_iterator<int>output(cout,""); unique_copy(vec.begin(),vec.end(),output);}11.2迭代子類下面結(jié)合copy算法和sort算法來介1911.2迭代子類輸入：4139572317191311373123294139^Z泛型算法copy()定義如下：template<typenameInputIterator,typenameInputIterator,typenameOutputInterator>OutputIteratorcopy(InputIteratorfirst,InputIteratorlast,OutputInteratorx){ for(;first!=last;++x,++first)*x=*first return(x);}11.2迭代子類輸入：2011.2迭代子類

end_of_stream是指示文件（流）結(jié)束位置，它使用了缺省的構(gòu)造函數(shù)，輸入時必須在最后一個數(shù)字后加分隔符，然后加Ctrl-Z結(jié)束。拷貝算法要求我們提供一對iterator來指示文件（流）內(nèi)部的開始和結(jié)束位置。我們使用由istream對象初始化的istream_iterator提供開始位置，本例中為input。

本例中插入迭代子inserter作為copy的第三個參數(shù)，它是輸出型的，把流插入vec。泛型算法sort()為升序排序算法，聲明如下template<typenameRandomAccessInterator,typenamePr>voidsort(RandomAccessIteratorfirst,RandomAccessInteratorlast,Prp);第三參數(shù)為排序方式，greater<int>()是預(yù)定義的“大于”函數(shù)對象，排序時用它來比較數(shù)值大小。缺省時為“小于”，即升序排序。

例中用輸出迭代子output來輸出，泛型算法unique_copy（），復(fù)制一個序列，并刪除序列中所有重復(fù)元素。本例中，拷貝到output迭代子，即用空格分隔各整數(shù)的標(biāo)準(zhǔn)輸出。輸出為：41393731292319171311975311.2迭代子類end_of_stream是指示2111.2迭代子類４．流緩沖迭代子。這是STL后添加的一對迭代子，用來直接從一個流緩沖區(qū)（streambuffer）中插入或提取某種類型（通常為char）的元素。

11.2迭代子類４．流緩沖迭代子。這是STL后添加的一2211.3順序容器

C++標(biāo)準(zhǔn)模板庫提供三種順序容器：vector，list和deque。vector類和deque類是以數(shù)組為基礎(chǔ)的，list類是以雙向鏈表為基礎(chǔ)的。

矢量（vector）類提供了具有連續(xù)內(nèi)存地址的數(shù)據(jù)結(jié)構(gòu)。通過下標(biāo)運算符[]直接有效地訪問矢量的任何元素。與數(shù)組不同，vector的內(nèi)存用盡時，vector自動分配更大的連續(xù)內(nèi)存區(qū)，將原先的元素復(fù)制到新的內(nèi)存區(qū)，并釋放舊的內(nèi)存區(qū)。這是矢量（vector）類的優(yōu)點。在這里內(nèi)存分配是由分配子（allocator）完成。

矢量可以用來實現(xiàn)隊列、堆棧、列表和其他更復(fù)雜的結(jié)構(gòu)。vector支持隨機(jī)訪問迭代子，vector的迭代子通常實現(xiàn)為vector元素的指針。所謂選擇容器類，實際上很大部分是在選擇所支持的迭代子。

11.3順序容器

C++標(biāo)準(zhǔn)模板庫提供三種順序容器：2311.3順序容器使用向量容器的聲明如下： #include<vector>

……vector<int>vi;//定義存放整形序列的向量容器對象vi，長度為0的空vectorvector<float>vf; //存放實型序列的向量容器vector<char>vch; //存放字符序列的向量容器vector<char*>vstr; //存放字符串（字符指針）序列的向量容器

使用方法是典型的函數(shù)模板的使用方法。調(diào)用缺省的構(gòu)造函數(shù)，創(chuàng)建長度為0的向量。矢量容器有多種構(gòu)造函數(shù)。包括構(gòu)造一個有n個元素的矢量，每個元素都是由元素缺省的構(gòu)造函數(shù)所構(gòu)造出來的，還可以為每個元素用同一個對象來賦初值。還包括拷貝構(gòu)造函數(shù)，可以由一個已有的矢量容器對象來初始化新容器各元素的構(gòu)造函數(shù)。這些構(gòu)造函數(shù)還可以顯式給出分配子(allocator)對象。11.3順序容器使用向量容器的聲明如下：2411.3順序容器

對矢量的操作包含了在順序表中所列出的操作，而且更多。１．列表（list）是由雙向鏈表（doublylinkedlist）組成的。我們也已經(jīng)在有關(guān)鏈表的一節(jié)中介紹過了，它有兩個指針域，可以向前也可以向后進(jìn)行訪問，但不能隨機(jī)訪問，即支持的迭代子類型為雙向迭代子。使用起來很方便，與我們在§7.2節(jié)中定義的雙鏈表類模板相似，但通用性更好，使用更方便。列表的定義在頭文件<list>中。２．雙端隊列（deque）（double-endedqueue）類。雙端隊列允許在隊列的兩端進(jìn)行操作。支持隨機(jī)訪問迭代子。也支持通過使用下標(biāo)操作符“[]”進(jìn)行訪問。

11.3順序容器對矢量的操作包含了在順序表中所列出的2511.3順序容器

當(dāng)要增加雙端隊列的存儲空間時，可以在內(nèi)存塊中deque兩端進(jìn)行分配，通常保存為這些塊的指針數(shù)組。雙端隊列利用不連續(xù)內(nèi)存空間，它的迭代子比vector的迭代子更加智能化。對雙端隊列分配存儲塊后，往往要等刪除雙端隊列時才釋放，它比重復(fù)分配（釋放和再分配）更有效，但也更浪費內(nèi)存。

使用雙端隊列，必須包含頭文件<deque>。

11.3順序容器當(dāng)要增加雙端隊列的存儲空間時，可以在2611.4關(guān)聯(lián)容器

查找和排序總是對關(guān)鍵字進(jìn)行的，函數(shù)模板和類模板中只介紹了通用類型（亦稱泛型類型），并沒有涉及關(guān)鍵字。關(guān)聯(lián)容器（associativecontainer）能通過關(guān)鍵字（searchkey）直接訪問(存儲和讀取元素)。四個關(guān)聯(lián)容器為：集合（set），多重集合（multiset），映射（map），多重映射（multimap）。集合和多重集合類提供了控制數(shù)值集合的操作，其中數(shù)值是關(guān)鍵字，映射和多重映射類提供了操作與關(guān)鍵字相關(guān)聯(lián)的映射值（mappedvalue）的方法。多重集合關(guān)聯(lián)容器用于快速存儲和讀取關(guān)鍵字。

11.4關(guān)聯(lián)容器查找和排序總是對關(guān)鍵字進(jìn)行的，函數(shù)2711.4關(guān)聯(lián)容器

multiset和set通常實現(xiàn)為紅黑二叉排序樹。常用的二叉排序樹一般結(jié)點有四個域：一個數(shù)據(jù)域，三個指針域（左孩子指針，右孩子指針和雙親指針）。雙親指針使直接回訪成為可能，它使二叉排序樹刪除節(jié)點的算法變的簡單。在生成二叉排序樹時，當(dāng)輸入數(shù)據(jù)為已排好序時，會形成高度不平衡的只有半邊的斜杠形的樹，即退化為鏈表，二叉排序樹只有形成平衡的樹，也就是接近完全二叉數(shù)或滿二叉樹的形狀才能達(dá)到對半查找的效果。紅黑二叉排序樹是實現(xiàn)平衡二叉排序樹的方法之一。11.4關(guān)聯(lián)容器multiset和set通常實現(xiàn)為2811.4關(guān)聯(lián)容器【例11.4】整型多重集合關(guān)聯(lián)容器類的演示。類模板聲明:template<typenameKey,typenamePred=less<Key>,typenameA=allocator<Key>>classmultiset;//模板參數(shù)表中的非類型參數(shù)同樣可有缺省值

#include<iostream>#include<set> //包含集合頭文件#include<algorithm> //包含算法頭文件usingnamespacestd;//C++標(biāo)準(zhǔn)庫名字空間域typedefmultiset<int>INTMS;//特例取名INTMS，整型多重集合按升序排列

11.4關(guān)聯(lián)容器【例11.4】整型多重集合關(guān)聯(lián)容器類的2911.4關(guān)聯(lián)容器

voidmain(){constintsize=16; inta[size]={17,11,29,89,73,53,61,37,41,29,3,47,31,59,5,2}; INTMSintMultiset(a,a+size); ostream_iterator<int>output(cout,"");cout<<"這里原來有"<<intMultiset.count(17)<<"個數(shù)值17"<<endl; intMultiset.insert(17);//插入一個重復(fù)的數(shù)17 cout<<"輸入后這里有"<<intMultiset.count(17)<<"個數(shù)值17"<<endl; INTMS::const_iteratorresult; result=intMultiset.find(18); if(result==intMultiset.end())cout<<"沒找到值18"<<endl;elsecout<<"找到值18"<<endl; cout<<"intMultiset容器中有"<<endl; copy(intMultiset.begin(),intMultiset.end(),output); cout<<endl;}11.4關(guān)聯(lián)容器

voidmain(){const3011.4關(guān)聯(lián)容器

請注意multiset容器中自動作了升序排列。如需要，可以在VC++幫助中（MSDN）由關(guān)鍵字multiset查找有關(guān)迭代子、成員函數(shù)的定義和用法。

多重映射和映射關(guān)聯(lián)容器類用于快速存儲和讀取關(guān)鍵字與相關(guān)值（關(guān)鍵字/數(shù)值對，key/valuepair）。如果保存學(xué)生的簡明資料，要求按學(xué)號排序，使用映射關(guān)聯(lián)容器（因為不會重號）是最合適的。如用姓名排序，因姓名可能重復(fù)，使用多重映射更為合適。使用時要用頭文件<set>。

11.4關(guān)聯(lián)容器請注意multiset容器中自動作3111.5容器適配器

STL提供了三個容器適配器（containeradapter）：棧（stack），隊列（queue）和優(yōu)先級隊。棧是標(biāo)準(zhǔn)的棧，使用時要用頭文件<stack>。隊也是標(biāo)準(zhǔn)的，使用時要用頭文件<queue>。所謂適配器并不獨立，它依附在一個順序容器上。如要聲明一個用矢量實現(xiàn)的字符型堆棧，可使用如下聲明：

stack<vector<char>>sk;然后它就可以象順序容器一樣使用。但是它沒有自己的構(gòu)造和析構(gòu)函數(shù)，它使用其實現(xiàn)類（如vector）的構(gòu)造和析構(gòu)函數(shù)。就象一個儀器加了一個適配器增加了某些功能一樣。隊列（queue）缺省用deque為基礎(chǔ)，棧（stack）可用vector或deque為基礎(chǔ)。優(yōu)先級隊列（priority_queue）適配器實現(xiàn)優(yōu)先級隊列。元素插入是自動按優(yōu)先級順序插入，使最高優(yōu)先級元素首先從優(yōu)先級隊列中取出。優(yōu)先級隊列（priority_queue）的每個常用操作都實現(xiàn)為內(nèi)聯(lián)函數(shù)，調(diào)用基礎(chǔ)容器的相應(yīng)函數(shù)時，可避免二次函數(shù)調(diào)用的開銷。常用矢量為基礎(chǔ)容器。缺省情況下priority_queue實現(xiàn)時用vector為基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。

11.5容器適配器STL提供了三個容器適配器（co3211.5容器適配器【例11.5】優(yōu)先級隊列類演示，頭文件用<queue>，優(yōu)先級用數(shù)表示，數(shù)值越大優(yōu)先級越高。#include<iostream>#include<queue>#include<functional>usingnamespacestd;

11.5容器適配器【例11.5】優(yōu)先級隊列類演示，頭文3311.5容器適配器voidmain(){ priority_queue<int>prioque; //實例化存放int值的優(yōu)先級隊列，并用deque作為基礎(chǔ)數(shù)據(jù)結(jié)構(gòu) prioque.push(7);//壓入優(yōu)先級隊列 prioque.push(12); prioque.push(9); prioque.push(18); cout<<"從優(yōu)先級隊列中彈出"<<endl; while(!prioque.empty()){ cout<<prioque.top()<<'\t';//取最高優(yōu)先級數(shù)據(jù) prioque.pop();//彈出最高優(yōu)先級數(shù)據(jù) } cout<<endl;}11.5容器適配器voidmain(){3411.6泛型算法與函數(shù)對象

算法表現(xiàn)為一系列的函數(shù)模板，它們完整定義在STL頭文件中。一般這些函數(shù)模板都使用迭代子作為它的參數(shù)和返回值，以此在容器（序列）上進(jìn)行各種操作。11.6.1函數(shù)對象

11.6.2泛型算法

11.6泛型算法與函數(shù)對象算法表現(xiàn)為一系列的函數(shù)模3511.6.1函數(shù)對象

每個泛型算法（genericalgorithm）的實現(xiàn)都獨立于單獨的容器類型，它消除了算法的類型依賴性。

在C++中，為了使程序的安全性更好，采用“引用”來代替指針作為函數(shù)的參數(shù)或返回值。在C++的泛型算法中類似地采用了“函數(shù)對象”（functionobject）來代替函數(shù)指針。函數(shù)對象是一個類，它重載了函數(shù)調(diào)用操作符（operator()）。該操作符封裝了應(yīng)該被實現(xiàn)為一個函數(shù)的操作。典型情況下，函數(shù)對象被作為實參傳遞給泛型算法。和“引用”一樣，“函數(shù)對象”獨立使用比較少。函數(shù)對象亦稱擬函數(shù)對象（function_likeobject）和函子（functor）。下面給出一個求和函數(shù)對象的定義：template<typenameT>classSum{ Tres;public: sum(Ti=0):res(i){}//構(gòu)造函數(shù),即sum(Ti=0){res=i;} voidoperator()(Tx){res+=x;}//累加 Tresult()const{returnres;}//}11.6.1函數(shù)對象每個泛型算法（generica3611.6.1函數(shù)對象

函數(shù)對象與函數(shù)指針相比較有三個優(yōu)點：第一，函數(shù)指針是間接引用，不能作為內(nèi)聯(lián)函數(shù)，而函數(shù)對象可以，這樣速度更快；第二，函數(shù)對象可以擁有任意數(shù)量的額外數(shù)據(jù)，用這些數(shù)據(jù)可以緩沖當(dāng)前數(shù)據(jù)和結(jié)果，當(dāng)然多數(shù)情況下不一定使用，上例中res就是一個額外數(shù)據(jù)；第三，編譯時對函數(shù)對象做類型檢查。下面給出采用函數(shù)對象作為“數(shù)值比較算法”的求序列中最小值的函數(shù)模板。template<typenameType,typenameComp>constType&min(constType*p,intsize,Compcomp){ intminIndex=0;//最小元素下標(biāo)初值為0,即設(shè)0號元素最小 for(inti=1;i<size;i++) if(comp(p[i],p[minIndex]))minIndex=i; returnp[minIndex];}11.6.1函數(shù)對象函數(shù)對象與函數(shù)指針相比較有三個3711.6.1函數(shù)對象函數(shù)對象來源。1．標(biāo)準(zhǔn)庫預(yù)定義的一組算術(shù)，關(guān)系和邏輯函數(shù)對象；2．預(yù)定義的一組函數(shù)適配器，允許對預(yù)定義的函數(shù)對象進(jìn)行特殊化或擴(kuò)展；３．自定義函數(shù)對象。預(yù)定義函數(shù)對象分為算術(shù)、關(guān)系和邏輯操作。每個對象都是一個類模板，其中操作數(shù)類型作為模板參數(shù)。使用時要包含頭文件：#include<functional>11.6.1函數(shù)對象函數(shù)對象來源。3811.6.1函數(shù)對象我們以加法為例，討論名為plus的類模板，對整數(shù)的用法實例如下：plus<int>intAdd;intival1=30,ival2=15;intsum=intAdd(ival1,ival2);//等效于:sum=ival1+inval2但是函數(shù)對象主要是作為泛型算法的實參使用，通常用來改變?nèi)笔〉牟僮?，比如在【?1.3】中有sort(vec.begin(),vec.end(),greater<int>());這就是把整數(shù)的大于關(guān)系函數(shù)對象作為實參，得降序排列。如果是字符串，則有：sort(svec.begin(),svec.end(),greater<string>());11.6.1函數(shù)對象我們以加法為例，討論名為plu3911.6.1函數(shù)對象比較算法在內(nèi)置類型int，字符串類string中定義。還可以自定義整數(shù)類Int:classInt{public: Int(intival=0):_val(ival){} intoperator_(){return-_val;}//負(fù)數(shù)符號重載 intoperator%(intval){return_val%ival;}//求余符號重載 booloperator<(intval){return_val<ival;}//小于符號重載 booloperator!(){return_val==0;}//邏輯非符號重載private: int_val;};每個類對象都可以作為有名或無名對象傳給函數(shù)，同時也把所需重載的算法傳過去了。

11.6.1函數(shù)對象比較算法在內(nèi)置類型int，字符4011.6.1函數(shù)對象

下面給出各種函數(shù)對象及其使用方法：參數(shù)和返回值。為方便，定義以下變量（對象）vector<string>svec;stringsval1,sval2,sres;complexcval1,cval2,cres;intival1,ival2,ires;IntIval1,Ival2,Ires;doubledval1,dval2,dres;11.6.1函數(shù)對象下面給出各種函數(shù)對象及其使用方4111.6.1函數(shù)對象

為了用實例來說明使用方法，定義一個可用單參數(shù)函數(shù)對象(一元函數(shù)對象)的函數(shù)模板和一個可用雙參數(shù)函數(shù)對象（二元函數(shù)對象）的函數(shù)模板：template<TypenameFuncObject,TypenameType>TypeUnaryFunc(FuncObjectfob,constType&val){returnfob(val);}template<TypenameFuncObject,TypenameType>TypeBinaryFunc(FuncObjectfob,constType&val1,constType&val2){returnfob(val1,val2);}11.6.1函數(shù)對象為了用實例來說明使用方法，定義4211.6.1函數(shù)對象算術(shù)函數(shù)對象：加法：plus<Type>minus<int>intSub;ires=intSub(ival1,ival2);dres=BinaryFunc(plus<double>(),dval1,dval2);sres=BinaryFunc(plus<string>(),sval1,sval2);減法：minus<Type>//同加法乘法：multiplies<Type>//對串類無定義,不能用串，可用于復(fù)數(shù)和浮點數(shù)等cres=BinaryFunc(multiplies<complex>(),cal1,cal2);dres=BinaryFunc(multiplies<double>(),dval1,dval2);除法：divides<Type>//同乘法求余：modulus<Type>//不能用于復(fù)數(shù),浮點數(shù),只能用于整數(shù)modulus<Int>ImtModulus;Ires=IntModulus<Ival1,Ival2);//自定義類型ires=BinaryFunc(modulus<int>(),ival1,ival2);11.6.1函數(shù)對象算術(shù)函數(shù)對象：4311.6.1函數(shù)對象取反：negate<Type>//同取余,但為單參數(shù)ires=UnaryFunc(negate<Int>(),Ival1);邏輯函數(shù)對象，這里Type必須支持邏輯運算，有兩個參數(shù)。邏輯與：//對應(yīng)&&邏輯或：//對應(yīng)||邏輯非：//對應(yīng)!關(guān)系函數(shù)對象，它們的返回值為布爾量，兩個參數(shù)，第一參數(shù)和第二參數(shù)相比：等于：equal_to<Type>不等于：not_equal_to<Type>大于：great<Type>大于等于：great_equal<Type>小于：less<Type>小于等于：less_equal<Type>11.6.1函數(shù)對象取反：negate<Type>//4411.6.1函數(shù)對象

返回布爾值的函數(shù)對象稱為謂詞（predicate），默認(rèn)的二進(jìn)制謂詞是小于比較操作符“<”，所以默認(rèn)的排序方式都是升序排列，它采用小于比較形式。和容器類一樣，函數(shù)對象也可以由函數(shù)適配器來特殊化或擴(kuò)展一元（單參數(shù)）或二元（雙參數(shù)）函數(shù)對象：1．綁定器（binder）：把二元函數(shù)對象中的一個參數(shù)固定（綁定），使之轉(zhuǎn)為一元函數(shù)，C++標(biāo)準(zhǔn)庫提供兩種預(yù)定義的binder適配器：bind1st和bind2nd，分別綁定了第一或第二個參數(shù)。２．取反器（negator）：把函數(shù)對象的值翻轉(zhuǎn)的適配器，如原來為小于，用了它后就變成了大于。C++標(biāo)準(zhǔn)庫也提供了兩種negator適配器：not1和not2。not1用于一元預(yù)定義函數(shù)對象；not2用于二元預(yù)定義函數(shù)對象。

11.6.1函數(shù)對象返回布爾值的函數(shù)對象稱為謂詞（4511.6.2泛型算法

在C++標(biāo)準(zhǔn)庫中給出了70余種算法，泛型算法函數(shù)名都加有后綴，這些后綴的意思如下：_if 表示函數(shù)采用的操作是在元素上，而不是對元素的值本身進(jìn)行操作。如find_if算法表示查找一些值滿足函數(shù)指定條