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