一個新標準的出現，對于熟習舊環境的工程師而言，總是有近鄉情怯之感。明知新標準一定比舊標準來的好，但對于舊標準總是有那么一點依依不舍，對新標準也總是有些許隔閡，雖然幾個月后就不這么想了。 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 container { T d; }; 透過template，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 #include void main() { vector v; v.push_back("me"); v.push_back("you"); v.push_back("he"); v.push_back("she"); for(int i=0;i<4;i++) cout< } //end程式輸出 me you he she vector表示我們可以放入各種資料型別到<...>之中，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、multiset、map、multimap四種容器物件，其主要特色為：「物件帶有關鍵值」。每種容器的特色如下：
Key可重復嗎？
容器有資料成員嗎
set
否
否
multiset
是
否
map
否
是
multiset
是
是
關系式容器讓C++程式可以處理關系式資料。關系式資料是指一組資料由鍵值與資料成員所組成。如同資料庫對資料表格的定義，STL的關系式容器中的鍵值可以選擇是否重復，不可重復的關系式容器好比數學中的集合概念，集合內的資料皆是唯一性的。由于這些容器在存入資料成員時都會把新的資料成員依鍵值做排序，所以您可想象成好比一個有序的表或集合，甚至關系式容器也容許資料成員是空的，容器只儲存鍵值，并做排序而已。 一個簡單使用map容器的程式如下： //work for Borland C++ only #include #include #include #include void main() { map> m; m["me"]=1; m["you"]=2; m["he"]=3; m["she"]=4; cout< < } //程式輸出 4 3 2 1 less為一個比較類別，目的在于如何在眾多物件中(string物件)，知道哪一個物件優先權高、哪一個低。而鍵物件是指“me”、“you”等字串，資料成員物件是指1、2、3、4等整數物件。 由上表，我們知道關系式容器的每個元素最多可含兩種物件。只含有鍵物件的統稱set類物件；含有鍵物件與值物件的統稱map類物件。而每類物件又可依其是否可含重復鍵，分成single物件與multi物件。這些物件事實上都是資料結構中的樹狀結構。每個容器在存入物件時，便依鍵物件的大小決定它在樹中的位置。而less是后段提到的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 Aclearcase/" target="_blank" >ccess Iterator慢。 Random Access
最強大的Iterator，幾乎與真實的指標一樣，也提供operator[]()的功能，但支援的容器物件只有vector容器物件與deque容器物件而已，list容器物件只支援Bidirectional Iterator。 圖三所以成金字塔型，因為支援最上層Random_Access_Iterator的容器物件與演算法物件最少；最下層的Input or Output Iterator，則幾乎所有的STL容器演算法物件都支援，應用范圍最為廣大。 舉個程式如下： // test program for iterator #include #include void main() { deque q; q.push_back(1); q.push_back(2); q.push_back(3); q.push_back(4); for(deque::iterator i=q.begin(); i != q.end(); i++) cout<<*i< } deque容器在定義時給定其儲存int型別的物件，存入一些int物件后，我們想要瀏覽之。宣告deque::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 #include #include #include class INT { public: INT() {} INT(int a) { d=a; } INT(const INT& a) { d=a.d; } INT& operator=(const INT& a) { d=a.d;return *this; } int operator<(const INT& a) { return d operator int() const { return d; } int d; }; int my_comp(const INT& a,const INT& b) { return a< b; } void main() { int i; vector v; cout<<"The original vector...\n"; for(i=0;i<10;i++) { v.push_back(rand()); cout<} sort(v.begin(),v.end(),my_comp); cout<<"\nAfter sorting ...\n"; for(i=0;i<10;i++) cout<cout< } 宣告一個vector表示容器物件，10個元素值，而sort函數的原型如下： tenplate void sort(RandomAccessIterator first,RandomAccessIterator last,Compare comp);傳進兩個RandomAccessIterator類的Iterator后，與一個函數指標型別，sort函數自動幫您做排序，所用的演算法為qsort，平均排序時間為NlogN。 您可發現，STL所定義的演算法物件幾乎都以template function出現，輸入的參數則是Iterator類的物件，從函數原型上更可看出「泛型化程式庫」的精神，演算法以抽象概念操作各種型態的物件。 不過，對于int my_comp(INT&,INT&)函數，在sort演算法物件中對應的宣告為template ，sort內的定義則使用comp(*first,*last)來執行此函數的功能?？梢韵胍?，今天我們定義一個INT型態的物件，需要一個比較INT物件大小的函數（如本例中的my_comp），如果以后定義一個X型別的物件，也必須為其定義一個比較大小的函數，而這個函數竟然只是執行一道指令： return a 它依靠X物件對于操作元<的過荷定義，呼叫X物件的operator<(X& x)函數完成實際功能，從這牽扯到三個步驟： 1.X物件必須為operator<()函數做定義， 2.如此一來，my_comp函數才可以單純地執行return a 3.在sort演算法物件內，才可以簡單地呼叫comp(*first,*last)，知道誰大誰小。 上述三步驟，如果以執行效率來看，第一步驟與第三步驟由于可以采用C++的inline機制，做巨集展開，幾乎不會花執行時間?？墒堑诙襟E雖然最單純，只有一道指令，但由于是以函數指標的方式傳進sort的函數內，透過函數指標執行此函數，執行時間自然比較慢；而且，我們必須為每一個型別（包括C++內建型別與自行定義的類別）做這個「小函數」，盡管它的功能如此簡單。 STL針對這個問題，再次應用了template的技巧，來幫忙演算法物件執行低階的工作。如下： // test program for Function Object #include #include #include #include #include #include class INT { public: INT() {} INT(int a) { d=a; } INT(const INT& a) { d=a.d; } INT& operator=(const INT& a) { d=a.d;return *this; } int operator<(const INT& a) { return d operator int() const { return d; } int d; }; template struct comp_less { int operator()(const T& a,const T& b) { return a }; void main() { int i; vector v; cout<<"The original vector...\n"; for(i=0;i<10;i++) { v.push_back(rand()); cout<} sort(v.begin(),v.end(),comp_less()); // sort(v.begin(),v.end(),less()); cout<<"\nAfter sorting ...\n"; for(i=0;i<10;i++) cout<cout< } 我們宣告一個comp_less的類別（或稱結構）來完成功能。在sort演算法物件中，使用comp(*first,*last)執行功能，如果comp是某個class的instance，則comp(*first,*last)便是呼叫comp物件里的operator()()操作元，因此將comp_less宣告成一個類別，里頭只有一個operator()()的函數，執行上述小函數之功能，再利用inline機制，在執行時間，便一點也不會浪費執行效率；同時，也不必為每一個類別做comp_less小函數的撰寫了。 而STL對于上述解決方式命名為Function物件，程式中sort指令下一行的//sort....便是同樣問題STL Function物件的正式解決辦法。 Adaptor與其他
接下來我們看看STL如何再次應用template達到Adaptor Container的功能。 // test program for stack container #include #include #include #include #include class big { public: big() {} // required big(char *cc,int ii,float ff) { strcpy(c,cc); i=ii; f=ff; } big(const big &a) { strcpy(c,a.c); i=a.i;f=a.f; } big& operator=(const big& a) { strcpy(c,a.c); i=a.i;f=a.f; return *this; } char c[60]; int i; float f; }; ostream& operator<<(ostream& a,big& b) { return a<} void main() { stack< vector > s; s.push(big("me",1,1.11)); s.push(big("you",2,2.22)); s.push(big("he",3,3.33)); s.push(big("she",4,4.44)); while(!s.empty()) { cout< s.pop(); } } 平常傳統OO式的思維方式，對于這種（模擬stack，利用變形的vector來改造），一定會使用繼承的方式，讓stack容器繼承vector容器，然后修改一些操作元。然而號稱物件導向化的C++的STL程式庫卻不采取這種作法，而以template class的方式讓stack容器內包含vector容器，這樣做的好處當然還是為了那句老話「執行效率」，STL以執行效率出發，任何程式碼，能在編譯階段就決定好的事情盡量在編譯階段做好。從STL我們可以學到： C++工程師最好不要隨便使用繼承機制，如果可以的話，用template機制去代替。而template機制使用情形有兩種， 1.template class：使用在改造STL現有的容器物件上，或者是一些想要繼承的資料結構。 2.template function：使用在幫助加強STL現有的演算法物件上，或者是一些想要繼承的物件行為。 當然，如果您想要改造或加強的是一整個物件（包括資料與函數），非單純的資料結構或演算法，最好還是使用繼承機制。 乍看之下，上述原則似乎沒有問題，然而template機制果真這么好嗎？ 在此我們提出寫作STL程式重要的遵守規則： 在使用每個容器物件供不同演算法物件操作的時候，必須非常小心該演算法物件是否要求自己定的類別T，必須提供某些操作元函式，供其使用。 這是一個相當不協調的限制，對于一個處處講究寫作優美的C++語言而言。C++創始人Bjarne，針對這個問題，想過一些解決方式，不過都沒有定案，等待日后的C++標準會議討論。Bjarne的基本觀念，便是將這些自訂型別必須提供的操作元寫在template的容器物件類別的定義之中。大致如下： template constraints { T& operator=(const T&); int operator==(const T&,const T&); } class Conatiner { ...... }; 所以，在標準尚未定案之前，建議您寫自訂型別class T，多定義預設建構元、拷貝建構元，設值操作元，與解構元等，才能確保您所使用的演算法物件可以正確地透過Iterator物件操作容器物件。如上面程式中，我們為big類別所做的事一樣。如果基本容器類別換成list容器，則甚是要定義operator==()與operator<()操作元才行。 到此，我們大致介紹了整個STL的主要特色，STL的各部份的詳細細節，可以參考下面的資料： 參考資料
[Mus95]Musser, David R. and Saini, Atul.(1995) STL Tutorial and Reference Guide. Addison Wesley. [Nel95]Nelson, Mark. (1995) C++ Programmer‘s Guide to the Standard Template Library. IDG Books.■ | 
模板
教程
環境
性能
功能
管理
