一、STL簡介

1.1 初識STL

STL（Standard Template Library页屠，即標準模版庫）是一個具有工業(yè)級強度的层亿，高效的C++程序庫。它被容納于C++標準程序庫（C++ Standard Library）中诗箍，是ANSI/ISO C++標準中最新的也是極具革命性的一部分。該庫包含了諸多在計算機科學領域所常用的基本數據結構和基本算法挽唉。為廣大C++程序員提供了一個可擴展的應用框架滤祖，高度體現了軟件的可復用性。這種現象有些類似于Microsoft Visual C++中的MFC（Microsoft Foundation Class Library）瓶籽，或者是Borland C++ Builder中的VCL（Virsual Component Library）匠童。

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

從實現層次看墓赴，整個STL是以一種類型參數化（type paramterized）的方式實現的竞膳，這種方式基于一個在早先C++標準中沒有出現的語言特性——模板（template）。如果查閱任何一個版本的STL源碼诫硕，你就會發(fā)現坦辟，模板作為構成整個STL的基石是一件千真萬確的事。除此之外章办，還有許多C++的新特性為STL的實現提供了方便锉走。

1.2 STL的歷史

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

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

1987年左右，在貝爾實驗室工作的Alexander Stepanov開始首次采用C++語言進行泛型軟件庫的研究秕豫。但遺憾的是朴艰，當時的C++語言還沒有引入模板（template）的語法观蓄，現在我們可以清楚的看到，模板概念之于STL實現祠墅，是何等重要侮穿。是時使然，采用繼承機制是別無選擇的毁嗦。盡管如此撮珠，Stepanov還是開發(fā)出了一個龐大的算法庫。與此同時金矛，在與Andrew Koenig（前ISO C++標準化委員會主席）和Bjarne Stroustrup（C++語言的創(chuàng)始人）等頂級大師們的共事過程中芯急，Stepanov開始注意到C/C++語言在實現其泛型思想方面所具有的潛在優(yōu)勢。就拿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++標準中不可或缺的一大部件。

二脏嚷、STL的框架

2.1 STL的分類

STL的代碼從廣義上講分為三類：algorithm（算法）、container（容器）和iterator（迭代器）瞒御。幾乎所有的代碼都采用了模板類和模板函數的方式父叙，這相比于傳統(tǒng)的由函數和類組成的庫來說提供了更好的代碼重用機會。

在C++標準中肴裙，STL被組織為下面13個頭文件：<algorithm>趾唱、<deque>、<functional>蜻懦、<iterator>甜癞、<vector>、<list>宛乃、<map>悠咱、<memory>蒸辆、<numeric>、<queue>析既、<set>躬贡、<stack>和<utility>。

2.2 算法

大家都能取得的一個共識是函數庫對數據類型的選擇對其可重用性起著至關重要的作用眼坏。舉例來說拂玻，一個求方根的函數，在使用浮點數作為其參數類型的情況下的可重用性肯定比使用整型作為它的參數類性要高宰译。而C++通過模板的機制允許推遲對某些類型的選擇檐蚜，直到真正想使用模板或者說對模板進行特化的時候，STL就利用了這一點提供了相當多的有用算法沿侈。它是在一個有效的框架中完成這些算法的——你可以將所有的類型劃分為少數的幾類闯第，然后就可以在模版的參數中使用一種類型替換掉同一種類中的其他類型。

算法（algorithm）是應用在容器上以各種方法處理其內容的行為和功能肋坚。例如：有對容器內容排序乡括、復制、檢索智厌、合并等算法诲泌。在STL中，算法是由模板函數表現的铣鹏。這些函數不是容器類的成員函數敷扫，相反它們是獨立的函數。令人吃驚的特點之一就是其算法是如此的通用诚卸，不僅可以將其用于STL容器葵第，而且可以用于普通的C++數組或任何其他應用程序指定的容器。

STL提供了大約100個實現算法的模版函數合溺，比如算法for_each將為指定序列中的每一個元素調用指定的函數卒密，stable_sort以你所指定的規(guī)則對序列進行穩(wěn)定性排序等等。這樣一來棠赛，只要我們熟悉了STL之后哮奇，許多代碼可以被大大的化簡，只需要通過調用一兩個算法模板睛约，就可以完成所需要的功能并大大地提升效率鼎俘。

算法部分主要由頭文件<algorithm>，<numeric>和<functional>組成辩涝。

• <algorithm>：是所有STL頭文件中最大的一個（盡管它很好理解）贸伐，它是由一大堆模板函數組成的，可以認為每個函數在很大程度上都是獨立的怔揩，其中常用到的功能范圍涉及到比較捉邢、交換脯丝、查找、遍歷操作歌逢、復制巾钉、修改、移除秘案、反轉砰苍、排序、合并等等阱高；
• <numeric>：體積很小赚导，只包括幾個在序列上面進行簡單數學運算的模版函數，包括加法和乘法在序列上的一些操作赤惊；
• <functional>：其中定義了一些模板類吼旧，用以聲明函數對象。

2.3 容器

在實際的開發(fā)過程中未舟，數據結構本身的重要性不會遜于操作于數據結構的算法的重要性圈暗，當程序中存在著對時間要求很高的部分時，數據結構的選擇就顯得更加重要裕膀。

經典的數據結構數量有限员串，但是我們常常重復著一些為了實現向量、鏈表等結構而編寫的代碼昼扛，這些代碼都十分相似寸齐，只是為了適應不同數據的變化而在細節(jié)上有所出入。STL容器就為我們提供了這樣的方便抄谐，它允許我們重復利用已有的實現構造自己的特定類型下的數據結構渺鹦，通過設置一些模版類，STL容器對最常用的數據結構提供了支持蛹含，這些模板的參數允許我們指定容器中元素的數據類型毅厚，可以將我們許多重復而乏味的工作簡化。

容器是數據在內存中的組織的方法浦箱，例如：數組卧斟、堆棧、隊列憎茂、鏈表、二叉樹等（這些都不是STL標準容器）锤岸。STL中的容器是一種存儲T（Template）類型值的有限集合的數據結構竖幔，容器的內部實現一般是類。這些值可以是對象本身是偷，如果數據類型T代表的是class的化拳氢。

容器部分主要由頭文件<vector>,<list>,<deque>,<set>,<map>,<stack>和<queue>組成募逞。對于常用的一些容器和容器適配器（可以看作由其它容器實現的容器），可以通過下表總結一下它們和相應頭文件的對應關系馋评。

• 向量（vector）：連續(xù)存儲的元素<vector>放接；
• 列表（list）：由節(jié)點組成的雙向列表，每個節(jié)點包含著一個元素<list>留特；
• 雙隊列（deque）：連續(xù)存儲的指向不同元素的指針所組成的數組<deque>纠脾；
• 集合（set）：由節(jié)點組成的紅黑樹，每個節(jié)點都包含著一個元素蜕青，節(jié)點之間以某種作用于元素對的謂詞排列苟蹈，沒有兩個不同的元素能夠擁有相同的次序<set>；
• 多重集合（multiset）：允許存在兩個次序相等的元素的集合<set>右核；
• 棧（stack）：后進先出的值的排列<stack>慧脱；
• 隊列（queue）：先進先出的值的排列<queue>；
• 優(yōu)先隊列（priority_queue）：元素的次序是由作用于所存儲的值對上的某種謂詞決定的一種隊列<queue>贺喝；
• 映射（map）：由{鍵,值}對組成的集合菱鸥，以某種作用于鍵對上的謂詞排列<map>；
• 多重映射（multimap）：允許鍵對有相等的次序的映射<map>躏鱼。

2.4 迭代器

一旦選定一種容器類型和數據行為（算法）氮采，那么剩下唯一要做的就是用迭代器使其相互作用∧铀可以把迭代器看作一個指向容器中元素的普通指針扳抽，可以如遞增一個指針那樣遞增迭代器，使其依次指向容器中每一個后繼的元素殖侵。迭代器是STL中的一個關鍵部分贸呢，因為它將算法和容器連接在一起。

下面要說的迭代器從作用上來說是最基本的部分拢军，可是理解起來比前兩者都要費力一些（至少筆者是這樣）楞陷。軟件設計有一個基本原則，所有的問題都可以通過引進一個間接層來簡化茉唉，這種簡化在STL中就是用迭代器來完成的固蛾。

概括來說，迭代器在STL中用來將算法和容器聯系起來度陆，起著一種黏和劑的作用艾凯。幾乎STL提供的所有算法都是通過迭代器存取元素序列進行工作的，每一個容器都定義了其本身所專有的迭代器懂傀，用以存取容器中的元素趾诗。

迭代器部分主要由頭文件<utility>,<iterator>和<memory>組成。

• <utility>：是一個很小的頭文件，它包括了貫穿使用在STL中的幾個模版的聲明恃泪；
• <iterator>：提供了迭代器使用的許多方法
• <memory>：它以不同尋常的方式為容器中的元素分配存儲空間葱色，同時也為某些算法執(zhí)行期間產生的臨時對象提供機制臂痕；<memory>中的主要部分是模板類allocator润努，它負責產生所有容器中的默認分配器貌矿。

