STL序列式容器使用概念總結(jié)-創(chuàng)新互聯(lián)

引入

最近看了《STL源碼剖析》的第 4 章和第 5 章，介紹了 C++ STL 中的序列式容器和關(guān)聯(lián)式容器，本文將總結(jié)序列式容器的基礎(chǔ)概念，不會詳細它們的實現(xiàn)原理（想知道自個兒看書吧，我目前只想了解它們的基本原理，用的時候心里有數(shù)就行）。

創(chuàng)新互聯(lián)堅持“要么做到，要么別承諾”的工作理念，服務(wù)領(lǐng)域包括：成都做網(wǎng)站、成都網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣等服務(wù)，滿足客戶于互聯(lián)網(wǎng)時代的尚志網(wǎng)站設(shè)計、移動媒體設(shè)計的需求，幫助企業(yè)找到有效的互聯(lián)網(wǎng)解決方案。努力成為您成熟可靠的網(wǎng)絡(luò)建設(shè)合作伙伴！容器概念

容器是存儲數(shù)據(jù)的地方。C++ STL 容器是一些常見數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)。任何數(shù)據(jù)結(jié)構(gòu)都是為了特定的算法服務(wù)的。

數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)的特定排列方式。

根據(jù)數(shù)據(jù)在容器中的排列方式，將容器分為序列式容器和關(guān)聯(lián)式容器。

接下來將介紹序列式容器：array,vector,list,deque以及它們的適配器：stack,queue,heap,priority_queue。

序列式容器與容器適配器基礎(chǔ)容器

STL 中的底層容器，可以作為其他容器的底層結(jié)構(gòu)（array除外）。

1.array

內(nèi)置的靜態(tài)數(shù)組類型，空間大小指定后不能改變，元素存儲在連續(xù)的線性內(nèi)存空間，不具備動態(tài)擴容的能力，實際應(yīng)用中幾乎沒有。
其迭代器類型為Random Access Iterator隨機訪問迭代器。

2.vector

動態(tài)數(shù)組，元素存儲在連續(xù)的線性內(nèi)存空間，其空間可以動態(tài)縮小或擴大，實際應(yīng)用中非常普遍。
動態(tài)擴容策略：申請更大的新空間（一般是舊空間大小的2倍），進行舊數(shù)據(jù)遷移，釋放舊空間， O ( n ) O(n) O(n) 線性時間開銷。
動態(tài)縮容策略：只需要將表達vector數(shù)據(jù)結(jié)構(gòu)的指針前移即可， O ( 1 ) O(1) O(1) 時間開銷。
為了避免頻繁發(fā)生擴容，vector有容量的概念，即它的實際大小比客戶端需求量更大一些。
引起vector內(nèi)存空間重新配置的操作（如插入、刪除操作），會導(dǎo)致之前定義的迭代器失效。
其迭代器類型為Random Access Iterator隨機訪問迭代器，支持算術(shù)運算。

3.list

雙向循環(huán)鏈表，元素存儲在非線性內(nèi)存空間，實際應(yīng)用中非常普遍。
list不會重新配置空間，因此只有被刪除元素的迭代器會失效，其他原先的迭代器不會失效。
其迭代器類型為Bidirectional Iterator雙向迭代器，只支持自增（++）和自減（--）運算。

4.deque

雙端隊列，采用二級結(jié)構(gòu)實現(xiàn)。一級結(jié)構(gòu)稱為中控器，是一個元素均為指針的數(shù)組，每個指針指向一段連續(xù)的線性空間，這段空間即為二級結(jié)構(gòu)，真正存儲數(shù)據(jù)的地方。
deque的迭代器實現(xiàn)營造了一種“它是連續(xù)空間”的假象，其實它只是“一段一段的定量連續(xù)空間”。
deque的擴容策略說起來簡單：如果一級結(jié)構(gòu)中控器仍有空間，就增加一個指針，指向一段新的連續(xù)空間用于存放新元素；否則申請更大的空間遷移一級結(jié)構(gòu)的指針，然后如前所述。
deque沒有容量概念，因為如第 3 點所述，它可以隨時申請一段新空間與舊空間“拼接”起來，不會發(fā)生“申請新空間 ->遷移元素 ->釋放舊空間”（指的是二級結(jié)構(gòu)即真正的數(shù)據(jù)不會發(fā)生遷移，一級結(jié)構(gòu)中的指針還是會發(fā)生遷移的）。
書中提到deque的迭代器比較復(fù)雜，若需要對deque排序，最好借助vector完成。
其迭代器類型為Random Access Iterator隨機訪問迭代器，支持算術(shù)運算。

