一個(gè)新標(biāo)準(zhǔn)的出現(xiàn)，對(duì)于熟習(xí)舊環(huán)境的工程師而言，總是有近鄉(xiāng)情怯之感。明知新標(biāo)準(zhǔn)一定比舊標(biāo)準(zhǔn)來(lái)的好，但對(duì)于舊標(biāo)準(zhǔn)總是有那么一點(diǎn)依依不舍，對(duì)新標(biāo)準(zhǔn)也總是有些許隔閡，雖然幾個(gè)月后就不這么想了。

 C++ STL程式庫(kù)的出現(xiàn)，對(duì)于習(xí)慣使用Borland C++等等程式庫(kù)的工程師而言，也有類(lèi)似的感覺(jué)。有人說(shuō)：C++就是把C語(yǔ)言那些令人既愛(ài)又恨的程式技巧，予以標(biāo)準(zhǔn)化，成為語(yǔ)言的一部份；STL則是把C++那些令人期待盼望的功能，予以公開(kāi)化，讓大家不用花大錢(qián)買(mǎi)程式庫(kù)就可使用！而且使用STL，不必?fù)?dān)心日后程式碼會(huì)有大更動(dòng)，因?yàn)楫吘惯@是ANSI C++的標(biāo)準(zhǔn)。所以本文將從STL概念上的基本原則出發(fā)，帶您在復(fù)雜的STL程式庫(kù)中找尋自己的認(rèn)知天地

 如果您對(duì)STL起源與基本結(jié)構(gòu)有興趣，可以參考上期STL的簡(jiǎn)介，或是到下面這個(gè)WWW站參考一下最新資訊，里面有ANSI C++通過(guò)的最新STL版本等等資料。

http://www.cs.rpi.edu/~musser/stl.html

STL對(duì)編譯器要求

 每當(dāng)我們學(xué)習(xí)一個(gè)新的程式庫(kù)，通常第一個(gè)會(huì)問(wèn)的，就是如何在我的編譯器上，寫(xiě)一個(gè)簡(jiǎn)單的程式，證明它可以跑。STL對(duì)編譯器的要求很?chē)?yán)格，以最普遍的Borland C++ 4.5為例，Borland C++必須在程式碼前加一段：

#define __MINMAX_DEFINED

#pragma option -vi-

才可以跑程式，并且include的路徑也要設(shè)對(duì)。而微軟的Visual C++ 4.0因?yàn)椴恢г瓺OS模式下的程式，如果要簡(jiǎn)化GUI的處理來(lái)使用STL，最簡(jiǎn)單的方式便是在Console Application模式下寫(xiě)程式，而且include的路徑也要設(shè)對(duì)，如此才可以跑。至于Visual C++2.x版本的編譯器，因?yàn)閠emplate機(jī)制做的不好，并不能編譯STL程式庫(kù)。值得注意的是，這里所說(shuō)的「可以跑程式」，并不代表所有STL的功能都可以使用，因?yàn)镃++ template機(jī)制過(guò)于復(fù)雜，可以有很多種變化，現(xiàn)今的編譯器技術(shù)無(wú)法正確的實(shí)作，所以現(xiàn)在用STL所寫(xiě)的程式，日后或多或少還是需要修改，但已經(jīng)比以往使用專(zhuān)屬程式庫(kù)改版時(shí)，需要做的修改來(lái)得少很多。

