引入

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

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

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

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

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

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

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

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

1.array

1. 內(nèi)置的靜態(tài)數(shù)組類型，空間大小指定后不能改變，元素存儲(chǔ)在連續(xù)的線性內(nèi)存空間，不具備動(dòng)態(tài)擴(kuò)容的能力，實(shí)際應(yīng)用中幾乎沒(méi)有。

2. 其迭代器類型為Random Access Iterator隨機(jī)訪問(wèn)迭代器。

2.vector

1. 動(dòng)態(tài)數(shù)組，元素存儲(chǔ)在連續(xù)的線性內(nèi)存空間，其空間可以動(dòng)態(tài)縮小或擴(kuò)大，實(shí)際應(yīng)用中非常普遍。

2. 動(dòng)態(tài)擴(kuò)容策略：申請(qǐng)更大的新空間（一般是舊空間大小的2倍），進(jìn)行舊數(shù)據(jù)遷移，釋放舊空間， O ( n ) O(n) O(n) 線性時(shí)間開(kāi)銷。

3. 動(dòng)態(tài)縮容策略：只需要將表達(dá)vector數(shù)據(jù)結(jié)構(gòu)的指針前移即可， O ( 1 ) O(1) O(1) 時(shí)間開(kāi)銷。

4. 為了避免頻繁發(fā)生擴(kuò)容，vector有容量的概念，即它的實(shí)際大小比客戶端需求量更大一些。

5. 引起vector內(nèi)存空間重新配置的操作（如插入、刪除操作），會(huì)導(dǎo)致之前定義的迭代器失效。

6. 其迭代器類型為Random Access Iterator隨機(jī)訪問(wèn)迭代器，支持算術(shù)運(yùn)算。

3.list

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

4.deque

1. 雙端隊(duì)列，采用二級(jí)結(jié)構(gòu)實(shí)現(xiàn)。一級(jí)結(jié)構(gòu)稱為中控器，是一個(gè)元素均為指針的數(shù)組，每個(gè)指針指向一段連續(xù)的線性空間，這段空間即為二級(jí)結(jié)構(gòu)，真正存儲(chǔ)數(shù)據(jù)的地方。

2. deque的迭代器實(shí)現(xiàn)營(yíng)造了一種“它是連續(xù)空間”的假象，其實(shí)它只是“一段一段的定量連續(xù)空間”。

3. deque的擴(kuò)容策略說(shuō)起來(lái)簡(jiǎn)單：如果一級(jí)結(jié)構(gòu)中控器仍有空間，就增加一個(gè)指針，指向一段新的連續(xù)空間用于存放新元素；否則申請(qǐng)更大的空間遷移一級(jí)結(jié)構(gòu)的指針，然后如前所述。

4. deque沒(méi)有容量概念，因?yàn)槿绲?3 點(diǎn)所述，它可以隨時(shí)申請(qǐng)一段新空間與舊空間“拼接”起來(lái)，不會(huì)發(fā)生“申請(qǐng)新空間 ->遷移元素 ->釋放舊空間”（指的是二級(jí)結(jié)構(gòu)即真正的數(shù)據(jù)不會(huì)發(fā)生遷移，一級(jí)結(jié)構(gòu)中的指針還是會(huì)發(fā)生遷移的）。

5. 書(shū)中提到deque的迭代器比較復(fù)雜，若需要對(duì)deque排序，最好借助vector完成。

6. 其迭代器類型為Random Access Iterator隨機(jī)訪問(wèn)迭代器，支持算術(shù)運(yùn)算。

5.補(bǔ)充

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

容器適配器

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

1.stack

1. stack棧的特性是“后進(jìn)先出”，默認(rèn)采用deque作為底層結(jié)構(gòu)。

2. 其實(shí)vector和list也可以作為底層結(jié)構(gòu)，可以根據(jù)應(yīng)用場(chǎng)景分別測(cè)試這 3 種底層結(jié)構(gòu)的性能差異進(jìn)行選擇。

3. stack沒(méi)有迭代器，因?yàn)樘峁┑鲿?huì)破壞它“后進(jìn)先出”的特性。

2.queue

1. queue隊(duì)列的特性是“先進(jìn)先出”，默認(rèn)采用deque作為底層結(jié)構(gòu)。

2. 其實(shí) vector 和 list 也可以作為底層結(jié)構(gòu)，但是顯然不應(yīng)該用 vector，因?yàn)?vector 刪除首元素的時(shí)間開(kāi)銷是 O ( n ) O(n) O(n)，同樣的操作 list 只要 O ( 1 ) O(1) O(1) 時(shí)間，因此實(shí)際應(yīng)用中只需要測(cè)試deque和 list 作為queue底層結(jié)構(gòu)時(shí)的性能差異。

3. queue沒(méi)有迭代器，因?yàn)樘峁┑鲿?huì)破壞它“先進(jìn)先出”的特性。

3.heap

1. 我傾向于把heap歸類為容器適配器，**因?yàn)槠湟蕾嚨讓咏Y(jié)構(gòu) vector 存儲(chǔ)數(shù)據(jù)。**眾所周知的一個(gè)小技巧，使用數(shù)組表示堆，可以通過(guò)下標(biāo)快速定位一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)。

2. STL 中heap采用隱式表述的方式，不開(kāi)放給外部使用，而是通過(guò)heap作為底層結(jié)構(gòu)實(shí)現(xiàn)priority_queue優(yōu)先隊(duì)列開(kāi)放給外部使用。

3. heap算法中有一個(gè) make_heap 算法，其作用是將一個(gè)vector中的元素進(jìn)行調(diào)整使之符合堆特性。在make_heap算法中需要調(diào)用一個(gè)perlocate down算法下拉調(diào)整每個(gè)節(jié)點(diǎn)（在vector中從后往前尋找第一個(gè)非葉子節(jié)點(diǎn)開(kāi)始），此時(shí)默認(rèn)采用<小于比較操作，即較小的節(jié)點(diǎn)被下拉了，那么較大的節(jié)點(diǎn)自然成為父節(jié)點(diǎn)，因此默認(rèn)情況下是大堆。

4. heap沒(méi)有迭代器，不提供遍歷功能，因?yàn)?code>heap是完全二叉樹(shù)，其元素需要遵循完全二叉樹(shù)的排列規(guī)則。

4.priority_queue

1. 優(yōu)先隊(duì)列，默認(rèn)采用vector作為底層結(jié)構(gòu)，且默認(rèn)采用max_heap實(shí)現(xiàn)。

2. 根據(jù)上述heap的make_heap算法所述，采用<小于比較操作得到的是大堆，相反采用>大于比較操作得到的是最小堆。

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

最后

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

如果本文對(duì)你有幫助，點(diǎn)個(gè)贊吧，這是我堅(jiān)持的動(dòng)力！

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

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

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

廣告

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