轉(zhuǎn)載自 ：http://blog.csdn.net/liguohanhaha/article/details/52089914

1、STL概述

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

STL六大組件的交互關(guān)系

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

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

2、迭代器

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

迭代器是一種智能指針

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

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