對于之前不太了解STL的讀者來說，上面的文字只是十分概括地描述了一下STL的框架览效，對您理解STL的機制乃至使用STL所起到的幫助微乎甚微却舀，這不光是因為深入STL需要對C++的高級應用有比較全面的了解，更因為STL的三個部分算法朽肥、容器和迭代器三部分是互相牽制或者說是緊密結合的禁筏。從概念上講最基礎的部分是迭代器，可是直接學習迭代器會遇到許多抽象枯燥和繁瑣的細節(jié)衡招，然而不真正理解迭代器又是無法直接進入另兩部分的學習的（至少對剖析源碼來說是這樣）篱昔。可以說始腾，適應STL處理問題的方法是需要花費一定的時間的州刽，但是以此為代價，STL取得了一種十分可貴的獨立性浪箭，它通過迭代器能在盡可能少地知道某種數據結構的情況下完成對這一結構的運算穗椅，所以下決心鉆研STL的朋友們千萬不要被一時的困難擊倒。其實STL運用的模式相對統(tǒng)一奶栖，只要適應了它匹表，從一個STL工具到另一個工具，都不會有什么大的變化宣鄙。

對于STL的使用袍镀，也普遍存在著兩種觀點。第一種認為STL的最大作用在于充當經典的數據結構和算法教材冻晤，因為它的源代碼涉及了許多具體實現方面的問題苇羡。第二種則認為STL的初衷乃是為了簡化設計，避免重復勞動鼻弧，提高編程效率设江，因此應該是“應用至上”的，對于源代碼則不必深究攘轩。筆者則認為分析源代碼和應用并不矛盾叉存，通過分析源代碼也能提高我們對其應用的理解，當然根據具體的目的也可以有不同的側重度帮。

三鹉胖、50條忠告

1. 把C++當成一門新的語言學習；
2. 看《Thinking In C++》，不要看《C++變成死相》甫菠；
3. 看《The C++ Programming Language》和《Inside The C++ Object Model》，不要因為他們很難而我們自己是初學者所以就不看冕屯；
4. 不要被VC寂诱、BCB、BC安聘、MV痰洒、TC等詞匯所迷惑——他們都是集成開發(fā)環(huán)境，而我們要學的是一門語言浴韭；
5. 不要放過任何一個看上去很簡單的小編程問題——他們往往并不那么簡單丘喻，或者可以引申出很多知識點；
6. 會用Visual C++念颈，并不說明你就會C++泉粉；
7. 學class并不難，template榴芳、STL嗡靡、generic programming也不過如此——難的是長期堅持實踐和不遺余力的博覽群書；
8. 如果不是天才的話窟感，想學編程就不要想玩游戲——你以為你做到了讨彼，其實你的C++水平并沒有和你通關的能力一起變高——其實可以時刻記住：學習C++是為了編游戲的柿祈；
9. 看Visual C++的樹哈误，是學不了C++語言的；
10. 把時髦的技術掛在嘴邊躏嚎，還不如把過時的技術記在心里蜜自；
11. 學習編程最好的方法之一就是閱讀源代碼；
12. 在任何時刻都不要認為自己手中的書已經足夠了紧索；
13. 請閱讀《The Standard C++ Bible》（中文版：標準C++寶典）袁辈，掌握C++標準；
14. 看得懂的書珠漂，請仔細看晚缩；看不懂的書，請硬著頭皮看媳危；
15. 別指望看一遍書就能記住和掌握什么——請看第二遍荞彼、第三遍。待笑。鸣皂。；
16. 請看《Effective C++》和《More Effective C++》以及《Exceptional C++》；
17. 不要停留在集成開發(fā)環(huán)境的搖籃上寞缝，要學會控制集成開發(fā)環(huán)境癌压，還要學會用命令行方式處理程序；
18. 和別人一起討論有意義的C++知識點荆陆，而不是真吵XX行不行或者YY與ZZ哪個好滩届；
19. 請看《程序設計實踐》，并嚴格的按照其要求去做被啼；
20. 不要因為C和C++中有一些語法和關鍵字看上去相同帜消，就認為它們的意義和作用完全一樣；
21. C++絕不是所謂的C的“擴充”——如果C++一開始就起名叫Z語言浓体，你一定不會把C和Z語言聯系得那么緊密泡挺；
22. 請不要認為學過XX語言再改學C++會有什么問題——你只不過又在學一門全新的語言而已；
23. 讀完了《Inside The C++ Object Model》以后再來認定自己是不是已經學會了C++命浴；
24. 學習編程的秘訣是：編程娄猫、編程、再編程咳促；
25. 請留意下列書籍：《C++面向對象高效編程（C++ Effective Object-Oriented Software Construction）》稚新、《面向對象軟件構造（Object-Oriented Software Construction）》、《設計模式（Design Patterns）》跪腹、《The Art of Computer Programming》褂删；
26. 請把書上的程序例子親手輸入到電腦上實踐，即使配套光盤中有源代碼冲茸；
27. 把在書上看到的有意義的例子擴充屯阀；
28. 請重視C++中的異常處理技術，并將其切實的運用到自己的程序中轴术；
29. 經衬阉ィ回顧自己以前寫過的程序，并嘗試重寫逗栽，把自己學到的新知識運用進去盖袭；
30. 不要漏掉書中任何一個練習題——請全部做完并記錄下解題思路；
31. C++語言和C++的集成開發(fā)環(huán)境要同時學習和掌握彼宠；
32. 既然決定了學習C++鳄虱，就請堅持下去，因為學習程序設計語言的目的是掌握程序設計技術凭峡，而程序設計技術是跨語言的拙已；
33. 就讓C++語言的各種平臺和開發(fā)環(huán)境去激烈競爭把，我們要以學習C++語言本身為主摧冀；
34. 當你寫C++程序寫到一半卻發(fā)現自己用的方法很拙劣時倍踪，請不要馬上停手系宫；請盡快將余下的部分初略的完成以保證這個設計的完整性，然后分析自己的錯誤并重新設計和編寫建车；
35. 別心急扩借，設計C++的class確實不容易；自己程序中的class和自己的class設計水平是在不斷的編程實踐中完善和發(fā)展的癞志；
36. 決不要因為程序“很小”就不遵循某些你不熟悉的規(guī)則——好習慣是培養(yǎng)出來的往枷，而不是一次性記住的；
37. 每學到一個C++難點的時候凄杯，嘗試著對別人講解這個知識點并讓他理解——你能講清楚才說明你真的理解了；
38. 記錄下在和別人交流時發(fā)現的自己忽視或不理解的知識點秉宿；
39. 請不斷的對自己寫的程序提出更高的要求戒突，哪怕你的程序版本號會變成Version 100.xxx；
40. 保存好你寫過的所有的程序——那是你最好的積累之一描睦；
41. 請不要做浮躁的人膊存；
42. 請熱愛C++。

