一個新標準的出現，對于熟習舊環境的工程師而言，總是有近鄉情怯之感。明知新標準一定比舊標準來的好，但對于舊標準總是有那么一點依依不舍，對新標準也總是有些許隔閡，雖然幾個月后就不這么想了。

 C++ STL程式庫的出現，對于習慣使用Borland C++等等程式庫的工程師而言，也有類似的感覺。有人說：C++就是把C語言那些令人既愛又恨的程式技巧，予以標準化，成為語言的一部份；STL則是把C++那些令人期待盼望的功能，予以公開化，讓大家不用花大錢買程式庫就可使用！而且使用STL，不必擔心日后程式碼會有大更動，因為畢竟這是ANSI C++的標準。所以本文將從STL概念上的基本原則出發，帶您在復雜的STL程式庫中找尋自己的認知天地

 如果您對STL起源與基本結構有興趣，可以參考上期STL的簡介，或是到下面這個WWW站參考一下最新資訊，里面有ANSI C++通過的最新STL版本等等資料。

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

STL對編譯器要求

 每當我們學習一個新的程式庫，通常第一個會問的，就是如何在我的編譯器上，寫一個簡單的程式，證明它可以跑。STL對編譯器的要求很嚴格，以最普遍的Borland C++ 4.5為例，Borland C++必須在程式碼前加一段：

#define __MINMAX_DEFINED

#pragma option -vi-

才可以跑程式，并且include的路徑也要設對。而微軟的Visual C++ 4.0因為不支援DOS模式下的程式，如果要簡化GUI的處理來使用STL，最簡單的方式便是在Console Application模式下寫程式，而且include的路徑也要設對，如此才可以跑。至于Visual C++2.x版本的編譯器，因為template機制做的不好，并不能編譯STL程式庫。值得注意的是，這里所說的「可以跑程式」，并不代表所有STL的功能都可以使用，因為C++ template機制過于復雜，可以有很多種變化，現今的編譯器技術無法正確的實作，所以現在用STL所寫的程式，日后或多或少還是需要修改，但已經比以往使用專屬程式庫改版時，需要做的修改來得少很多。

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

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

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

     圖一、STL的根本概念

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

  圖二、STL的五個部份[Nel95]

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

Container

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

template <class T>

class container {

/t T d;

};

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

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

循序式容器

循序式容器又可分成四種基本的容器類別，C語言指標中的記憶體（您可想象其為一個巨大的陣列）、vector（向量）、deque（雙向佇列）、list（串列），一個簡單的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物件便會正確的產生空間存放此型的物件。v.push_back(object)函數則把屬于該型別的物件存入容器物件的記憶空間中。

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

 start表示陣列起始處，finish表示陣列結束處，end_of_storage表示實際陣列結束的地方，如果陣列仍持續成長，超過end_of_storage，則vector容器會自動在配置一塊記憶體，維持注標值不超過邊界值。

 其他STL的基本容器簡介如下：

1.deque容器如同資料結構中的雙向佇列，單向佇列具有FIFO的性質，雙向佇列則更進一步可以由兩邊存入資料。

圖三、vector容器的記憶體結構

2.list容器為一個雙向串列，可以實作樹等資料結構。

3.C語言中的記憶體則為最傳統的容器物件，因為記憶體也可以儲存各種型態的物件，只要透過適當的C語言指標指向之即可。

關系式容器

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

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

 一個簡單使用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>為一個比較類別，目的在于如何在眾多物件中(string物件)，知道哪一個物件優先權高、哪一個低。而鍵物件是指“me”、“you”等字串，資料成員物件是指1、2、3、4等整數物件。

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

 關系式容器的功用還可加以擴大，如同資料庫程式對于關連式表格的應用，STL關系式容器可以很直覺地對應的關連式資料庫中的表格，再搭配下期將介紹的「擴充STL的Allocator物件」，便可使您的C++程式擁有簡單的永存機制(persistence)，成為物件導向資料庫系統(OODB)。

Iterator

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

 整個STL Iterator物件可以分為五類，如圖四：各種Iterator物件簡介如下：

Input

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

圖四、Iterator的種類

Output

輸出Iterator。負責輸出物件于指定的串列

流，如同檔案I/O。

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

Forward

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

Bidirectional

同Forward Iterator，并提供operator--()的功能。STL循序式容器物件皆支援此Iterator，可以說Bidirectional Iterator可操作的容器物件最多。但是，就是因為支援的容器物件較多，所以執行速度比Random Access Iterator慢。

Random Access

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

 圖三所以成金字塔型，因為支援最上層Random_Access_Iterator的容器物件與演算法物件最少；最下層的Input or Output Iterator，則幾乎所有的STL容器演算法物件都支援，應用范圍最為廣大。

 舉個程式如下：

// 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>容器在定義時給定其儲存int型別的物件，存入一些int物件后，我們想要瀏覽之。宣告deque<int>::iterator i，表示i為deque定義的Iterator，想象i為一個指標，游走于deque容器之中，如要取得容器內int物件值時，使用*i便可。q.begin()、q.end()為傳回deque容器的開始與結束的指標。

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

Algorithm與Function Object

 STL提供的演算法均是最基本的演算，如排序、收尋演算法等。演算法操作Iterator物件，再透過Iterator物件操作容器物件，便達到演算法與容器物件無關化。

 整個STL定義的演算法大致可分為七類，簡介如下：

Non-mutating sequence algorithms

此類演算法只適用于循序式容器，并且執行完后不會改變容器內的值。如find()、count()函數等。

Mutating sequence algorithms

此類演算法只適用于循序式容器，并且執行完后會改變容器內的值。如copy()、swap()、fill()函數等。

Sorting and searching algorithms

就如同其名字一樣，此類演算法執行排序與收尋的工作，只適用于循序式容器，因為關系式容器必定是排序好的，因此不需要此類函數。

Set operations

此類演算法適用于所有STL定義的容器物件，執行集合的運算，如set_union()、set_intersection()、set_difference()函數等。

Heap operations

此類演算法很像堆積資料結構中的運算，如push_heap()、pop_heap()函數等，與Adaptor容器物件很像，只是一個為資料結構定義其資料(Adaptor)；一個為資料結構定義其操作函數（如xx_heap()函數等）。

Numeric algorithms

此類演算法執行一般簡單的數值計算功能，如accumulate()、partial_sum()函數等。

Other functions

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

 以下我們以排序與收尋類的演算法為例，說明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;

}

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

tenplate <class RandomAccessIterator,class Compare> void sort(RandomAccessIterator first,RandomAccessIterator last,Compare comp);傳進兩個RandomAccessIterator類的Iterator后，與一個函數指標型別，sort函數自動幫您做排序，所用的演算法為qsort，平均排序時間為NlogN。

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

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

return a<b;

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

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

2.如此一來，my_comp函數才可以單純地執行return a<b;就可，

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

 上述三步驟，如果以執行效率來看，第一步驟與第三步驟由于可以采用C++的inline機制，做巨集展開，幾乎不會花執行時間。可是第二步驟雖然最單純，只有一道指令，但由于是以函數指標的方式傳進sort的函數內，透過函數指標執行此函數，執行時間自然比較慢；而且，我們必須為每一個型別（包括C++內建型別與自行定義的類別）做這個「小函數」，盡管它的功能如此簡單。

 STL針對這個問題，再次應用了template的技巧，來幫忙演算法物件執行低階的工作。如下：

// 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; }