1. C/C++與STL
1.1. 什麼是STL？
STL -- 資料結構和算法的分離，模闆（GP）；
STL的一個重要特點是資料結構和算法的分離。盡管這是個簡單的概念，但這種分離确實使得STL變得非常通用。例如，由于STL的sort()函數是完全通用的，你可以用它來操作幾乎任何資料集合，包括連結清單，容器和數組；
STL另一個重要特性是它不是面向對象的。為了具有足夠通用性，STL主要依賴于模闆而不是封裝，繼承和虛函數（多态性）——OOP的三個要素。你在STL中找不到任何明顯的類繼承關系。這好像是一種倒退，但這正好是使得STL的元件具有廣泛通用性的底層特征。另外，由于STL是基于模闆，内聯函數的使用使得生成的代碼短小高效；
STL（Standard Template Library），即标準模闆庫，是一個具有工業強度的，高效的C++程式庫。它被容納于C++标準程式庫（C++ Standard Library）中，是ANSI/ISO C++标準中最新的也是極具革命性的一部分。該庫包含了諸多在計算機科學領域裡所常用的基本資料結構和基本算法。為廣大C++程式員們提供了一個可擴充的應用架構，高度展現了軟體的可複用性。這種現象有些類似于Microsoft Visual C++中的MFC（Microsoft Foundation Class Library），或者是Borland C++ Builder中的VCL(Visual Component Library)；
從邏輯層次來看，在STL中展現了泛型化程式設計的思想（generic programming），引入了諸多新的名詞，比如像需求（requirements），概念（concept），模型（model），容器（container），算法（algorithmn），疊代子（iterator）等。與OOP（object-oriented programming）中的多态（polymorphism）一樣，泛型也是一種軟體的複用技術；
從實作層次看，整個STL是以一種類型參數化（type parameterized）的方式實作的，這種方式基于一個在早先C++标準中沒有出現的語言特性--模闆（template）。如果查閱任何一個版本的STL源代碼，你就會發現，模闆作為構成整個STL的基石是一件千真萬确的事情。除此之外，還有許多C++的新特性為STL的實作提供了友善；
1.2. Hello World!
先從經典的Hello World來引入C與C++的不同：
C語言：
1: //C Hello World Demo. 2: // 3: #include "stdio.h" 4: 5: int main(void) 6: { 7: printf("Hello World!\n"); 8: return 0; 9: } C++語言：
1: //C++ Hello World Demo. 2: // 3: #include <iostream> 4: 5: int main(void) 6: { 7: std::cout<< "Hello World!" << std::endl; 8: return 0; 9: } C标準函數庫中 printf 的函數定義： int __cdecl printf(_In_z_ _Printf_format_string_ const char * _Format, ...); （面向過程）
C++标準庫中的 cout 對象定義： extern ostream cout; （面向對象）
任何一門程式設計語言，基本都包括兩大部分：核心的語言環境 + 常用的資料結構和算法（庫）；（算法+資料結構=程式）
1.3. C++标準庫
作為C++，其标準庫包括以下内容：
（1）C标準函數庫，基本保持了與原有C語言程式庫的良好相容，盡管有些微變化。人們總會忍不住留戀過去的美好歲月，如果你曾經是一個C程式員，對這一點一定體會頗深。或許有一點會讓你覺得奇怪，那就是在C++标準庫中存在兩套C的函數庫，一套是帶有.h擴充名的（比如<stdio.h>），而另一套則沒有（比如<cstdio>）。它們确實沒有太大的不同。
（2）語言支援（language support）部分，包含了一些标準類型的定義以及其他特性的定義，這些内容，被用于标準庫的其他地方或是具體的應用程式中。
診斷（diagnostics）部分，提供了用于程式診斷和報錯的功能，包含了異常處理（exception handling），斷言（assertions），錯誤代碼（error number codes）三種方式。
（3）診斷（diagnostics）部分，提供了用于程式診斷和報錯的功能，包含了異常處理（exception handling），斷言（assertions），錯誤代碼（error number codes）三種方式。
（4）通用工具（general utilities）部分，這部分内容為C++标準庫的其他部分提供支援，當然你也可以在自己的程式中調用相應功能。比如：動态記憶體管理工具，日期/時間處理工具。記住，這裡的内容也已經被泛化了（即采用了模闆機制）。
（5）字元串（string）部分，用來代表和處理文本。它提供了足夠豐富的功能。事實上，文本是一個string對象，它可以被看作是一個字元序列，字元類型可能是char，或者wchar_t等等。string可以被轉換成 char*類型，這樣便可以和以前所寫的C/C++代碼和平共處了。因為那時侯除了char*，沒有别的。
（6）國際化（internationalization）部分，作為OOP特性之一的封裝機制在這裡扮演着消除文化和地域差異的角色，采用locale和facet可以為程式提供衆多國際化支援，包括對各種字元集的支援，日期和時間的表示，數值和貨币的處理等等。畢竟，在中國和在美國，人們表示日期的習慣是不同的。
（7）容器（containers）部分，STL的一個重要組成部分，涵蓋了許多資料結構，比如前面曾經提到的連結清單，還有：vector（類似于大小可動态增加的數組）、queue（隊列）、stack（堆棧）……。string也可以看作是一個容器，适用于容器的方法同樣也适用于string。現在你可以輕松的完成資料結構課程的家庭作業了。
（8）算法（algorithms）部分，STL的一個重要組成部分，包含了大約 70個通用算法，用于操控各種容器，同時也可以操控内建數組。比如：find用于在容器中查找等于某個特定值的元素，for_each用于将某個函數應用到容器中的各個元素上，sort用于對容器中的元素排序。所有這些操作都是在保證執行效率的前提下進行的，是以，如果在你使用了這些算法之後程式變得效率底下，首先一定不要懷疑這些算法本身，仔細檢查一下程式的其他地方。
（9）疊代器（iterators）部分，STL的一個重要組成部分，如果沒有疊代器的撮合，容器和算法便無法結合的如此完美。事實上，每個容器都有自己的疊代器，隻有容器自己才知道如何通路自己的元素。它有點像指針，算法通過疊代器來定位和操控容器中的元素。
（10）數值（numerics）部分，包含了一些數學運算功能，提供了複數運算的支援。
（11）輸入/輸出（input/output）部分，就是經過模闆化了的原有标準庫中的iostream部分，它提供了對C++程式輸入輸出的基本支援。在功能上保持了與原有iostream的相容，并且增加了異常處理的機制，并支援國際化（internationalization）。
總體上，在C++标準函數庫中，STL主要包含了容器、算法、疊代器。string也可以算做是STL的一部分。
簡單來講，STL是作為C++标準庫的一部分存在的（據統計，STL的代碼占到了整個C++标準庫德80%）；
STL用到了C++中的模闆機制（泛型程式設計的思想）、函數重載、命名空間等特性，從其誕生的過程來看，STL與C++可以說是相輔相成的；
STL的背後蘊含着泛型化程式設計（GP）的思想，在這種思想裡，大部分基本算法被抽象，被泛化，獨立于與之對應的資料結構，用于以相同或相近的方式處理各種不同情形。這一思想和面向對象的程式設計思想（OOP）不盡相同，因為，在OOP中更注重的是對資料的抽象，即所謂抽象資料類型（Abstract Data Type），而算法則通常被附屬于資料類型之中。幾乎所有的事情都可以被看作類或者對象（即類的執行個體），通常，我們所看到的算法被作為成員函數（member function）包含在類（class）中，類和類則構成了錯綜複雜的繼承體系。
2. 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 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++标準中不可或缺的一大部件；
STL的不同實作版本：HP STL，P. J. Plauger STL，Rouge Wave STL，SGI STL，STLport；
HP STL是所有其它STL實作版本的根源。它是STL之父Alexander Stepanov在惠普的Palo Alto實驗室工作時，和Meng Lee共同完成的，是第一個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）；
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++語言标準的支援還算不錯，使其表現在一定程度上得以改善。此外，其源代碼的可讀性較好；
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平台上的性能相當出色；
STLport最初源于俄國人Boris Fomitchev的一個開發項目，主要用于将SGI STL的基本代碼移植到其他諸如C++Builder或者是Visual C++這樣的主流編譯器上。因為SGI STL屬于開放源碼，是以STLport才有權這樣做；
3. STL内容介紹
STL體系結構如下：
STL中六大元件：
1）容器（Container），是一種資料結構，如list，vector，和deques ，以模闆類的方法提供。為了通路容器中的資料，可以使用由容器類輸出的疊代器；
2）疊代器（Iterator），提供了通路容器中對象的方法。例如，可以使用一對疊代器指定list或vector中的一定範圍的對象。疊代器就如同一個指針。事實上，C++的指針也是一種疊代器。但是，疊代器也可以是那些定義了operator*()以及其他類似于指針的操作符地方法的類對象；
3）算法（Algorithm），是用來操作容器中的資料的模闆函數。例如，STL用sort()來對一個vector中的資料進行排序，用find()來搜尋一個list中的對象，函數本身與他們操作的資料的結構和類型無關，是以他們可以在從簡單數組到高度複雜容器的任何資料結構上使用；
4）仿函數（Function object）
5）疊代擴充卡（Adaptor）
6）空間配制器（allocator）
1. C/C++與STLC++标準模闆庫(STL)—簡介1. C/C++與STL2. STL的曆史3. STL内容介紹4. STL使用示例 3.1. STL容器
（1）序列式容器（Sequence containers），每個元素都有固定位置－－取決于插入時機和地點，和元素值無關，vector、deque、list；
Vectors：将元素置于一個動态數組中加以管理，可以随機存取元素（用索引直接存取），數組尾部添加或移除元素非常快速。但是在中部或頭部安插元素比較費時；
Deques：是“double-ended queue”的縮寫，可以随機存取元素（用索引直接存取），數組頭部和尾部添加或移除元素都非常快速。但是在中部或頭部安插元素比較費時；
Lists：雙向連結清單，不提供随機存取（按順序走到需存取的元素，O(n)），在任何位置上執行插入或删除動作都非常迅速，内部隻需調整一下指針；
（2）關聯式容器（Associated containers），元素位置取決于特定的排序準則，和插入順序無關，set、multiset、map、multimap；
Sets/Multisets：内部的元素依據其值自動排序，Set内的相同數值的元素隻能出現一次，Multisets内可包含多個數值相同的元素，内部由二叉樹實作，便于查找；
Maps/Multimaps：Map的元素是成對的鍵值/實值，内部的元素依據其值自動排序，Map内的相同數值的元素隻能出現一次，Multimaps内可包含多個數值相同的元素，内部由二叉樹實作，便于查找；
容器的比較：
| Vector | Deque | List | Set | MultiSet | Map | MultiMap | |
| 内部結構 | dynamic array | array of arrays | double linked list | binary tree | binary tree | binary tree | binary tree |
| 随機存取 | Yes | Yes | No | No | No | Yes(key) | No |
| 搜尋速度 | 慢 | 慢 | 很慢 | 快 | 快 | 快 | 快 |
| 快速插入移除 | 尾部 | 首尾 | 任何位置 | -- | -- | -- | -- |
疊代器的作用：能夠讓疊代器與算法不幹擾的互相發展，最後又能無間隙的粘合起來，重載了*，＋＋，＝＝，！＝，＝運算符。用以操作複雜的資料結構，容器提供疊代器，算法使用疊代器；
3.2 STL疊代器
疊代器作用：
（1）能夠讓疊代器與算法不幹擾的互相發展，最後又能無間隙的粘合起來；
（2）重載了＊，＋＋，＝＝，！＝，＝運算符。用以操作複雜的資料結構；
（3）容器提供疊代器，算法使用疊代器；
簡單例子：
疊代器的分類：
Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator, Random access Iterator等；
不同容器提供自己的疊代器，是以不同疊代器具有不同的能力；
不同的算法需要不同的疊代器的能力；相同的算法需要根據疊代器的能力不同而做相應的優化；
3.3 STL算法
STL算法部分主要由頭檔案<algorithm>, <numeric>, <functional>組成；要使用STL中的算法函數必須包含頭檔案<algorithm>，對于數值算法須包含<numeric>，<functional>中則定義了一些模闆類，用來聲明函數對象；
STL中算法大緻分為四類：
非可變序列算法：指不直接修改其所操作的容器内容的算法。
可變序列算法：指可以修改它們所操作的容器内容的算法。
排序算法：包括對序列進行排序和合并的算法、搜尋算法以及有序序列上的集合操作。
數值算法：對容器内容進行數值計算。
查找算法(13個)：判斷容器中是否包含某個值；
adjacent_find：在iterator對辨別元素範圍内，查找一對相鄰重複元素，找到則傳回指向這對元素的第一個元素的Forward Iterator；否則傳回last；
binary_search：在有序序列中查找value，找到傳回true。重載的版本實用指定的比較函數對象或函數指針來判斷相等；
count：利用等于操作符，把标志範圍内的元素與輸入值比較，傳回相等元素個數；
count_if：利用輸入的操作符，對标志範圍内的元素進行操作，傳回結果為true的個數；
equal_range：功能類似equal，傳回一對iterator，第一個表示lower_bound，第二個表示upper_bound；
其他：find，find_end，find_first_of，find_if，lower_bound，upper_bound，search，search_n；
排序和通用算法(14個)：提供元素排序政策；
inplace_merge：合并兩個有序序列，結果序列覆寫兩端範圍。重載版本使用輸入的操作進行排序；
merge：合并兩個有序序列，存放到另一個序列。重載版本使用自定義的比較；
nth_element：将範圍内的序列重新排序，使所有小于第n個元素的元素都出現在它前面，而大于它的都出現在後面。重載版本使用自定義的比較操作；
partial_sort：對序列做部分排序，被排序元素個數正好可以被放到範圍内。重載版本使用自定義的比較操作；
partial_sort_copy：與partial_sort類似，不過将經過排序的序列複制到另一個容器；
其他：partition，random_shuffle，reverse，reverse_copy，rotate， rotate_copy，sort，stable_sort，stable_partition；
删除和替換算法(15個)；
排列組合算法(2個)：提供計算給定集合按一定順序的所有可能排列組合；
算術算法(4個)；
生成和異變算法(6個)；
關系算法(8個)；
集合算法(4個)；
堆算法(4個)；
4. STL使用示例
待續…
5. 參考文檔
（1）C++ STL 快速入門 http://morningspace.51.net/resource/stlintro/stlintro.html
（2）三十分鐘掌握STL http://net.pku.edu.cn/~yhf/UsingSTL.htm