容器概述
C++標(biāo)準(zhǔn)里提供了以下容器或容器配接器：
| 序列式容器 | 配接器 | 關(guān)聯(lián)式容器 | 不定序關(guān)聯(lián)容器 |
|---|---|---|---|
| array | stack | set | unordered_set |
| vector | queue | map | unordered_map |
| list | priority_queue | multiset | unordered_multiset |
| deque | multimap | unordered_multimap | |
| forward_list |
序列式容器
array
array是靜態(tài)連續(xù)空間，一經(jīng)配置，大小不可改變。
就是數(shù)組，除了空間的靈活性不足，其他與vector很像。用的也比較少，一般都用vector了，這里就不多說了。
vector
vector的數(shù)據(jù)安排與操作方式，與array很相似。二者唯一的差別在于空間的運(yùn)用的靈活性。
- array是靜態(tài)空間，一旦配置不能改變；
- vector是動態(tài)空間，隨著元素加入，內(nèi)部機(jī)制會自行擴(kuò)充空間以容納新元素。
vector維護(hù)的是連續(xù)線性空間，其指針就是普通指針。
|
1
|
vector<int>::iterator iter; |
那么iter其實(shí)就是int*類型。
兩個迭代器start和finish之間是連續(xù)空間中目前已被使用的空間，end_of_storage指向整塊連續(xù)空間的尾端。
為了降低頻繁空間配置帶來的成本開銷，vector實(shí)際配置的大小會比客戶需求的更大一些，以備將來可能的擴(kuò)充。這便是capacity的概念。
- [start,finish]是size();
- [start, end_of_storage]是capacity();
- [finish, end_of_storage]是備用空間。
一旦size() == capacity(),便是滿載。下次再有新增元素，整個vector就要另覓他所了。“另覓他所”的過程會經(jīng)歷“重新配置大空間，元素移動，釋放原空間”這一系列動作，工程浩大。
所謂動態(tài)增加大小，并不是在原空間之后接續(xù)新空間（因?yàn)闊o法保證原空間之后有可供配置的空間），而是以原空間大小的兩倍另外配置一塊較大空間，然后將原內(nèi)容拷貝過來，然后才開始在原內(nèi)容后邊構(gòu)造新元素，并釋放原空間。
因此，對vector的任何操作，一旦引起空間重新配置，指向原vector的所有迭代器就都失效了，這是一個經(jīng)常犯的錯誤，務(wù)必小心。
list
list是環(huán)狀雙向鏈表。它的好處在于每次插入或刪除一個元素，就配置或釋放一個元素空間，與vector相比，list對空間運(yùn)用更加精準(zhǔn)，絕不浪費(fèi)。且對于任何位置的元素插入或移除，list永遠(yuǎn)是常數(shù)時間。
vector和list適用場景與以下有關(guān)：
- 元素多寡
- 元素的構(gòu)造復(fù)雜度（有無non-trival copy constructor， non-trival copy assignment operator）
- 元素存取行為的特性
list的節(jié)點(diǎn)結(jié)構(gòu)如下：
|
1
2
3
4
5
6
7
|
template <class T>struct __list_node{ typedef void* void_pointer; void_pointer prev; void_pointer next; T data;}; |
由于list的內(nèi)存空間無法保證是連續(xù)的，所以它的迭代器不再是普通指針。list的迭代器必須有能力指向list節(jié)點(diǎn)，并進(jìn)行正確的遞增、遞減、取值、成員存取等操作。
list的操作大多不會使迭代器失效，即便是刪除操作，也只有指向被刪除元素的那個迭代器失效。
由于list是一個環(huán)狀雙向鏈表，所以它只需要一個指針，便可以完整遍歷整個鏈表。
對于insert操作，新節(jié)點(diǎn)將位于哨兵迭代器（標(biāo)示出插入點(diǎn)）所指節(jié)點(diǎn)的前方，這是STL對插入操作的標(biāo)準(zhǔn)規(guī)范。
deque
vector是單向開口的連續(xù)線性空間，deque則是一種雙向開口的線性連續(xù)空間。所謂雙向開口，即可以在首尾兩端分別做元素的插入和刪除操作。
deque其實(shí)是動態(tài)地以分段連續(xù)空間組合而成。但是這些分段的連續(xù)空間，在用戶看來確實(shí)一整塊連續(xù)空間，這其實(shí)是deque做出的假象。這種假象由deque的中控器map（注意，不是STL中的map容器）負(fù)責(zé)維持。
這個map可以理解為映射，它是一個指針，指向一小段連續(xù)內(nèi)存空間，這塊空間中的每個元素又都是一個指針，每個指針都指向deque的分段連續(xù)空間中的某一段。默認(rèn)每一段是512字節(jié)。
forward_list
forward_list是單向鏈表。
前邊說了，對于insert操作，新節(jié)點(diǎn)將位于哨兵迭代器（標(biāo)示出插入點(diǎn)）所指節(jié)點(diǎn)的前方，這是STL對插入操作的標(biāo)準(zhǔn)規(guī)范。
但是forward_list作為單向鏈表，它沒有什么方便方法回頭定出前一個位置，它只能從頭找起，所以除了forward_list起點(diǎn)處附近的區(qū)域外，在其他位置insert()或erase()就很慢，對此，forward_list特別提供了insert_after()和erase_after()。
同樣出于效率考慮，它不提供push_back()，只提供push_front()。
Adapter（配接器）
stack
stack是先進(jìn)后出（FILO）的數(shù)據(jù)結(jié)構(gòu)。他只有一個出口，除了最頂端元素外，沒有其他方法獲得stack的其他元素。即stack是不允許有遍歷行為的，自然也就沒有迭代器了。
STL中的stack其實(shí)不算是container，而是adapter，因?yàn)槠涞讓幽J(rèn)是deque，把deque的頭端封閉，便形成一個stack。
具有“修改某物接口，形成另一種風(fēng)貌”之性質(zhì)者，謂之a(chǎn)dapter。
除了deque，list也是雙向開口的，所以list也可以做stack的底層結(jié)構(gòu)。
queue
queue是先進(jìn)先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)。它有兩個出入口，但都是被限制的，尾端只進(jìn)不出，頭端只出不進(jìn)。除了尾端進(jìn)，頭端出之外，沒有其他方法存取queue的其他元素，即queue也是不允許遍歷的，自然也就沒有迭代器了。
queue也是一種adapter，它同stack一樣，默認(rèn)以deque作為底層結(jié)構(gòu)，list同樣也可以做其底層結(jié)構(gòu)。
把deque的頭端入口和尾端出口，就成了一個queue。
priority_queue
priority_queue是擁有權(quán)值觀念的queue。
所謂擁有權(quán)值觀念，可以理解為有序的，其內(nèi)的元素并非按照加入的次序排列，而是按照元素的權(quán)值排列，權(quán)值最高者排在最前邊。
默認(rèn)狀態(tài)下，priority_queue是用一個大根堆（max-heap）來完成，而大根堆是一個以vector表現(xiàn)得完全二叉樹。
大根堆：max-heap，父節(jié)點(diǎn)值大于或等于子節(jié)點(diǎn)值的完全二叉樹；
小根堆：min-heap，父節(jié)點(diǎn)值小于或等于子節(jié)點(diǎn)值的完全二叉樹。
所以，priority_queue是以vector為底層結(jié)構(gòu)，輔以heap處理規(guī)則來實(shí)現(xiàn)的，所以它也是一種adapter。
priority_queue也不允許遍歷，自然也沒有迭代器。
到此這篇關(guān)于C++ STL 序列式容器與配接器的簡單使用的文章就介紹到這了,更多相關(guān)C++ STL 序列式容器與配接器內(nèi)容請搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！
原文鏈接：https://blog.csdn.net/qq_29186859/article/details/118345549
