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

第12章STL簡介12.1C++標(biāo)準(zhǔn)庫及其組成

12.2STL容器和迭代器簡介12.3STL通用算法簡介本章小結(jié)習(xí)題

STL(StandardTemplateLibrary，標(biāo)準(zhǔn)模板庫)是惠普實驗室開發(fā)的一系列軟件的統(tǒng)稱。它是由AlexanderStepanov、MengLee和DavidRMusser在惠普實驗室工作時所開發(fā)的?，F(xiàn)在雖說它主要出現(xiàn)在C++中，但在被引入C++之前該技術(shù)就已經(jīng)存在了很長一段時間。

STL的代碼從廣義上可分為三類：算法(Algorithm)、容器(Container)和迭代器(Iterator)。幾乎所有的代碼都采用了模板類和模板函數(shù)的方式，這相比于傳統(tǒng)的由函數(shù)和類組成的庫來說提供了更好的代碼重用機會。在C++標(biāo)準(zhǔn)中，STL被組織為13個頭文件，即<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack>和<utility>。12.1C++標(biāo)準(zhǔn)庫及其組成12.1.1C++標(biāo)準(zhǔn)庫

C++?標(biāo)準(zhǔn)可分為兩部分：C++?語言本身和C++?標(biāo)準(zhǔn)庫。其中C++?語言本身定義了C++語言的最基本要素，而C++?標(biāo)準(zhǔn)庫是利用C++?語言本身所定義的要素開發(fā)的一些具有特定功能的函數(shù)、類、對象等內(nèi)容。標(biāo)準(zhǔn)庫提供了標(biāo)準(zhǔn)的輸入/輸出、字符串、容器(如矢量、列表和映射等)、非數(shù)值運算(如排序、搜索和合并等)和對數(shù)值計算的支持。應(yīng)該說，C/C++包含了相對少的關(guān)鍵字，而且很多有用的函數(shù)都來源于庫。要使用C++?標(biāo)準(zhǔn)庫定義的內(nèi)容就需要包括定義這些內(nèi)容的頭文件。比如要想使用輸入/輸出就要包括頭文件iostream.h(C++?舊標(biāo)準(zhǔn))和iostream(C++?新標(biāo)準(zhǔn))。這里出現(xiàn)了兩個頭文件：iostream.h和iostream。在以前的C++?舊標(biāo)準(zhǔn)中將標(biāo)準(zhǔn)庫的內(nèi)容定義在全局作用域中，這樣如果用戶定義的函數(shù)、類、對象與標(biāo)準(zhǔn)庫中定義的同名就會產(chǎn)生沖突。為了解決這個問題，在C++?的新標(biāo)準(zhǔn)中，將所有標(biāo)準(zhǔn)庫中定義的內(nèi)容都放到了命名空間std中。但為了使利用舊標(biāo)準(zhǔn)編寫的程序仍然可以在新標(biāo)準(zhǔn)中運行，C++?新標(biāo)準(zhǔn)沒有在原來的頭文件中修改，而是將老版中的內(nèi)容放到了不帶?.h的文件中并加上了命名空間std。這樣就出現(xiàn)了文件帶.h的和不帶?.h的兩套頭文件。由于新標(biāo)準(zhǔn)中標(biāo)準(zhǔn)庫內(nèi)容的定義都放到了命名空間std中，因此我們?nèi)绻瞬粠?.h的頭文件就要使用命名空間std。引用命名空間可可以在程序開頭加上usingnamespacestd;語句，如程序12.1所示?？梢杂胹td和作用域運算符來引導(dǎo)標(biāo)準(zhǔn)庫中定義的內(nèi)容，如程序12.1所示。

【程序12.1】

#include<iostream>

usingnamespacestd;

intmain(intargc,char*argv[])

{ cout<<"要輸出的內(nèi)容"<<endl; return0;

}

【程序12.2】

#include<iostream>

intmain(intargc,char*argv[])

{ std::cout<<"要輸出的內(nèi)容"<<std::endl; return0;

}12.1.2標(biāo)準(zhǔn)庫的組成