5.補充

在新的 C++ 標(biāo)準(zhǔn)中增加了forward_list單向鏈表，應(yīng)該也算基礎(chǔ)容器吧，但它的應(yīng)用限制太多，只有在特定場合下才能使用。

容器適配器

以某種容器作為底層結(jié)構(gòu)，改變其接口，使之符合某種特性。

1.stack

stack棧的特性是“后進先出”，默認采用deque作為底層結(jié)構(gòu)。
其實vector和list也可以作為底層結(jié)構(gòu)，可以根據(jù)應(yīng)用場景分別測試這 3 種底層結(jié)構(gòu)的性能差異進行選擇。
stack沒有迭代器，因為提供迭代器會破壞它“后進先出”的特性。

2.queue

queue隊列的特性是“先進先出”，默認采用deque作為底層結(jié)構(gòu)。
其實 vector 和 list 也可以作為底層結(jié)構(gòu)，但是顯然不應(yīng)該用 vector，因為 vector 刪除首元素的時間開銷是 O ( n ) O(n) O(n)，同樣的操作 list 只要 O ( 1 ) O(1) O(1) 時間，因此實際應(yīng)用中只需要測試deque和 list 作為queue底層結(jié)構(gòu)時的性能差異。
queue沒有迭代器，因為提供迭代器會破壞它“先進先出”的特性。

3.heap

我傾向于把heap歸類為容器適配器，**因為其依賴底層結(jié)構(gòu) vector 存儲數(shù)據(jù)。**眾所周知的一個小技巧，使用數(shù)組表示堆，可以通過下標(biāo)快速定位一個節(jié)點的父節(jié)點和子節(jié)點。
STL 中heap采用隱式表述的方式，不開放給外部使用，而是通過heap作為底層結(jié)構(gòu)實現(xiàn)priority_queue優(yōu)先隊列開放給外部使用。
heap算法中有一個 make_heap 算法，其作用是將一個vector中的元素進行調(diào)整使之符合堆特性。在make_heap算法中需要調(diào)用一個perlocate down算法下拉調(diào)整每個節(jié)點（在vector中從后往前尋找第一個非葉子節(jié)點開始），此時默認采用<小于比較操作，即較小的節(jié)點被下拉了，那么較大的節(jié)點自然成為父節(jié)點，因此默認情況下是大堆。
heap沒有迭代器，不提供遍歷功能，因為heap是完全二叉樹，其元素需要遵循完全二叉樹的排列規(guī)則。

4.priority_queue

優(yōu)先隊列，默認采用vector作為底層結(jié)構(gòu)，且默認采用max_heap實現(xiàn)。
根據(jù)上述heap的make_heap算法所述，采用<小于比較操作得到的是大堆，相反采用>大于比較操作得到的是最小堆。

#include<`queue`>int main() {priority_`queue`, less>pq1;    // 大堆
    priority_`queue`, greater>pq2; // 最小堆
    return 0;
}

最后

如果你有疑惑，歡迎評論，我會盡可能回復(fù)！

如果本文對你有幫助，點個贊吧，這是我堅持的動力！

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

本文題目：STL序列式容器使用概念總結(jié)-創(chuàng)新互聯(lián)
分享地址：http://muchs.cn/article2/csppic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制開發(fā)、網(wǎng)頁設(shè)計公司、網(wǎng)站收錄、網(wǎng)站營銷、服務(wù)器托管、做網(wǎng)站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容