一、相關(guān)介紹

STL

• 標準模板庫
• 在編寫代碼的過程中有一些程序經(jīng)常會被用到，而且需求特別穩(wěn)定，所以C++中把這些常用的模板做了統(tǒng)一的規(guī)范，慢慢的就形成了STL
• 提供三種類型的組件:?容器、迭代器和算法，它們都支持泛型程序設(shè)計標準

容器

• 順序容器（vector、list、deque）：通過元素在容器中的位置順序存儲和訪問元素
• 關(guān)聯(lián)容器（set、map、multiset、multimap）：通過鍵（Key）存儲和讀取元素
• 容器適配器（stack、queue、priority_queue）

迭代器

• 一種檢查容器內(nèi)元素并遍歷元素的數(shù)據(jù)類型
• 每種容器類型都定義了自己的迭代器類型
• 包括：雙向迭代器、隨機迭代器

二、容器

【順序容器】

• 順序容器中元素排列順序與其值無關(guān)，而僅僅由元素添加到容器里的次序決定
• 容器內(nèi)的元素類型必須至少滿足2個條件：可復(fù)制和可賦值
• 所有的迭代器范圍都是左閉右開區(qū)間，［beg，end） 包括beg，但不包括end

標準庫定義了三種順序容器：vector，list和deque。

vector——連續(xù)存儲的元素，單向的

list——由節(jié)點組成的不連續(xù)存儲的雙向鏈表

deque——連續(xù)存儲的元素，雙向的

它們的區(qū)別在于訪問元素的方式，以及添加或刪除元素相關(guān)操作的運行代價。

如下圖：

【關(guān)聯(lián)容器】

• 獨特之處在于支持鍵的使用
• 支持通過鍵來高效地查找和讀取元素

標準庫定義了兩種關(guān)聯(lián)容器：set，map

set——僅含一個鍵，并有效地支持關(guān)于某個鍵是否存在的查詢

map——元素以鍵-值（key-value）對的形式組織：鍵用作元素在map中的索引，而值則表示所存儲和讀取的元素

一般來說，如果希望有效的存儲不同值的集合，那么set容器比較合適，而map容器則更適用于需要存儲（乃至修改）每個鍵所關(guān)聯(lián)值的情況。

在做某種文本處理時，可使用set保存要忽略的單詞。而字典則是map的一種很好的應(yīng)用：單詞本身是鍵，而它的解釋說明則是值。

map和set類型的對象所包含的元素都具有不同的鍵，不允許同一個鍵添加第二個元素。如果一個鍵必須對應(yīng)多個實例，則需要使用multimap和multiset類型。

【容器適配器】

• 不是第一類容器
• 沒有提供與元素的保存形式有關(guān)的真正數(shù)據(jù)結(jié)構(gòu)實現(xiàn)
• 適配器都是建立在某個順序容器之上的
• 適配器不支持迭代器
• 優(yōu)點：能夠使程序員選擇一種合適的底層數(shù)據(jù)結(jié)構(gòu)

STL提供了三種容器適配器：stack,queue,priority_queue。

statck——可以建立在vector,list,deque任何一種容器之上
queue——要求關(guān)聯(lián)容器提供front操作，所以只有l(wèi)ist和deque滿足
priority_queue——要求提供隨機訪問功能 ，所有只有vector和deque滿足

• stack類允許在底層數(shù)據(jù)結(jié)構(gòu)的一端執(zhí)行插入和刪除操作（先入后出）。堆棧能夠用任何順序容器實現(xiàn)：vector、list、deque。
• queue類允許在底層數(shù)據(jù)結(jié)構(gòu)的末尾插入元素，也允許從前面插入元素（先入先出）。隊列能夠用STL數(shù)據(jù)結(jié)構(gòu)的list和deque實現(xiàn)，默認情況下是用deque實現(xiàn)的。
• priority_queue類，能夠按照有序的方式在底層數(shù)據(jù)結(jié)構(gòu)中執(zhí)行插入操作，也能從底層數(shù)據(jù)結(jié)構(gòu)的前面執(zhí)行刪除操作。priority_queue能夠用STL的序列容器vector和deque實現(xiàn)。默認情況下使用vector作為底層容器的。當(dāng)元素添加到priority_queue時，它們按優(yōu)先級順序插入。這樣，具有最高優(yōu)先級的元素，就是從priority_queue中首先被刪除的元素。通常這是利用堆排序來實現(xiàn)的。堆排序總是將最大值（即優(yōu)先級最高的元素）放在數(shù)據(jù)結(jié)構(gòu)的前面。這種數(shù)據(jù)結(jié)構(gòu)稱為（heap）。