STL的基本概念：Container,Iterator,Algorithm

 在學(xué)習(xí)STL之前，讓我們介紹STL最基本的概念，如圖一：演算法物件透過(guò)Iterator操作各種容器物件，完成運(yùn)算。而除了基本的演算法由STL內(nèi)建提供外，工程師可以自己定義一些新的輔助演算法（help function，或稱輔助函數(shù)），來(lái)完成新的計(jì)算。這些新的輔助演算法，通常是利用C++的template function的方式設(shè)計(jì)。您可能會(huì)問(wèn)，依照OO理論對(duì)于物件的定義，為什么稱STL的演算法物件為「物件」，它其實(shí)只是函數(shù)而已？答案是：因?yàn)镃++中的函數(shù)名稱事實(shí)上也是一種型別，利用typedef可將之宣告成指向函數(shù)指標(biāo)的型別，所以當(dāng)我們以C++中的型別為準(zhǔn)，enum、union、struct、typedef等等關(guān)鍵字都可看做是一種類(lèi)別的變形宣告，也因此可以把單一函數(shù)看做是物件（沒(méi)有資料成員的物件）。

 圖一左邊的容器物件，STL則定義三個(gè)最基本也最常用到的的容器物件：vector,deque,list。而其他各種資料結(jié)構(gòu)教科書(shū)上定義的特定資料結(jié)構(gòu)，如stack, heap, binary tree等等，都可以再利用這三個(gè)基本的容器，加以變化，實(shí)作之。基本上，圖一左邊的物件，STL利用C++的template class制作。

     圖一、STL的根本概念

 所以有些人（如[Nel95]書(shū)）就把STL的功能分成五大部份，掌管圖一從左至右大大小小的事情，如圖二：

  圖二、STL的五個(gè)部份[Nel95]

 演算法物件，Iterator物件，容器物件仍在，STL的Adaptor物件包裝了由基本容器物件所產(chǎn)生的變形資料結(jié)構(gòu)，如stack,queue,priority_queue等；Function物件則輔助演算法物件完成一些更為基本的運(yùn)算，如比較大小等。以下，我們將以圖一的原則審視STL的各組成部份。

Container

 Container顧名思義，就是一種容器，里頭可以裝各式各樣的物件。如下，

template <class T>

class container {

/t T d;

};

透過(guò)template<class T>，T可表示任意物件所屬的類(lèi)別，于是在容器類(lèi)別內(nèi)產(chǎn)生一個(gè)T類(lèi)別的物件d。由于T可以表示各種資料型別，不管是C++內(nèi)建的基本資料型別或是利用class定義的類(lèi)別，都可以存入STL的容器物件中。

 STL將容器物件分為兩種，循序式容器(Sequence Container)與關(guān)系式容器(Associate Container)。循序式容器內(nèi)的每一個(gè)元素，只能包含一種物件，且各元素的排列順序完全依照元素插入時(shí)的順序。關(guān)系式容器內(nèi)的每一個(gè)元素，則包含兩種物件，一個(gè)為鍵物件(key object)；一個(gè)為值物件(value object)，且各元素的排列順序完全依照鍵物件決定。

循序式容器

循序式容器又可分成四種基本的容器類(lèi)別，C語(yǔ)言指標(biāo)中的記憶體（您可想象其為一個(gè)巨大的陣列）、vector（向量）、deque（雙向佇列）、list（串列），一個(gè)簡(jiǎn)單的vector容器使用如下：

// test program for vector container

#include <iostream.h>

#include <vector.h>

void main() {

/t vector<char*> v;

/t v.push_back("me");

/t v.push_back("you");

/t v.push_back("he");

/t v.push_back("she");

/t for(int i=0;i<4;i++)

/t/t   cout<<v<<"";

}

//end程式輸出

me

you

he

she

 vector<data_type>表示我們可以放入各種資料型別到<...>之中，vector物件便會(huì)正確的產(chǎn)生空間存放此型的物件。v.push_back(object)函數(shù)則把屬于該型別的物件存入容器物件的記憶空間中。

 一個(gè)vector容器好比一個(gè)傳統(tǒng)C語(yǔ)言中的陣列，只是傳統(tǒng)C語(yǔ)言中的陣列必須明確地指出陣列大小，如果注標(biāo)值超過(guò)邊界值，則系統(tǒng)將得到一個(gè)未知的錯(cuò)誤。然而，STL的vector容器卻不然，vector容器自己視需要，自動(dòng)加大陣列的大小，所以應(yīng)用程式就不需擔(dān)心注標(biāo)值超過(guò)陣列范圍。圖示如三。

 start表示陣列起始處，finish表示陣列結(jié)束處，end_of_storage表示實(shí)際陣列結(jié)束的地方，如果陣列仍持續(xù)成長(zhǎng)，超過(guò)end_of_storage，則vector容器會(huì)自動(dòng)在配置一塊記憶體，維持注標(biāo)值不超過(guò)邊界值。

 其他STL的基本容器簡(jiǎn)介如下：

1.deque容器如同資料結(jié)構(gòu)中的雙向佇列，單向佇列具有FIFO的性質(zhì)，雙向佇列則更進(jìn)一步可以由兩邊存入資料。

圖三、vector容器的記憶體結(jié)構(gòu)

2.list容器為一個(gè)雙向串列，可以實(shí)作樹(shù)等資料結(jié)構(gòu)。

3.C語(yǔ)言中的記憶體則為最傳統(tǒng)的容器物件，因?yàn)橛洃涹w也可以儲(chǔ)存各種型態(tài)的物件，只要透過(guò)適當(dāng)?shù)腃語(yǔ)言指標(biāo)指向之即可。

關(guān)系式容器

 關(guān)系式容器，STL共定義了set<Key>、multiset<Key>、map<Key,T>、multimap<Key,T>四種容器物件，其主要特色為：「物件帶有關(guān)鍵值」。每種容器的特色如下：

 關(guān)系式容器讓C++程式可以處理關(guān)系式資料。關(guān)系式資料是指一組資料由鍵值與資料成員所組成。如同資料庫(kù)對(duì)資料表格的定義，STL的關(guān)系式容器中的鍵值可以選擇是否重復(fù)，不可重復(fù)的關(guān)系式容器好比數(shù)學(xué)中的集合概念，集合內(nèi)的資料皆是唯一性的。由于這些容器在存入資料成員時(shí)都會(huì)把新的資料成員依鍵值做排序，所以您可想象成好比一個(gè)有序的表或集合，甚至關(guān)系式容器也容許資料成員是空的，容器只儲(chǔ)存鍵值，并做排序而已。

 一個(gè)簡(jiǎn)單使用map容器的程式如下：

//work for Borland C++ only

#include <iostream.h>

#include <iomanip.h>

#include <cstring.h>

#include <map.h>

void main() {

/t map<string,int,less<string>> m;

/t m["me"]=1;

/t m["you"]=2;

/t m["he"]=3;

/t m["she"]=4;

/t cout<<setw(3)<<m["she"]<<setw(3)<<m["he"]<<setw(3)

/t/t   <<setw(3)<<m["you"]<<setw(3)<<m["me"];

}

//程式輸出

 4  3  2  1

 less<string>為一個(gè)比較類(lèi)別，目的在于如何在眾多物件中(string物件)，知道哪一個(gè)物件優(yōu)先權(quán)高、哪一個(gè)低。而鍵物件是指“me”、“you”等字串，資料成員物件是指1、2、3、4等整數(shù)物件。

 由上表，我們知道關(guān)系式容器的每個(gè)元素最多可含兩種物件。只含有鍵物件的統(tǒng)稱set類(lèi)物件；含有鍵物件與值物件的統(tǒng)稱map類(lèi)物件。而每類(lèi)物件又可依其是否可含重復(fù)鍵，分成single物件與multi物件。這些物件事實(shí)上都是資料結(jié)構(gòu)中的樹(shù)狀結(jié)構(gòu)。每個(gè)容器在存入物件時(shí)，便依鍵物件的大小決定它在樹(shù)中的位置。而less<string>是后段提到的Function物件，在此先略過(guò)不談。

 關(guān)系式容器的功用還可加以擴(kuò)大，如同資料庫(kù)程式對(duì)于關(guān)連式表格的應(yīng)用，STL關(guān)系式容器可以很直覺(jué)地對(duì)應(yīng)的關(guān)連式資料庫(kù)中的表格，再搭配下期將介紹的「擴(kuò)充STL的Allocator物件」，便可使您的C++程式擁有簡(jiǎn)單的永存機(jī)制(persistence)，成為物件導(dǎo)向資料庫(kù)系統(tǒng)(OODB)。

Iterator

 Iterator物件之于容器物件，好比指標(biāo)之于記憶體。外部程式透過(guò)Iterator，可以在不知容器物件內(nèi)部情況之下，操作容器物件，進(jìn)而控制容器內(nèi)裝的物件，參考圖一。STL很多地方均倚賴Iterator才能實(shí)現(xiàn)「效率」與「泛型」兩個(gè)主要目標(biāo)。使用Iterator后，演算法可以實(shí)作于各種物件、各種容器之上，只要該容器提供相對(duì)應(yīng)的Iterator物件即可。

 整個(gè)STL Iterator物件可以分為五類(lèi)，如圖四：各種Iterator物件簡(jiǎn)介如下：

Input

輸入Iterator。負(fù)責(zé)從指定串列流讀入資料，如同檔案I/O般。

圖四、Iterator的種類(lèi)

Output

輸出Iterator。負(fù)責(zé)輸出物件于指定的串列

流，如同檔案I/O。