四忱叭、C++頭文件

4.1 傳統(tǒng)C++

#include <assert.h>　　　　設定插入點
#include <ctype.h>　　　　字符處理
#include <errno.h>　　　　 定義錯誤碼
#include <float.h>　　　　浮點數處理
#include <fstream.h>　　　文件輸入／輸出
#include <iomanip.h>　　　 參數化輸入／輸出
#include <iostream.h>　　　數據流輸入／輸出
#include <limits.h>　　　　定義各種數據類型最值常量
#include <locale.h>　　　　定義本地化函數
#include <math.h>　　　　　定義數學函數
#include <stdio.h>　　　　定義輸入／輸出函數
#include <stdlib.h>　　　　定義雜項函數及內存分配函數
#include <string.h>　　　　字符串處理
#include <strstrea.h>　　　基于數組的輸入／輸出
#include <time.h>　　　　　定義關于時間的函數
include <wchar.h>　　　　 寬字符處理及輸入／輸出
include <wctype.h>　　　　寬字符分類

4.2 標準 C++

#include <algorithm>　　　  通用算法
#include <bitset>　　　　　 位集容器
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>　　　　 復數類
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>　　　　　 雙端隊列容器
#include <exception>　　　 異常處理類
#include <fstream>
#include <functional>　　　 定義運算函數（代替運算符）
#include <limits>
#include <list>　　　　　　 線性列表容器
#include <map>　　　　　　 映射容器
#include <iomanip>
#include <ios>　　　　　　基本輸入／輸出支持
#include <iosfwd>　　　　輸入／輸出系統(tǒng)使用的前置聲明
#include <iostream>
#include <istream>　　　　 基本輸入流
#include <ostream>　　　　 基本輸出流
#include <queue>　　　　　  隊列容器
#include <set>　　　　　　 集合容器
#include <sstream>　　　　 基于字符串的流
#include <stack>　　　　　 堆棧容器
#include <stdexcept>　　　 標準異常類
#include <streambuf>　　　底層輸入／輸出支持
#include <string>　　　　　字符串類
#include <utility>　　　　 通用模板類
#include <vector>　　　　 動態(tài)數組容器
#include <cwchar>
#include <cwctype>

4.3 C99增加

#include <complex.h>　　復數處理
#include <fenv.h>　　　　浮點環(huán)境
#include <inttypes.h>　　整數格式轉換
#include <stdbool.h>　　 布爾環(huán)境
#include <stdint.h>　　　整型環(huán)境
#include <tgmath.h>　　通用類型數學宏

想了解更多有關嵌入式Linux驅動隔崎、應用、常用開源庫韵丑、框架爵卒、模式、重構等相關相關的主題內容撵彻，請長安下面圖片钓株，關注我的公眾號（只有技術干貨分享，不拉稀擺帶陌僵！）轴合。

image