C++序列式容器與配接器如何使用

這篇“C++序列式容器與配接器如何使用”文章的知識點大部分人都不太理解，所以小編給大家總結了以下內容，內容詳細，步驟清晰，具有一定的借鑒價值，希望大家閱讀完這篇文章能有所收獲，下面我們一起來看看這篇“C++序列式容器與配接器如何使用”文章吧。

容器概述

C++標準里提供了以下容器或容器配接器：

序列式容器

array

array是靜態連續空間，一經配置，大小不可改變。

就是數組，除了空間的靈活性不足，其他與vector很像。用的也比較少，一般都用vector了，這里就不多說了。

vector

vector的數據安排與操作方式，與array很相似。二者唯一的差別在于空間的運用的靈活性。

• array是靜態空間，一旦配置不能改變；

• vector是動態空間，隨著元素加入，內部機制會自行擴充空間以容納新元素。

vector維護的是連續線性空間，其指針就是普通指針。

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的節點結構如下：

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++序列式容器與配接器如何使用”這篇文章的內容，相信大家都有了一定的了解，希望小編分享的內容對大家有幫助，若想了解更多相關的知識內容，請關注億速云行業資訊頻道。