快捷導(dǎo)航

STL常用容器詳細(xì)解析

更新時(shí)間：2013年09月23日 09:33:39 作者：

這里我們不涉及容器的基本操作之類，只是要討論一下各個(gè)容器其各自的特點(diǎn)STL中的常用容器包括：順序性容器（vector、deque、list）、關(guān)聯(lián)容器（map、set）、容器適配器（queue、stac）

STL是C/C++開發(fā)中一個(gè)非常重要的模板，而其中定義的各種容器也是非常方便我們大家使用。下面，我們就淺談某些常用的容器。這里我們不涉及容器的基本操作之類，只是要討論一下各個(gè)容器其各自的特點(diǎn)。STL中的常用容器包括：順序性容器（vector、deque、list）、關(guān)聯(lián)容器（map、set）、容器適配器（queue、stac）。

1、順序性容器

（1）vector
vector是一種動(dòng)態(tài)數(shù)組，在內(nèi)存中具有連續(xù)的存儲(chǔ)空間，支持快速隨機(jī)訪問。由于具有連續(xù)的存儲(chǔ)空間，所以在插入和刪除操作方面，效率比較慢。vector有多個(gè)構(gòu)造函數(shù)，默認(rèn)的構(gòu)造函數(shù)是構(gòu)造一個(gè)初始長度為0的內(nèi)存空間，且分配的內(nèi)存空間是以2的倍數(shù)動(dòng)態(tài)增長的，即內(nèi)存空間增長是按照20,21,22,23.....增長的，在push_back的過程中，若發(fā)現(xiàn)分配的內(nèi)存空間不足，則重新分配一段連續(xù)的內(nèi)存空間，其大小是現(xiàn)在連續(xù)空間的2倍，再將原先空間中的元素復(fù)制到新的空間中，性能消耗比較大，尤其是當(dāng)元素是非內(nèi)部數(shù)據(jù)時(shí)(非內(nèi)部數(shù)據(jù)往往構(gòu)造及拷貝構(gòu)造函數(shù)相當(dāng)復(fù)雜)。vector的另一個(gè)常見的問題就是clear操作。clear函數(shù)只是把vector的size清為零，但vector中的元素在內(nèi)存中并沒有消除，所以在使用vector的過程中會(huì)發(fā)現(xiàn)內(nèi)存消耗會(huì)越來越多，導(dǎo)致內(nèi)存泄露，現(xiàn)在經(jīng)常用的方法是swap函數(shù)來進(jìn)行解決：

vector<int> V;V.push_back(1); V.push_back(2);V.push_back(1); V.push_back(2);
vector<int>().swap(V); 或者 V.swap(vector<int>());

利用swap函數(shù)，和臨時(shí)對(duì)象交換，使V對(duì)象的內(nèi)存為臨時(shí)對(duì)象的內(nèi)存，而臨時(shí)對(duì)象的內(nèi)存為V對(duì)象的內(nèi)存。交換以后，臨時(shí)對(duì)象消失，釋放內(nèi)存。

（2）deque
deque和vector類似，支持快速隨機(jī)訪問。二者最大的區(qū)別在于，vector只能在末端插入數(shù)據(jù)，而deque支持雙端插入數(shù)據(jù)。deque的內(nèi)存空間分布是小片的連續(xù)，小片間用鏈表相連，實(shí)際上內(nèi)部有一個(gè)map的指針。deque空間的重新分配要比vector快，重新分配空間后，原有的元素是不需要拷貝的。

（3）list
list是一個(gè)雙向鏈表，因此它的內(nèi)存空間是可以不連續(xù)的，通過指針來進(jìn)行數(shù)據(jù)的訪問，這使list的隨機(jī)存儲(chǔ)變得非常低效，因此list沒有提供[]操作符的重載。但list可以很好地支持任意地方的插入和刪除，只需移動(dòng)相應(yīng)的指針即可。

