作為C++標(biāo)準(zhǔn)不可缺少的一部分，STL應(yīng)該是滲透在C++程序的角角落落里的。STL不是實(shí)驗(yàn)室里的寵兒，也不是程序員桌上的擺設(shè)，她的激動(dòng)人心并非曇花一現(xiàn)。本教程旨在傳播和普及STL的基礎(chǔ)知識(shí)，若能借此機(jī)會(huì)為STL的推廣做些力所能及的事情，到也是件讓人愉快的事情。   

初識(shí)STL：解答一些疑問(wèn)   

1.1 一個(gè)最關(guān)心的問(wèn)題：什么是STL   

"什么是STL？"，假如你對(duì)STL還知之甚少，那么我想，你一定很想知道這個(gè)問(wèn)題的答案，坦率地講，要指望用短短數(shù)言將這個(gè)問(wèn)題闡述清楚，也決非易事。因此，如果你在看完本節(jié)之后還是覺(jué)得似懂非懂，大可不必著急，在閱讀了后續(xù)內(nèi)容之后，相信你對(duì)STL的認(rèn)識(shí)，將會(huì)愈加清晰、準(zhǔn)確和完整。不過(guò)，上述這番話聽(tīng)起來(lái)是否有點(diǎn)像是在為自己糟糕的表達(dá)能力開(kāi)脫罪責(zé)呢？:）   

不知道你是否有過(guò)這樣的經(jīng)歷。在你準(zhǔn)備著手完成數(shù)據(jù)結(jié)構(gòu)老師所布置的家庭作業(yè)時(shí)，或者在你為你所負(fù)責(zé)的某個(gè)軟件項(xiàng)目中添加一項(xiàng)新功能時(shí)，你發(fā)現(xiàn)需要用到一個(gè)鏈表(List)或者是映射表（Map）之類的東西，但是手頭并沒(méi)有現(xiàn)成的代碼。于是在你開(kāi)始正式考慮程序功能之前，手工實(shí)現(xiàn)List或者M(jìn)ap是不可避免的。于是……，最終你順利完成了任務(wù)。或許此時(shí)，作為一個(gè)具有較高素養(yǎng)的程序員的你還不肯罷休（或者是一個(gè)喜歡偷懶的優(yōu)等生:），因?yàn)槟銜?huì)想到，如果以后還遇到這樣的情況怎么辦？沒(méi)有必要再做一遍同樣的事情吧！   

如果說(shuō)上述這種情形每天都在發(fā)生，或許有點(diǎn)夸張。但是，如果說(shuō)整個(gè)軟件領(lǐng)域里，數(shù)十年來(lái)確實(shí)都在為了一個(gè)目標(biāo)而奮斗--可復(fù)用性（reusability），這看起來(lái)似乎并不夸張。從最早的面向過(guò)程的函數(shù)庫(kù)，到面向?qū)ο蟮某绦蛟O(shè)計(jì)思想，到各種組件技術(shù)（如：COM、EJB），到設(shè)計(jì)模式（design pattern）等等。而STL也在做著類似的事情，同時(shí)在它背后蘊(yùn)涵著一種新的程序設(shè)計(jì)思想--泛型化設(shè)計(jì)（generic programming）。   

繼續(xù)上面提到的那個(gè)例子，假如你把List或者map完好的保留了下來(lái)，正在暗自得意。且慢，如果下一回的List里放的不是浮點(diǎn)數(shù)而是整數(shù)呢？如果你所實(shí)現(xiàn)的Map在效率上總是令你不太滿意并且有時(shí)還會(huì)出些bug呢？你該如何面對(duì)這些問(wèn)題？使用STL是一個(gè)不錯(cuò)的選擇，確實(shí)如此，STL可以漂亮地解決上面提到的這些問(wèn)題，盡管你還可以尋求其他方法。   

說(shuō)了半天，到底STL是什么東西呢？   

STL（Standard Template Library），即標(biāo)準(zhǔn)模板庫(kù)，是一個(gè)具有工業(yè)強(qiáng)度的，高效的C++程序庫(kù)。它被容納于C++標(biāo)準(zhǔn)程序庫(kù)（C++ Standard Library）中，是ANSI/ISO C++標(biāo)準(zhǔn)中最新的也是極具革命性的一部分。該庫(kù)包含了諸多在計(jì)算機(jī)科學(xué)領(lǐng)域里所常用的基本數(shù)據(jù)結(jié)構(gòu)和基本算法。為廣大C++程序員們提供了一個(gè)可擴(kuò)展的應(yīng)用框架，高度體現(xiàn)了軟件的可復(fù)用性。這種現(xiàn)象有些類似于Microsoft Visual C++中的MFC（Microsoft Foundation Class Library），或者是Borland C++ Builder中的VCL(Visual Component Library)，對(duì)于此二者，大家一定不會(huì)陌生吧。   

從邏輯層次來(lái)看，在STL中體現(xiàn)了泛型化程序設(shè)計(jì)的思想（generic programming），引入了諸多新的名詞，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），迭代子（iterator）等。與OOP（object-oriented programming）中的多態(tài)（polymorphism）一樣，泛型也是一種軟件的復(fù)用技術(shù)。   

從實(shí)現(xiàn)層次看，整個(gè)STL是以一種類型參數(shù)化（type parameterized）的方式實(shí)現(xiàn)的，這種方式基于一個(gè)在早先C++標(biāo)準(zhǔn)中沒(méi)有出現(xiàn)的語(yǔ)言特性--模板（template）。如果查閱任何一個(gè)版本的STL源代碼，你就會(huì)發(fā)現(xiàn)，模板作為構(gòu)成整個(gè)STL的基石是一件千真萬(wàn)確的事情。除此之外，還有許多C++的新特性為STL的實(shí)現(xiàn)提供了方便。   

不知你對(duì)這里一下子冒出這么多術(shù)語(yǔ)做何感想，希望不會(huì)另你不愉快。假如你對(duì)它們之中的大多數(shù)不甚了解，敬請(qǐng)放心，在后續(xù)內(nèi)容中將會(huì)對(duì)這些名詞逐一論述。正如開(kāi)頭所提到的。   

有趣的是，對(duì)于STL還有另外一種解釋--STepanov %26amp; Lee，前者是指Alexander Stepanov，STL的創(chuàng)始人；而后者是Meng Lee，她也是使STL得以推行的功臣，第一個(gè)STL成品就是他們合作完成的。這一提法源自1995年3月，Dr.Dobb’s Journal特約記者, 著名技術(shù)書籍作家Al Stevens對(duì)Alexander Stepanov的一篇專訪。   






1.2 追根溯源：STL的歷史   


在結(jié)識(shí)新朋友的時(shí)候，大多數(shù)人總是忍不住想了解對(duì)方的過(guò)去。本節(jié)將帶您簡(jiǎn)單回顧一下STL的過(guò)去。   

被譽(yù)為STL之父的Alexander Stepanov，出生于蘇聯(lián)莫斯科，早在20世紀(jì)70年代后半期，他便已經(jīng)開(kāi)始考慮，在保證效率的前提下，將算法從諸多具體應(yīng)用之中抽象出來(lái)的可能性，這便是后來(lái)泛型化思想的雛形。為了驗(yàn)證自己的思想，他和紐約州立大學(xué)教授Deepak Kapur，倫塞里爾技術(shù)學(xué)院教授David Musser共同開(kāi)發(fā)了一種叫做Tecton的語(yǔ)言。盡管這次嘗試最終沒(méi)有取得實(shí)用性的成果，但卻給了Stepanov很大的啟示。   

在隨后的幾年中，他又和David Musser等人先后用Schema語(yǔ)言（一種Lisp語(yǔ)言的變種）和Ada語(yǔ)言建立了一些大型程序庫(kù)。這其間，Alexander Stepanov開(kāi)始意識(shí)到，在當(dāng)時(shí)的面向?qū)ο蟪绦蛟O(shè)計(jì)思想中所存在的一些問(wèn)題，比如抽象數(shù)據(jù)類型概念所存在的缺陷。Stepanov希望通過(guò)對(duì)軟件領(lǐng)域中各組成部分的分類，逐漸形成一種軟件設(shè)計(jì)的概念性框架。   

1987年左右，在貝爾實(shí)驗(yàn)室工作的Alexander Stepanov開(kāi)始首次采用C++語(yǔ)言進(jìn)行泛型軟件庫(kù)的研究。但遺憾的是，當(dāng)時(shí)的C++語(yǔ)言還沒(méi)有引入模板（template）的語(yǔ)法，現(xiàn)在我們可以清楚的看到，模板概念之于STL實(shí)現(xiàn)，是何等重要。是時(shí)使然，采用繼承機(jī)制是別無(wú)選擇的。盡管如此，Stepanov還是開(kāi)發(fā)出了一個(gè)龐大的算法庫(kù)。與此同時(shí)，在與Andrew Koenig（前ISO C++標(biāo)準(zhǔn)化委員會(huì)主席）和Bjarne Stroustrup（C++語(yǔ)言的創(chuàng)始人）等頂級(jí)大師們的共事過(guò)程中，Stepanov開(kāi)始注意到C/C++語(yǔ)言在實(shí)現(xiàn)其泛型思想方面所具有的潛在優(yōu)勢(shì)。就拿C/C++中的指針而言，它的靈活與高效運(yùn)用，使后來(lái)的STL在實(shí)現(xiàn)泛型化的同時(shí)更是保持了高效率。另外，在STL中占據(jù)極其重要地位的迭代子概念便是源自于C/C++中原生指針（ native pointer）的抽象。   

1988年，Alexander Stepanov開(kāi)始進(jìn)入惠普的Palo Alto實(shí)驗(yàn)室工作，在隨后的4年中，他從事的是有關(guān)磁盤驅(qū)動(dòng)器方面的工作。直到1992年，由于參加并主持了實(shí)驗(yàn)室主任Bill Worley所建立的一個(gè)有關(guān)算法的研究項(xiàng)目，才使他重新回到了泛型化算法的研究工作上來(lái)。項(xiàng)目自建立之后，參與者從最初的8人逐漸減少，最后只剩下兩個(gè)人--Stepanove本人和Meng Lee。經(jīng)過(guò)長(zhǎng)時(shí)間的努力，最終，信念與汗水所換來(lái)的是一個(gè)包含有大量數(shù)據(jù)結(jié)構(gòu)和算法部件的龐大運(yùn)行庫(kù)。這便是現(xiàn)在的STL的雛形（同時(shí)也是STL的一個(gè)實(shí)現(xiàn)版本--HP STL）。   