C++?標(biāo)準(zhǔn)庫包含的內(nèi)容相當(dāng)豐富，它主要由以下六部分組成。

1．標(biāo)準(zhǔn)C庫

C++?是C的擴集，因此C++?標(biāo)準(zhǔn)庫也完全包含C標(biāo)準(zhǔn)庫。另外，在C++?新標(biāo)準(zhǔn)中對原來的標(biāo)準(zhǔn)C庫中的函數(shù)定義放到了命名空間std中，同時為使利用舊標(biāo)準(zhǔn)的C庫開發(fā)的程序能夠繼續(xù)編譯，新標(biāo)準(zhǔn)將原來的內(nèi)容放到新的頭文件中進行定義。這些新的頭文件名是在舊版C標(biāo)準(zhǔn)庫的頭文件前加上一個C并去掉?.h形成的。例如，在C語言中或舊版的C++?中要用到數(shù)學(xué)庫時可以加上預(yù)編譯命令#include<math.h>，而在C++?新標(biāo)準(zhǔn)中則使用以下語句：

#include<cmath>

usingnamespacestd;

2．輸入/輸出流這部分包括支持流緩沖區(qū)、格式化標(biāo)識符、操作運算符和文件格式等。這部分知識在第5章已經(jīng)介紹過了，這里不再贅述。

3．字符串類string在C++?標(biāo)準(zhǔn)庫中還提供了一個字符串類string。string的對象在大多數(shù)應(yīng)用中被用來取代char*指針的使用。string類提供了很多成員函數(shù)來對字符串進行操作。string類的主要成員函數(shù)如表12.1所示。

4．標(biāo)準(zhǔn)模板庫(STL)部分這部分就是本章所要學(xué)習(xí)的主要內(nèi)容。它主要包括三方面的內(nèi)容，即容器、迭代器和算法。表12.1string類的主要成員函數(shù)

5．工具部分

1997年，ANSIC++?委員會將以前只在部分C++?編譯器中實現(xiàn)的異常處理和命名空間的內(nèi)容納入到ANSIC++?標(biāo)準(zhǔn)中，并建議所有的C++?編譯器都能夠?qū)崿F(xiàn)這些功能。這些工具是非常有用的，應(yīng)該盡量使用這些工具。異常處理給我們提供了一種很好的處理邏輯錯誤的方法，使用它有助于提高程序的健壯性。C++?處理異常的機制主要由三部分組成，分別是檢查部分(try語句)、拋出部分(throw語句)和捕獲部分(catch語句)。命名空間是C++?新標(biāo)準(zhǔn)中引入的可以由用戶自己命名的作用域，主要用來處理程序中的命名沖突問題。例如，一個大的工程是由不同的程序員分別開發(fā)的，在最后將這些分別由不同程序員開發(fā)的代碼合并到一起時，很可能由于兩個不同的程序員定義了相同的代碼而使程序產(chǎn)生錯誤。利用命名空間，不同的程序員可以將自己申明的變量、類名等放到不同的命名空間中，這樣即使變量名相同，它們也在不同的命名空間中，也就是在不同的作用域中，也就不會產(chǎn)生沖突。

6．對國際化的支持部分采用locale和facet可以為程序提供眾多國際化支持，包括對各種字符集的支持、日期和時間的表示、數(shù)值和貨幣的處理等。12.2STL容器和迭代器簡介

STL是C++標(biāo)準(zhǔn)庫中很重要的一個組成部分，它是一些容器、迭代器和算法的組合。12.2.1STL容器在實際的開發(fā)過程中，數(shù)據(jù)結(jié)構(gòu)本身的重要性不遜于操作于數(shù)據(jù)結(jié)構(gòu)的算法的重要性，當(dāng)程序中存在著對時間要求很高的部分時，數(shù)據(jù)結(jié)構(gòu)的選擇就顯得更加重要。我們常常重復(fù)編寫一些代碼，這些代碼都十分相似，只是為了適應(yīng)不同數(shù)據(jù)的變化而在細(xì)節(jié)上有所出入。STL容器就為我們提供了這樣的方便，它允許我們重復(fù)利用已有的實現(xiàn)構(gòu)造自己的特定類型下的數(shù)據(jù)結(jié)構(gòu)，通過設(shè)置一些模板類，STL容器對最常用的數(shù)據(jù)結(jié)構(gòu)提供了支持，這些模板的參數(shù)允許我們指定容器中元素的數(shù)據(jù)類型，可以將許多重復(fù)而乏味的工作簡化。容器部分主要由頭文件<vector>、<list>、<deque>、<set>、<map>、<stack>和<queue>組成，它們分別對應(yīng)與其名字相對應(yīng)的數(shù)據(jù)結(jié)構(gòu)。由于篇幅所限，下面僅簡要介紹其中的一部分，其余部分可參照此部分使用。

