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