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

1、順序性容器

（1）vector
vector是一種動態(tài)數(shù)組，在內(nèi)存中具有連續(xù)的存儲空間，支持快速隨機(jī)訪問。由于具有連續(xù)的存儲空間，所以在插入和刪除操作方面，效率比較慢。vector有多個(gè)構(gòu)造函數(shù)，默認(rèn)的構(gòu)造函數(shù)是構(gòu)造一個(gè)初始長度為0的內(nèi)存空間，且分配的內(nèi)存空間是以2的倍數(shù)動態(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的過程中會發(fā)現(xiàn)內(nèi)存消耗會越來越多，導(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í)對象交換，使V對象的內(nèi)存為臨時(shí)對象的內(nèi)存，而臨時(shí)對象的內(nèi)存為V對象的內(nèi)存。交換以后，臨時(shí)對象消失，釋放內(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ī)存儲變得非常低效，因此list沒有提供[]操作符的重載。但list可以很好地支持任意地方的插入和刪除，只需移動相應(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ù)自動排序的功能，所以在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)閷﹃P(guān)聯(lián)容器來說，不需要做內(nèi)存的拷貝和移動，只是指針的移動。由于map的每個(gè)數(shù)據(jù)對應(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í)僅僅移動指針即可，不涉及內(nèi)存的移動和拷貝，所以效率比較高。set中的元素都是唯一的，而且默認(rèn)情況下會對元素進(jìn)行升序排列。所以在set中，不能直接改變元素值，因?yàn)槟菢訒騺y原本正確的順序，要改變元素值必須先刪除舊元素，再插入新元素。不提供直接存取元素的任何操作函數(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)及對稱差(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í)在重新申請空間的時(shí)候無需拷貝所有元素。其模板為：
template < TYPENAME _Sequence="deque<_TP" typeneam _Tp,> > class queue;

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

最新評論