1993年，當(dāng)時(shí)在貝爾實(shí)驗(yàn)室的Andrew Koenig看到了Stepanove的研究成果，很是興奮。在他的鼓勵(lì)與幫助下，Stepanove于是年9月的圣何塞為ANSI/ISO C++標(biāo)準(zhǔn)委員會(huì)做了一個(gè)相關(guān)演講（題為"The Science of C++ Programming"），向委員們講述了其觀念。然后又于次年3月，在圣迭戈會(huì)議上，向委員會(huì)提交了一份建議書，以期使STL成為C++標(biāo)準(zhǔn)庫(kù)的一部分。盡管這一建議十分龐大，以至于降低了被通過(guò)的可能性，但由于其所包含的新思想，投票結(jié)果以壓倒多數(shù)的意見(jiàn)認(rèn)為推遲對(duì)該建議的決定。   

隨后，在眾人的幫助之下，包括Bjarne Stroustrup在內(nèi)，Stepanove又對(duì)STL進(jìn)行了改進(jìn)。同時(shí)加入了一個(gè)封裝內(nèi)存模式信息的抽象模塊，也就是現(xiàn)在STL中的allocator，它使STL的大部分實(shí)現(xiàn)都可以獨(dú)立于具體的內(nèi)存模式，從而獨(dú)立于具體平臺(tái)。在同年夏季的滑鐵盧會(huì)議上，委員們以80%贊成，20%反對(duì)，最終通過(guò)了提案，決定將STL正式納入C++標(biāo)準(zhǔn)化進(jìn)程之中，隨后STL便被放進(jìn)了會(huì)議的工作文件中。自此，STL終于成為了C++家族中的重要一員。   

此后，隨著C++標(biāo)準(zhǔn)的不斷改進(jìn)，STL也在不斷地作著相應(yīng)的演化。直至1998年，ANSI/ISO C++標(biāo)準(zhǔn)正式定案，STL始終是C++標(biāo)準(zhǔn)中不可或缺的一大部件。








一.什么時(shí)候用STL

    如果，有的時(shí)候，你要在程序中用到堆、棧、隊(duì)列、鏈表等一些基本的算法，而你又實(shí)在不想自己去實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)教科書中那些繁瑣的算法，那么你就可以考慮使用STL。

    另外，STL作為一種標(biāo)準(zhǔn)，便于交流，掌握它，一方面可以讓你寫的程序，易于讓別人理解，另一方面你也能夠比較容易地理解別人寫的程序。

二.什么是STL

    全稱為  Standard Template Library  ，即標(biāo)準(zhǔn)模板庫(kù)

    要使用STL，要了解以下幾個(gè)基本概念：

        容器：可以把它理解為存放數(shù)據(jù)的地方，常用的一些容器有 鏈表(list) 棧(stack) 動(dòng)態(tài)數(shù)組 (vector) 雙端隊(duì)列(deque) 隊(duì)列(queue) 映射(map)

        游標(biāo)(iterator)：可以把它理解為指針類型，STL中的許多函數(shù)需要用到它們作為參數(shù)

        算法：它們通常需要與容器和游標(biāo)配合使用，使用它們，你可以方便地對(duì)容器中的數(shù)據(jù)進(jìn)行各種常見(jiàn)的操作，如排序操作，尋找最大元素的操作等

一、容器模板的使用     大致有下面6個(gè)步驟：         1.添加相應(yīng)的頭文件(如 #include <list> )( 注意，沒(méi)有 .h )         2.添加std命名空間(用 using namespace std; )         3.賦予模板具體的使用類型(如 typedef list<string> LISTSTR; )         4.實(shí)例化模板(如 LISTSTR test; )         5.實(shí)例化游標(biāo)(如 LISTSTR::iterator i; )         6.通過(guò)迭代器對(duì)象訪問(wèn)模板對(duì)象，例如             // 逐個(gè)輸出鏈表test中的元素             for ( i =  test.begin(); i != test.end(); ++i )                 cout << *i << " "; 二、容器模板中的常用函數(shù)    assign()           賦值    empty()            容器為空則返回非0值    erase()            刪除指定位置或指定范圍內(nèi)的元素    push_front()   從容器頭部插入元素      push_back()   從容器尾部插入元素    pop_front()     刪除第一個(gè)元素    pop_back()     刪除最后一個(gè)元素    back()              返回最后一個(gè)元素的引用    front()              返回第一個(gè)元素的引用    begin()             返回指向第一個(gè)元素的游標(biāo) (與迭代器配合使用)    end()                返回指向最后一個(gè)元素的后一個(gè)位置的游標(biāo) (最后1個(gè)元素再加1) (與迭代器配合使用)