以上兩個(gè)Iterator只是單純地負(fù)責(zé)物件輸入與輸出的工作，在整個(gè)Iterator階層中顯得較不重要。

Forward

如同C的指標(biāo)，具有operator*()的功能，并限制Iterator進(jìn)行的方向永遠(yuǎn)往前（就是提供operator++()的功能），不能跳格。為最有用的Iterator。

Bidirectional

同F(xiàn)orward Iterator，并提供operator--()的功能。STL循序式容器物件皆支援此Iterator，可以說(shuō)Bidirectional Iterator可操作的容器物件最多。但是，就是因?yàn)橹г娜萜魑锛^多，所以執(zhí)行速度比Random Access Iterator慢。

Random Access

最強(qiáng)大的Iterator，幾乎與真實(shí)的指標(biāo)一樣，也提供operator[]()的功能，但支援的容器物件只有vector容器物件與deque容器物件而已，list容器物件只支援Bidirectional Iterator。

 圖三所以成金字塔型，因?yàn)橹г钌蠈覴andom_Access_Iterator的容器物件與演算法物件最少；最下層的Input or Output Iterator，則幾乎所有的STL容器演算法物件都支援，應(yīng)用范圍最為廣大。

 舉個(gè)程式如下：

// test program for iterator

#include <iostream.h>

#include <deque.h>

void main() {

/t deque<int> q;

/t q.push_back(1);

/t q.push_back(2);

/t q.push_back(3);

/t q.push_back(4);

/t for(deque<int>::iterator i=q.begin();

/t/t   i != q.end(); i++)

/t/t   cout<<*i<<endl;

}

 deque<int>容器在定義時(shí)給定其儲(chǔ)存int型別的物件，存入一些int物件后，我們想要瀏覽之。宣告deque<int>::iterator i，表示i為deque定義的Iterator，想象i為一個(gè)指標(biāo)，游走于deque容器之中，如要取得容器內(nèi)int物件值時(shí)，使用*i便可。q.begin()、q.end()為傳回deque容器的開(kāi)始與結(jié)束的指標(biāo)。

 到此，體會(huì)一下演算法物件如何透過(guò)Iterator操作容器物件。您可想象這里的for回圈為演算法物件，只要輸入q.begin()、q.end()便可完成將容器內(nèi)之值輸出的工作。以下，我們正式介紹演算法物件。

Algorithm與Function Object

 STL提供的演算法均是最基本的演算，如排序、收尋演算法等。演算法操作Iterator物件，再透過(guò)Iterator物件操作容器物件，便達(dá)到演算法與容器物件無(wú)關(guān)化。

 整個(gè)STL定義的演算法大致可分為七類(lèi)，簡(jiǎn)介如下：

Non-mutating sequence algorithms

此類(lèi)演算法只適用于循序式容器，并且執(zhí)行完后不會(huì)改變?nèi)萜鲀?nèi)的值。如find()、count()函數(shù)等。

Mutating sequence algorithms

此類(lèi)演算法只適用于循序式容器，并且執(zhí)行完后會(huì)改變?nèi)萜鲀?nèi)的值。如copy()、swap()、fill()函數(shù)等。

Sorting and searching algorithms

就如同其名字一樣，此類(lèi)演算法執(zhí)行排序與收尋的工作，只適用于循序式容器，因?yàn)殛P(guān)系式容器必定是排序好的，因此不需要此類(lèi)函數(shù)。

Set operations

此類(lèi)演算法適用于所有STL定義的容器物件，執(zhí)行集合的運(yùn)算，如set_union()、set_intersection()、set_difference()函數(shù)等。

Heap operations

此類(lèi)演算法很像堆積資料結(jié)構(gòu)中的運(yùn)算，如push_heap()、pop_heap()函數(shù)等，與Adaptor容器物件很像，只是一個(gè)為資料結(jié)構(gòu)定義其資料(Adaptor)；一個(gè)為資料結(jié)構(gòu)定義其操作函數(shù)（如xx_heap()函數(shù)等）。

Numeric algorithms

此類(lèi)演算法執(zhí)行一般簡(jiǎn)單的數(shù)值計(jì)算功能，如accumulate()、partial_sum()函數(shù)等。

Other functions

不屬于上面分類(lèi)的其他演算法，如min()、max()函數(shù)等。

 以下我們以排序與收尋類(lèi)的演算法為例，說(shuō)明STL中的演算法物件如何與Iterator和容器物件互相工作。

