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

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

容器概述

C++標(biāo)準(zhǔn)里提供了以下容器或容器配接器：

序列式容器

array

array是靜態(tài)連續(xù)空間，一經(jīng)配置，大小不可改變。

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

vector

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

• array是靜態(tài)空間，一旦配置不能改變；

• vector是動(dòng)態(tài)空間，隨著元素加入，內(nèi)部機(jī)制會(huì)自行擴(kuò)充空間以容納新元素。

vector維護(hù)的是連續(xù)線性空間，其指針就是普通指針。

vector<int>::iterator iter;

那么iter其實(shí)就是int*類型。

兩個(gè)迭代器start和finish之間是連續(xù)空間中目前已被使用的空間，end_of_storage指向整塊連續(xù)空間的尾端。

為了降低頻繁空間配置帶來的成本開銷，vector實(shí)際配置的大小會(huì)比客戶需求的更大一些，以備將來可能的擴(kuò)充。這便是capacity的概念。

• [start,finish]是size();

• [start, end_of_storage]是capacity();

• [finish, end_of_storage]是備用空間。

一旦size() == capacity(),便是滿載。下次再有新增元素，整個(gè)vector就要另覓他所了?！傲硪捤钡倪^程會(huì)經(jīng)歷“重新配置大空間，元素移動(dòng)，釋放原空間”這一系列動(dòng)作，工程浩大。

所謂動(dòng)態(tài)增加大小，并不是在原空間之后接續(xù)新空間（因?yàn)闊o法保證原空間之后有可供配置的空間），而是以原空間大小的兩倍另外配置一塊較大空間，然后將原內(nèi)容拷貝過來，然后才開始在原內(nèi)容后邊構(gòu)造新元素，并釋放原空間。

因此，對vector的任何操作，一旦引起空間重新配置，指向原vector的所有迭代器就都失效了，這是一個(gè)經(jīng)常犯的錯(cuò)誤，務(wù)必小心。

list

list是環(huán)狀雙向鏈表。它的好處在于每次插入或刪除一個(gè)元素，就配置或釋放一個(gè)元素空間，與vector相比，list對空間運(yùn)用更加精準(zhǔn)，絕不浪費(fèi)。且對于任何位置的元素插入或移除，list永遠(yuǎn)是常數(shù)時(shí)間。

vector和list適用場景與以下有關(guān)：

• 元素多寡

• 元素的構(gòu)造復(fù)雜度（有無non-trival copy constructor， non-trival copy assignment operator）

• 元素存取行為的特性

list的節(jié)點(diǎn)結(jié)構(gòu)如下：

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的操作大多不會(huì)使迭代器失效，即便是刪除操作，也只有指向被刪除元素的那個(gè)迭代器失效。

由于list是一個(gè)環(huán)狀雙向鏈表，所以它只需要一個(gè)指針，便可以完整遍歷整個(gè)鏈表。

對于insert操作，新節(jié)點(diǎn)將位于哨兵迭代器（標(biāo)示出插入點(diǎn)）所指節(jié)點(diǎn)的前方，這是STL對插入操作的標(biāo)準(zhǔn)規(guī)范。

deque

vector是單向開口的連續(xù)線性空間，deque則是一種雙向開口的線性連續(xù)空間。所謂雙向開口，即可以在首尾兩端分別做元素的插入和刪除操作。

deque其實(shí)是動(dòng)態(tài)地以分段連續(xù)空間組合而成。但是這些分段的連續(xù)空間，在用戶看來確實(shí)一整塊連續(xù)空間，這其實(shí)是deque做出的假象。這種假象由deque的中控器map（注意，不是STL中的map容器）負(fù)責(zé)維持。

這個(gè)map可以理解為映射，它是一個(gè)指針，指向一小段連續(xù)內(nèi)存空間，這塊空間中的每個(gè)元素又都是一個(gè)指針，每個(gè)指針都指向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作為單向鏈表，它沒有什么方便方法回頭定出前一個(gè)位置，它只能從頭找起，所以除了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)。他只有一個(gè)出口，除了最頂端元素外，沒有其他方法獲得stack的其他元素。即stack是不允許有遍歷行為的，自然也就沒有迭代器了。

STL中的stack其實(shí)不算是container，而是adapter，因?yàn)槠涞讓幽J(rèn)是deque，把deque的頭端封閉，便形成一個(gè)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)。它有兩個(gè)出入口，但都是被限制的，尾端只進(jìn)不出，頭端只出不進(jìn)。除了尾端進(jìn)，頭端出之外，沒有其他方法存取queue的其他元素，即queue也是不允許遍歷的，自然也就沒有迭代器了。

queue也是一種adapter，它同stack一樣，默認(rèn)以deque作為底層結(jié)構(gòu)，list同樣也可以做其底層結(jié)構(gòu)。

把deque的頭端入口和尾端出口，就成了一個(gè)queue。

priority_queue

priority_queue是擁有權(quán)值觀念的queue。

所謂擁有權(quán)值觀念，可以理解為有序的，其內(nèi)的元素并非按照加入的次序排列，而是按照元素的權(quán)值排列，權(quán)值最高者排在最前邊。

默認(rèn)狀態(tài)下，priority_queue是用一個(gè)大根堆（max-heap）來完成，而大根堆是一個(gè)以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++序列式容器與配接器如何使用”這篇文章的內(nèi)容，相信大家都有了一定的了解，希望小編分享的內(nèi)容對大家有幫助，若想了解更多相關(guān)的知識內(nèi)容，請關(guān)注億速云行業(yè)資訊頻道。