《C++程序設(shè)計語言》課件第16章

第16章標準模板庫STL簡介

16.1STL概述16.2容器類16.3STL類的一般操作原理16.4vector容器16.5list容器16.6deque雙向隊列16.7關(guān)聯(lián)容器16.8容器適配器16.9算法16.10函數(shù)對象

16.1STL概述

雖然標準模板庫STL非常龐大且其語法復(fù)雜，然而一旦了解了它的構(gòu)造方式和基本原理，使用STL庫中的構(gòu)件還是相對簡單的。

標準模板庫STL核心有三個組成部分：容器、算法和迭代器。三者之間協(xié)同工作，從而為各種編程問題提供了行之有效的解決方案。16.1.1容器

所謂容器，即存放其它對象的對象。在STL中容器分為三大類：順序容器(SequenceContainer)、關(guān)聯(lián)容器(AssociativeContainer)和容器適配器(ContainerAdapter)。例如，vector類(動態(tài)數(shù)組)、deque(雙向隊列)、list(線性列表)等都是順序容器；map(鍵-值對)、set(集合)等都屬于關(guān)聯(lián)容器；queue是容器deque的一個適配器。

每個容器類都定義了一組成員函數(shù)，這些成員函數(shù)可以被應(yīng)用于該容器。例如，一個列表容器包括插入函數(shù)、刪除函數(shù)和合并元素函數(shù)；一個堆棧容器包括用于壓棧和彈棧的函數(shù)。16.1.2算法

算法作用于容器，它們提供操作容器中對象的各種方法，這些操作包括初始化、排序、搜索和轉(zhuǎn)換容器中的內(nèi)容等。許多算法都可以在一個容器內(nèi)對一定范圍的元素進行操作。16.1.3迭代器

迭代器是一種對象，其操作與指針類似，但指針只能指向特定類型的對象，而迭代器可指向容器中的元素而忽略其類型。利用迭代器可方便地對容器中的元素進行遍歷與循環(huán)。STL提供了以下5種迭代器：

(1)隨機訪問迭代器：存儲和檢索容器中元素的值，元素可以被隨機訪問。

(2)雙向迭代器：存儲和檢索容器中元素的值，元素可以被隨機訪問。

(3)前向迭代器：存儲和檢索容器中元素的值，只能向前移動。

(4)輸入迭代器：檢索但不能存儲容器中元素的值，只能向前移動。

(5)輸出迭代器：存儲但不能檢索容器中元素的值，只能向前移動。

一般而言，可用訪問能力較強的迭代器代替訪問能力較弱的迭代器。例如，可以用前向迭代器代替輸入迭代器。

迭代器的處理很像指針，可以對其進行遞增和遞減操作，也可以對其應(yīng)用運算符“*”。迭代器由各種容器定義的Iterator類型聲明。

STL也支持反向迭代器。反向迭代器可以是雙向的隨機訪問的迭代器，該迭代器可以相反的方向遍歷一個序列。因此，如果一個反向迭代器指向一個序列的末尾，對該迭代器的遞增操作將使其指向序列末尾的前一個元素。

當涉及STL中不同的迭代器類型時，本書將采用以下術(shù)語：

BiIter：雙向迭代器；

ForIter：前向迭代器；

InIter：輸入迭代器；

OutIter：輸出迭代器；

RandIter：隨機訪問迭代器。16.1.4其它STL元素

除容器、算法和迭代器之外，STL還有幾種標準組件，其中最重要的幾種組件是：分配器(Allocator)、謂詞(Predicate)、比較函數(shù)和函數(shù)對象。

每個容器都定義了一個分配器。分配器用于管理一個容器的內(nèi)存分配。默認的分配器是一個allocator類的對象。如果應(yīng)用中有特殊需求，也可以自定義分配器，但大多數(shù)情況下，使用默認分配器就足夠了。個別算法和容器使用一個稱為謂詞的特殊類型的函數(shù)。謂詞有兩種變體：一元謂詞和二元謂詞。一元謂詞有一個參數(shù)，二元謂詞有兩個參數(shù)。這些函數(shù)的返回值為true或false，其返回值由謂詞條件而定。在本章其余部分，當需要使用一元謂詞函數(shù)時，用UnPred類型標識；當使用二元謂詞函數(shù)時，則用BinPred類型標識。無論是一元謂詞還是二元謂詞，其參數(shù)都將包含被該容器存儲的對象類型的值。

在STL中，某些算法和類使用一種特殊的二元謂詞，這類謂詞可以比較兩個元素。比較函數(shù)用類型Comp標識。各種STL類都要求包含頭文件，C++標準庫也包括<utility>和<functional>頭文件。在頭文件<utility>中定義了一些實用類，如pair類等。<functional>頭文件包含了一些操作符對象，這些對象稱為函數(shù)對象，這些函數(shù)對象可代替函數(shù)指針。在<functional>中預(yù)定義了如下函數(shù)對象：