1．向量類vector

vector是STL中提供的最簡單也是最常用的容器類模板之一，使用它可以代替數(shù)組的功能。它和數(shù)組一樣提供了對序列中元素的隨機訪問。和數(shù)組相比，它具有動態(tài)改變自身大小、在序列指定位置插入和刪除元素的功能。但由于在中間插入元素后需要將其后的元素后移，因此效率較低。

vector類的主要成員函數(shù)如表12.2所示。表12.2vector類的主要成員函數(shù)上表中，函數(shù)參數(shù)中的size_type就是unsingedint。STL中定義的類都是模板類，所以上面函數(shù)中的數(shù)據(jù)類型T為定義模板類時定義的通用數(shù)據(jù)類型。在具體定義vector對象時將一特定的數(shù)據(jù)類型傳送給T。程序12.3給出了一個使用vector計算斐波那契數(shù)列的例子。

【程序12.3】

#include<iostream>

#include<vector>

usingnamespacestd;

intmain()

{ vector<int>v_int; v_int.push_back(1); v_int.push_back(1); v_int.resize(10,0);

for(inti=2;i<10;i++) { v_int[i]=v_int[i-2]+v_int[i-1]; }

for(intj=0;j<10;j++) { cout<<v_int[j]<<""; }

return0;

}上面的程序中定義了一個保存int型元素的vector，使用vector比使用數(shù)組優(yōu)越的地方在于可以通過調(diào)用resize函數(shù)來根據(jù)要求動態(tài)地擴展vector的大小。

2．鏈表類list

list類封裝了標(biāo)準(zhǔn)雙向鏈表的所有操作，它不支持隨機訪問的數(shù)組類型。但由于list是以鏈表的方式實現(xiàn)的，因此list對象插入和刪除一個元素所需要的時間與該元素在鏈表中的位置無關(guān)。

list類的主要成員函數(shù)如表12.3所示。

list的許多函數(shù)與vector相似，但是它和vector在內(nèi)部實現(xiàn)上有很大的區(qū)別，vector內(nèi)部是以動態(tài)數(shù)組來實現(xiàn)的，所以它可以隨機訪問(反映在成員函數(shù)operator[]上)。而list內(nèi)部是以鏈表的形式來實現(xiàn)的，因此它不具有隨機訪問，但它的插入和刪除(無論是在兩端還是在中間)效率很高。

STL中還有很多其他的容器，如雙端隊列<deque>、集合<set>、映射<map>、棧<stack>等。它們的使用方法可參照vector和list，由于篇幅所限就不一一介紹了。表12.3

list類的主要成員函數(shù)12.2.2STL迭代器迭代器是STL算法和容器的粘合劑，是STL的核心。通過迭代器，容器與容器上執(zhí)行的算法之間無需彼此了解，這也是STL的優(yōu)秀思想所在。迭代器提供對一個容器中的對象的訪問方法。迭代器類似于指針。事實上，指針是迭代器的一種特例。可以像操縱指針那樣操縱迭代器；迭代器也可以像指針一樣指向序列中的一個元素，獲取它所指向的對向的值。一個容器可以生成一對迭代器來指定一個元素序列，而算法則對該序列進行操作。例如，對于上節(jié)中使用vector計算斐波那契數(shù)列的例子中除了可以用下標(biāo)來操作元素外，還可以用迭代器來操作，如程序12.4所示。

【程序12.4】

#include<iostream>

#include<vector>

usingnamespacestd;

intmain()

{ vector<int>v_int; v_int.push_back(1); v_int.push_back(1); v_int.resize(10,0);

vector<int>::iteratorit; //定義適用于vector<int>的迭代器

for(it=v_int.begin()+2;it!=v_int.end();it++) { *it=*(it-2)+*(it-1); }

for(it=v_int.begin();it!=v_int.end();it++) { cout<<*it<<""; } return0;

}從上例可以看出，迭代器就是一個廣義的指針，它給容器提供了統(tǒng)一的訪問方式。vector<int>::?iteratorit定義了一個適用于vector<int>類型的迭代器it，在for循環(huán)中用成員函數(shù)begin()的返回值來初始化它。這就如同定義一個整型指針并讓它指向一個整型數(shù)組的第一個元素一樣。it!=v_int.end()用來判斷迭代器是否指向了容器的最后一個元素之后的位置。it++?和指針?++?起到一樣的作用：使迭代器指向下一個元素。為了對比迭代器和指針的作用，下面將上例用數(shù)組和指針來實現(xiàn)，并盡量使這兩個程序具有相同的結(jié)構(gòu)。

【程序12.5】

#include<iostream>

usingnamespacestd;

intmain()

{ intarr_int[10]; arr_int[0]=arr_int[1]=1;

int*p; for(p=arr_int+2;p!=arr_int+10;p++)

{ *p=*(p-2)+*(p-1); }

for(p=arr_int;p!=arr_int+10;p++) { cout<<*p<<""; } return0;

}12.2.3綜合應(yīng)用：Josephus問題了解了STL的容器和迭代器的使用后，我們來看一個綜合使用容器和迭代器的例子——Josephus問題。

Josephus問題是，有m個小孩圍成一圈，任意假定一個數(shù)n，從第一個小孩起，按固定方向數(shù)，每數(shù)到第n個小孩時，該小孩便離開。小孩不斷離開，圈子不斷縮小。最后，剩下一個小孩便是勝利者。問題就是要求勝利的小孩是第幾個小孩。小孩圍成圈，所以此問題從邏輯上來看應(yīng)該將小孩的編號構(gòu)成一個環(huán)形鏈表，但STL沒有環(huán)形鏈表，只有一個雙向鏈表，我們可以改造這個雙向鏈表來模擬一個環(huán)形鏈表。改造的方法用一個迭代器來指示當(dāng)前數(shù)數(shù)的小孩。小孩每數(shù)一個數(shù)就相當(dāng)于迭代器后移(加1)。然后判斷只要迭代器的值等于鏈表的end()函數(shù)的值時就將迭代器的值改變?yōu)殒湵淼腷egin()函數(shù)的值。

Josephus問題的流程圖如圖12.1所示。具體程序代碼如程序12.6所示。圖12.1Josephus問題流程圖

【程序12.6】

#include<iostream>

#include<list>

usingnamespacestd;

intmain()

{

cout<<"請輸入小孩總數(shù)!!"<<endl;

intm; //接收小孩總數(shù)

cin>>m;

cout<<"請輸入間隔數(shù)!!"<<endl;

intn; //接收數(shù)數(shù)間隔

cin>>n;

list<int>li;

li.resize(m); //更改list大小等于小孩總數(shù)

list<int>::iteratorit; //定義迭代器

inti;

//初始化list的內(nèi)容為小孩編號(從1到m)

for(it=li.begin(),i=1;it!=li.end();it++,i++)

{

*it=i;

}

it=li.begin(); //初始化迭代器到list第一個元素

for(intj=0;j<m-1;j++) //共數(shù)數(shù)m-1輪，淘汰m-1個小孩

{

intk;

for(k=1;k<n;k++,it++) //開始數(shù)數(shù)

{ if(it==li.end()) //模擬環(huán)形鏈表

{ it=li.begin(); }

} if(it==li.end()) //判斷循環(huán)后是否是結(jié)束點

{ it=li.begin(); } it=li.erase(it);

//將要淘汰小孩對應(yīng)的節(jié)點清除

}

cout<<"勝出的小孩為:"<<*(li.begin())<<"號小孩!!"<<endl;

return0;

}運行結(jié)果如下：12.3STL通用算法簡介

STL中的通用算法庫是STL中最重要和最實用的技術(shù)之一。通用算法庫提供了大量的在實際編程中使用頻率很高的算法，這些算法都是以函數(shù)模板的形式提供的。同時這些算法大多都是作用在容器上的算法。在STL中提供的算法都是非常經(jīng)典的，我們可以在編程中直接使用來提高編程效率。12.3.1STL算法的結(jié)構(gòu)及常用算法對算法進行函數(shù)設(shè)計，有兩個主要的通用部分：

(1)它們都使用模板來提供通用類型；

(2)它們都用迭代器來提供訪問容器中數(shù)據(jù)的通用表示。

STL將算法庫分成四組：

(1)非修改式序列操作，如find()、for_each()等；

(2)修改式序列操作，如transform()、random_shuffle()、copy()等；

(3)排序和相關(guān)操作，如sort()等；

(4)通用數(shù)字運算。前三組在<algorithm>頭文件中描述，第四組是專用于數(shù)值數(shù)據(jù)的，有自己的頭文件<numeric>。其中常用的是前三組，它們提供的常用算法如表12.4所示。表12.4

STL常用算法12.3.2STL常用算法使用實例

1．查找算法find()

find()算法在頭文件<algorithm>中的定義如下所示：

template<classInIt,classT>

InItfind(InItfirst,InItlast,constT&val);這個模板函數(shù)中，InIt是一個迭代器，T代表迭代器中所存放的數(shù)據(jù)類型。由此可見，find()算法的作用是在短迭代器所指定的范圍內(nèi)查找與參數(shù)val所匹配的內(nèi)容，并返回與val匹配位置的迭代器。程序12.7為find()函數(shù)的用法。

【程序12.7】#include<algorithm>

#include<iostream>

usingnamespacestd;

intmain()

{

constintARRAY_SIZE=8; //數(shù)組大小

//數(shù)組初始化

intIntArray[ARRAY_SIZE]={1,2,3,4,4,5,6,7};

int*location;

inti;

intvalue=4;

//輸出數(shù)組

cout<<"IntArray{";

for(i=0;i<ARRAY_SIZE;i++)

cout<<IntArray[i]<<",";

cout<<"}"<<endl;

location=find(IntArray,IntArray+ARRAY_SIZE,value);

if(location!=IntArray+ARRAY_SIZE)//找到匹配元素

cout<<"Firstelementthatmatches"<<value

<<"isatlocation"<<location-IntArray<<endl;

else//沒有找到匹配元素

cout<<"Thesequencedoesnotcontainanyelements"

<<"withvalue"<<value<<endl;

return0;

}該程序中我們將find()算法用于一個數(shù)組，而且給find()傳遞的前兩個參數(shù)分別是數(shù)組元素的首地址和尾地址。我們知道find()算法的前兩個數(shù)需要兩個迭代器，前面提到迭代器就是廣義的指針，而指針是用來保存變量的地址的變量，所以通用算法中的迭代器變量也可以傳送數(shù)組中兩個元素的地址。這時通用算法所作用的區(qū)間就是這兩個地址之間的數(shù)據(jù)。其實數(shù)組就是最基本的容器，而指針或地址就是一種簡單的迭代器。以上程序輸出結(jié)果為：

IntArray{1,2,3,4,4,5,6,7}

Firstelementthatmatches4isatlocation3

2.條件查找算法find_if()

find_if()算法的函數(shù)原型為：

template<classInIt,classPred>

InItfind_if(InItfirst,InItlast,Predpr);

find_if()算法的功能是在容器迭代器first和last之間查找滿足函數(shù)對象pr條件的第一個元素。前兩個參數(shù)與find()算法的含義相同，第三個算法是一個函數(shù)對象。函數(shù)對象是一個類，它重載了函數(shù)調(diào)用操作符(operator())。該操作符封裝了通常應(yīng)該被實現(xiàn)為一個函數(shù)的動作。典型情況下，函數(shù)對象被作為實參傳遞給泛型算法，當(dāng)然也可定義獨立的對象。程序12.8為find_if()函數(shù)的用法。該實例中先構(gòu)造一個list，然后在list中查找第一個偶數(shù)并輸出。

