轉載自 ：http://blog.csdn.net/liguohanhaha/article/details/52089914

1、STL概述

STL提供六大組件，彼此可以組合套用：

STL六大組件的交互關系

一些可能令人困惑的C++語法糖：

泛型指針、原生指針和智能指針

2、迭代器

　　STL的中心思想是：將數據容器和算法分隔開，彼此獨立設計，最后再用黏合劑將它們撮合在一起。容器和算法的泛型化，可以用C++的class template和function template來實現，而二者的黏合劑就是迭代器了。

迭代器是一種智能指針

　　與其說迭代器是一種指針，不如說迭代器是一種智能指針，它將指針進行了一層封裝，既包含了原生指針的靈活和強大，也加上很多重要的特性，使其能發(fā)揮更大的作用以及能更好的使用。迭代器對指針的一些基本操作如*、->、++、==、!=、=進行了重載，使其具有了遍歷復雜數據結構的能力，其遍歷機制取決于所遍歷的數據結構。下面上一段代碼，了解一下迭代器的“智能”：

template<typename T>  class Iterator  {  public:      Iterator& operator++();      //...  PRivate:       T *m_ptr;  };  
　　對于不同的數據容器，以上Iterator類中的成員函數operator++的實現會各不相同，例如，對于數組的可能實現如下：
//對于數組的實現  template<typename T>  Iterator& operator++()  {      ++m_ptr;      retrun *this;  }
　　對于鏈表，它會有一個類似于next的成員函數用于獲取下一個結點，其可能實現如下：
//對于鏈表的實現  template<typename T>  Iterator& operator++()  {     m_ptr = m_ptr->next();//next()用于獲取鏈表的下一個節(jié)點      return *this;  }  
　　iterator首先要對iterator指向對象的實現細節(jié)有非常豐富的了解，所以iterator為了不暴露所指向對象的信息，干脆就將iterator的實現由各個容器的設計者來實現好了。STL將迭代器的實現交給了容器，每種容器都會以嵌套的方式在內部定義專屬的迭代器。各種迭代器的接口相同，內部實現卻不相同，這也直接體現了泛型編程的概念。
迭代器使用示例
#include <iostream>  #include <vector>  #include <list>  #include <algorithm>  using namespace std;int main(int argc, const char *argv[]){    int arr[5] = { 1, 2, 3, 4, 5 };    vector<int> iVec(arr, arr + 5);//定義容器vector      list <int> iList(arr, arr + 5);//定義容器list      //在容器iVec的頭部和尾部之間尋找整形數3      vector<int>::iterator iter1 = find(iVec.begin(), iVec.end(), 3);    if (iter1 == iVec.end())        cout << "3 not found" << endl;    else        cout << "3 found" << endl;    //在容器iList的頭部和尾部之間尋找整形數4      list<int>::iterator iter2 = find(iList.begin(), iList.end(), 4);    if (iter2 == iList.end())        cout << "4 not found" << endl;    else        cout << "4 found" << endl;    system("pause");    return 0;}
　　從上面迭代器的使用中可以看到，迭代器依附于具體的容器，即不同的容器有不同的迭代器實現，同時，我們也看到，對于算法find來說，只要給它傳入不同的迭代器，即可對不同的容器進行查找操作。通過迭代器的穿針引線，有效地實現了算法對不同容器的訪問，這也是迭代器的設計目的。
 
3、序列式容器
　　所謂序列式容器，其中的元素都可序，但未必有序，C++本身內建了一個序列式容器array，STL另外提供了vector、list、deque、stack、queue、priority-queue等序列式容器。其中stack和queue由于只是deque改頭換面而來，技術上被歸為一種配接器 (adapter)。
vector
　　vector采用的數據結構非常簡單：線性連續(xù)空間。它以兩個迭代器start和finish分別指向配置得來的連續(xù)空間中目前已被使用的范圍，并以迭代器end_of_storage指向整塊連續(xù)空間(含備用空間)的尾端。
template <class T, class Alloc = alloc>class vector {    ...protected:    iterator start;    //表示    iterator finish;    iterator end_of_storage;    ...};
 
　　注意：所謂動態(tài)增加大小，并不是在原來空間之后接續(xù)新空間(因為無法保證原空間之后尚有可供分配的空間)，而是以原來大小的的兩倍另外分配一塊較大空間，然后將原內容拷貝過來，然后才開始在原內容之后構造新元素，并釋放原空間。因此，對vector的任何操作，一旦引起空間重新配置，指向原vector的所有迭代器就都失效啦。
 
vector變量的大小分析
　　vector類中有3個迭代器域(也就是指針域)，所以大小至少為12字節(jié)。
測試環(huán)境：Win7 64位 VS2013
測試代碼：
#include <iostream>#include <vector>using namespace std;int main(void){    vector<int> a(5, 0); //16    cout << sizeof(a) << endl;    cout << (int)(void *)&a << endl;    cout << (int)(void *)&a[0] << endl;    cout << (int)(void *)&a[a.size() - 1] << endl;    cout << endl;    cout << *((int *)&a) << endl;    cout << *(((int *)&a) + 1) << endl;    cout << *(((int *)&a) + 2) << endl;    cout << *(((int *)&a) + 3) << endl;    cout << endl;    cout << a.size() << endl;    cout << a.capacity() << endl;    system("pause");    return 0;}
　　測試結果顯示此時vector的大小為16字節(jié)，分別包括start、finish、end_of_storage成員，剩下的4個字節(jié)暫時不知道代表什么意思… :(
測試環(huán)境：Ubuntu12.04 codeblocks10.05
　　測試代碼：
#include <iostream>#include <vector>using namespace std;int main(void){    vector<int> a(5, 0); //12    cout << sizeof(a) << endl;    cout << (int)(void *)&a << endl;    cout << (int)(void *)&a[0] << endl;    cout << (int)(void *)&a[a.size() - 1] << endl;    cout << endl;    cout << *((int *)&a) << endl;    cout << *(((int *)&a) + 1) << endl;    cout << *(((int *)&a) + 2) << endl;    cout << *(((int *)&a) + 3) << endl;    cout << endl;    cout << a.size() << endl;    cout << a.capacity() << endl;    return 0;}
　　測試結果顯示此時vector的大小為12字節(jié)，包括start、finish、end_of_storage成員
小結
　　win和Ubuntu所用的STL的版本是不一樣的，不同的STL所使用的vector類也不同，有著不同的容器管理方式。
list
　　相對于vector的連續(xù)線性空間，list就顯得復雜許多，它的好處就是插入或刪除一個元素，就配置或刪除一個元素空間。對于任何位置的元素的插入或刪除，list永遠是常數時間。
　　list本身和節(jié)點是不同的結構，需要分開設計。以下是STL list的節(jié)點node結構：
template <class T>class __list_node {    typedef void* void_pointer;    void_pointer prev;    void_pointer next;    T data;};
這是一個雙向鏈表
list數據結構
       SGI list不僅是一個雙向鏈表，而且是一個環(huán)狀雙向鏈表。只需一個指針就可遍歷整個鏈表。
deque
　　deque和vector的最大差異，一在于deque允許常數時間內對起頭端進行插入或移除操作，二在于deque沒有所謂容量(capacity)概念，因為它是以分段連續(xù)空間組合而成，隨時可以增加一段新的空間連接起來。
　　deque由一段一段連續(xù)空間組成，一旦有必要在deque的前端或尾端增加新空間，便配置一段連續(xù)空間，串接在整個deque的前端或尾端。deque的最大任務，便是在這些分段的連續(xù)空間上，維護其整體連續(xù)的假象，并提供隨機存取的接口，避開了“重新配置、復制、釋放”的輪回，代價是復雜的迭代器結構。
deque迭代器
　　迭代器首先必須指出分段連續(xù)空間在哪里，其次它必須能夠判斷自己是否已經處在緩沖區(qū)的邊緣，如果是，一旦前進或后退就必須跳躍下一個緩沖區(qū)，為了能夠正常跳躍，deque必須隨時掌握管控中心。
迭代器結構：
template <class T, class Ref, class Ptr, size_t BufSiz>struct __deque_iterator { // 未繼承 std::iterator    // 保持迭代器的連接    T* cur; // 此迭代器所指之緩沖區(qū)的現行（ current）元素    T* first; // 此迭代器所指之緩沖區(qū)的的頭    T* last; // 此迭代器所指之緩沖區(qū)的的尾（含備用空間）    map_pointer node; // 指向管控中心    ...};
　　假如deque中已經包含了20個元素了，緩沖區(qū)大小為8，則內存布局如下：
注意：deque最初狀態(tài)(無任何元素)保有一個緩沖區(qū)，因此，clear()完成之后回到初始狀態(tài)，也一樣會保留一個緩沖區(qū)。
stack
　　tack是一種先進后出(First In Last Out，FILO)的數據結構，它只有一個出口。stack允許增加元素、移除元素、取得最頂端元素。但除了最頂端外，沒有任何其他方法可以存取，stack的其他元素，換言之，stack不允許有遍歷行為。stack默認以deque為底層容器。
queue
　　queue是一種先進先出(First In First Out，FIFO)的數據結構，它有兩個出口，允許增加元素、移除元素、從最底端加入元素、取得最頂端元素。但除了最底端可以加入、最頂端可以取出外，沒有任何其他方法可以存取queue的其他元素，換言之，queue不允許有遍歷行為。queue默認以deque為底層容器。
heap
　　heap并不歸屬于STL容器組件，它是個幕后英雄，扮演prority queue的助手。priority queue允許用戶以任何次序將任何元素推入容器內，但取出時一定是按照優(yōu)先級最高的元素開始取。binary max heap正好具有這樣的特性，適合作為priority queue的底層機制。heap默認建立的是大堆。
heap測試用例：
#include <iostream>#include <queue>#include <algorithm>using namespace std;template <class T>struct display{    void operator()(const T &x)    {        cout << x << " ";    }};/// heap默認為大堆，以下設置為建立小堆template <typename T>struct greator{    bool operator()(const T &x, const T &y)    {        return x > y;    }};int main(void){    int ia[9] = { 0, 1, 2, 3, 4, 8, 9, 3, 5 };    vector<int> ivec(ia, ia + 9);    make_heap(ivec.begin(), ivec.end(), greator<int>()); //注意：此函數調用時，新元素應已止于底部容器的尾端    for_each(ivec.begin(), ivec.end(), display<int>());    cout << endl;    ivec.push_back(7);    push_heap(ivec.begin(), ivec.end(), greator<int>());    for_each(ivec.begin(), ivec.end(), display<int>());    cout << endl;    pop_heap(ivec.begin(), ivec.end(), greator<int>());    cout << ivec.back() << endl;    ivec.pop_back();    for_each(ivec.begin(), ivec.end(), display<int>());    cout << endl;    sort_heap(ivec.begin(), ivec.end(), greator<int>());    for_each(ivec.begin(), ivec.end(), display<int>());    cout << endl;    system("pause");    return 0;}
priority_queue
　　priority_queue是一個擁有權值的queue，它允許加入新元素、移除舊元素、審視元素值等功能。由于是一個queue，所以只允許在底端加入元素，從頂端取出元素，除此之外別無其他存取元素方法。priority_queue內的元素并非按照被推入的順序排列，而是自動按照元素的權值排列。權值最高者排在前面。
　　默認情況下priority_queue利用max-heap按成，后者是一個以vector為底層容器的complate binary tree。
priority_queue測試用例：
#include <iostream>#include <queue>#include <algorithm>using namespace std;int main(void){    int ia[9] = { 0, 1, 2, 3, 4, 8, 9, 3, 5 };    vector<int> ivec(ia, ia + 9);    priority_queue<int> ipq(ivec.begin(), ivec.end());    ipq.push(7);    ipq.push(23);    while (!ipq.empty())    {        cout << ipq.top() << " ";        ipq.pop();    }    cout << endl;    system("pause");    return 0;}
 
4、關聯性容器
　　set和map底層數據結構都是紅黑樹，紅黑樹的data域段為pair<key, value>類型。關于紅黑樹更多知識請點擊：深入理解紅黑樹。
set
　　set的所有元素都會根據元素的鍵值自動排序。set的元素不像map那樣可以同時擁有實值(value)和鍵值(key)，set元素的鍵值就是實值，實值就是鍵值，set不允許有兩個相同的元素。Set元素不能改變，在set源碼中，set<T>::iterator被定義為底層TB-tree的const_iterator，杜絕寫入操作，也就是說，set iterator是一種constant iterators(相對于mutable iterators)
測試用例(讓set從大到小存放元素)：
#include <iostream>#include <set>#include <functional>using namespace std;/// set默認是從小到大排列，以下是讓set從大到小排列template <typename T>struct greator{    bool operator()(const T &x, const T &y)    {        return x > y;    }};int main(void){    set<int, greator<int>> iset;    iset.insert(12);    iset.insert(1);    iset.insert(24);    for (set<int>::const_iterator iter = iset.begin(); iter != iset.end(); iter++)    {        cout << *iter << " ";    }    cout << endl;    system("pause");    return 0;}
map
　　 map的所有元素都會根據元素的鍵值自動排序。map的所有元素都是pair，同時擁有實值(value)和鍵值(key)。pair的第一元素為鍵值，第二元素為實值。map不允許有兩個相同的鍵值。
　　如果通過map的迭代器改變元素的鍵值，這樣是不行的，因為map元素的鍵值關系到map元素的排列規(guī)則。任意改變map元素鍵值都會破壞map組織。如果修改元素的實值，這是可以的，因為map元素的實值不影響map元素的排列規(guī)則。因此，map iterator既不是一種constant iterators，也不是一種mutable iterators。
測試用例(map從大到小存放元素)：
#include <iostream>#include <string>#include <map>#include <functional>using namespace std;/// map默認是從小到大排列，以下是讓map從大到小排列template <typename T>struct greator{    bool operator()(const T x, const T y)    {        return x > y;    }};int main(void){    map<int, string, greator<int>> imap;    imap[3] = "333";    imap[1] = "333";    imap[2] = "333";    for (map<int, string>::const_iterator iter = imap.begin(); iter != imap.end(); iter++)    {        cout << iter->first << ": " << iter->second << endl;    }    system("pause");    return 0;}
multiset/multimap
　　multiset的特性以及用法和set完全相同，唯一的差別在于它允許鍵值重復，因此它的插入操作采用的是底層機制RB-tree的insert_equal()而非insert_unique()。
　　multimap的特性以及用法和map完全相同，唯一的差別在于它允許鍵值重復，因此它的插入操作采用的是底層機制RB-tree的insert_equal()而非insert_unique()。
hashtable (底層數據結構)
　　二叉搜索樹具有對數平均時間表現，但這樣的表現構造在一個假設上：輸入數據有足夠的隨機性。hashtable這種結構在插入、刪除、查找具有“常數平均時間”，而且這種表現是以統計為基礎，不需依賴元素的隨機性。
　　hashtable底層數據結構為分離連接法的hash表，如下所示：
　　hashtable中的buckets使用的是vector數據結構，當插入一個元素時，找到該插入哪個buckets的插槽，然后遍歷該插槽指向的鏈表，如果有相同的元素，就返回；否則的話就將該元素插入到該鏈表的頭部。(當然，如果是multi版本的話，是可以插入重復元素的，此時插入過程為：當插入一個元素時，找到該插入哪個buckets的插槽，然后遍歷該插槽指向的鏈表，如果有相同的元素，就將新節(jié)點插入到該相同元素的后面；如果沒有相同的元素，產生新節(jié)點，插入到鏈表頭部)
　　當調用成員函數clear()后，buckets vector并未釋放空間，仍保留原來大小，只是刪除了buckets所連接的鏈表。
hash_multimap插入式的圖示說明
hash_set
　　運用set，為的是快速搜尋元素。這一點，不論其底層是RB-tree或是hashtable，都可以完成任務，但是，RB-tree有自動排序功能而hashtable沒有，即set的元素有自動排序功能而hash_set沒有。
測試代碼：
 hash_set測試代碼
hash_map
　　hash_map以hashtable為底層結構，由于hash_map所提供的操作接口，hashtable都提供了，所以幾乎所有的hash_map操作行為都是轉調用hashtable的操作行為結果。RB-tree有自動排序功能而hashtable沒有，反映出來的結果就是，map的元素有自動排序功能而hash_map沒有。
測試代碼：　　
 hash_map測試代碼
hash_multiset/hash_multimap
　　hash_multiset的特性與multiset完全相同，唯一的差別在于它的底層機制是hashtable，因此，hash_multiset的元素是不會自動排序的。
　　hash_multimap的特性與multimap完全相同，唯一的差別在于它的底層機制是hashtable，因此，hash_multimap的元素是不會自動排序的。
hash_multimap測試用例：
#include <iostream>#include <hash_map>#include <cstring>#include <algorithm>#include <string>using namespace std;template <typename T>struct print{    void operator()(const T &x)    {        cout << x.first << ": " << x.second << endl;    }};int main(void){    hash_multimap<int, string> hmap;    hmap.insert(pair<int, string>(2, "32"));    hmap.insert(pair<int, string>(2, "22"));    hmap.insert(pair<int, string>(2, "12"));    hmap.insert(pair<int, string>(2, "2"));    for_each(hmap.begin(), hmap.end(), print<pair<int, string>>());    return 0;}
在vs2013(Windows 7 64位)下運行結果為：
在Kali2.0中運行(程序需添加using namespace __gun_cxx)結果為：
　　由運行結果可知，不同的系統所用的STL是有差別的，不同的STL的hash_table沖突解決方法不一樣。