欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

深入解析C++ STL中的常用容器

 更新時間:2013年09月09日 10:12:00   作者:  
這里我們不涉及容器的基本操作之類,只是要討論一下各個容器其各自的特點。STL中的常用容器包括:順序性容器(vector、deque、list)、關(guān)聯(lián)容器(map、set)、容器適配器(queue、stac)

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

1、順序性容器

(1)vector
vector是一種動態(tài)數(shù)組,在內(nèi)存中具有連續(xù)的存儲空間,支持快速隨機訪問。由于具有連續(xù)的存儲空間,所以在插入和刪除操作方面,效率比較慢。vector有多個構(gòu)造函數(shù),默認的構(gòu)造函數(shù)是構(gòu)造一個初始長度為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倍,再將原先空間中的元素復制到新的空間中,性能消耗比較大,尤其是當元素是非內(nèi)部數(shù)據(jù)時(非內(nèi)部數(shù)據(jù)往往構(gòu)造及拷貝構(gòu)造函數(shù)相當復雜)。vector的另一個常見的問題就是clear操作。clear函數(shù)只是把vector的size清為零,但vector中的元素在內(nèi)存中并沒有消除,所以在使用vector的過程中會發(fā)現(xiàn)內(nèi)存消耗會越來越多,導致內(nèi)存泄露,現(xiàn)在經(jīng)常用的方法是swap函數(shù)來進行解決:

復制代碼 代碼如下:

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ù),和臨時對象交換,使V對象的內(nèi)存為臨時對象的內(nèi)存,而臨時對象的內(nèi)存為V對象的內(nèi)存。交換以后,臨時對象消失,釋放內(nèi)存。

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

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

(4)在實際使用時,如何選擇這三個容器中哪一個,應(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ù)都是有序的,以二叉樹的形式進行組織。

這是map的模板:
template < class Key, class T, class Compare= less<Key>, class Allocator=allocator< pair<const Key,T> > > class map;

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

(2)set
set也是一種關(guān)聯(lián)性容器,它同map一樣,底層使用紅黑樹實現(xiàn),插入刪除操作時僅僅移動指針即可,不涉及內(nèi)存的移動和拷貝,所以效率比較高。set中的元素都是唯一的,而且默認情況下會對元素進行升序排列。所以在set中,不能直接改變元素值,因為那樣會打亂原本正確的順序,要改變元素值必須先刪除舊元素,再插入新元素。不提供直接存取元素的任何操作函數(shù),只能通過迭代器進行間接存取。

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是一個隊列,實現(xiàn)先進先出功能,queue不是標準的STL容器,卻以標準的STL容器為基礎(chǔ)。queue是在deque的基礎(chǔ)上封裝的。之所以選擇deque而不選擇vector是因為deque在刪除元素的時候釋放空間,同時在重新申請空間的時候無需拷貝所有元素。

其模板為:
template < TYPENAME _Sequence="deque<_TP" typeneam _Tp,> > class queue;

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

相關(guān)文章

最新評論