使用最普遍的函數(shù)對象也許是less，它用于比較兩個對象的大小。在后面所介紹的STL算法中，我們可以用函數(shù)對象代替函數(shù)指針。利用函數(shù)對象(而不是函數(shù)指針)可以生成更有效的代碼。

還有兩個移植到STL的實體是綁定器(Binder)和取反器(Negator)。一個綁定器可以把一個參數(shù)和一個函數(shù)對象綁定在一起，一個取反器將返回一個謂詞的補碼。

16.2容器類

容器就是存儲其它對象的對象。在STL中定義的容器如表16.1所示。使用STL中的每一個容器類都必須包含相應(yīng)的頭文件，因此，表16.1列出了其所必需的頭文件。特別需要指出的是：string類實際上亦是一個容器，我們將在本章后面進行討論。

16.3STL類的一般操作原理

雖然STL內(nèi)部操作非常復(fù)雜，但STL的使用卻很簡單。首先，必須確定想要使用的容器類型，每種容器都有其優(yōu)缺點。例如，當需要一個隨機訪問的、類似于數(shù)組的對象而且不需要進行太多的插入和刪除操作時，采用vector是非常適宜的。list雖然能夠提供廉價的插入和刪除，但卻以降低速度為代價。map是一個關(guān)聯(lián)容器，它用鍵作索引求值。

一旦選擇了某種容器類，就可以利用其成員函數(shù)往該容器中添加元素、訪問或修改并刪除這些元素。除bitset以外，一個容器在被添加元素時將自動擴張其容量，在被刪除元素時將自動縮小其容量。

元素可以多種不同的方式添加到各類容器中，或者是從容器中刪除。例如，順序容器和關(guān)聯(lián)容器都提供一個稱為insert()的成員函數(shù)，該函數(shù)可以將元素插入到一個容器中；這兩類容器還提供了一個稱為erase()的函數(shù)，該函數(shù)可以從一個容器中刪除元素。此外，順序容器還提供push_back()和pop_back()函數(shù)，它們分別把一個元素添加到容器末端或從容器末端刪除。對于順序容器而言，這些成員函數(shù)或許是最常用的添加或刪除元素的方法。list和deque容器還包括push_front()和pop_front()方法，它們能夠從容器的起始處添加和刪除元素。

在一個容器內(nèi)部訪問元素的最常用方法之一是通過迭代器。順序容器和關(guān)聯(lián)容器都提供了成員函數(shù)begin()和end()，這兩個函數(shù)分別返回指向該容器起始位置和終止位置的迭代器。這些迭代器在訪問遍歷容器時非常方便。例如，為了在一個容器中進行循環(huán)操作，可以利用begin()以獲得一個指向容器起始位置的迭代器，然后對其進行遞增，直到它的值變?yōu)閑nd()。

關(guān)聯(lián)容器提供了成員函數(shù)find()，該函數(shù)被用于根據(jù)關(guān)鍵字在關(guān)聯(lián)容器中查找相應(yīng)的元素。由于關(guān)聯(lián)容器總是一個鍵-值對，因此find()是關(guān)聯(lián)容器中大多數(shù)元素的查找方式。

因為vector是一個動態(tài)數(shù)組，所以可采用下標運算符對其元素進行訪問。

一旦有了一個存放對象的容器，就可以利用一種或多種算法來使用它。這些算法不僅可以使你以某種規(guī)定的方式改變?nèi)萜鞯膬?nèi)容，還可以把一種順序類型的容器轉(zhuǎn)換為另一種順序類型的容器。

在下面幾節(jié)中，我們將重點介紹如何把這些方法應(yīng)用于三個具有代表性的容器，即容器vector、list和map。一旦理解了這些容器的工作方式，那么其它容器的使用方法類同。

16.4vector容器

用途最多的容器當數(shù)vector類了。一個vector類的實例是一個動態(tài)數(shù)組，該數(shù)組可根據(jù)需求自動調(diào)整其大小。又因為vector是一個數(shù)組，故我們可使用下標運算符對其元素進行訪問。

vector類模板原型如下：

template<classT,classAllocator=allocator<T>>classvector

其中：模板參數(shù)T可為任何類型(基本類型或自定義類型)；Allocator為分配器類型，缺省值為標準分配器allocator<T>。

vector具有如下構(gòu)造函數(shù)：

(1)?explicitvector(constAllocator&a=Allocator());

(2)?explicitvector(size_typenum,constT&val=T();

(3)?constAllocator&a=Allocator());

(4)?vector(constvector<T,Allocator>&ob);

template<classInIter>vector(InIterstart,InIterend,constAllocator&a=Allocator());第(1)種形式構(gòu)造一個空的vector對象；第(2)種形式構(gòu)造一個具有num個元素、值為val的vector對象，val的值可以取缺省值；第(3)種形式根據(jù)一個已有的vector對象拷貝構(gòu)造另一個同樣的vector對象；第(4)種形式構(gòu)造一個其元素限定在迭代器start和end所指定的范圍內(nèi)的vector對象。