【程序12.8】#include<algorithm>

#include<list>

#include<iostream>

usingnamespacestd;

//判斷是否偶數(shù)

intIsOdd(intn)

{

return!(n%2);

}

intmain()

{

constintSIZE=8;

intIntArray[SIZE]={7,8,3,4,4,5,6,7};

list<int>li(IntArray,IntArray+SIZE); list<int>::iteratorit; it=find_if(li.begin(),li.end(),IsOdd); if(it!li.end()) cout<<"容器中第一個偶數(shù)是:"<<*it<<endl; else cout<<"容器中沒有偶數(shù)"<<endl;

return0;

}上面的程序中傳給算法find_if()的第三個參數(shù)是一個函數(shù)名(函數(shù)指針)。當(dāng)然，該參數(shù)也可以是一個函數(shù)對象。由于篇幅有限，本章沒有詳細(xì)講解函數(shù)對象，有興趣的讀者可以查閱相關(guān)書籍。將上面的程序改為以函數(shù)對象來描述，如程序12.9所示。

【程序12.9】#include<algorithm>

#include<list>

#include<iostream>

usingnamespacestd;

//判斷是否偶數(shù)

classIsOdd

{

public: intoperator()(inti) { return!(i%2); }

};

intmain()

{

constintSIZE=8; intIntArray[SIZE]={7,8,3,4,4,5,6,7};

list<int>li(IntArray,IntArray+SIZE); list<int>::iteratorit; it=find_if(li.begin(),li.end(),IsOdd()); if(it!=li.end()) cout<<"容器中第一個偶數(shù)是:"<<*it<<endl; else cout<<"容器中沒有偶數(shù)"<<endl;

return0;

}

STL中查找類的通用算法還有很多，但用法都和find()算法及find_if()算法差不多，大家可以在學(xué)習(xí)的過程中參照上面的程序進行使用。3.排序算法sort()

sort()算法可以對一個容器中指定迭代器范圍內(nèi)的元素進行排序。它有以下兩個重載版本：

template<classRanIt>

voidsort(RanItfirst,RanItlast);

template<classRanIt,classPred>

voidsort(RanItfirst,RanItlast,Predpr);第一個版本默認(rèn)按升序進行排序，第二個可以指定一個函數(shù)對象來確定排序方式。程序12.10為利用sort()算法對數(shù)組中元素進行排序的實例。

【程序12.10】#include<algorithm>

#include<list>

#include<iostream>

usingnamespacestd;

intmain()

{

constintSIZE=8; intIntArray[SIZE]={7,8,3,4,4,5,6,7}; sort(IntArray,IntArray+SIZE);

for(inti=0;i<SIZE;i++) cout<<IntArray[i]<<","; cout<<endl;

return0;

}運行結(jié)果如下：如果要進行降序排序，則可加入用函數(shù)對象(或函數(shù)指針)調(diào)用sort()算法的第二個版本，其代碼如程序12.11所示。

【程序12.11】#include<algorithm>

#include<list>

#include<iostream>

usingnamespacestd;

//排序方式

intway(inta,intb)

{ returna>b;

}

intmain()

{

constintSIZE=8; intIntArray[SIZE]={7,8,3,4,4,5,6,7};

sort(IntArray,IntArray+SIZE,way); for(inti=0;i<SIZE;i++) cout<<IntArray[i]<<","; cout<<endl;

return0;

}

4．替換算法replace()

replace()算法的函數(shù)原型為：

template<caassFwdIt,classT>

voidreplace(FwdItfirst,FwdItlast,constT&vold,constT&vnew);

replace算法對容器中指定迭代器范圍內(nèi)的內(nèi)容進行查找替換。前兩個參數(shù)是兩個迭代器，用來指定操作的容器的范圍。第三個參數(shù)為容器指定范圍內(nèi)要被替換的內(nèi)容。第四個參數(shù)指定替換后的內(nèi)容。程序12.12為replace()算法實例。本實例實現(xiàn)對字符串鏈表中的內(nèi)容進行查找替換。

【