C++的STL序列式容器與配接器怎么使用

本篇內(nèi)容主要講解“C++的STL序列式容器與配接器怎么使用”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學(xué)習(xí)“C++的STL序列式容器與配接器怎么使用”吧!

創(chuàng)新互聯(lián)建站于2013年創(chuàng)立，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項目成都網(wǎng)站建設(shè)、網(wǎng)站設(shè)計網(wǎng)站策劃，項目實施與項目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元米東做網(wǎng)站,已為上家服務(wù),為米東各地企業(yè)和個人服務(wù),聯(lián)系電話:18982081108

容器概述

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

序列式容器配接器關(guān)聯(lián)式容器不定序關(guān)聯(lián)容器
arraystacksetunordered_set
vectorqueuemapunordered_map
listpriority_queuemultisetunordered_multiset
deque
multimapunordered_multimap
forward_list


序列式容器

array

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

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

vector

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

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

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

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

vector<int>::iterator iter;

那么iter其實就是int*類型。

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

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

  • [start,finish]是size();

  • [start, end_of_storage]是capacity();

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

一旦size() == capacity(),便是滿載。下次再有新增元素，整個vector就要另覓他所了。“另覓他所”的過程會經(jīng)歷“重新配置大空間，元素移動，釋放原空間”這一系列動作，工程浩大。

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

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

list

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

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

  • 元素多寡

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

  • 元素存取行為的特性

list的節(jié)點結(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é)點，并進行正確的遞增、遞減、取值、成員存取等操作。

list的操作大多不會使迭代器失效，即便是刪除操作，也只有指向被刪除元素的那個迭代器失效。

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

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

deque

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

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

這個map可以理解為映射，它是一個指針，指向一小段連續(xù)內(nèi)存空間，這塊空間中的每個元素又都是一個指針，每個指針都指向deque的分段連續(xù)空間中的某一段。默認每一段是512字節(jié)。

forward_list

forward_list是單向鏈表。

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

但是forward_list作為單向鏈表，它沒有什么方便方法回頭定出前一個位置，它只能從頭找起，所以除了forward_list起點處附近的區(qū)域外，在其他位置insert()或erase()就很慢，對此，forward_list特別提供了insert_after()和erase_after()。

同樣出于效率考慮，它不提供push_back()，只提供push_front()。

Adapter（配接器）

stack

stack是先進后出（FILO）的數(shù)據(jù)結(jié)構(gòu)。他只有一個出口，除了最頂端元素外，沒有其他方法獲得stack的其他元素。即stack是不允許有遍歷行為的，自然也就沒有迭代器了。

STL中的stack其實不算是container，而是adapter，因為其底層默認是deque，把deque的頭端封閉，便形成一個stack。

具有“修改某物接口，形成另一種風(fēng)貌”之性質(zhì)者，謂之a(chǎn)dapter。

除了deque，list也是雙向開口的，所以list也可以做stack的底層結(jié)構(gòu)。

queue

queue是先進先出（FIFO）的數(shù)據(jù)結(jié)構(gòu)。它有兩個出入口，但都是被限制的，尾端只進不出，頭端只出不進。除了尾端進，頭端出之外，沒有其他方法存取queue的其他元素，即queue也是不允許遍歷的，自然也就沒有迭代器了。

queue也是一種adapter，它同stack一樣，默認以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)值最高者排在最前邊。

默認狀態(tài)下，priority_queue是用一個大根堆（max-heap）來完成，而大根堆是一個以vector表現(xiàn)得完全二叉樹。

大根堆：max-heap，父節(jié)點值大于或等于子節(jié)點值的完全二叉樹；
小根堆：min-heap，父節(jié)點值小于或等于子節(jié)點值的完全二叉樹。

所以，priority_queue是以vector為底層結(jié)構(gòu)，輔以heap處理規(guī)則來實現(xiàn)的，所以它也是一種adapter。

priority_queue也不允許遍歷，自然也沒有迭代器。

到此，相信大家對“C++的STL序列式容器與配接器怎么使用”有了更深的了解，不妨來實際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進入相關(guān)頻道進行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！

網(wǎng)頁名稱：C++的STL序列式容器與配接器怎么使用
地址分享：http://muchs.cn/article40/picieo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、網(wǎng)站設(shè)計、品牌網(wǎng)站制作、微信小程序、網(wǎng)站改版、品牌網(wǎng)站設(shè)計

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

網(wǎng)站建設(shè)網(wǎng)站維護公司