程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 詳細介紹C++ STL編程

詳細介紹C++ STL編程

編輯:C++入門知識

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

1 初識STL:解答一些疑問

1.1 一個最關心的問題:什麼是STL

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

不知道你是否有過這樣的經歷。在你准備著手完成數據結構老師所布置的家庭作業時,或者在你為你所負責的某個軟件項目中添加一項新功能時,你發現需要用到一個鏈表(List)或者是映射表Map)之類的東西,但是手頭並沒有現成的代碼。於是在你開始正式考慮程序功能之前,手工實現List或者Map是不可避免的。

於是……,最終你順利完成了任務。或許此時,作為一個具有較高素養的程序員的你還不肯罷休或者是一個喜歡偷懶的優等生:),因為你會想到,如果以後還遇到這樣的情況怎麼辦?沒有必要再做一遍同樣的事情吧!

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

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

說了半天,到底STL是什麼東西呢?

STLStandard Template Library),即標准模板庫,是一個具有工業強度的,高效的C++程序庫。它被容納於C++標准程序庫C++ Standard Library)中,是ANSI/ISO C++標准中最新的也是極具革命性的一部分。該庫包含了諸多在計算機科學領域裡所常用的基本數據結構和基本算法。為廣大C++程序員們提供了一個可擴展的應用框架,高度體現了軟件的可復用性。這種現象有些類似於Microsoft Visual C++中的MFCMicrosoft Foundation Class Library),或者是Borland C++ Builder中的VCL(Visual Component Library),對於此二者,大家一定不會陌生吧。

從邏輯層次來看,在STL中體現了泛型化程序設計的思想generic programming),引入了諸多新的名詞,比如像需求requirements),概念concept),模型model),容器container),算法algorithmn),迭代子iterator)等。與OOPobject-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的歷史

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

被譽為STL之父的Alexander Stepanov,出生於蘇聯莫斯科,早在20世紀70年代後半期,他便已經開始考慮,在保證效率的前提下,將算法從諸多具體應用之中抽象出來的可能性,這便是後來泛型化思想的雛形。為了驗證自己的思想,他和紐約州立大學教授Deepak Kapur,倫塞裡爾技術學院教授David Musser共同開發了一種叫做Tecton的語言。盡管這次嘗試最終沒有取得實用性的成果,但卻給了Stepanov很大的啟示。

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

1987年左右,在貝爾實驗室工作的Alexander Stepanov開始首次采用C++語言進行泛型軟件庫的研究。但遺憾的是,當時的C++語言還沒有引入模板template)的語法,現在我們可以清楚的看到,模板概念之於STL實現,是何等重要。是時使然,采用繼承機制是別無選擇的。盡管如此,Stepanov還是開發出了一個龐大的算法庫。

與此同時,在與Andrew Koenig前ISO C++標准化委員會主席)和Bjarne StroustrupC++語言的創始人)等頂級大師們的共事過程中,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 千絲萬縷的聯系

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

1.3.1 STL和C++

沒有C++語言就沒有STL,這麼說毫不為過。一般而言,STL作為一個泛型化的數據結構和算法庫,並不牽涉具體語言當然,在C++裡,它被稱為STL)。也就是說,如果條件允許,用其他語言也可以實現之。這裡所說的條件,主要是指類似於"模板"這樣的語法機制。如果你沒有略過前一節內容的話,應該可以看到,Alexander Stepanov在選擇C++語言作為實現工具之前,早以采用過多種程序設計語言。

但是,為什麼最終還是C++幸運的承擔了這個歷史性任務呢?原因不僅在於前述那個條件,還在於C++在某些方面所表現出來的優越特性,比如:高效而靈活的指針。但是如果把C++作為一種OOPObject-Oriented Programming,面向對象程序設計)語言來看待的話事實上我們一般都是這麼認為的,不是嗎?),其功能強大的繼承機制卻沒有給STL的實現幫上多大的忙。在STL的源代碼裡,並沒有太多太復雜的繼承關系。