?

三、迭代器

?

一、迭代器的變化

和vector、list不同，set、map都是關(guān)聯(lián)式容器。set內(nèi)部是基于紅黑樹實現(xiàn)的。插入和刪除操作效率較高，因為只需要修改相關(guān)指針而不用進行數(shù)據(jù)的移動。?
在進行數(shù)據(jù)刪除操作后，迭代器會不會失效呢？刪除set的數(shù)據(jù)時，實際的操作是刪除紅黑樹中的一個節(jié)點，然后相關(guān)指針做相關(guān)調(diào)整。指向其他元素的迭代器還是指向原位置，并沒有改變，所以刪除一個節(jié)點后其他迭代器不會失效。list和map也是同樣的道理。然而刪除vector中的某個元素，vector中其他迭代器會失效，因為vector是基于數(shù)組的，刪除一個元素后，后面的元素會往前移動，所以指向后面元素的迭代器會失效。?

二、迭代器的實現(xiàn)

迭代器是一個對象，vector的迭代器是封裝了數(shù)組下標；list、map、set的迭代器是封裝了元素節(jié)點的指針。?
還有一點，從數(shù)學(xué)層面，set的一個集合，好比一個袋子里面裝了好多個小球。但是紅黑樹是一種特殊的二叉搜索樹，set中的元素根據(jù)其值的大小在紅黑樹中有特定的位置，是不可移動的。所以，1是search操作效率會很高O(log n)，2是set中元素的值不可改變。

?

【小問題】

set是基于紅黑樹實現(xiàn)的，那么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; //輸出結(jié)果是：0247} }

紅黑樹首先是二叉搜索樹，所以begin()迭代器指向紅黑樹的最左邊的節(jié)點，end()迭代器指向紅黑樹的最右邊的節(jié)點。另外這個小程序還說明了重復(fù)插入無效。

?

(1)STL中迭代器容器中都要注意的地方(vector中已經(jīng)提到)：
1）任何時候同時使用兩個迭代器產(chǎn)生的將會是一個前閉后開的區(qū)間(具體見插入和刪除的例子)
2）begin()指向的是vec中的第0個元素，而end是指向最后一個元素的后面一個位置（不是最后一個元素）
3）迭代器的時效性，如果一個迭代器所指向的內(nèi)容已經(jīng)被刪除，而后又使用該迭代器的話，會造成意想不到的后果

(2)list的迭代器是雙向迭代器(只能++?? --，沒有偏移功能)而不是像vector那樣的隨機迭代器(和指針幾乎一樣的所有功能)

在list中，由于其內(nèi)存是非連續(xù)的，因此不能像vector那樣，用[]操作符取值，只能用迭代器。

(3)list和vector的區(qū)別，本質(zhì)區(qū)別：list是鏈式存儲，vector在內(nèi)存中是連續(xù)區(qū)別的，有本質(zhì)區(qū)別而導(dǎo)致下面區(qū)別

1）list不支持隨機訪問(2)中已經(jīng)說明,vector可以像數(shù)組那樣使用平[]訪問元素，而list是不可以的

2) list的插入和刪除效率很高，所以list有push_front、pop_front、sort而vector中這些操作的效率太低了，所以STL中沒有寫這些功能

與vector相比，list除了有push_back()//在尾部插入 和 insert()之外，還有push_front()//即在鏈表的頭部插入

3）list的一些特有的函數(shù)remove、reverse、unique、splice、merge功能(這些連deque中都沒有的)

轉(zhuǎn)載于:https://www.cnblogs.com/xzxl/p/7277261.html

總結(jié)

以上是生活随笔為你收集整理的C++STL——概述的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。