舞影凌亂

專注C/C++，Linux

隨筆分類(11)

隨筆檔案(11)

統計

隨筆 - 11
文章 - 0
評論 - 2
引用 - 0

留言簿(1)

積分與排名

積分 - 20589
排名 - 813

Linux好站點

純中文 CentOS 攻略站

Oracle

Oracle Concepts 中文版 (10g R2)

閱讀排行榜

評論排行榜

C++ STL編程輕松入門

　　作為C++標準不可缺少的一部分，STL應該是滲透在C++程序的角角落落里的。STL不是實驗室里的寵兒，也不是程序員桌上的擺設，她的激動人心并非曇花一現。本教程旨在傳播和普及STL的基礎知識，若能借此機會為STL的推廣做些力所能及的事情，到也是件讓人愉快的事情。

　　1 初識STL：解答一些疑問　　1.1 一個最關心的問題：什么是STL科學領域里所常用的基本數據結構和基本算法。為廣大C++程序員們提供了一個可擴展的應用框架，高度體現了軟件的可復用性。這種現象有些類似于Microsoft Visual C++中的MFC（Microsoft Foundation Class Library），或者是Borland C++ Builder中的VCL(Visual Component Library)，對于此二者，大家一定不會陌生吧。

　　"什么是STL？"，假如你對STL還知之甚少，那么我想，你一定很想知道這個問題的答案，坦率地講，要指望用短短數言將這個問題闡述清楚，也決非易事。因此，如果你在看完本節之后還是覺得似懂非懂，大可不必著急，在閱讀了后續內容之后，相信你對STL的認識，將會愈加清晰、準確和完整。不過，上述這番話聽起來是否有點像是在為自己糟糕的表達能力開脫罪責呢？:）

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

　　如果說上述這種情形每天都在發生，或許有點夸張。但是，如果說整個軟件領域里，數十年來確實都在為了一個目標而奮斗--可復用性（reusability），這看起來似乎并不夸張。從最早的面向過程的函數庫，到面向對象的程序設計思想，到各種組件技術（如：COM、EJB），到設計模式（design pattern）等等。而STL也在做著類似的事情，同時在它背后蘊涵著一種新的程序設計思想--泛型化設計（generic programming）。

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

　說了半天，到底STL是什么東西呢？

　　STL（Standard Template Library），即標準模板庫，是一個具有工業強度的，高效的C++程序庫。它被容納于C++標準程序庫（C++ Standard Library）中，是ANSI/ISO C++標準中最新的也是極具革命性的一部分。該庫包含了諸多在計算機

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

　　從實現層次看，整個STL是以一種類型參數化（type parameterized）的方式實現的，這種方式基于一個在早先C++標準中沒有出現的語言特性--模板（template）。如果查閱任何一個版本的STL源代碼，你就會發現，模板作為構成整個STL的基石是一件千真萬確的事情。除此之外，還有許多C++的新特性為STL的實現提供了方便。

　　不知你對這里一下子冒出這么多術語做何感想，希望不會另你不愉快。假如你對它們之中的大多數不甚了解，敬請放心，在后續內容中將會對這些名詞逐一論述。正如開頭所提到的。

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

　　1.2 追根溯源：STL的歷史學院教授David Musser共同開發了一種叫做Tecton的語言。盡管這次嘗試最終沒有取得實用性的成果，但卻給了Stepanov很大的啟示。

　　在結識新朋友的時候，大多數人總是忍不住想了解對方的過去。本節將帶您簡單回顧一下STL的過去。

　　被譽為STL之父的Alexander Stepanov，出生于蘇聯莫斯科，早在20世紀70年代后半期，他便已經開始考慮，在保證效率的前提下，將算法從諸多具體應用之中抽象出來的可能性，這便是后來泛型化思想的雛形。為了驗證自己的思想，他和紐約州立大學教授Deepak Kapur，倫塞里爾技術

　　在隨后的幾年中，他又和David Musser等人先后用Schema語言（一種Lisp語言的變種）和Ada語言建立了一些大型程序庫。這其間，Alexander Stepanov開始意識到，在當時的面向對象程序設計思想中所存在的一些問題，比如抽象數據類型概念所存在的缺陷。Stepanov希望通過對軟件領域中各組成部分的分類，逐漸形成一種軟件設計的概念性框架。

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

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

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

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

　　此后，隨著C++標準的不斷改進，STL也在不斷地作著相應的演化。直至1998年，ANSI/ISO C++標準正式定案，STL始終是C++標準中不可或缺的一大部件。

　　1.3 千絲萬縷的聯系　　1.3.1 STL和C++　　1.3.2 STL和C++標準函數庫1.3.3 STL和GP，GP和OOP 　　1.4 STL的不同實現版本　　1.4.1 HP STL　　1.4.2 P.J. Plauger STLhttp://www.dinkumware.comVisualStudiohashset容器。1.4.3 Rouge Wave STLhttp://www.rougewave.com源代碼C:Program Files\Borland\Cbuilder6\Include\oldstl）。1.4.4 STLporthttp://www.stlport.org免費下載VC中的STL要快。比Rouge Wave STL更符合標準，也更容易移植。Borland C++ Builder已經在其6.0版中加入了對STLport的支持，它使用的STLport就是4.5版的，C++ Builder 6.0同時還提供了STLport的使用說明。你可以在C++ Builder的Include\Stlport子目錄下找到所有頭文件（比如：C:\Program Files\Borland\Cbuilder6\Include\Stlport）。1.4.5 SGI STLhttp://www.sgi.com新版本是3.3。

　　在你了解了STL的過去之后，一些名詞開始不斷在你的大腦中浮現，STL、C++、C++標準函數庫、泛型程序設計、面向對象程序設計……，這些概念意味著什么？他們之間的關系又是什么？如果你想了解某些細節，這里也許有你希望得到的答案。

　　沒有C++語言就沒有STL，這么說毫不為過。一般而言，STL作為一個泛型化的數據結構和
　　此外，STL對于C++的發展，尤其是模板機制，也起到了促進作用。比如：模板函數的偏特化（template function partial specialization），它被用于在特定應用場合，為一般模板函數提供一系列特殊化版本。這一特性是繼STL被ANSI/ISO C++標準委員會通過之后，在Bjarne和Stepanov共同商討之下并由Bjarne向委員會提出建議的，最終該項建議被通過。這使得STL中的一些算法在處理特殊情形時可以選擇非一般化的方式，從而保證了執行的效率。

　　STL是最新的C++標準函數庫中的一個子集，這個龐大的子集占據了整個庫的大約80%的分量。而作為在實現STL過程中扮演關鍵角色的模板則充斥了幾乎整個C++標準函數庫。在這里，我們有必要看一看C++標準函數庫里包含了哪些內容，其中又有哪些是屬于標準模板庫（即STL）的。

　　C++標準函數庫為C++程序員們提供了一個可擴展的基礎性框架。我們從中可以獲得極大的便利，同時也可以通過繼承現有類，自己編制符合接口規范的容器、算法、迭代子等方式對之進行擴展。它大致包含了如下幾個組件：

　　C標準函數庫，基本保持了與原有C語言程序庫的良好兼容，盡管有些微變化。人們總會忍不住留戀過去的美好歲月，如果你曾經是一個C程序員，對這一點一定體會頗深。或許有一點會讓你覺得奇怪，那就是在C++標準庫中存在兩套C的函數庫，一套是帶有.h擴展名的（比如），而另一套則沒有（比如）。它們確實沒有太大的不同。

　　語言支持（language support）部分，包含了一些標準類型的定義以及其他特性的定義，這些內容，被用于標準庫的其他地方或是具體的應用程序中。

　　診斷（diagnostics）部分，提供了用于程序診斷和報錯的功能，包含了異常處理（exception handling），斷言（assertions），錯誤代碼（error number codes）三種方式。

　　通用工具（general utilities）部分，這部分內容為C++標準庫的其他部分提供支持，當然你也可以在自己的程序中調用相應功能。比如：動態內存管理工具，日期/時間處理工具。記住，這里的內容也已經被泛化了（即采用了模板機制）。

　　字符串（string）部分，用來代表和處理文本。它提供了足夠豐富的功能。事實上，文本是一個string對象，它可以被看作是一個字符序列，字符類型可能是char，或者wchar_t等等。string可以被轉換成char*類型，這樣便可以和以前所寫的C/C++代碼和平共處了。因為那時侯除了char*，沒有別的。

　　國際化（internationalization）部分，作為OOP特性之一的封裝機制在這里扮演著消除文化和地域差異的角色，采用locale和facet可以為程序提供眾多國際化支持，包括對各種字符集的支持，日期和時間的表示，數值和貨幣的處理等等。畢竟，在中國和在美國，人們表示日期的習慣是不同的。

　　容器（containers）部分，STL的一個重要組成部分，涵蓋了許多數據結構，比如前面曾經提到的鏈表，還有：vector（類似于大小可動態增加的數組）、queue（隊列）、stack（堆棧）……。string也可以看作是一個容器，適用于容器的方法同樣也適用于string。現在你可以輕松的完成數據結構課程的家庭作業了。

　　算法（algorithms）部分，STL的一個重要組成部分，包含了大約70個通用算法，用于操控各種容器，同時也可以操控內建數組。比如：find用于在容器中查找等于某個特定值的元素，for_each用于將某個函數應用到容器中的各個元素上，sort用于對容器中的元素排序。所有這些操作都是在保證執行效率的前提下進行的，所以，如果在你使用了這些算法之后程序變得效率底下，首先一定不要懷疑這些算法本身，仔細檢查一下程序的其他地方。

　　迭代器（iterators）部分，STL的一個重要組成部分，如果沒有迭代器的撮合，容器和算法便無法結合的如此完美。事實上，每個容器都有自己的迭代器，只有容器自己才知道如何訪問自己的元素。它有點像指針，算法通過迭代器來定位和操控容器中的元素。

　　數值（numerics）部分，包含了一些數學運算功能，提供了復數運算的支持。

　　輸入/輸出（input/output）部分，就是經過模板化了的原有標準庫中的iostream部分，它提供了對C++程序輸入輸出的基本支持。在功能上保持了與原有iostream的兼容，并且增加了異常處理的機制，并支持國際化（internationalization）。

　　總體上，在C++標準函數庫中，STL主要包含了容器、算法、迭代器。string也可以算做是STL的一部分。

　　正如前面所提到的，在STL的背后蘊含著泛型化程序設計（GP）的思想，在這種思想里，大部分基本算法被抽象，被泛化，獨立于與之對應的數據結構，用于以相同或相近的方式處理各種不同情形。這一思想和面向對象的程序設計思想（OOP）不盡相同，因為，在OOP中更注重的是對數據的抽象，即所謂抽象數據類型（Abstract Data Type），而算法則通常被附屬于數據類型之中。幾乎所有的事情都可以被看作類或者對象（即類的實例），通常，我們所看到的算法被作為成員函數（member function）包含在類（class）中，類和類則構成了錯綜復雜的繼承體系。

　　盡管在象C++這樣的程序設計語言中，你還可以用全局函數來表示算法，但是在類似于Java這樣的純面向對象的語言中，全局函數已經被"勒令禁止"了。因此，用Java來模擬GP思想是頗為困難的。如果你對前述的STL歷史還有印象的話，應該記得Alexander Stepanove也曾用基于OOP的語言嘗試過實現GP思想，但是效果并不好，包括沒有引入模板之前的C++語言。站在巨人的肩膀上，我們可以得出這樣的結論，在OOP中所體現的思想與GP的思想確實是相異的。C++并不是一種純面向對象的程序設計語言，它的絕妙之處，就在于既滿足了OOP，又成全了GP。對于后者，模板立下了汗馬功勞。另外，需要指出的是，盡管GP和OOP有諸多不同，但這種不同還不至于到"水火不容"的地步。并且，在實際運用的時候，兩者的結合使用往往可以使問題的解決更為有效。作為GP思想實例的STL本身便是一個很好的范例，如果沒有繼承，不知道STL會是什么樣子，似乎沒有人做過這樣的試驗。
　　相信你對STL的感性認識應該有所提高了，是該做一些實際的工作了，那么我們首先來了解一下STL的不同實現版本。ANSI/ISO C++文件中的STL是一個僅被描述在紙上的標準，對于諸多C++編譯器而言，需要有各自實際的STL，它們或多或少的實現了標準中所描述的內容，這樣才能夠為我們所用。之所以有不同的實現版本，則存在諸多原因，有歷史的原因，也有各自編譯器生產廠商的原因。以下是幾個常見的STL實現版本。

　　HP STL是所有其它STL實現版本的根源。它是STL之父Alexander Stepanov在惠普的Palo Alto實驗室工作時，和Meng Lee共同完成的，是第一個STL的實現版本（參見1.2節）。這個STL是開放源碼的，所以它允許任何人免費使用、復制、修改、發布和銷售該軟件和相關文檔，前提是必須在所有相關文件中加入HP STL的版本信息和授權信息。現在已經很少直接使用這個版本的STL了。

　　P. J. Plauger STL屬于個人作品，由P. J. Plauger本人實現，是HP STL的一個繼承版本，因此在其所有頭文件中都含有HP STL的相關聲明，同時還有P. J. Plauger本人的版權聲明。P. J. Plauger是標準C中stdio庫的早期實現者，現在是C/C++ User's Journal的主編，與Microsoft保持著良好的關系。P. J. Plauger STL便是被用于Microsoft的Visual C++中的。在Windows平臺下的同類版本中，其性能不錯，但是queue組件（隊列，一種容器）的效率不理想，同時由于Visual C++對C++語言標準的支持不是很好（至少直到VC6.0為止，還是如此），因此一定程度上影響了P. J. Plauger STL的性能。此外，該版本的源代碼可讀性較差，你可以在VC的Include子目錄下找到所有源文件（比如：C:\Program Files\Microsoft Visual Studio\VC98\Include）。因為不是開放源碼的（open source），所以這些源代碼是不能修改和銷售的，目前P.J. Plauger STL由Dinkumware公司提供相關服務.

　　Rouge Wave STL是由Rouge Wave公司實現的，也是HP STL的一個繼承版本，除了HP STL的相關聲明之外，還有Rouge Wave公司的版權聲明。同時，它也不是開放源碼的，因此無法修改和銷售。該版本被Borland C++ Builder所采用，你可以在C++ Builder的Include子目錄下找到所有頭文件（比如：C:\Program Files\Borland\Cbuilder5\Include）。盡管Rouge Wave STL的性能不是很好，但由于C++ Builder對C++語言標準的支持還算不錯，使其表現在一定程度上得以改善。此外，其源代碼的可讀性較好。可以從如下網站得到更詳細的情況介紹：

　　STLport最初源于俄國人Boris Fomitchev的一個開發項目，主要用于將SGI STL的基本代碼移植到其他諸如C++Builder或者是Visual C++這樣的主流編譯器上。因為SGI STL屬于開放源碼，所以STLport才有權這樣做。目前STLport的最新版本是4.5。可以從如下網站得到更詳細的情況介紹：

　　SGI STL是由Silicon Graphics Computer System, Inc公司實現的，其設計者和編寫者包括Alexander Stepanov和Matt Austern，同樣它也是HP STL的一個繼承版本。它屬于開放源碼，因此你可以修改和銷售它。SGI STL被GCC（linux下的C++編譯器）所采用，你可以在GCC的Include子目錄下找到所有頭文件（比如：C:\cygnus\cygwin-b20\include\g++\include）。由于GCC對C++語言標準的支持很好，SGI STL在linux平臺上的性能相當出色。此外，其源代碼的可讀性也很好。

posted on 2010-06-02 00:17 幽夢新影閱讀(496) 評論(0) 編輯收藏引用所屬分類: C/C++基礎知識

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: STL vector 容器介紹 C++ STL編程輕松入門 C++類庫：OTL通用的數據庫連接類庫 boost庫linux編譯安裝在Linux系統中安裝和配置ACE(轉)

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品