（4）在實(shí)際使用時(shí)，如何選擇這三個(gè)容器中哪一個(gè)，應(yīng)根據(jù)你的需要而定，一般應(yīng)遵循下面的原則：
　　1) 如果你需要高效的隨即存取，而不在乎插入和刪除的效率，使用vector
　　2) 如果你需要大量的插入和刪除，而不關(guān)心隨即存取，則應(yīng)使用list
　　3) 如果你需要隨即存取，而且關(guān)心兩端數(shù)據(jù)的插入和刪除，則應(yīng)使用deque

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

（1）map
map是一種關(guān)聯(lián)容器，該容器用唯一的關(guān)鍵字來映射相應(yīng)的值，即具有key-value功能。map內(nèi)部自建一棵紅黑樹（一種自平衡二叉樹），這棵樹具有數(shù)據(jù)自動(dòng)排序的功能，所以在map內(nèi)部所有的數(shù)據(jù)都是有序的，以二叉樹的形式進(jìn)行組織。這是map的模板：

template < class Key, class T, class Compare= less<Key>, class Allocator=allocator< pair<const Key,T> > > class map;

從模板中我們可以看出，再構(gòu)造map時(shí)，是按照一定的順序進(jìn)行的。map的插入和刪除效率比其他序列的容器高，因?yàn)閷?duì)關(guān)聯(lián)容器來說，不需要做內(nèi)存的拷貝和移動(dòng)，只是指針的移動(dòng)。由于map的每個(gè)數(shù)據(jù)對(duì)應(yīng)紅黑樹上的一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)在不保存你的數(shù)據(jù)時(shí)，是占用16個(gè)字節(jié)的，一個(gè)父節(jié)點(diǎn)指針，左右孩子指針，還有一個(gè)枚舉值（標(biāo)示紅黑色），所以map的其中的一個(gè)缺點(diǎn)就是比較占用內(nèi)存空間。

（2）set
set也是一種關(guān)聯(lián)性容器，它同map一樣，底層使用紅黑樹實(shí)現(xiàn)，插入刪除操作時(shí)僅僅移動(dòng)指針即可，不涉及內(nèi)存的移動(dòng)和拷貝，所以效率比較高。set中的元素都是唯一的，而且默認(rèn)情況下會(huì)對(duì)元素進(jìn)行升序排列。所以在set中，不能直接改變?cè)刂?，因?yàn)槟菢訒?huì)打亂原本正確的順序，要改變?cè)刂当仨毾葎h除舊元素，再插入新元素。不提供直接存取元素的任何操作函數(shù)，只能通過迭代器進(jìn)行間接存取。set模板原型：

template <class Key, class Compare=class<Key>, class Alloc=STL_DEFAULT_ALLOCATOR(Key) > class set;
set支持集合的交(set_intersection)、差(set_difference)、并(set_union)及對(duì)稱差(set_symmetric_difference) 等一些集合上的操作。

3、容器適配器

（1）queue
queue是一個(gè)隊(duì)列，實(shí)現(xiàn)先進(jìn)先出功能，queue不是標(biāo)準(zhǔn)的STL容器，卻以標(biāo)準(zhǔn)的STL容器為基礎(chǔ)。queue是在deque的基礎(chǔ)上封裝的。之所以選擇deque而不選擇vector是因?yàn)閐eque在刪除元素的時(shí)候釋放空間，同時(shí)在重新申請(qǐng)空間的時(shí)候無需拷貝所有元素。其模板為：
template < TYPENAME _Sequence="deque<_TP" typeneam _Tp,> > class queue;

（2）stack
stack是實(shí)現(xiàn)先進(jìn)后出的功能，和queue一樣，也是內(nèi)部封裝了deque，這也是為啥稱為容器適配器的原因吧（純屬猜測(cè)）。自己不直接維護(hù)被控序列的模板類，而是它存儲(chǔ)的容器對(duì)象來為它實(shí)現(xiàn)所有的功能。stack的源代碼原理和實(shí)現(xiàn)方式均跟queue相同。

您可能感興趣的文章: