什么是容器

首先，我們必須理解一下什么是容器，在C++中容器被定義為：在數(shù)據(jù)存儲(chǔ)上，有一種對(duì)象類(lèi)型，它可以持有其它對(duì)象或指向其它對(duì)像的指針，這種對(duì)象類(lèi)型就叫做容器。很簡(jiǎn)單，容器就是保存其它對(duì)象的對(duì)象，當(dāng)然這是一個(gè)樸素的理解，這種“對(duì)象”還包含了一系列處理“其它對(duì)象”的方法，因?yàn)檫@些方法在程序的設(shè)計(jì)上會(huì)經(jīng)常被用到，所以容器也體現(xiàn)了一個(gè)好處，就是“容器類(lèi)是一種對(duì)特定代碼重用問(wèn)題的良好的解決方案”。

容器還有另一個(gè)特點(diǎn)是容器可以自行擴(kuò)展。在解決問(wèn)題時(shí)我們常常不知道我們需要存儲(chǔ)多少個(gè)對(duì)象，也就是說(shuō)我們不知道應(yīng)該創(chuàng)建多大的內(nèi)存空間來(lái)保存我們的對(duì)象。顯然，數(shù)組在這一方面也力不從心。容器的優(yōu)勢(shì)就在這里，它不需要你預(yù)先告訴它你要存儲(chǔ)多少對(duì)象，只要你創(chuàng)建一個(gè)容器對(duì)象，并合理的調(diào)用它所提供的方法，所有的處理細(xì)節(jié)將由容器來(lái)自身完成。它可以為你申請(qǐng)內(nèi)存或釋放內(nèi)存，并且用最優(yōu)的算法來(lái)執(zhí)行您的命令。

容器是隨著面向?qū)ο笳Z(yǔ)言的誕生而提出的，容器類(lèi)在面向?qū)ο笳Z(yǔ)言中特別重要，甚至它被認(rèn)為是早期面向?qū)ο笳Z(yǔ)言的基礎(chǔ)。在現(xiàn)在幾乎所有的面向?qū)ο蟮恼Z(yǔ)言中也都伴隨著一個(gè)容器集，在C++中，就是標(biāo)準(zhǔn)模板庫(kù)（STL）。

和其它語(yǔ)言不一樣，C++中處理容器是采用基于模板的方式。標(biāo)準(zhǔn)C++庫(kù)中的容器提供了多種數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)可以與標(biāo)準(zhǔn)算法一起很好的工作，這為我們的軟件開(kāi)發(fā)提供了良好的支持！

通用容器的分類(lèi)

STL對(duì)定義的通用容器分三類(lèi)：順序性容器、關(guān)聯(lián)式容器和容器適配器。

順序性容器是一種各元素之間有順序關(guān)系的線性表，是一種線性結(jié)構(gòu)的可序群集。順序性容器中的每個(gè)元素均有固定的位置，除非用刪除或插入的操作改變這個(gè)位置。這個(gè)位置和元素本身無(wú)關(guān)，而和操作的時(shí)間和地點(diǎn)有關(guān)，順序性容器不會(huì)根據(jù)元素的特點(diǎn)排序而是直接保存了元素操作時(shí)的邏輯順序。比如我們一次性對(duì)一個(gè)順序性容器追加三個(gè)元素，這三個(gè)元素在容器中的相對(duì)位置和追加時(shí)的邏輯次序是一致的。

關(guān)聯(lián)式容器和順序性容器不一樣，關(guān)聯(lián)式容器是非線性的樹(shù)結(jié)構(gòu)，更準(zhǔn)確的說(shuō)是二叉樹(shù)結(jié)構(gòu)。各元素之間沒(méi)有嚴(yán)格的物理上的順序關(guān)系，也就是說(shuō)元素在容器中并沒(méi)有保存元素置入容器時(shí)的邏輯順序。但是關(guān)聯(lián)式容器提供了另一種根據(jù)元素特點(diǎn)排序的功能，這樣迭代器就能根據(jù)元素的特點(diǎn)“順序地”獲取元素。

關(guān)聯(lián)式容器另一個(gè)顯著的特點(diǎn)是它是以鍵值的方式來(lái)保存數(shù)據(jù)，就是說(shuō)它能把關(guān)鍵字和值關(guān)聯(lián)起來(lái)保存，而順序性容器只能保存一種（可以認(rèn)為它只保存關(guān)鍵字，也可以認(rèn)為它只保存值）。這在下面具體的容器類(lèi)中可以說(shuō)明這一點(diǎn)。

容器適配器是一個(gè)比較抽象的概念，C++的解釋是：適配器是使一事物的行為類(lèi)似于另一事物的行為的一種機(jī)制。容器適配器是讓一種已存在的容器類(lèi)型采用另一種不同的抽象類(lèi)型的工作方式來(lái)實(shí)現(xiàn)的一種機(jī)制。其實(shí)僅是發(fā)生了接口轉(zhuǎn)換。那么你可以把它理解為容器的容器，它實(shí)質(zhì)還是一個(gè)容器，只是他不依賴(lài)于具體的標(biāo)準(zhǔn)容器類(lèi)型，可以理解是容器的模版。或者把它理解為容器的接口，而適配器具體采用哪種容器類(lèi)型去實(shí)現(xiàn)，在定義適配器的時(shí)候可以由你決定。

下表列出STL定義的三類(lèi)容器所包含的具體容器類(lèi)：

vector ,deque和list

順序性容器：

向量vector：

是一個(gè)線性順序結(jié)構(gòu)。相當(dāng)于數(shù)組，但其大小可以不預(yù)先指定，并且自動(dòng)擴(kuò)展。它可以像數(shù)組一樣被操作，由于它的特性我們完全可以將vector看作動(dòng)態(tài)數(shù)組。在創(chuàng)建一個(gè)vector后，它會(huì)自動(dòng)在內(nèi)存中分配一塊連續(xù)的內(nèi)存空間進(jìn)行數(shù)據(jù)存儲(chǔ)，初始的空間大小可以預(yù)先指定也可以由vector默認(rèn)指定，這個(gè)大小即capacity（）函數(shù)的返回值。當(dāng)存儲(chǔ)的數(shù)據(jù)超過(guò)分配的空間時(shí)vector會(huì)重新分配一塊內(nèi)存塊，但這樣的分配是很耗時(shí)的，在重新分配空間時(shí)它會(huì)做這樣的動(dòng)作：

首先，vector會(huì)申請(qǐng)一塊更大的內(nèi)存塊；

然后，將原來(lái)的數(shù)據(jù)拷貝到新的內(nèi)存塊中；

其次，銷(xiāo)毀掉原內(nèi)存塊中的對(duì)象（調(diào)用對(duì)象的析構(gòu)函數(shù)）；

最后，將原來(lái)的內(nèi)存空間釋放掉。

如果vector保存的數(shù)據(jù)量很大時(shí)，這樣的操作一定會(huì)導(dǎo)致糟糕的性能（這也是vector被設(shè)計(jì)成比較容易拷貝的值類(lèi)型的原因）。所以說(shuō)vector不是在什么情況下性能都好，只有在預(yù)先知道它大小的情況下vector的性能才是最優(yōu)的。

vector的特點(diǎn)：(1)指定一塊如同數(shù)組一樣的連續(xù)存儲(chǔ)，但空間可以動(dòng)態(tài)擴(kuò)展。即它可以像數(shù)組一樣操作，并且可以進(jìn)行動(dòng)態(tài)操作。通常體現(xiàn)在push_back() pop_back()。(2)隨機(jī)訪問(wèn)方便，它像數(shù)組一樣被訪問(wèn)，即支持[ ]操作符和vector.at()(3)節(jié)省空間，因?yàn)樗沁B續(xù)存儲(chǔ)，在存儲(chǔ)數(shù)據(jù)的區(qū)域都是沒(méi)有被浪費(fèi)的，但是要明確一點(diǎn)vector大多情況下并不是滿存的，在未存儲(chǔ)的區(qū)域?qū)嶋H是浪費(fèi)的。

(4)在內(nèi)部進(jìn)行插入、刪除操作效率非常低，這樣的操作基本上是被禁止的。Vector被設(shè)計(jì)成只能在后端進(jìn)行追加和刪除操作，其原因是vector內(nèi)部的實(shí)現(xiàn)是按照順序表的原理。(5)只能在vector的最后進(jìn)行push和pop，不能在vector的頭進(jìn)行push和pop。(6)當(dāng)動(dòng)態(tài)添加的數(shù)據(jù)超過(guò)vector默認(rèn)分配的大小時(shí)要進(jìn)行內(nèi)存的重新分配、拷貝與釋放，這個(gè)操作非常消耗性能。所以要vector達(dá)到最優(yōu)的性能，最好在創(chuàng)建vector時(shí)就指定其空間大小。

雙向鏈表list

是一個(gè)線性鏈表結(jié)構(gòu)，它的數(shù)據(jù)由若干個(gè)節(jié)點(diǎn)構(gòu)成，每一個(gè)節(jié)點(diǎn)都包括一個(gè)信息塊（即實(shí)際存儲(chǔ)的數(shù)據(jù)）、一個(gè)前驅(qū)指針和一個(gè)后驅(qū)指針。它無(wú)需分配指定的內(nèi)存大小且可以任意伸縮，這是因?yàn)樗鎯?chǔ)在非連續(xù)的內(nèi)存空間中，并且由指針將有序的元素鏈接起來(lái)。

由于其結(jié)構(gòu)的原因，list隨機(jī)檢索的性能非常的不好，因?yàn)樗幌駐ector那樣直接找到元素的地址，而是要從頭一個(gè)一個(gè)的順序查找，這樣目標(biāo)元素越靠后，它的檢索時(shí)間就越長(zhǎng)。檢索時(shí)間與目標(biāo)元素的位置成正比。

雖然隨機(jī)檢索的速度不夠快，但是它可以迅速地在任何節(jié)點(diǎn)進(jìn)行插入和刪除操作。因?yàn)閘ist的每個(gè)節(jié)點(diǎn)保存著它在鏈表中的位置，插入或刪除一個(gè)元素僅對(duì)最多三個(gè)元素有所影響，不像vector會(huì)對(duì)操作點(diǎn)之后的所有元素的存儲(chǔ)地址都有所影響，這一點(diǎn)是vector不可比擬的。

list的特點(diǎn)：(1)不使用連續(xù)的內(nèi)存空間這樣可以隨意地進(jìn)行動(dòng)態(tài)操作；(2)可以在內(nèi)部任何位置快速地插入或刪除，當(dāng)然也可以在兩端進(jìn)行push和pop。(3)不能進(jìn)行內(nèi)部的隨機(jī)訪問(wèn)，即不支持[ ]操作符和vector.at()；(4)相對(duì)于verctor占用更多的內(nèi)存。

雙端隊(duì)列deque是一種優(yōu)化了的、對(duì)序列兩端元素進(jìn)行添加和刪除操作的基本序列容器。它允許較為快速地隨機(jī)訪問(wèn)，但它不像vector把所有的對(duì)象保存在一塊連續(xù)的內(nèi)存塊，而是采用多個(gè)連續(xù)的存儲(chǔ)塊，并且在一個(gè)映射結(jié)構(gòu)中保存對(duì)這些塊及其順序的跟蹤。向deque兩端添加或刪除元素的開(kāi)銷(xiāo)很小。它不需要重新分配空間，所以向末端增加元素比vector更有效。

實(shí)際上，deque是對(duì)vector和list優(yōu)缺點(diǎn)的結(jié)合，它是處于兩者之間的一種容器。

deque的特點(diǎn)：(1)隨機(jī)訪問(wèn)方便，即支持[ ]操作符和vector.at()，但性能沒(méi)有vector好；(2)可以在內(nèi)部進(jìn)行插入和刪除操作，但性能不及l(fā)ist；(3)可以在兩端進(jìn)行push、pop；

三者的比較

下圖描述了vector、list、deque在內(nèi)存結(jié)構(gòu)上的特點(diǎn)：

vector是一段連續(xù)的內(nèi)存塊，而deque是多個(gè)連續(xù)的內(nèi)存塊，list是所有數(shù)據(jù)元素分開(kāi)保存，可以是任何兩個(gè)元素沒(méi)有連續(xù)。

vector的查詢(xún)性能最好，并且在末端增加數(shù)據(jù)也很好，除非它重新申請(qǐng)內(nèi)存段；適合高效地隨機(jī)存儲(chǔ)。

list是一個(gè)鏈表，任何一個(gè)元素都可以是不連續(xù)的，但它都有兩個(gè)指向上一元素和下一元素的指針。所以它對(duì)插入、刪除元素性能是最好的，而查詢(xún)性能非常差；適合大量地插入和刪除操作而不關(guān)心隨機(jī)存取的需求。

deque是介于兩者之間，它兼顧了數(shù)組和鏈表的優(yōu)點(diǎn)，它是分塊的鏈表和多個(gè)數(shù)組的聯(lián)合。所以它有被list好的查詢(xún)性能，有被vector好的插入、刪除性能。如果你需要隨即存取又關(guān)心兩端數(shù)據(jù)的插入和刪除，那么deque是最佳之選。

關(guān)聯(lián)容器

set, multiset, map, multimap是一種非線性的樹(shù)結(jié)構(gòu)，具體的說(shuō)采用的是一種比較高效的特殊的平衡檢索二叉樹(shù)——紅黑樹(shù)結(jié)構(gòu)。（至于什么是紅黑樹(shù)，我也不太理解，只能理解到它是一種二叉樹(shù)結(jié)構(gòu)）

因?yàn)殛P(guān)聯(lián)容器的這四種容器類(lèi)都使用同一原理，所以他們核心的算法是一致的，但是它們?cè)趹?yīng)用上又有一些差別，先描述一下它們之間的差別。

set，又稱(chēng)集合，實(shí)際上就是一組元素的集合，但其中所包含的元素的值是唯一的，且是按一定順序排列的，集合中的每個(gè)元素被稱(chēng)作集合中的實(shí)例。因?yàn)槠鋬?nèi)部是通過(guò)鏈表的方式來(lái)組織，所以在插入的時(shí)候比vector快，但在查找和末尾添加上被vector慢。

multiset，是多重集合，其實(shí)現(xiàn)方式和set是相似的，只是它不要求集合中的元素是唯一的，也就是說(shuō)集合中的同一個(gè)元素可以出現(xiàn)多次。

map，提供一種“鍵-值”關(guān)系的一對(duì)一的數(shù)據(jù)存儲(chǔ)能力。其“鍵”在容器中不可重復(fù)，且按一定順序排列（其實(shí)我們可以將set也看成是一種鍵-值關(guān)系的存儲(chǔ)，只是它只有鍵沒(méi)有值。它是map的一種特殊形式）。由于其是按鏈表的方式存儲(chǔ)，它也繼承了鏈表的優(yōu)缺點(diǎn)。

multimap， 和map的原理基本相似，它允許“鍵”在容器中可以不唯一。

關(guān)聯(lián)容器的特點(diǎn)是明顯的，相對(duì)于順序容器，有以下幾個(gè)主要特點(diǎn)：

1，其內(nèi)部實(shí)現(xiàn)是采用非線性的二叉樹(shù)結(jié)構(gòu)，具體的說(shuō)是紅黑樹(shù)的結(jié)構(gòu)原理實(shí)現(xiàn)的；

2，set和map保證了元素的唯一性，mulset和mulmap擴(kuò)展了這一屬性，可以允許元素不唯一；

3，元素是有序的集合，默認(rèn)在插入的時(shí)候按升序排列。

基于以上特點(diǎn)，

1，關(guān)聯(lián)容器對(duì)元素的插入和刪除操作比vector要快，因?yàn)関ector是順序存儲(chǔ)，而關(guān)聯(lián)容器是鏈?zhǔn)酱鎯?chǔ)；比list要慢，是因?yàn)榧词顾鼈兺擎準(zhǔn)浇Y(jié)構(gòu)，但list是線性的，而關(guān)聯(lián)容器是二叉樹(shù)結(jié)構(gòu)，其改變一個(gè)元素涉及到其它元素的變動(dòng)比list要多，并且它是排序的，每次插入和刪除都需要對(duì)元素重新排序；

2，關(guān)聯(lián)容器對(duì)元素的檢索操作比vector慢，但是比list要快很多。vector是順序的連續(xù)存儲(chǔ)，當(dāng)然是比不上的，但相對(duì)鏈?zhǔn)降膌ist要快很多是因?yàn)閘ist是逐個(gè)搜索，它搜索的時(shí)間是跟容器的大小成正比，而關(guān)聯(lián)容器查找的復(fù)雜度基本是Log(N)，比如如果有1000個(gè)記錄，最多查找10次，1,000,000個(gè)記錄，最多查找20次。容器越大，關(guān)聯(lián)容器相對(duì)list的優(yōu)越性就越能體現(xiàn)；

3，在使用上set區(qū)別于vector,deque,list的最大特點(diǎn)就是set是內(nèi)部排序的，這在查詢(xún)上雖然遜色于vector，但是卻大大的強(qiáng)于list。

4，在使用上map的功能是不可取代的，它保存了“鍵-值”關(guān)系的數(shù)據(jù)，而這種鍵值關(guān)系采用了類(lèi)數(shù)組的方式。數(shù)組是用數(shù)字類(lèi)型的下標(biāo)來(lái)索引元素的位置，而map是用字符型關(guān)鍵字來(lái)索引元素的位置。在使用上map也提供了一種類(lèi)數(shù)組操作的方式，即它可以通過(guò)下標(biāo)來(lái)檢索數(shù)據(jù)，這是其他容器做不到的，當(dāng)然也包括set。（STL中只有vector和map可以通過(guò)類(lèi)數(shù)組的方式操作元素，即如同ele[1]方式）

容器適配器

STL中包含三種適配器：棧stack、隊(duì)列queue和優(yōu)先級(jí)priority_queue。

適配器是容器的接口，它本身不能直接保存元素，它保存元素的機(jī)制是調(diào)用另一種順序容器去實(shí)現(xiàn)，即可以把適配器看作“它保存一個(gè)容器，這個(gè)容器再保存所有元素”。

STL中提供的三種適配器可以由某一種順序容器去實(shí)現(xiàn)。默認(rèn)下stack和queue基于deque容器實(shí)現(xiàn)，priority_queue則基于vector容器實(shí)現(xiàn)。當(dāng)然在創(chuàng)建一個(gè)適配器時(shí)也可以指定具體的實(shí)現(xiàn)容器，創(chuàng)建適配器時(shí)在第二個(gè)參數(shù)上指定具體的順序容器可以覆蓋適配器的默認(rèn)實(shí)現(xiàn)。

由于適配器的特點(diǎn)，一個(gè)適配器不是可以由任一個(gè)順序容器都可以實(shí)現(xiàn)的。

棧stack的特點(diǎn)是后進(jìn)先出，所以它關(guān)聯(lián)的基本容器可以是任意一種順序容器，因?yàn)檫@些容器類(lèi)型結(jié)構(gòu)都可以提供棧的操作有求，它們都提供了push_back、pop_back和back操作；

隊(duì)列queue的特點(diǎn)是先進(jìn)先出，適配器要求其關(guān)聯(lián)的基礎(chǔ)容器必須提供pop_front操作，因此其不能建立在vector容器上；

優(yōu)先級(jí)隊(duì)列priority_queue適配器要求提供隨機(jī)訪問(wèn)功能，因此不能建立在list容器上。