STL標準容器類簡介

標準容器類	說明
順序性容器
vector	從后面快速的插入與刪除，直接訪問任何元素
deque	從前面或后面快速的插入與刪除，直接訪問任何元素
list	雙鏈表，從任何地方快速插入與刪除
關聯容器
set	快速查找，不允許重復值
multiset	快速查找，允許重復值
map	一對多映射，基于關鍵字快速查找，不允許重復值
multimap	一對多映射，基于關鍵字快速查找，允許重復值
容器適配器
stack	后進先出
queue	先進先出
priority_queue	最高優先級元素總是第一個出列

所有標準庫共有函數

默認構造函數	提供容器默認初始化的構造函數。
復制構造函數	將容器初始化為現有同類容器副本的構造函數
析構函數	不再需要容器時進行內存整理的析構函數
empty	容器中沒有元素時返回true,否則返回false
max_size	返回容器中最大元素個數
size	返回容器中當前元素個數
operator=	將一個容器賦給另一個容器
operator<	如果第一個容器小于第二個容器，返回true，否則返回false，
operator<=	如果第一個容器小于或等于第二個容器，返回true，否則返回false
operator>	如果第一個容器大于第二個容器，返回true，否則返回false
operator>=	如果第一個容器大于或等于第二個容器，返回true，否則返回false
operator==	如果第一個容器等于第二個容器，返回true，否則返回false
operator!=	如果第一個容器不等于第二個容器，返回true，否則返回false
swap	交換兩個容器的元素

其中operator>,operator>=,operator<,operator<=,operator==,operator!=均不適用于priority_queue

順序容器和關聯容器共有函數

begin	該函數兩個版本返回iterator或const_iterator，引用容器第一個元素
end	該函數兩個版本返回iterator或const_iterator,引用容器最后一個元素后面一位
rbegin	該函數兩個版本返回reverse_iterator或const_reverse_iterator,引用容器最后一個元素
rend	該函數兩個版本返回reverse_iterator或const_reverse_iterator，引用容器第一個元素前面一位
erase	從容器中清除一個或幾個元素
clear	清除容器中所有元素

下表顯示了順序容器和關聯容器中常用的typedef，這些typedef常用于變量、參數和函數返回值的一般性聲明。

value_type	容器中存放元素的類型
reference	容器中存放元素類型的引用
const_reference	容器中存放元素類型的常量引用，這種引用只能讀取容器中的元素和進行const操作
pointer	容器中存放元素類型的指針
iterator	指向容器中存放元素類型的迭代器
const_iterator	指向容器中存放元素類型的常量迭代器，只能讀取容器中的元素
reverse_iterator	指向容器中存放元素類型的逆向迭代器，這種迭代器在容器中逆向迭代
const_reverse_iterator	指向容器中存放元素類型的逆向迭代器，只能讀取容器中的元素
difference_type	引用相同容器的兩個迭代器相減結果的類型（list和關聯容器沒有定義operator-）
size_type	用于計算容器中項目數和檢索順序容器的類型（不能對list檢索）

什么是容器

首先，我們必須理解一下什么是容器，在C++?中容器被定義為：在數據存儲上，有一種對象類型，它可以持有其它對象或指向其它對像的指針，這種對象類型就叫做容器。很簡單，容器就是保存其它對象的對象，當然這是一個樸素的理解，這種“對象”還包含了一系列處理“其它對象”的方法，因為這些方法在程序的設計上會經常被用到，所以容器也體現了一個好處，就是“容器類是一種對特定代碼重用問題的良好的解決方案”。

容器還有另一個特點是容器可以自行擴展。在解決問題時我們常常不知道我們需要存儲多少個對象，也就是說我們不知道應該創建多大的內存空間來保存我們的對象。顯然，數組在這一方面也力不從心。容器的優勢就在這里，它不需要你預先告訴它你要存儲多少對象，只要你創建一個容器對象，并合理的調用它所提供的方法，所有的處理細節將由容器來自身完成。它可以為你申請內存或釋放內存，并且用最優的算法來執行您的命令。

