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

第16章標(biāo)準(zhǔn)模板庫(kù)STL簡(jiǎn)介

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

16.1STL概述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

BiIter：雙向迭代器；

ForIter：前向迭代器；

InIter：輸入迭代器；

OutIter：輸出迭代器；

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

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

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

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

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

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

16.2容器類

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

16.3STL類的一般操作原理

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

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

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

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

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

因?yàn)関ector是一個(gè)動(dòng)態(tài)數(shù)組，所以可采用下標(biāo)運(yùn)算符對(duì)其元素進(jìn)行訪問。

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

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

16.4vector容器

用途最多的容器當(dāng)數(shù)vector類了。一個(gè)vector類的實(shí)例是一個(gè)動(dòng)態(tài)數(shù)組，該數(shù)組可根據(jù)需求自動(dòng)調(diào)整其大小。又因?yàn)関ector是一個(gè)數(shù)組，故我們可使用下標(biāo)運(yùn)算符對(duì)其元素進(jìn)行訪問。

vector類模板原型如下：

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

其中：模板參數(shù)T可為任何類型(基本類型或自定義類型)；Allocator為分配器類型，缺省值為標(biāo)準(zhǔn)分配器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)造一個(gè)空的vector對(duì)象；第(2)種形式構(gòu)造一個(gè)具有num個(gè)元素、值為val的vector對(duì)象，val的值可以取缺省值；第(3)種形式根據(jù)一個(gè)已有的vector對(duì)象拷貝構(gòu)造另一個(gè)同樣的vector對(duì)象；第(4)種形式構(gòu)造一個(gè)其元素限定在迭代器start和end所指定的范圍內(nèi)的vector對(duì)象。

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

vector<int>iv;

//創(chuàng)建一個(gè)長(zhǎng)度為0的int型vector對(duì)象iv

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

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

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

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

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

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

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

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

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

size=10

abcdefghij

Expandingvector

Sizenow=20

Currentcontents:

abcdefghijklmnopqrst

ModifiedContents:

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

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

下面我們?cè)俳o出一實(shí)例，以展示vector其它成員函數(shù)的使用方法。程序運(yùn)行輸出結(jié)果：

Vectorvcontains:123456

Firstelementofv:1

Lastelementofv:6

Contentsofvectorvafterchanges:722210456

Exception:invalidvector<T>subscript

Contentsofvectorvaftererase:22210456

Aftererase,vectorvisempty

Contentsofvectorvbeforeclear:123456

Afterclear,vectorvisempty16.4.3在vector中存儲(chǔ)自定義類型的對(duì)象

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

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

16.5list容器

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

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

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

其中，T為list中存儲(chǔ)的數(shù)據(jù)類型。分配器由Allocator指定，其默認(rèn)值為標(biāo)準(zhǔn)分配器。它具有如下構(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)造一個(gè)空的列表；第(2)種形式構(gòu)造一個(gè)含有num個(gè)元素、元素的值為val的列表，該值可以是默認(rèn)值；第(3)種形式構(gòu)造一個(gè)包含元素與ob相同的列表；第(4)種形式構(gòu)造一個(gè)包含的元素在迭代器start和end指定的范圍內(nèi)的列表。在list中過載了如下操作符：

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

因此兩個(gè)list對(duì)象可以用上述過載的操作符進(jìn)行比較運(yùn)算。

除過載了上述操作符外，list還定義了很多具有多種過載形式的成員函數(shù)。表16.4列出了一些常用的成員函數(shù)。程序運(yùn)行輸出結(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一樣亦可存儲(chǔ)自定義類型的對(duì)象，此時(shí)，自定義類型應(yīng)定義默認(rèn)的構(gòu)造函數(shù)，并且應(yīng)過載相應(yīng)的比較和賦值運(yùn)算符。

16.6deque雙向隊(duì)列

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

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

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

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

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

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

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

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

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

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

其中，Key為關(guān)鍵字的數(shù)據(jù)類型；T是被存儲(chǔ)(映射)的值的數(shù)據(jù)類型；Comp是對(duì)兩個(gè)關(guān)鍵字進(jìn)行比較的函數(shù)，它默認(rèn)為標(biāo)準(zhǔn)的less()函數(shù)對(duì)象；Allocator是分配器，默認(rèn)為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)造一個(gè)空的map；第(2)種形式是拷貝構(gòu)造函數(shù)；第(3)種形式是構(gòu)造一個(gè)其元素在迭代器start和end之間的map,由cmpfn指定的函數(shù)確定該映射的順序。正如前面所述，對(duì)于任何作為關(guān)鍵字的對(duì)象(自定義類型對(duì)象)，應(yīng)定義默認(rèn)的構(gòu)造函數(shù)，并應(yīng)過載相應(yīng)的關(guān)系與賦值運(yùn)算符。

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

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

