最近看了《STL源碼剖析》的第 4 章和第 5 章，介紹了 C++ STL 中的序列式容器和關(guān)聯(lián)式容器，本文將總結(jié)序列式容器的基礎(chǔ)概念，不會(huì)詳細(xì)它們的實(shí)現(xiàn)原理（想知道自個(gè)兒看書吧，我目前只想了解它們的基本原理，用的時(shí)候心里有數(shù)就行）。
容器是存儲(chǔ)數(shù)據(jù)的地方。C++ STL 容器是一些常見數(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)式容器。
接下來將介紹序列式容器：array,vector,list,deque以及它們的適配器：stack,queue,heap,priority_queue。
STL 中的底層容器，可以作為其他容器的底層結(jié)構(gòu)（array除外）。
內(nèi)置的靜態(tài)數(shù)組類型，空間大小指定后不能改變，元素存儲(chǔ)在連續(xù)的線性內(nèi)存空間，不具備動(dòng)態(tài)擴(kuò)容的能力，實(shí)際應(yīng)用中幾乎沒有。
其迭代器類型為Random Access Iterator隨機(jī)訪問迭代器。
動(dòng)態(tài)數(shù)組，元素存儲(chǔ)在連續(xù)的線性內(nèi)存空間，其空間可以動(dòng)態(tài)縮小或擴(kuò)大，實(shí)際應(yīng)用中非常普遍。
動(dòng)態(tài)擴(kuò)容策略：申請(qǐng)更大的新空間（一般是舊空間大小的2倍），進(jìn)行舊數(shù)據(jù)遷移，釋放舊空間，
O
(
n
)
O(n)
O(n) 線性時(shí)間開銷。
動(dòng)態(tài)縮容策略：只需要將表達(dá)vector數(shù)據(jù)結(jié)構(gòu)的指針前移即可，
O
(
1
)
O(1)
O(1) 時(shí)間開銷。
為了避免頻繁發(fā)生擴(kuò)容，vector有容量的概念，即它的實(shí)際大小比客戶端需求量更大一些。
引起vector內(nèi)存空間重新配置的操作（如插入、刪除操作），會(huì)導(dǎo)致之前定義的迭代器失效。
其迭代器類型為Random Access Iterator隨機(jī)訪問迭代器，支持算術(shù)運(yùn)算。
重慶分公司
重慶分公司
list不會(huì)重新配置空間，因此只有被刪除元素的迭代器會(huì)失效，其他原先的迭代器不會(huì)失效。Bidirectional Iterator雙向迭代器，只支持自增（++）和自減（--）運(yùn)算。雙端隊(duì)列，采用二級(jí)結(jié)構(gòu)實(shí)現(xiàn)。一級(jí)結(jié)構(gòu)稱為中控器，是一個(gè)元素均為指針的數(shù)組，每個(gè)指針指向一段連續(xù)的線性空間，這段空間即為二級(jí)結(jié)構(gòu)，真正存儲(chǔ)數(shù)據(jù)的地方。
deque的迭代器實(shí)現(xiàn)營(yíng)造了一種“它是連續(xù)空間”的假象，其實(shí)它只是“一段一段的定量連續(xù)空間”。
deque的擴(kuò)容策略說起來簡(jiǎn)單：如果一級(jí)結(jié)構(gòu)中控器仍有空間，就增加一個(gè)指針，指向一段新的連續(xù)空間用于存放新元素；否則申請(qǐng)更大的空間遷移一級(jí)結(jié)構(gòu)的指針，然后如前所述。
deque沒有容量概念，因?yàn)槿绲?3 點(diǎn)所述，它可以隨時(shí)申請(qǐng)一段新空間與舊空間“拼接”起來，不會(huì)發(fā)生“申請(qǐng)新空間 ->遷移元素 ->釋放舊空間”（指的是二級(jí)結(jié)構(gòu)即真正的數(shù)據(jù)不會(huì)發(fā)生遷移，一級(jí)結(jié)構(gòu)中的指針還是會(huì)發(fā)生遷移的）。
書中提到deque的迭代器比較復(fù)雜，若需要對(duì)deque排序，最好借助vector完成。
其迭代器類型為Random Access Iterator隨機(jī)訪問迭代器，支持算術(shù)運(yùn)算。
在新的 C++ 標(biāo)準(zhǔn)中增加了forward_list單向鏈表，應(yīng)該也算基礎(chǔ)容器吧，但它的應(yīng)用限制太多，只有在特定場(chǎng)合下才能使用。
以某種容器作為底層結(jié)構(gòu)，改變其接口，使之符合某種特性。
1.stackstack棧的特性是“后進(jìn)先出”，默認(rèn)采用deque作為底層結(jié)構(gòu)。
其實(shí)vector和list也可以作為底層結(jié)構(gòu)，可以根據(jù)應(yīng)用場(chǎng)景分別測(cè)試這 3 種底層結(jié)構(gòu)的性能差異進(jìn)行選擇。
stack沒有迭代器，因?yàn)樘峁┑鲿?huì)破壞它“后進(jìn)先出”的特性。
queue隊(duì)列的特性是“先進(jìn)先出”，默認(rèn)采用deque作為底層結(jié)構(gòu)。
其實(shí) vector 和 list 也可以作為底層結(jié)構(gòu)，但是顯然不應(yīng)該用 vector，因?yàn)?vector 刪除首元素的時(shí)間開銷是
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í)的性能差異。
queue沒有迭代器，因?yàn)樘峁┑鲿?huì)破壞它“先進(jìn)先出”的特性。
我傾向于把heap歸類為容器適配器，**因?yàn)槠湟蕾嚨讓咏Y(jié)構(gòu) vector 存儲(chǔ)數(shù)據(jù)。**眾所周知的一個(gè)小技巧，使用數(shù)組表示堆，可以通過下標(biāo)快速定位一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)。
STL 中heap采用隱式表述的方式，不開放給外部使用，而是通過heap作為底層結(jié)構(gòu)實(shí)現(xiàn)priority_queue優(yōu)先隊(duì)列開放給外部使用。
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)開始），此時(shí)默認(rèn)采用<小于比較操作，即較小的節(jié)點(diǎn)被下拉了，那么較大的節(jié)點(diǎn)自然成為父節(jié)點(diǎn)，因此默認(rèn)情況下是大堆。
heap沒有迭代器，不提供遍歷功能，因?yàn)?code>heap是完全二叉樹，其元素需要遵循完全二叉樹的排列規(guī)則。
優(yōu)先隊(duì)列，默認(rèn)采用vector作為底層結(jié)構(gòu)，且默認(rèn)采用max_heap實(shí)現(xiàn)。
根據(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ù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
