深入解析C++ STL中的常用容器
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)文章
C語言詳解用char實現(xiàn)大小寫字母的轉(zhuǎn)換
這篇文章主要給大家介紹了關(guān)于C語言實現(xiàn)大小寫字母轉(zhuǎn)換的相關(guān)資料,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2022-05-05Qt多線程實現(xiàn)網(wǎng)絡(luò)發(fā)送文件功能
這篇文章主要為大家詳細介紹了Qt多線程實現(xiàn)網(wǎng)絡(luò)發(fā)送文件功能,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2022-08-08ON_COMMAND_RANGE多個按鈕響應(yīng)一個函數(shù)的解決方法
這篇文章主要介紹了ON_COMMAND_RANGE多個按鈕響應(yīng)一個函數(shù)的解決方法,需要的朋友可以參考下2014-07-07對比C語言中execv相關(guān)的執(zhí)行文件的三個函數(shù)
這篇文章主要介紹了對比C語言中execv相關(guān)的執(zhí)行文件的三個函數(shù),分別為execv()函數(shù)和execve()函數(shù)以及execvp()函數(shù),需要的朋友可以參考下2015-08-08