容器是隨著面向對象語言的誕生而提出的，容器類在面向對象語言中特別重要，甚至它被認為是早期面向對象語言的基礎。在現在幾乎所有的面向對象的語言中也都伴隨著一個容器集，在C++?中，就是標準模板庫（STL?）。

和其它語言不一樣，C++?中處理容器是采用基于模板的方式。標準C++?庫中的容器提供了多種數據結構，這些數據結構可以與標準算法一起很好的工作，這為我們的軟件開發提供了良好的支持！

通用容器的分類

STL?對定義的通用容器分三類：順序性容器、關聯式容器和容器適配器。

順序性容器?是一種各元素之間有順序關系的線性表，是一種線性結構的可序群集。順序性容器中的每個元素均有固定的位置，除非用刪除或插入的操作改變這個位置。這個位置和元素本身無關，而和操作的時間和地點有關，順序性容器不會根據元素的特點排序而是直接保存了元素操作時的邏輯順序。比如我們一次性對一個順序性容器追加三個元素，這三個元素在容器中的相對位置和追加時的邏輯次序是一致的。

關聯式容器?和順序性容器不一樣，關聯式容器是非線性的樹結構，更準確的說是二叉樹結構。各元素之間沒有嚴格的物理上的順序關系，也就是說元素在容器中并沒有保存元素置入容器時的邏輯順序。但是關聯式容器提供了另一種根據元素特點排序的功能，這樣迭代器就能根據元素的特點“順序地”獲取元素。

關聯式容器另一個顯著的特點是它是以鍵值的方式來保存數據，就是說它能把關鍵字和值關聯起來保存，而順序性容器只能保存一種（可以認為它只保存關鍵字，也可以認為它只保存值）。這在下面具體的容器類中可以說明這一點。

容器適配器?是一個比較抽象的概念，?C++的解釋是：適配器是使一事物的行為類似于另一事物的行為的一種機制。容器適配器是讓一種已存在的容器類型采用另一種不同的抽象類型的工作方式來實現的一種機制。其實僅是發生了接口轉換。那么你可以把它理解為容器的容器，它實質還是一個容器，只是他不依賴于具體的標準容器類型，可以理解是容器的模版。或者把它理解為容器的接口，而適配器具體采用哪種容器類型去實現，在定義適配器的時候可以由你決定。

下表列出STL?定義的三類容器所包含的具體容器類：

順序性容器

向量?vector?：??

是一個線性順序結構。相當于數組，但其大小可以不預先指定，并且自動擴展。它可以像數組一樣被操作，由于它的特性我們完全可以將vector?看作動態數組。
在創建一個vector?后，它會自動在內存中分配一塊連續的內存空間進行數據存儲，初始的空間大小可以預先指定也可以由vector?默認指定，這個大小即capacity?（）函數的返回值。當存儲的數據超過分配的空間時vector?會重新分配一塊內存塊，但這樣的分配是很耗時的，在重新分配空間時它會做這樣的動作：

首先，vector?會申請一塊更大的內存塊；

然后，將原來的數據拷貝到新的內存塊中；

其次，銷毀掉原內存塊中的對象（調用對象的析構函數）；

最后，將原來的內存空間釋放掉。

如果vector?保存的數據量很大時，這樣的操作一定會導致糟糕的性能（這也是vector?被設計成比較容易拷貝的值類型的原因）。所以說vector?不是在什么情況下性能都好，只有在預先知道它大小的情況下vector?的性能才是最優的。

vector?的特點：
(1)?指定一塊如同數組一樣的連續存儲，但空間可以動態擴展。即它可以像數組一樣操作，并且可以進行動態操作。通常體現在push_back() pop_back()?。
(2)?隨機訪問方便，它像數組一樣被訪問，即支持[ ]?操作符和vector.at()
(3)?節省空間，因為它是連續存儲，在存儲數據的區域都是沒有被浪費的，但是要明確一點vector?大多情況下并不是滿存的，在未存儲的區域實際是浪費的。

(4)?在內部進行插入、刪除操作效率非常低，這樣的操作基本上是被禁止的。Vector?被設計成只能在后端進行追加和刪除操作，其原因是vector?內部的實現是按照順序表的原理。
(5)?只能在vector?的最后進行push?和pop?，不能在vector?的頭進行push?和pop?。
(6)?當動態添加的數據超過vector?默認分配的大小時要進行內存的重新分配、拷貝與釋放，這個操作非常消耗性能。?所以要vector?達到最優的性能，最好在創建vector?時就指定其空間大小。

雙向鏈表list

是一個線性鏈表結構，它的數據由若干個節點構成，每一個節點都包括一個信息塊（即實際存儲的數據）、一個前驅指針和一個后驅指針。它無需分配指定的內存大小且可以任意伸縮，這是因為它存儲在非連續的內存空間中，并且由指針將有序的元素鏈接起來。

由于其結構的原因，list?隨機檢索的性能非常的不好，因為它不像vector?那樣直接找到元素的地址，而是要從頭一個一個的順序查找，這樣目標元素越靠后，它的檢索時間就越長。檢索時間與目標元素的位置成正比。

雖然隨機檢索的速度不夠快，但是它可以迅速地在任何節點進行插入和刪除操作。因為list?的每個節點保存著它在鏈表中的位置，插入或刪除一個元素僅對最多三個元素有所影響，不像vector?會對操作點之后的所有元素的存儲地址都有所影響，這一點是vector?不可比擬的。

list?的特點：
(1)?不使用連續的內存空間這樣可以隨意地進行動態操作；
(2)?可以在內部任何位置快速地插入或刪除，當然也可以在兩端進行push?和pop?。
(3)?不能進行內部的隨機訪問，即不支持[ ]?操作符和vector.at()?；
(4)?相對于verctor?占用更多的內存。

雙端隊列deque?
是一種優化了的、對序列兩端元素進行添加和刪除操作的基本序列容器。它允許較為快速地隨機訪問，但它不像vector?把所有的對象保存在一塊連續的內存塊，而是采用多個連續的存儲塊，并且在一個映射結構中保存對這些塊及其順序的跟蹤。向deque?兩端添加或刪除元素的開銷很小。它不需要重新分配空間，所以向末端增加元素比vector?更有效。

實際上，deque?是對vector?和list?優缺點的結合，它是處于兩者之間的一種容器。

deque?的特點：
(1)?隨機訪問方便，即支持[ ]?操作符和vector.at()?，但性能沒有vector?好；
(2)?可以在內部進行插入和刪除操作，但性能不及list?；
(3)?可以在兩端進行push?、pop?；

三者的比較

下圖描述了vector?、list?、deque?在內存結構上的特點：

vector?是一段連續的內存塊，而deque?是多個連續的內存塊，?list?是所有數據元素分開保存，可以是任何兩個元素沒有連續。

vector?的查詢性能最好，并且在末端增加數據也很好，除非它重新申請內存段；適合高效地隨機存儲。

list?是一個鏈表，任何一個元素都可以是不連續的，但它都有兩個指向上一元素和下一元素的指針。所以它對插入、刪除元素性能是最好的，而查詢性能非常差；適合?大量地插入和刪除操作而不關心隨機存取的需求。

deque?是介于兩者之間，它兼顧了數組和鏈表的優點，它是分塊的鏈表和多個數組的聯合。所以它有被list?好的查詢性能，有被vector?好的插入、刪除性能。?如果你需要隨即存取又關心兩端數據的插入和刪除，那么deque?是最佳之選。

關聯容器

set, multiset, map, multimap?是一種非線性的樹結構，具體的說采用的是一種比較高效的特殊的平衡檢索二叉樹——?紅黑樹結構。（至于什么是紅黑樹，我也不太理解，只能理解到它是一種二叉樹結構）

因為關聯容器的這四種容器類都使用同一原理，所以他們核心的算法是一致的，但是它們在應用上又有一些差別，先描述一下它們之間的差別。

set?，又稱集合，實際上就是一組元素的集合，但其中所包含的元素的值是唯一的，且是按一定順序排列的，集合中的每個元素被稱作集合中的實例。因為其內部是通過鏈表的方式來組織，所以在插入的時候比vector?快，但在查找和末尾添加上被vector?慢。

multiset?，是多重集合，其實現方式和set?是相似的，只是它不要求集合中的元素是唯一的，也就是說集合中的同一個元素可以出現多次。

map?，提供一種“鍵-?值”關系的一對一的數據存儲能力。其“鍵”在容器中不可重復，且按一定順序排列（其實我們可以將set?也看成是一種鍵-?值關系的存儲，只是它只有鍵沒有值。它是map?的一種特殊形式）。由于其是按鏈表的方式存儲，它也繼承了鏈表的優缺點。

multimap?， 和map?的原理基本相似，它允許“鍵”在容器中可以不唯一。

關聯容器的特點是明顯的，相對于順序容器，有以下幾個主要特點：

1，?其內部實現是采用非線性的二叉樹結構，具體的說是紅黑樹的結構原理實現的；

2，?set?和map?保證了元素的唯一性，mulset?和mulmap?擴展了這一屬性，可以允許元素不唯一；

3，?元素是有序的集合，默認在插入的時候按升序排列。

基于以上特點，

1，?關聯容器對元素的插入和刪除操作比vector?要快，因為vector?是順序存儲，而關聯容器是鏈式存儲；比list?要慢，是因為即使它們同是鏈式結構，但list?是線性的，而關聯容器是二叉樹結構，其改變一個元素涉及到其它元素的變動比list?要多，并且它是排序的，每次插入和刪除都需要對元素重新排序；

2，?關聯容器對元素的檢索操作比vector?慢，但是比list?要快很多。vector?是順序的連續存儲，當然是比不上的，但相對鏈式的list?要快很多是因為list?是逐個搜索，它搜索的時間是跟容器的大小成正比，而關聯容器?查找的復雜度基本是Log(N)?，比如如果有1000?個記錄，最多查找10?次，1,000,000?個記錄，最多查找20?次。容器越大，關聯容器相對list?的優越性就越能體現；

3，?在使用上set?區別于vector,deque,list?的最大特點就是set?是內部排序的，這在查詢上雖然遜色于vector?，但是卻大大的強于list?。

4，?在使用上map?的功能是不可取代的，它保存了“鍵-?值”關系的數據，而這種鍵值關系采用了類數組的方式。數組是用數字類型的下標來索引元素的位置，而map?是用字符型關鍵字來索引元素的位置。在使用上map?也提供了一種類數組操作的方式，即它可以通過下標來檢索數據，這是其他容器做不到的，當然也包括set?。（STL?中只有vector?和map?可以通過類數組的方式操作元素，即如同ele[1]?方式）

容器適配器

STL?中包含三種適配器：棧stack?、隊列queue?和優先級priority_queue?。

適配器是容器的接口，它本身不能直接保存元素，它保存元素的機制是調用另一種順序容器去實現，即可以把適配器看作“它保存一個容器，這個容器再保存所有元素”。

STL?中提供的三種適配器可以由某一種順序容器去實現。默認下stack?和queue?基于deque?容器實現，priority_queue?則基于vector?容器實現。當然在創建一個適配器時也可以指定具體的實現容器，創建適配器時在第二個參數上指定具體的順序容器可以覆蓋適配器的默認實現。

由于適配器的特點，一個適配器不是可以由任一個順序容器都可以實現的。

棧stack?的特點是后進先出，所以它關聯的基本容器可以是任意一種順序容器，因為這些容器類型結構都可以提供棧的操作有求，它們都提供了push_back?、pop_back?和back?操作；

隊列queue?的特點是先進先出，適配器要求其關聯的基礎容器必須提供pop_front?操作，因此其不能建立在vector?容器上；

優先級隊列priority_queue?適配器要求提供隨機訪問功能，因此不能建立在list?容器上。

vector：

一種隨機訪問的數組類型，他提供了對數組元素的快速、隨機訪問，以及在序列尾部快速、隨機的插入和刪除操作。它在需要時可以改變其大小，也就是說大小可變的向量，比較靈活。可取代C++語言本身提供的傳統數組。提供隨機存儲能力。操作尾端元素的速度最快。由于所有元素占用連續空間，所以一旦進行插入或者刪除動作，有可能使原本的某些 iterators失效。

list:

這是一個雙向鏈表容器，完成了標準的C++數據結構中鏈表的所有功能。它不支持隨機訪問的數組類型，因為STL以雙向鏈表的方式實現list對象，所以訪問鏈表元素要指針從鏈表的某個端點開始。插入和刪除操作所花的時間是固定的，也就是說，list對象插入和刪除一個元素所需要的時間與該元素在鏈表中的位置無關。在任何位置做插入和刪除動作都很快，不像vector只局限于尾端，而deque只局限于兩端才有高效率。由于各元素并不占用連續空間，所以一旦進行插入或者刪除動作，原本的iterators任然有效。注意，許多只在元素搬移的STL algorithms用于list身上會有不佳的效率。幸好這些STL algorithms 都有對應的list member functions 可以替代。后者之所以會有比較好的效率，原因是他們只操作指標，而非真正去拷貝或者移動元素。

queue:

這是一種隊列容器，它采用deque和list對象創建一個先進先出(FIFO)的容器，它實際上完成了標準的C++數據結構中的隊列所有功能。不提供隨機存儲能力。行為與特性都很類似vector，但因為是雙向開口，所以操作兩端元素的速度都很快，不像vectoer只在操作尾端元素時才有高效率。由于所有元素占用連續空間，所以一旦進行插入或者刪除動作，有可能是原本的某些iterators失效。

stack:

這是一種棧容器，完成了標準的C++數據結構中棧的所有功能。也就是說，它通過vector、deque或者list對象創建了一個先進后出的容器。stack特性是先進后出(FILO: First In, Last Out)。

deque:

這是一種隨機訪問的數據類型，提供了在序列兩端快速插入和刪除操作的功能，他可以再需要的時候修改器自身大小。也就是說這是一種雙端隊列容器，完成了標準的C++數據結構中隊列的所有功能。queue特性是先進先出。

priority_queue:

這是一種按值排序的隊列容器。它使用vector或者deque對象創建了一個排序隊列。priority_queue特性是依優先權來誰是下一個元素。

set:

這是一種隨機存取的集合容器。其關鍵詞和數據元素是同一個值，也就是說它不能包含重復的元素。set經過排序的結構體，以某個可指定的排序方式排序，每個元素第一無二。由于已經排序，所以搜尋速度極快。但也因此不允許我們直接修改某個元素的內容，因為這可能會影響排序。修改元素內容的正確的作法是，先將該元素刪除，再加入（此時使用新值）。set通常是以平衡二叉樹(balanced binary tree)來存儲（但并不是強制規定），甚至是以red-black trees來完成。

multiset:

其關鍵詞和數據元素也是同一個值，但和set不同的以及最大的區別在于這是一種允許出現重復元素的集合容器。multiset允許元素重復。

map:

其是一種關聯數組容器，它包含成對數據的容器，其中一個值是實際數據值，另外一個是用來尋找數據的關鍵值，一個特定的關鍵詞只能與一個元素相關聯。map是由一對一對的鍵值（key/value）所組成的排序結構體，鍵值獨一無二。map通常是以balanced binary tree來實現，但并不強制規定。事實上map的內部結構通常與set是一樣的，因此我們可以將set視為一種特殊的map，其鍵值和實值是相同的，所以map和set幾乎擁有完全相同的能力。

multimap:

這是一種允許出現重復關鍵之的關聯數組容器，然而與map對象不同，它的一個關鍵詞可以與多個元素相聯系，multimap允許鍵值重復。

hash table:

這并不是C++ Standard規范內的一容器（因標準委員會作業時間的關系），但是它對于大量數據的搜索而言，很實用也很重要。有許多STL實作品例如SGI都涵蓋了它。通常STL產品廠商會提供4中hash tables: hash_set、hash_multiset、hash_map、hash_multimap。