為了獲得最大的靈活性與可移植性，若存儲在vector中元素的類型為自定義類型，則這些自定義類型都應(yīng)該定義一個默認的構(gòu)造函數(shù)，并過載比較與賦值運算符?；绢愋妥詣訚M足這些要求。下面我們根據(jù)vector的構(gòu)造函數(shù)列舉一些定義vector對象的實例：

vector<int>iv;

//創(chuàng)建一個長度為0的int型vector對象iv

vector<char>cv(5);//創(chuàng)建其長度為5的char型vector對象cv

vector<char>cv1(5,‘x’);

//創(chuàng)建其長度為5并均初始化為?‘x’?的char型vector對象cv1

vector<int>iv1(iv); //創(chuàng)建一個和iv一模一樣的vector對象iv1

在vector類模板中過載了如下操作符：

==、！=、<、<=、>、>=、[]

因此，我們可用這些過載的操作符對vector中的元素進行比較與取元素操作。

在類模板vector中除過載了一些操作符外，還定義了一些非常有用的成員函數(shù)，利用這些成員函數(shù)可方便地操作vector中的元素。vector中定義的常用成員函數(shù)見表16.3。下面給出一實例，說明矢量vector的基本操作。

#include<iostream>

#include<vector>

#include<cctype>

usingnamespacestd;

intmain()

{

vector<char>v(10); //createavectoroflength10

unsignedinti;

//displayoriginalsizeofv

cout<<"size="<<v.size()<<endl; //assigntheelementsofthevectorsomevalues

for(i=0;i<10;i++)v[i]=i+'a';

//displaycontentsofvector

for(i=0;i<v.size();i++)cout<<v[i]<<"";

cout<<endl;

cout<<"Expandingvector"<<endl;

/*putmorevaluesontotheendofthevector,

itwillgrowasneeded*/

for(i=0;i<10;i++)v.push_back(i+10+'a');

//displaycurrentsizeofv

cout<<"Sizenow="<<v.size()<<endl; //displaycontentsofvector

cout<<“Currentcontents:”<<endl;

for(i=0;i<v.size();i++)cout<<v[i]<<“”;

cout<<endl;

//changecontentsofvector

for(i=0;i<v.size();i++)v[i]=toupper(v[i]);

cout<<endl;

cout<<“ModifiedContents:”<<endl;

for(i=0;i<v.size();i++)cout<<v[i]<<“”;

cout<<endl;

return0;

}程序運行輸出結(jié)果：

size=10

abcdefghij

Expandingvector

Sizenow=20

Currentcontents:

abcdefghijklmnopqrst

ModifiedContents:

ABCDEFGHIJKLMNOPQRST16.4.1通過迭代器訪問vector矢量中的元素

通過前面的學(xué)習我們已經(jīng)知道：在C++中數(shù)組和指針是密切相關(guān)的，一個數(shù)組元素既可以通過下標訪問，亦可以通過指針來訪問。在STL中與此相對應(yīng)的就是矢量與迭代器之間的聯(lián)系。一個vector中的元素可以通過下標訪問，亦可以通過迭代器訪問，下面我們給出一實例說明之。16.4.2vector的其它成員函數(shù)

下面我們再給出一實例，以展示vector其它成員函數(shù)的使用方法。程序運行輸出結(jié)果：

Vectorvcontains:123456

Firstelementofv:1

Lastelementofv:6

Contentsofvectorvafterchanges:722210456

Exception:invalidvector<T>subscript

Contentsofvectorvaftererase:22210456

Aftererase,vectorvisempty

Contentsofvectorvbeforeclear:123456

Afterclear,vectorvisempty16.4.3在vector中存儲自定義類型的對象

前面的例程中，vector中存儲的都是基本類型的數(shù)據(jù)，其實，vector中可存儲任何類型的對象。下面我們舉例說明這一問題?，F(xiàn)定義了一自定義類型DailyTemp(日常氣溫類)，我們要在一vector中存放一周之內(nèi)的每日最高氣溫。由于vector中的元素類型為DailyTemp(自定義類型)，在生成vector時要調(diào)用存儲對象所屬自定義類型的默認構(gòu)造函數(shù)，因此，一般而言，在vector中存儲的自定義類型(對象)應(yīng)自定義默認構(gòu)造函數(shù)并且應(yīng)過載一些必要的比較和賦值運算符。例如：

ector容器類提供了強大的功能性、安全性和靈活性，但它不如數(shù)組高效。因此，對于大多數(shù)編程而言，當需要定長尺寸的數(shù)組時，原始的數(shù)組仍是首選。

16.5list容器

容器list類支持雙向線性列表。和支持隨機訪問的vector不同，list只能被順序訪問。由于列表是雙向的，所以它們既可以按照從前向后的順序訪問，也可以按照從后向前的順序訪問。

容器list的類模板原型如下：

template<classT,classAllocator&=allocator<T>>classlist

其中，T為list中存儲的數(shù)據(jù)類型。分配器由Allocator指定，其默認值為標準分配器。它具有如下構(gòu)造函數(shù)：

(1)?explicitlist(constAllocator&a=Allocator());

(2)?explicitlist(size_typenum,constT&val=T(),constAllcator&a=Allocator());

(3)?list(constlist<T,Allocator>&ob);

(4)?template<classInIter>list(InIterstart,InIterend,constAllocator&a=Allocator());

第(1)種形式構(gòu)造一個空的列表；第(2)種形式構(gòu)造一個含有num個元素、元素的值為val的列表，該值可以是默認值；第(3)種形式構(gòu)造一個包含元素與ob相同的列表；第(4)種形式構(gòu)造一個包含的元素在迭代器start和end指定的范圍內(nèi)的列表。在list中過載了如下操作符：

==、!=、<、<=、>、>=

因此兩個list對象可以用上述過載的操作符進行比較運算。

除過載了上述操作符外，list還定義了很多具有多種過載形式的成員函數(shù)。表16.4列出了一些常用的成員函數(shù)。程序運行輸出結(jié)果：

valuescontains:2143

valuesaftersortingcontains:1234

otherValuescontains:2648

Aftersplicevaluescontains:12342648

valuescontains:12234468

otherValuescontains:2468

Aftermerge:

valuescontains:122234446688

otherValuescontains:Listisempty

Afterpop_frontandpop_backvaluescontains:

2223444668

Afteruniquevaluescontains:23468

Afterswap:

valuescontains:Listisempty

otherValuescontains:23468

Afterassignvaluescontains:23468

valuescontains:2233446688

Afterremove(4)valuescontains:22336688

容器類list和vector一樣亦可存儲自定義類型的對象，此時，自定義類型應(yīng)定義默認的構(gòu)造函數(shù)，并且應(yīng)過載相應(yīng)的比較和賦值運算符。

16.6deque雙向隊列

順序容器類deque集vector和list的優(yōu)勢于一身，它是一個雙向隊列(double-endedqueue)。我們既可以順序訪問其中的元素，亦可以像數(shù)組一樣用下標隨機地訪問其中的元素。它支持順序與隨機訪問迭代器，并且deque尺寸的增加可在隊列的兩端進行。deque采用非連續(xù)內(nèi)存分配，因此，deque迭代器較vector和基于指針數(shù)組中用于迭代的指針更加智能化。

deque擁有vector和list的大部分操作，具體內(nèi)容請查閱相關(guān)手冊或書籍。

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

關(guān)聯(lián)容器通過關(guān)鍵字訪問容器中相應(yīng)的值。在STL中共有四個關(guān)聯(lián)容器：set、multiset、map和multimap。在關(guān)聯(lián)容器中，按排列順序維護關(guān)鍵字。對關(guān)聯(lián)容器迭代時，按該容器元素的排列順序進行遍歷。

set和multiset類提供了控制數(shù)值集合的操作，其中數(shù)值即為關(guān)鍵字。set和multiset的主要區(qū)別在于：set中不允許有重復(fù)的元素，而multiset中允許出現(xiàn)重復(fù)的元素。

map和multimap維護著一鍵-值對，我們可通過其關(guān)鍵字來訪問所對應(yīng)的值。二者的差別僅在于map不允許重復(fù)的鍵-值對，而multimap允許。16.7.1map關(guān)聯(lián)容器類

前面我們已經(jīng)提到，一個map只能存放唯一的鍵-值對。為了創(chuàng)建非唯一性的鍵-值對，可使用multimap。在此，我們僅講述map，multimap的原理與map類同。

map和multimap的模板類原型如下：

template<classKey,classT,classComp=less<Key>,

classAllocator=allocator<pair<constkey,T>>classmap

其中，Key為關(guān)鍵字的數(shù)據(jù)類型；T是被存儲(映射)的值的數(shù)據(jù)類型；Comp是對兩個關(guān)鍵字進行比較的函數(shù)，它默認為標準的less()函數(shù)對象；Allocator是分配器，默認為allocator。

map具有如下構(gòu)造函數(shù)：

(1)?explicitmap(constComp&cmpfn=Comp(),constAllocator&a=Allocator());

(2)?map(constmap<Ley,T,Comp,Allocator>&ob);

(3)?template<classInIter>map(InIterstart,InIterend,

constComp&cmpfn=Comp(),constAllocator&a=Allocator());

第(1)種形式是構(gòu)造一個空的map；第(2)種形式是拷貝構(gòu)造函數(shù)；第(3)種形式是構(gòu)造一個其元素在迭代器start和end之間的map,由cmpfn指定的函數(shù)確定該映射的順序。正如前面所述，對于任何作為關(guān)鍵字的對象(自定義類型對象)，應(yīng)定義默認的構(gòu)造函數(shù)，并應(yīng)過載相應(yīng)的關(guān)系與賦值運算符。

在map中過載了如下操作符：

==、!=、<、<=、>、>=

另外，在map中還定義了多種類別的過載的成員函數(shù)以提供對map的操作，表16.5列出了一些常用的map成員函數(shù)。關(guān)鍵字-值對作為pair類型的對象存儲在一個map中，pair的類模板說明如下：

template<classKtype,classVtype>structpair{

typedefKtypefirst_type; //關(guān)鍵字的類型

typedefVtypesecond_type;

//值的類型

Ktypefirst;

//關(guān)鍵字

Vtypesecond;

//值

pair();

//構(gòu)造器

pair(constKtype&k,constVtype&v);

//構(gòu)造器

template<classA,classB>pair(const<A,B>&ob);

//拷貝構(gòu)造器

};可利用pair的構(gòu)造函數(shù)或make_pair()(一種函數(shù)模板)來構(gòu)造一個關(guān)鍵字-值對。make_pair的原型如下：

template<classKtype,classVtype>

pair<Ktype,Vtype>make_pair(constKtype&k,constVtype&v);

下面我們給出一實例，來闡述map的基本用法。

#include<iostream>

#include<map>

usingnamespacestd;

intmain()

{

map<char,int>m;

inti;程序運行輸出結(jié)果為

Enterkey:A

ItsASCIIvalueis6516.7.2set和multiset關(guān)聯(lián)容器類

一個set也可以被看成是一個map，只是它不是一個關(guān)鍵字-值對，它只有關(guān)鍵字，即值。一個set是若干元素的集合，在set中不允許出現(xiàn)相同的元素，multiset則不然，它允許出現(xiàn)相同的元素。set類模板的說明如下：

template<classKey,classCmp=less<Key>,

classAllocator=allocator<Key>>classset{

public:

//與map相同，除了以下兩種情況：

typedefKeyvalue_type;//關(guān)鍵字就是值

typedefCmpvalue_compare;

//無過載下標操作符[]

｝；

set的大部分操作與map相同，它支持雙向迭代器。下面給出一實例，用以展示set的簡單應(yīng)用。

#include<iostream>

#include<set>

#include<algorithm>

usingnamespacestd;

intmain()

{

typedefset<double,less<double>>double_set;

constintSIZE=5;

doublea[SIZE]={2.1,4.2,9.5,2.1,3.7};

double_setdoubleSet(a,a+SIZE);;

ostream_iterator<double>output(cout,"");

cout<<“doubleSetcontains:”;

copy(doubleSet.begin(),doubleSet.end(),output);

pair<double_set::const_iterator,bool>p;

p=doubleSet.insert(13.8); //valuenotinset

cout<<‘\n’<<*(p.first)

<<(p.second?“was”:“wasnot”)<<“inserted”;

cout<<“\ndoubleSetcontains:”;

copy(doubleSet.begin(),doubleSet.end(),output);

p=doubleSet.insert(9.5); //valuealreadyinset

cout<<‘\n’<<*(p.first)

<<(p.second?“was”:“wasnot”)<<“inserted”;

cout<<"\ndoubleSetcontains:";

copy(doubleSet.begin(),doubleSet.end(),output);

cout<<endl;

return0;

}

程序運行輸出結(jié)果：

doubleSetcontains:2.13.74.29.5

13.8wasinserted

doubleSetcontains:2.13.74.29.513.8

9.5wasnotinserted

doubleSetcontains:2.13.74.29.513.8

16.8容?器?適?配?器

一個容器適配器采用某種容器以實現(xiàn)自己特殊的行為。STL提供了三個容器適配器(ContainerAdapter):stack(堆棧)、queue(隊列)和priority_queue(優(yōu)先級隊列)。它們不同于上述的容器類，因為它們不提供存放數(shù)據(jù)的實際數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)方法，而且容器適配器不支持迭代器。容器適配器的好處是可利用上述容器實現(xiàn)自己的容器適配器。所有這些容器適配器都提供push和pop方法以實現(xiàn)在容器適配器數(shù)據(jù)結(jié)構(gòu)中插入元素和從容器適配器中讀取元素。下面我們簡要介紹這三個容器適配器。16.8.1stack適配器

stack采用一種后進先出(LastInFirstOut,LIFO)的數(shù)據(jù)結(jié)構(gòu)。stack可以用任何順序容器vector、list和deque實現(xiàn)，默認情況下stack由deque實現(xiàn)。stack適配器常用的方法有壓棧操作push(調(diào)用基礎(chǔ)容器的push_back成員函數(shù)實現(xiàn))、彈棧操作pop(調(diào)用基礎(chǔ)容器的pop_back成員函數(shù)實現(xiàn))、判空操作empty和取棧中元素個數(shù)的操作size。下面我們給出一實例，該stack分別用STL庫中的每個順序容器生成一個整數(shù)堆棧，以此來展示stack的實現(xiàn)與使用方法。程序運行輸出結(jié)果：

PoppingfromintDequeStack:9876543210

PoppingfromintVectorStack:9876543210

PoppingfromintListStack:987654321016.8.2queue適配器

queue類采用先進先出(FirstInFirstOut，F(xiàn)IFO)的數(shù)據(jù)結(jié)構(gòu)。它只能在隊列的尾部插入元素，在隊列的開頭刪除元素。queue可以用STL的list和deque實現(xiàn)，默認情況下用deque實現(xiàn)。隊列queue的基本操作有：從隊尾插入一個元素push(調(diào)用基礎(chǔ)容器的push_back成員函數(shù)實現(xiàn))、從隊頭刪除一個元素pop(調(diào)用基礎(chǔ)容器的pop_front成員函數(shù)實現(xiàn))、取得隊列的第一個元素的引用front(調(diào)用基礎(chǔ)容器的front成員函數(shù)實現(xiàn))、取得隊列中的最后一個元素back(調(diào)用基礎(chǔ)容器的back成員函數(shù)實現(xiàn))、判queue是否為空empty(調(diào)用基礎(chǔ)容器的empty成員函數(shù)實現(xiàn))、求隊列中元素的個數(shù)size(調(diào)用基礎(chǔ)容器的size成員函數(shù)實現(xiàn))。下面我們給出一實例，來說明queue的基本方法。

cout<<endl;

return0;

}

程序運行輸出結(jié)果：

Poppingfromvalues:3.29.85.416.8.3priority_queue適配器

priority_queue是一種其元素按優(yōu)先級排序的先進先出隊列。它可由vector和dequeue實現(xiàn)，默認情況下用vector實現(xiàn)。當插入元素時，元素自動按優(yōu)先級順序插入，取出元素時亦按優(yōu)先級的順序取出，即取出優(yōu)先最高的(值最大)元素。priority_queue的常規(guī)操作與queue相同。下面我們給出一實例來展示priority_queue的使用方法。

#include<iostream>

#include<queue>

#include<functional>

usingnamespacestd;

intmain()

{

priority_queue<double>priorities;

priorities.push(3.2);

priorities.push(9.8);

priorities.push(5.4);

cout<<“Poppingfrompriorities:”;

while(!priorities.empty()){

cout<<priorities.top()<<‘’;

priorities.pop();

}

cout<<endl;

return0;

}

程序運行輸出結(jié)果：

Poppingfrompriorities:9.85.43.2

16.9算法

前面已經(jīng)談到，STL的算法針對容器起作用。盡管各種容器都有其自身的基本操作，但STL標準算法還支持更廣泛、更復(fù)雜的操作。此外，STL算法還允許同時操作兩種不同類型的容器。為了采用STL中提供的算法，必須包含頭文件<algorithm>。

STL中定義了很多算法，表16.6為這些算法一覽表。STL中的所有算法都是函數(shù)模板，因此這些算法可應(yīng)用于任何類型的容器。STL算法的詳細內(nèi)容請參閱相關(guān)文獻與書籍，本節(jié)將演示一些具有代表性的范例來展示STL某些算法的功能。16.9.1fill、fill_n、generate與generate_n算法

下面我們給出一范例程序，以展示fill、fill_n、generate和generate_n算法的基本使用方法。

#include<iostream>

#include<algorithm>

#include<vector>

usingnamespacestd;

charnextLetter();

intmain()

{

vector<char>chars(10);

ostream_iterator<char>output(cout,"");

fill(chars.begin(),chars.end(),‘5’);

cout<<“Vectorcharsafterfillingwith5s:\n”;

copy(chars.begin(),chars.end(),output);

fill_n(chars.begin(),5,‘A’);

cout<<“\nVectorcharsafterfillingfiveelements”

<<“withAs:\n”;

copy(chars.begin(),chars.end(),output);

generate(chars.begin(),chars.end(),nextLetter);

cout<<“\nVectorcharsaftergeneratinglettersA-J:\n”;

copy(chars.begin(),chars.end(),output);

generate_n(chars.begin(),5,nextLetter);

cout<<“\nVectorcharsaftergeneratingK-Oforthe”

<<“firstfiveelements:\n”;

copy(chars.begin(),chars.end(),output);

cout<<endl;

return0;

}

charnextLetter()

{

staticcharletter=‘A’;

returnletter++;

}程序運行輸出結(jié)果：

Vectorcharsafterfillingwith5s:

5555555555

VectorcharsafterfillingfiveelementswithAs:

AAAAA55555

VectorcharsaftergeneratinglettersA-J:

ABCDEFGHIJ

VectorcharsaftergeneratingK-Oforthefirstfiveelements:

KLMNOFGHIJ16.9.2equal、mismatch和lexicographica_compare算法

下面我們給出一范例程序，以展示equal、mismatch和lexicographica_compare算法的基本用法。

//Demonstratesstandardlibraryfunctionsequal,

//mismatch,lexicographical_compare.

#include<iostream>

#include<algorithm>

#include<vector>

usingnamespacestd;

intmain()