繼承的思想,甚而面向對象的思想,還不足以實現類似STL這樣的泛型庫。C++只有在引入了"模板"之後,才直接導致了STL的誕生。這也正是為什麼,用其他比C++更純的面向對象語言無法實現泛型思想的一個重要原因。當然,事情總是在變化之中,像Java在這方面,就是一個很好的例子,jdk1.4中已經加入了泛型的特性。

此外,STL對於C++的發展,尤其是模板機制,也起到了促進作用。比如:模板函數的偏特化template function partial specialization),它被用於在特定應用場合,為一般模板函數提供一系列特殊化版本。這一特性是繼STL被ANSI/ISO C++標准委員會通過之後,在Bjarne和Stepanov共同商討之下並由Bjarne向委員會提出建議的,最終該項建議被通過。這使得STL中的一些算法在處理特殊情形時可以選擇非一般化的方式,從而保證了執行的效率。

1.3.2 STL和C++標准函數庫

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和C++標准函數庫

圖1:STL和C++標准函數庫

1.3.3 STL和GP,GP和OOP

正如前面所提到的,在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會是什麼樣子,似乎沒有人做過這樣的試驗。

1.4 STL的不同實現版本

相信你對STL的感性認識應該有所提高了,是該做一些實際的工作了,那麼我們首先來了解一下STL的不同實現版本。ANSI/ISO C++文件中的STL是一個僅被描述在紙上的標准,對於諸多C++編譯器而言,需要有各自實際的STL,它們或多或少的實現了標准中所描述的內容,這樣才能夠為我們所用。之所以有不同的實現版本,則存在諸多原因,有歷史的原因,也有各自編譯器生產廠商的原因。以下是幾個常見的STL實現版本。

1.4.1 HP STL

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

1.4.2 P.J. Plauger 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公司提供相關服務,詳情請見http://www.dinkumware.com。據稱Visual Studio.NET中的Visual C++.NET即VC7.0),對C++標准的支持有所提高,並且多了以哈希表hash table)為基礎而實現的map容器,multimap容器和set容器。

1.4.3 Rouge Wave STL

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++語言標准的支持還算不錯,使其表現在一定程度上得以改善。

此外,其源代碼的可讀性較好。可以從如下網站得到更詳細的情況介紹:http://www.rougewave.com。遺憾的是該版本已有一段時間沒有更新且不完全符合標准。因此在Borland C++ Builder 6.0中,它的地位被另一個STL的實現版本--STLport見後)取代了。但是考慮到與以前版本的兼容,C++ Builder 6.0還是保留了Rouge Wave STL,只是如果你想查看它的源代碼的話,需要在別的目錄中才能找到比如:C:\Program Files\Borland\Cbuilder6\Include\oldstl)。

1.4.4 STLport

STLport最初源於俄國人Boris Fomitchev的一個開發項目,主要用於將SGI STL的基本代碼移植到其他諸如C++Builder或者是Visual C++這樣的主流編譯器上。因為SGI STL屬於開放源碼,所以STLport才有權這樣做。目前STLport的最新版本是4.5。可以從如下網站得到更詳細的情況介紹:http://www.stlport.org,可以免費下載其源代碼。STLport已經被C/C++技術委員會接受成為工業標准,且在許多平台上都支持。

根據測試STLport的效率比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 STL

SGI STL是由Silicon Graphics Computer System, Inc公司實現的,其設計者和編寫者包括Alexander Stepanov和Matt Austern,同樣它也是HP STL的一個繼承版本。它屬於開放源碼,因此你可以修改和銷售它。SGI STL被GCClinux下的C++編譯器)所采用,你可以在GCC的Include子目錄下找到所有頭文件比如:C:\cygnus\cygwin-b20\include\g++\include)。由於GCC對C++語言標准的支持很好,SGI STL在linux平台上的性能相當出色。此外,其源代碼的可讀性也很好。可以從如下網站得到更詳細的情況介紹:http://www.sgi.com,可以免費下載其源代碼。目前的最新版本是3.3。

STL家族的譜系

圖2:STL家族的譜系

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved