一、相關介紹
STL
- 標準模板庫
- 在編寫代碼的過程中有一些程序經常會被用到，而且需求特別穩定，所以C++中把這些常用的模板做了統一的規范，慢慢的就形成了STL
- 提供三種類型的組件:?容器、迭代器和算法，它們都支持泛型程序設計標準
容器
- 順序容器（vector、list、deque）：通過元素在容器中的位置順序存儲和訪問元素
- 關聯容器（set、map、multiset、multimap）：通過鍵（
Key）存儲和讀取元素 - 容器適配器（stack、queue、priority_queue）
迭代器
- 一種檢查容器內元素并遍歷元素的數據類型
- 每種容器類型都定義了自己的迭代器類型
- 包括：雙向迭代器、隨機迭代器
二、容器
【順序容器】
- 順序容器中元素排列順序與其值無關，而僅僅由元素添加到容器里的次序決定
- 容器內的元素類型必須至少滿足2個條件：可復制和可賦值
- 所有的迭代器范圍都是左閉右開區間，［beg，end） 包括beg，但不包括end
標準庫定義了三種順序容器：vector，list和deque。
vector——連續存儲的元素，單向的
list——由節點組成的不連續存儲的雙向鏈表
deque——連續存儲的元素，雙向的
它們的區別在于訪問元素的方式，以及添加或刪除元素相關操作的運行代價。
如下圖：
【關聯容器】
- 獨特之處在于支持鍵的使用
- 支持通過鍵來高效地查找和讀取元素
標準庫定義了兩種關聯容器：set，map
set——僅含一個鍵，并有效地支持關于某個鍵是否存在的查詢
map——元素以鍵-值（key-value）對的形式組織：鍵用作元素在map中的索引，而值則表示所存儲和讀取的元素
一般來說，如果希望有效的存儲不同值的集合，那么set容器比較合適，而map容器則更適用于需要存儲（乃至修改）每個鍵所關聯值的情況。
在做某種文本處理時，可使用set保存要忽略的單詞。而字典則是map的一種很好的應用：單詞本身是鍵，而它的解釋說明則是值。
map和set類型的對象所包含的元素都具有不同的鍵，不允許同一個鍵添加第二個元素。如果一個鍵必須對應多個實例，則需要使用multimap和multiset類型。
【容器適配器】
- 不是第一類容器
- 沒有提供與元素的保存形式有關的真正數據結構實現
- 適配器都是建立在某個順序容器之上的
- 適配器不支持迭代器
- 優點：能夠使程序員選擇一種合適的底層數據結構
STL提供了三種容器適配器：stack,queue,priority_queue。
statck——可以建立在vector,list,deque任何一種容器之上
queue——要求關聯容器提供front操作，所以只有list和deque滿足
priority_queue——要求提供隨機訪問功能 ，所有只有vector和deque滿足
- stack類允許在底層數據結構的一端執行插入和刪除操作（先入后出）。堆棧能夠用任何順序容器實現：vector、list、deque。
- queue類允許在底層數據結構的末尾插入元素，也允許從前面插入元素（先入先出）。隊列能夠用STL數據結構的list和deque實現，默認情況下是用deque實現的。
- priority_queue類，能夠按照有序的方式在底層數據結構中執行插入操作，也能從底層數據結構的前面執行刪除操作。priority_queue能夠用STL的序列容器vector和deque實現。默認情況下使用vector作為底層容器的。當元素添加到priority_queue時，它們按優先級順序插入。這樣，具有最高優先級的元素，就是從priority_queue中首先被刪除的元素。通常這是利用堆排序來實現的。堆排序總是將最大值（即優先級最高的元素）放在數據結構的前面。這種數據結構稱為（heap）。
?
三、迭代器
?
一、迭代器的變化
和vector、list不同，set、map都是關聯式容器。set內部是基于紅黑樹實現的。插入和刪除操作效率較高，因為只需要修改相關指針而不用進行數據的移動。?
在進行數據刪除操作后，迭代器會不會失效呢？刪除set的數據時，實際的操作是刪除紅黑樹中的一個節點，然后相關指針做相關調整。指向其他元素的迭代器還是指向原位置，并沒有改變，所以刪除一個節點后其他迭代器不會失效。list和map也是同樣的道理。然而刪除vector中的某個元素，vector中其他迭代器會失效，因為vector是基于數組的，刪除一個元素后，后面的元素會往前移動，所以指向后面元素的迭代器會失效。?
二、迭代器的實現
迭代器是一個對象，vector的迭代器是封裝了數組下標；list、map、set的迭代器是封裝了元素節點的指針。?
還有一點，從數學層面，set的一個集合，好比一個袋子里面裝了好多個小球。但是紅黑樹是一種特殊的二叉搜索樹，set中的元素根據其值的大小在紅黑樹中有特定的位置，是不可移動的。所以，1是search操作效率會很高O(log n)，2是set中元素的值不可改變。
?
【小問題】
set是基于紅黑樹實現的，那么set的迭代器begin()、end()是指向哪里的呢？?
一個測試程序：
#include<iostream>
#include<set>
using namespace std;
int main(){set<int> myset;myset.insert(4);myset.insert(7);myset.insert(2);myset.insert(0);myset.insert(4);set<int>::iterator it;for(it = myset.begin(); it != myset.end(); it++){cout<< *it; //輸出結果是：0247}
}
紅黑樹首先是二叉搜索樹，所以begin()迭代器指向紅黑樹的最左邊的節點，end()迭代器指向紅黑樹的最右邊的節點。另外這個小程序還說明了重復插入無效。
?
(1)STL中迭代器容器中都要注意的地方(vector中已經提到)：
1）任何時候同時使用兩個迭代器產生的將會是一個前閉后開的區間(具體見插入和刪除的例子)
2）begin()指向的是vec中的第0個元素，而end是指向最后一個元素的后面一個位置（不是最后一個元素）
3）迭代器的時效性，如果一個迭代器所指向的內容已經被刪除，而后又使用該迭代器的話，會造成意想不到的后果
(2)list的迭代器是雙向迭代器(只能++?? --，沒有偏移功能)而不是像vector那樣的隨機迭代器(和指針幾乎一樣的所有功能)
在list中，由于其內存是非連續的，因此不能像vector那樣，用[]操作符取值，只能用迭代器。
(3)list和vector的區別，本質區別：list是鏈式存儲，vector在內存中是連續區別的，有本質區別而導致下面區別
1）list不支持隨機訪問(2)中已經說明,vector可以像數組那樣使用平[]訪問元素，而list是不可以的
2) list的插入和刪除效率很高，所以list有push_front、pop_front、sort而vector中這些操作的效率太低了，所以STL中沒有寫這些功能
與vector相比，list除了有push_back()//在尾部插入 和 insert()之外，還有push_front()//即在鏈表的頭部插入
3）list的一些特有的函數remove、reverse、unique、splice、merge功能(這些連deque中都沒有的)
)
