STL[模板庫]

STL是Standard Template Library的簡稱，中文名標準模板庫，惠普實驗室開發的一系列軟體的統稱。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普實驗室工作時所開發出來的。從根本上說，STL是一些“容器”的集合，這些“容器”有list,vector,set,map等，STL也是算法和其他一些組件的集合。這裡的“容器”和算法的集合指的是世界上很多聰明人很多年的傑作。STL的目的是標準化組件，這樣就不用重新開發，可以使用現成的組件。STL現在是C++的一部分，因此不用安裝額外的庫檔案。 STL的版本很多，常見的有HP STL、PJ STL、 SGI STL等。 在C++標準中，STL被組織為下面的13個頭檔案：、、、、、、、、、、、、、、、和。

組成部分

STL可分為容器(containers)、疊代器(iterators)、空間配置器(allocator)、配接器(adapters)、算法(algorithms)、仿函式(functors)六個部分。

容器

在實際的開發過程中，數據結構本身的重要性不會遜於操作於數據結構的算法的重要性，當程式中存在著對時間要求很高的部分時，數據結構的選擇就顯得更加重要。

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

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

序列式容器

向量(vector) 連續存儲的元素<vector>

列表(list) 由節點組成的雙向鍊表，每個結點包含著一個元素<list>

雙端佇列(deque) 連續存儲的指向不同元素的指針所組成的數組<deque>

適配器容器

棧(stack) 後進先出(LIFO)的值的排列 <stack>

佇列(queue) 先進先出(FIFO)的值的排列 <queue>

優先佇列(priority_queue) 元素的次序是由作用於所存儲的值對上的某種謂詞決定的的一種佇列 <queue>

關聯式容器

集合(set) 由節點組成的紅黑樹，每個節點都包含著一個元素，節點之間以某種作用於元素隊的謂詞排列，沒有兩個不同的元素能夠擁有相同的次序 <set>

多重集合(multiset) 允許存在兩個次序相等的元素的集合 <set>

映射(map) 由{鍵，值}對組成的集合，以某種作用於鍵對上的謂詞排列 <map>

多重映射(multimap) 允許鍵對有相等的次序的映射 <map>

疊代器

下面要說的疊代器從作用上來說是最基本的部分，可是理解起來比前兩者都要費力一些（至少筆者是這樣）。軟體設計有一個基本原則，所有的問題都可以通過引進一個間接層來簡化，這種簡化在STL中就是用疊代器來完成的。概括來說，疊代器在STL中用來將算法和容器聯繫起來，起著一種黏和劑的作用。幾乎STL提供的所有算法都是通過疊代器存取元素序列進行工作的，每一個容器都定義了其本身所專有的疊代器，用以存取容器中的元素。

疊代器部分主要由頭檔案<utility>,<iterator>和<memory>組成。<utility>是一個很小的頭檔案，它包括了貫穿使用在STL中的幾個模板的聲明，<iterator>中提供了疊代器使用的許多方法，而對於<memory>的描述則十分的困難，它以不同尋常的方式為容器中的元素分配存儲空間，同時也為某些算法執行期間產生的臨時對象提供機制,<memory>中的主要部分是模板類allocator，它負責產生所有容器中的默認分配器。

算法

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

STL提供了大約100個實現算法的模版函式，比如算法for_each將為指定序列中的每一個元素調用指定的函式，stable_sort以你所指定的規則對序列進行穩定性排序等等。這樣一來，只要我們熟悉了STL之後，許多代碼可以被大大的化簡，只需要通過調用一兩個算法模板，就可以完成所需要的功能並大大地提升效率。

算法部分主要由頭檔案<algorithm>，<numeric>和<functional>組成。<algorithm>是所有STL頭檔案中最大的一個（然而它很好理解），它是由一大堆模版函式組成的，可以認為每個函式在很大程度上都是獨立的，其中常用到的功能範圍涉及到比較、交換、查找、遍歷操作、複製、修改、移除、反轉、排序、合併等等。<numeric>體積很小，只包括幾個在序列上面進行簡單數學運算的模板函式，包括加法和乘法在序列上的一些操作。<functional>中則定義了一些模板類，用以聲明函式對象。