{16.9.3remove、remove_if、remove_copy和remove_copy_if算法

下面我們給出一范例程序，以展示remove、remove_if、remove_copy和remove_copy_if算法的基本用法。

//DemonstratesStandardLibraryfunctionsremove,remove_if

//remove_copyandremove_copy_if

#include<iostream>

#include<algorithm>

#include<vector>

usingnamespacestd;

boolgreater9(int);程序運行輸出結(jié)果：

Vectorvbeforeremovingall10s:

1021041661481210

Vectorvafterremovingall10s:

2416614812

Vectorv2beforeremovingall10sandcopying:

1021041661481210

Vectorcafterremovingall10sfromv2:

2416614812000

Vectorv3beforeremovingallelements

greaterthan9:

1021041661481210

Vectorv3afterremovingallelements

greaterthan9:

2468

Vectorv4beforeremovingallelements

greaterthan9andcopying:

1021041661481210

Vectorc2afterremovingallelements

greaterthan9fromv4:

246800000016.9.4replace、replace_if、replace_copy和replace_copy_if算法

下面給出一范例程序，以展示replace、replace_if、replace_copy和replace_copy_if算法的基本用法。

//DemonstratesStandardLibraryfunctionsreplace,replace_if

//replace_copyandreplace_copy_if

#include<iostream>

#include<algorithm>

#include<vector>

usingnamespacestd;

boolgreater9(int);程序運行輸出結(jié)果：

Vectorv1beforereplacingall10s:

1021041661481210

Vectorv1afterreplacingall10swith100s:

1002100416614812100

Vectorv2beforereplacingall10sandcopying:

1021041661481210

Vectorc1afterreplacingall10sinv2:

1002100416614812100

Vectorv3beforereplacingvaluesgreaterthan9:

1021041661481210

Vectorv3afterreplacingallvaluesgreater

than9with100s:

1002100410061008100100

Vectorv4beforereplacingallvaluesgreater

than9andcopying:

1021041661481210

Vectorc2afterreplacingallvaluesgreater

than9inv4:

100210041006100810010016.9.5一些常用的數(shù)學(xué)算法

在STL中包含一些常用的數(shù)學(xué)算法，例如random_shuffle、count、count_if、min_element、max_element、accumulate、for_each和transform。下面給出一程序范例，以展示STL中這些常用數(shù)學(xué)算法的使用方法。

//ExamplesofmathematicalalgorithmsintheStandardLibrary.

#include<iostream>

#include<algorithm>

#include<numeric> //accumulateisdefinedhere

#include<vector>

usingnamespacestd;程序運行輸出結(jié)果：

Vectorvbeforerandom_shuffle:12345678910

Vectorvafterrandom_shuffle:92103168457

Vectorv2contains:10028150388910

Numberofelementsmatching8:3

Numberofelementsgreaterthan9:3

MinimumelementinVectorv2is:1

MaximumelementinVectorv2is:100

ThetotaloftheelementsinVectorvis:55

ThesquareofeveryintegerinVectorvis:

814100913664162549

ThecubeofeveryintegerinVectorvis:

729810002712165126412534316.9.6基本查找與排序算法

在STL中的查找與排序算法有：find、find_if、sort和binary_search。下面給出一范例程序，以展示這些算法的基本使用方法。

//Demonstratessearchandsortcapabilities.

#include<iostream>

#include<algorithm>

#include<vector>

usingnamespacestd;

boolgreater10(intvalue);

intmain()

{程序運行輸出結(jié)果：

Vectorvcontains:1021751681311207

Found16atlocation4

100notfound

Thefirstvaluegreaterthan10is17

foundatlocation2

Vectorvaftersort:2578101113161720

13wasfoundinv

100wasnotfoundinv16.9.7swap、iter_swap和swap_ranges算法

下面給出一范例程序，以展示swap、iter_swap和swap_ranges算法的基本用法。

//Demonstratesiter_swap,swapandswap_ranges.

#include<iostream>

#include<algorithm>

usingnamespacestd;

intmain()

{

constintSIZE=10;

inta[SIZE]={1,2,3,4,5,6,7,8,9,10};

ostream_iterator<int>output(cout,"");

copy(a,a+SIZE,output);

cout<<endl;

return0;

}

程序運行輸出結(jié)果：

Arrayacontains:

12345678910

Arrayaafterswappinga[0]anda[1]usingswap:

21345678910

Arrayaafterswappinga[0]anda[1]usingiter_swap:

12345678910

Arrayaafterswappingthefirstfiveelements

withthelastfiveelements:

6789101234516.9.8copy_backward、mergeunique和reverse算法

下面給出一范例程序，以展示copy_backward、mergeunique和reverse算法的基本用法。

//Demonstratesmiscellaneousfunctions:copy_backward,merge,

//uniqueandreverse.

#include<iostream>

#include<algorithm>

#include<vector>

usingnamespacestd;

intmain()

{

constintSIZE=5;

inta1[SIZE]={1,3,5,7,9};

inta2[SIZE]={2,4,5,7,9};

vector<int>v1(a1,a1+SIZE);

vector<int>v2(a2,a2+SIZE);

ostream_iterator<int>output(cout,“”);

cout<<“Vectorv1contains:”;

copy(v1.begin(),v1.end(),output);

cout<<“\nVectorv2contains:”;

copy(v2.begin(),v2.end(),output);

vector<int>results(v1.size());

copy_backward(v1.begin(),v1.end(),results.end());

cout<<“\n\nAftercopy_backward,resultscontains:”;

copy(results.begin(),results.end(),output);

vector<int>results2(v1.size()+v2.size());

merge(v1.begin(),v1.end(),v2.begin(),v2.end(),results2.begin());

cout<<“\n\nAftermergeofv1andv2results2contains:\n”;

copy(results2.begin(),results2.end(),output);

vector<int>::iteratorendLocation;

endLocation=unique(results2.begin(),results2.end());

cout<<“\n\nAfteruniqueresults2contains:\n”;

copy(results2.begin(),endLocation,output);

cout<<“\n\nVectorv1afterreverse:”;

reverse(v1.begin(),v1.end());

copy(v1.begin(),v1.end(),output);

cout<<endl;

return0;

}

程序運行輸出結(jié)果：

Vectorv1contains:13579

Vectorv2contains:24579

Aftercopy_backward,resultscontains:13579

Aftermergeofv1andv2results2contains:

1234557799

Afteruniqueresults2contains:

1234579

Vectorv1afterreverse:9753116.9.9inplace_merge、unique_copy和reverse_copy算法

下面給出一范例程序，以展示inplace_merge、unique_copy和reverse_copy算法的基本用法。

//Demonstratesmiscellaneousfunctions:inplace_merge,

//reverse_copy,andunique_copy.

#include<iostream>

#include<algorithm>

#include<vector>

#include<iterator>

usingnamespacestd;

intmain()

{

constintSIZE=10;

inta1[SIZE]={1,3,5,7,9,1,3,5,7,9};

vector<int>v1(a1,a1+SIZE);

ostream_iterator<int>output(cout,“”);

cout<<“Vectorv1contains:”;

copy(v1.begin(),v1.end(),output);

inplace_merge(v1.begin(),v1.begin()+5,v1.end());

cout<<“\nAfterinplace_merge,v1contains:”;

copy(v1.begin(),v1.end(),output);

vector<int>results1;

unique_copy(v1.begin(),v1.end(),back_inserter(results1));

cout<<“\nAfterunique_copyresults1contains:”;

copy(results1.begin(),results1.end(),output);

vector<int>results2;

cout<<“\nAfterreverse_copy,results2contains:”;

reverse_copy(v1.begin(),v1.end(),back_inserter(results2));

copy(results2.begin(),results2.end(),output);

cout<<endl;

return0;

}程序運行輸出結(jié)果：

Vectorv1contains:1357913579

Afterinplace_merge,v1contains:1133557799

Afterunique_copyresults1contains:13579

Afterreverse_copy,results2contains:997755331116.9.10集合操作

在STL中有若干集合操作，如inlude、set_difference、set_intersection等。下面給出一范例程序，以展示這些集合操作算法的基本用法。

//Demonstratesincludes,set_difference,set_intersection,

//set_symmetric_differenceandset_union.

#include<iostream>

#include<algorithm>

usingnamespacestd;

intmain()

{

constintSIZE1=10,SIZE2=5,SIZE3=20;

inta1[SIZE1]={1,2,3,4,5,6,7,8,9,10};程序運行輸出結(jié)果：

a1contains:12345678910

a2contains:45678

a3contains:4561115

a1includesa2

a1doesnotincludea3

set_differenceofa1anda2is:123910

set_intersectionofa1anda2is:45678

set_symmetric_differenceofa1anda2is:123910

set_unionofa1anda3is:12345678910111516.9.11lower_bound、upper_bound和equal_range算法

下面給出一范例程序，以展示lower_bound、upper_bound和equal_range算法的基本用法。

//Demonstrateslower_bound,upper_boundandequal_rangefor

//asortedsequenceofvalues.

#include<iostream>

#include<algorithm>

#include<vector>

usingnamespacestd;

intmain()

{程序運行輸出結(jié)果：

Vectorvcontains:

2244466668

Lowerboundof6iselement5ofvectorv

Upperboundof6iselement9ofvectorv

Usingequal_range:

Lowerboundof6iselement5ofvectorv

Upperboundof6iselement9ofvectorv

Uselower_boundtolocatethefirstpoint

atwhich5canbeinsertedinorder

Lowerboundof5iselement5ofvectorv

Useupper_boundtolocatethelastpoint

atwhich7canbeinsertedinorder

Upperboundof7iselement9ofvectorv

Useequal_rangetolocatethefirstand

lastpointatwhich5canbeinsertedinorder

Lowerboundof5iselement5ofvectorv

Upperboundof5iselement5ofvectorv16.9.12堆排序

堆排序算法將元素數(shù)組排列成特殊的二叉樹，稱為堆(heap)。堆的關(guān)鍵特性是最大元素總在堆的頂上，二叉樹中任何節(jié)點的子節(jié)點值總是小于或等該節(jié)點的值。堆排序算法通常在“數(shù)據(jù)結(jié)構(gòu)”或“算法”課程中有所介紹。在此，我們僅給出一范例程序，以展示STL堆排序算法的基本用法。

//Demonstratingpush_heap,pop_heap,make_heapandsort_heap.

#include<iostream>