另外，在map中還定義了多種類別的過載的成員函數(shù)以提供對(duì)map的操作，表16.5列出了一些常用的map成員函數(shù)。關(guān)鍵字-值對(duì)作為pair類型的對(duì)象存儲(chǔ)在一個(gè)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)造一個(gè)關(guān)鍵字-值對(duì)。make_pair的原型如下：

template<classKtype,classVtype>

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

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

#include<iostream>

#include<map>

usingnamespacestd;

intmain()

{

map<char,int>m;

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

Enterkey:A

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

一個(gè)set也可以被看成是一個(gè)map，只是它不是一個(gè)關(guān)鍵字-值對(duì)，它只有關(guān)鍵字，即值。一個(gè)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;

//無過載下標(biāo)操作符[]

｝；

set的大部分操作與map相同，它支持雙向迭代器。下面給出一實(shí)例，用以展示set的簡(jiǎn)單應(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;

}

程序運(yùn)行輸出結(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容?器?適?配?器

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

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

PoppingfromintDequeStack:9876543210

PoppingfromintVectorStack:9876543210

PoppingfromintListStack:987654321016.8.2queue適配器

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

cout<<endl;

return0;

}

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

Poppingfromvalues:3.29.85.416.8.3priority_queue適配器

priority_queue是一種其元素按優(yōu)先級(jí)排序的先進(jìn)先出隊(duì)列。它可由vector和dequeue實(shí)現(xiàn)，默認(rèn)情況下用vector實(shí)現(xiàn)。當(dāng)插入元素時(shí)，元素自動(dòng)按優(yōu)先級(jí)順序插入，取出元素時(shí)亦按優(yōu)先級(jí)的順序取出，即取出優(yōu)先最高的(值最大)元素。priority_queue的常規(guī)操作與queue相同。下面我們給出一實(shí)例來展示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;

}

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

Poppingfrompriorities:9.85.43.2

16.9算法

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

STL中定義了很多算法，表16.6為這些算法一覽表。STL中的所有算法都是函數(shù)模板，因此這些算法可應(yīng)用于任何類型的容器。STL算法的詳細(xì)內(nèi)容請(qǐng)參閱相關(guān)文獻(xià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++;

}程序運(yùn)行輸出結(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);程序運(yùn)行輸出結(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);程序運(yùn)行輸出結(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;程序運(yùn)行輸出結(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()

{程序運(yùn)行輸出結(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;

}

程序運(yùn)行輸出結(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;

}

程序運(yùn)行輸出結(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;

}程序運(yùn)行輸出結(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};程序運(yùn)行輸出結(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()

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

Vectorvcontains:

2244466668

Lowerboundof6iselement5ofvectorv

Upperboundof6iselement9ofvectorv

Usingequal_range:

Lowerboundof6iselement5ofvectorv

Upperboundof6iselement9ofvectorv

Uselower_boundtolocatethefirstpoint

atwhich5canbeinsertedinorder

Lowerboundof5iselement5ofvectorv

Useupper_boundtolocatethelastpoint

atwhich7canbeinsertedinorder

Upperboundof7iselement9ofvectorv

Useequal_rangetolocatethefirstand

lastpointatwhich5canbeinsertedinorder

Lowerboundof5iselement5ofvectorv

Upperboundof5iselement5ofvectorv16.9.12堆排序

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

//Demonstratingpush_heap,pop_heap,make_heapandsort_heap.

#include<iostream>