// test program for sort algorithm

#include <stdlib.h>

#include <iostream.h>

#include <algo.h>

#include <vector.h>

class INT {

public:

/t INT() {}

/t INT(int a) { d=a; }

/t INT(const INT& a) { d=a.d; }

/t INT& operator=(const INT& a) { d=a.d;return *this; }

/t int operator<(const INT& a) { return d<a.d; }

/t operator int() const  { return d; }

/t int d;   };

int my_comp(const INT& a,const INT& b) {

/t return a< b;   }

void main() {

/t int i;

/t vector<INT> v;

/t cout<<"The original vector...";

/t for(i=0;i<10;i++) {

/t/t   v.push_back(rand());

/t/t   cout<<v<<" ";

/t }

/t sort(v.begin(),v.end(),my_comp);

/t cout<<"After sorting ...";

/t for(i=0;i<10;i++)

/t/t   cout<<v<<" ";

/t cout<<endl;

}

   宣告一個(gè)vector<INT>表示容器物件，10個(gè)元素值，而sort函數(shù)的原型如下：

tenplate <class RandomAccessIterator,class Compare> void sort(RandomAccessIterator first,RandomAccessIterator last,Compare comp);傳進(jìn)兩個(gè)RandomAccessIterator類(lèi)的Iterator后，與一個(gè)函數(shù)指標(biāo)型別，sort函數(shù)自動(dòng)幫您做排序，所用的演算法為qsort，平均排序時(shí)間為NlogN。

 您可發(fā)現(xiàn)，STL所定義的演算法物件幾乎都以template function出現(xiàn)，輸入的參數(shù)則是Iterator類(lèi)的物件，從函數(shù)原型上更可看出「泛型化程式庫(kù)」的精神，演算法以抽象概念操作各種型態(tài)的物件。

 不過(guò)，對(duì)于int my_comp(INT&,INT&)函數(shù)，在sort演算法物件中對(duì)應(yīng)的宣告為template <class Compare comp>，sort內(nèi)的定義則使用comp(*first,*last)來(lái)執(zhí)行此函數(shù)的功能。可以想見(jiàn)，今天我們定義一個(gè)INT型態(tài)的物件，需要一個(gè)比較INT物件大小的函數(shù)（如本例中的my_comp），如果以后定義一個(gè)X型別的物件，也必須為其定義一個(gè)比較大小的函數(shù)，而這個(gè)函數(shù)竟然只是執(zhí)行一道指令：

return a<b;

它依靠X物件對(duì)于操作元<的過(guò)荷定義，呼叫X物件的operator<(X& x)函數(shù)完成實(shí)際功能，從這牽扯到三個(gè)步驟：

1.X物件必須為operator<()函數(shù)做定義，

2.如此一來(lái)，my_comp函數(shù)才可以單純地執(zhí)行return a<b;就可，

3.在sort演算法物件內(nèi)，才可以簡(jiǎn)單地呼叫comp(*first,*last)，知道誰(shuí)大誰(shuí)小。

 上述三步驟，如果以執(zhí)行效率來(lái)看，第一步驟與第三步驟由于可以采用C++的inline機(jī)制，做巨集展開(kāi)，幾乎不會(huì)花執(zhí)行時(shí)間?？墒堑诙襟E雖然最單純，只有一道指令，但由于是以函數(shù)指標(biāo)的方式傳進(jìn)sort的函數(shù)內(nèi)，透過(guò)函數(shù)指標(biāo)執(zhí)行此函數(shù)，執(zhí)行時(shí)間自然比較慢；而且，我們必須為每一個(gè)型別（包括C++內(nèi)建型別與自行定義的類(lèi)別）做這個(gè)「小函數(shù)」，盡管它的功能如此簡(jiǎn)單。

 STL針對(duì)這個(gè)問(wèn)題，再次應(yīng)用了template的技巧，來(lái)幫忙演算法物件執(zhí)行低階的工作。如下：

// test program for Function Object

#include <stdio.h>

#include <stdlib.h>

#include <iostream.h>

#include <vector.h>

#include <algo.h>

#include <function.h>

class INT {

public:

/t INT() {}

/t INT(int a) { d=a; }

/t INT(const INT& a) { d=a.d; }

/t INT& operator=(const INT& a) { d=a.d;return *this; }