【文章內(nèi)容簡(jiǎn)介】 一個(gè)功能強(qiáng)大的 STL 庫(kù)。 STL 的一個(gè)重大成就在于，它提供了相當(dāng)多的有用算法。它是在一個(gè)有效的框架中完成這些算法的。 STL 提供了大約 100 個(gè)實(shí)現(xiàn)算法的模板函數(shù)。熟悉了STL 之后，你就會(huì)發(fā)現(xiàn)：以前所寫(xiě)的許多 “有趣功能 ”的代碼現(xiàn)在只需要用短短幾行主能完全替換了。 “The Art of Computer Programming”書(shū)中強(qiáng)調(diào) 算法 + 數(shù)據(jù)結(jié)構(gòu) = 程序 在過(guò)去，一般來(lái)說(shuō)程序皆由算法加數(shù)據(jù)結(jié)構(gòu)，互相配合、一起工作，完成程序的功能。但如此一來(lái)便將數(shù)據(jù)結(jié)構(gòu)與算法綁再一起，不能分離，缺乏彈性。 Stepanov 先生便針對(duì)此問(wèn)題，采通用型設(shè)計(jì)的思維，使得程式師可以 ? 以效率高的算法解決問(wèn)題，此算法可處理各種數(shù)據(jù)結(jié)構(gòu)即算法與數(shù)據(jù)結(jié)構(gòu)互為獨(dú)立 ? 各種數(shù)據(jù)結(jié)構(gòu)使用一致的接口 (interface)，讓各種算法可以透過(guò)此接口處理各種數(shù)據(jù)結(jié)構(gòu) 如何做到這點(diǎn)？下面就簡(jiǎn)單介紹一下 STL 的組成。 STL 有五 個(gè)組成部分： 容器、迭代器、算法、適配器、函數(shù)對(duì)象 。 ? 容器 (container)－用來(lái)儲(chǔ)存其他物件 ? 迭代器 (iterator)－好比傳統(tǒng) C 語(yǔ)言的指針，可藉之來(lái)處理容器對(duì)象 ? 算法 (algorithm)－算法通過(guò)迭代器來(lái)操作容器對(duì)象 ? 適配器 (adaptor)－利用基礎(chǔ)容器對(duì)象，加以包裝，改變其接口，以適應(yīng)另一種需求 ? 函數(shù)對(duì)象 (function object)－為 STL 中較低階的對(duì)象，用來(lái)代替?zhèn)鹘y(tǒng)的 函數(shù)指針(function pointer) STL 的簡(jiǎn)單結(jié)構(gòu)可用下圖表示：其中容器類表示通常意義上的數(shù) 據(jù)結(jié)構(gòu)，和算法通過(guò)迭代器連接起來(lái)，做到上面的兩點(diǎn)。 實(shí)際上，為了做到數(shù)據(jù)結(jié)構(gòu)和算法之間的獨(dú)立并保持相當(dāng)?shù)撵`活性， STL 的實(shí)際結(jié)構(gòu)容 器類 (container) 算法 (Algotithms) Iterator 3 要比上圖表示復(fù)雜的多，下面給出 STL 的實(shí)際組成圖。 三、 STL 的應(yīng)用 標(biāo)準(zhǔn)的 C++庫(kù)包含一個(gè) INCLUDE 庫(kù)和一個(gè) LIB 庫(kù)。 Include 庫(kù)里的函數(shù)和類都是以源文件的形式給出的，用戶可以查看它的源代碼，而 LIB 庫(kù)中則以二進(jìn)制的形式給出。 STL都是以源碼的形式給出 的，各個(gè)編譯器有不同的版本。 VC++中的 STL 可讀性很差，變量和內(nèi)部函數(shù)名完全沒(méi)有真實(shí)意義，如果要看源碼的話建議看其他編譯器的版本。 在做題目的時(shí)候可以選用 VC++或 DEV C++，但是 VC++用的不是 g++內(nèi)核，而現(xiàn)在的JUDER一般都用 g++來(lái)編譯測(cè)試，所以從適應(yīng)比賽角度來(lái)說(shuō)用 DEV C++比較合適，它也用很好的編輯環(huán)境，而且比較小，容易存儲(chǔ)。不過(guò)如果嚴(yán)格按照標(biāo)準(zhǔn) C++的格式來(lái)編制程序的話，一般不會(huì)遇到因編譯器而出錯(cuò)的問(wèn)題。 現(xiàn)在大多數(shù)編譯器都包含新舊兩個(gè)版本的頭文件，舊版本的頭文件是以 .h 為擴(kuò)展名的，新版本的頭文件則不帶擴(kuò)展名，兩者都可以用記事本打開(kāi)來(lái)查看。例如在 C/C++中使用標(biāo)準(zhǔn)輸入輸出流為： include include 而使用新版頭文件則為： include iostream include stdio using namespace std。 上面的 using namespace std。一句是使用名字域 std，在 std聲明了所有 stl中的接口，在Algorithms Function Objects Adapter Iterators Containers STL 4 文件中聲明一次即可。此外，新舊文件的文件名不盡相同，例如 cmath，一般情況下名字不同時(shí)在原文件名前加 c 即可。 在介紹 STL 具體的數(shù)據(jù)結(jié)構(gòu)之前，我們必須先了解一種叫迭代器的結(jié)構(gòu)。用戶不必在意它的內(nèi)部實(shí)現(xiàn)，但在使用 STL 的時(shí)候卻無(wú)論如何都不能忽略它的存在。迭代器 (Iterator)可以看成是一種特殊的指針，即一個(gè)指針類，它包含一類對(duì)象的指針和可以對(duì)這種指針進(jìn)行的操作，也就是說(shuō)迭代器保存所操作的特定容器需要的狀態(tài)信息。例如一個(gè)數(shù)組 int array[N]的迭代器可以為 int *p＝ array，現(xiàn)在 p 指向的是數(shù)組的首地址，我們可以對(duì) p 進(jìn)行加減操作來(lái)改變它所指的元素，如： p++是將指針 p 的值直接加上整形的字長(zhǎng)而指向數(shù)組的下一個(gè)元素。但是對(duì)于鏈表來(lái)說(shuō)，如果 pit 是它的迭代器并且指向鏈表中的某個(gè)元素 T，如果要使 pit 指向鏈表的下一個(gè)元素則必須將 pit 內(nèi)部用于定位的指針指向 Tnext。其實(shí)我們可以像操作指針一樣方便的操作迭代器，所不同地就是迭代器的功能比較完善，限制了對(duì)一些特殊結(jié)構(gòu)類型的操作，包括隨機(jī)迭代器，順序迭代器 (重載 ++)，雙向迭代器 (重載 ++和)等。第一類容器提供成員函數(shù) begin()和 end()來(lái)返回容器的首尾迭代器。例如： include iostream include vector using namespace std。 vectorint vint。 int main() { int i。 for(i=0。i10。i++) (i)。 vectorint::iterator pit。 for(pit=()。pit!=()。pit++) cout(*pit)“ ” 。 return 0。 } 上述代碼只是讓讀者了解一下迭代器的 使用，我們將在以后詳細(xì)地介紹中具體地分析各個(gè)數(shù)據(jù)結(jié)構(gòu)迭代器的用法。 請(qǐng)看下面 STL 中的一段代碼： templateclass T, class U struct pair { typedef T first_type。 typedef U second_type T first。 U second。 pair()。 pair(const Tamp。 x, const Uamp。 y)。 templateclass V, class W pair(const pairV, Wamp。 pr)。 5 }。 STL 中最簡(jiǎn)單地?cái)?shù)據(jù)結(jié)構(gòu)應(yīng)屬于 utility中定義地 pairTYPE,TYPE,它包含兩個(gè)內(nèi)部變量 first,second，用來(lái)將兩個(gè)相關(guān)的數(shù)據(jù)配對(duì)，并重載了比較大小、判等、轉(zhuǎn)化等函數(shù)，使用它可以方便地實(shí)例化自己地結(jié)構(gòu)，如要建立一個(gè)坐標(biāo)的數(shù)據(jù)結(jié)構(gòu)則可以： include utility using namespace std。 typedef pairint,int POINT。 這樣在下邊的代碼中我們就可以使用 POINT 這個(gè)結(jié)構(gòu)了。如果要使用它的判斷函數(shù)，則所傳遞的類型必須已經(jīng)重載了比較運(yùn)算符或者使系統(tǒng)自定義類型。 例如： include iostream include utility using namespace std。 typedef pairint,int POINT。 int main() { POINT p1,p2。 cin。 if(p1==p2)cout“ Equal!”endl。 else cout“ Not Equal”endl。 return 0。 } 此外， utility 中還有一個(gè) pairT, U make_pair(const T amp。x, const U amp。y)函數(shù)，用來(lái)將兩個(gè)數(shù)據(jù)組成一個(gè) pair 對(duì)象返回。 C++標(biāo)準(zhǔn)模板庫(kù)提供三種順序容器： vector、 list 和 deque。 Vector 類和 deque 類都是基于數(shù)組的， list 類實(shí)現(xiàn)鏈表數(shù)據(jù)結(jié)構(gòu)。 【 vector類】 vector 類是一個(gè)線性數(shù)組類，內(nèi)部用線性空間來(lái)存放元素，內(nèi)部有兩個(gè)不同 的變量來(lái)標(biāo)識(shí)當(dāng)前元素個(gè)數(shù) _size 和當(dāng)前共分配的空間數(shù) _capacity，通常情況下 _size 要小于 _capacity，這樣當(dāng)在數(shù)組中添加元素時(shí)就不用每次都重新分配空間，從而提高了時(shí)間效率，直到分配的空間使用完時(shí)才重新分配。至于每次分配空間的大小則與數(shù)組元素的個(gè)數(shù)有關(guān)，可以用capacity()函數(shù)得到。 Vector 類元素最多一般可以為 1073741823 個(gè)。 Vector 類重載了下標(biāo)運(yùn)算符，可以像數(shù)組一樣訪問(wèn)容器中的元素，而且 vector 可以相互賦值，這是 C 語(yǔ)言的數(shù)組所不能實(shí)現(xiàn)的。 Vector 不進(jìn)行下標(biāo)檢查 ，但是它通過(guò)成員函數(shù) at 提供這個(gè)功能。使用 vector可以方便的實(shí)現(xiàn)線性多維數(shù)組。例如要分別建立坐標(biāo)的一維和二維數(shù)組： 6 include utility include vector using namespace std。 typedef pairint,intPOINT； typedef vectorPOINT Array1D。 typedef vectorvectorPOINT Array2D。 在上面我們定義了一維坐標(biāo)類 Array1D 和二維坐標(biāo)類 Array2D，值得注 意的是在定義Array2D 的時(shí)候，后面的尖括號(hào)中間要用空格隔開(kāi)，否則編譯器可能誤認(rèn)為是移位運(yùn)算符而報(bào)錯(cuò)。 Vector 類常用的接口如下： 函數(shù)名 返回值 參數(shù) 功能 at 元素的引用 要取元素的位置 (int pos) 如果該位置元素存在則返回它的引用，否則進(jìn)行一場(chǎng)處理 back 元素的引用 無(wú) 返回容器最后一個(gè)元素的引用，如果容器為空則出錯(cuò) begin 迭代器 無(wú) 取得元素的首迭代器 end 迭代器 無(wú) 取得元素的尾迭代器 clear 無(wú) 無(wú) 將容器清空 empty bool值 無(wú) 如果容器為空則 為真，否則為假 erase 迭代器 要?jiǎng)h除元素的迭代器 要?jiǎng)h除容器段的首尾迭代器 第一個(gè)版本刪除指定的元素 第二個(gè)版本刪除指定的容器段 不存在則出錯(cuò) front 元素的引用 無(wú) 返回首元素的引用，為空則出錯(cuò) insert 無(wú) iterator it, const Tamp。 x iterator it, const_iterator first, const_iterator last 在 it 這個(gè)位置插入元素 T 從 it 位置開(kāi)始，依次插入 first 到 last所指的元素 pop_back 無(wú) 無(wú) 刪除 最后一個(gè)元素 push_back 無(wú) const Tamp。 x 從最后插入一個(gè)元素 resize 無(wú) size_type n 將容器大小重設(shè)置為 n size int 無(wú) 返回容器中元素的個(gè)數(shù) 請(qǐng)看下面的實(shí)例程序： include iostream include vector using namespace std。 typedef vectorint Array1D。 7 typedef vectorvectorint Array2D。 int main() { int i,j。 Array1D sz。 for(i=0。i10。i++) (i)。 for(i=0。i10。i++) coutsz[i] 。 cout\n() ()endl。 (()+3)。 for(i=0。i()。i++) coutsz[i] 。 coutendl。 (()+2,()+5)。 for(i=0。i()。i++) coutsz[i] 。 coutendl。 ((),())。//()。 Array2D tw。 (5)。 for(i=0。i5。i++) tw[i].resize(5)。 for(i=0。i5。i++) for(j=0。j5。j++) tw[i][j]=i*5+j。 for(i=0。i()。i++) { for(j=0。jtw[i].size()。j++) couttw[i][j] 。 coutendl。 } system(PAUSE)。 //press any key to continue...... return 0。 } 對(duì)應(yīng)的輸 出應(yīng)當(dāng)為： 0 1 2 3 4 5 6 7 8 9 0 9 0 1 2 4 5 6 7 8 9 0 1 6 7 8 9 0 1 2 3 4 8 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 請(qǐng)按任意鍵繼續(xù) . . . 讀者對(duì)照輸出可體會(huì)各函數(shù)的用法 【 list 類】 lsit 順序容器提供在容器中任意位置進(jìn)行插入