摘要：本文探討了C++語言中STL容器的概念、分類和內(nèi)存管理方式，并在最后總結(jié)了不同容器對(duì)程序性能的影響。不同的STL容器具有各自特點(diǎn)和應(yīng)用場(chǎng)景，在適當(dāng)?shù)胤绞褂谜_的STL容器，既可以提高編碼效率又可保證程序質(zhì)量，達(dá)到事半功倍的效果；反之，如果毫無規(guī)則的應(yīng)用STL容器，將會(huì)給程序帶來一些莫名其妙的隱患，最明顯的是對(duì)性能的影響，造成事倍功半的反效果。

關(guān)鍵詞：STL 容器 vector deque list set map 效率

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2015）09-0000-00

1概念

STL是Standard Template Library的英文簡(jiǎn)稱，中文名稱為標(biāo)準(zhǔn)模板庫(kù)，STL最開始由惠普實(shí)驗(yàn)室開發(fā)，后來收錄到C++標(biāo)準(zhǔn)規(guī)范中。從根本上說，STL是一些“容器”的集合，這些“容器”有l(wèi)ist、vector、set、map等，STL也是算法和其他一些組件的集合。STL的目的是標(biāo)準(zhǔn)化組件，這樣在編寫應(yīng)用程序過程中就不用重新開發(fā)，可以使用現(xiàn)成的組件。當(dāng)前所有的C++編譯器都提供對(duì)STL支持，STL的版本很多，常見的有HP STL、PJ STL、 SGI STL等。本文討論的目標(biāo)為標(biāo)準(zhǔn)STL容器。

2 STL容器的分類

根據(jù)STL容器自身性質(zhì)和數(shù)據(jù)組織方式可以分為兩類：序列容器、關(guān)聯(lián)容器。序列容器有vector、deque、list、string，關(guān)聯(lián)容器有set、map。在序列容器中，元素的組織是有序的，而在關(guān)聯(lián)容器中，序列的組織是無序的。

根據(jù)STL容器的存儲(chǔ)方式可以分為兩類：連續(xù)存儲(chǔ)容器、節(jié)點(diǎn)存儲(chǔ)容器。連續(xù)存儲(chǔ)容器有vector、deque、string，節(jié)點(diǎn)存儲(chǔ)容器有set、map、list。在連續(xù)存儲(chǔ)容器中，元素被保存在連續(xù)的內(nèi)存空間；在節(jié)點(diǎn)存儲(chǔ)容器中，元素被分散保存在系統(tǒng)可用內(nèi)存中，節(jié)點(diǎn)存儲(chǔ)容器對(duì)分散保存的元素提供管理，通過指針將所有元素組合在一起，形成邏輯上整體。

3不同容器的內(nèi)存管理方式

STL的每種容器內(nèi)存管理方式在實(shí)現(xiàn)上各不相同，可根據(jù)不同應(yīng)用場(chǎng)景要求，結(jié)合容器內(nèi)存管理方式優(yōu)缺點(diǎn)，選取適合使用的容器。

3.1 vector

vector中的元素保存在一片連續(xù)內(nèi)存空間中。vector采取內(nèi)存預(yù)申請(qǐng)策略避免新增數(shù)據(jù)引起內(nèi)存頻繁操作，在初始狀態(tài)時(shí)，vector會(huì)默認(rèn)申請(qǐng)一片內(nèi)存，當(dāng)預(yù)申請(qǐng)的內(nèi)存不夠用時(shí)，vector會(huì)參照內(nèi)存分配策略申請(qǐng)比當(dāng)前所需內(nèi)存更大的空間；由于新增元素導(dǎo)致預(yù)申請(qǐng)空間不夠用時(shí)，vector執(zhí)行操作步驟如下：

（1）申請(qǐng)一塊大小為當(dāng)前使用的內(nèi)存空間兩倍大小的內(nèi)存；（2）將現(xiàn)有的元素拷貝到步驟1申請(qǐng)的內(nèi)存塊中；（3）釋放當(dāng)前使用的內(nèi)存空間，并將剛申請(qǐng)的內(nèi)存空間設(shè)置為當(dāng)前在用內(nèi)存；（4）保存新增元素。

如果在vector的非末尾位置新增/刪除元素，vector需要在內(nèi)存中拷貝移動(dòng)現(xiàn)有元素位置，為新增元素騰出存儲(chǔ)空間/用覆蓋的方式刪除指定元素。此外，vector中的元素被刪除后，vector不會(huì)主動(dòng)釋放已經(jīng)申請(qǐng)內(nèi)存空間。

3.2 deque

deque中的元素保存在若干片連續(xù)內(nèi)存空間中，有deque內(nèi)部的管理器對(duì)這些空間進(jìn)行管理。deque也是采取內(nèi)存預(yù)申請(qǐng)策略避免新增數(shù)據(jù)引起內(nèi)存頻繁操作，在初始狀態(tài)時(shí)，deque會(huì)默認(rèn)申請(qǐng)一片內(nèi)存，當(dāng)預(yù)申請(qǐng)的內(nèi)存不夠用時(shí)，deque會(huì)參照內(nèi)存分配策略申請(qǐng)一片新增的內(nèi)存空間；由于新增元素導(dǎo)致預(yù)申請(qǐng)空間不夠用時(shí)，deque執(zhí)行操作步驟如下：

（1）申請(qǐng)新增一塊內(nèi)存；（2）將步驟1申請(qǐng)的內(nèi)存塊納入內(nèi)部管理器；（3）保存新增元素。

對(duì)deque中的元素執(zhí)行刪除后，deque不會(huì)主動(dòng)釋放已經(jīng)申請(qǐng)的內(nèi)存空間，deque可在隊(duì)列的頭和尾新增元素。

3.3 list

list中的元素不是保存在連續(xù)的內(nèi)存塊中，在大部分的list實(shí)現(xiàn)中，list其實(shí)是一個(gè)雙向的環(huán)形隊(duì)列。當(dāng)新增加一個(gè)元素時(shí)，動(dòng)態(tài)為該元素分配內(nèi)存，并插入到list中相應(yīng)的位置。刪除一個(gè)元素時(shí)，list會(huì)立即釋放該元素占用的內(nèi)存。

3.4 set/map

set/map中的元素不是保存在連續(xù)的內(nèi)存塊中，在大部分的set/map實(shí)現(xiàn)中，set/map是一棵平衡二叉樹。當(dāng)新增加一個(gè)元素時(shí)，動(dòng)態(tài)為該元素分配內(nèi)存，并插入到set/map中相應(yīng)的位置。刪除一個(gè)元素時(shí)，set/map會(huì)立即釋放該元素占用的內(nèi)存。

4 不同容器對(duì)性能的影響

實(shí)際編程過程中對(duì)stl容器有各種不同的應(yīng)用場(chǎng)景，下表根據(jù)STL容器的內(nèi)存管理方式，針對(duì)若干典型應(yīng)用場(chǎng)景進(jìn)行分析，在具體項(xiàng)目的應(yīng)用過程中，可以結(jié)合項(xiàng)目特點(diǎn)，選擇自己適用的容器見圖1。

圖1

5 結(jié)語

本文介紹了STL常見容器的分類和基本特點(diǎn)，并在此基礎(chǔ)上對(duì)各種容器在不同應(yīng)用場(chǎng)景下的性能進(jìn)行說明。在程序中正確的使用STL容器可以減少代碼量，提升開發(fā)效率，讓系統(tǒng)更穩(wěn)定、高效。

參考文獻(xiàn)

[1][美]Noel Llopis著，李鵬賈傳俊譯.C++游戲編程[M].清華大學(xué)出版社，2004年9月.

[2][美]Stanley B.Lippman，[美]Josee Lajoie著，潘愛民，張麗譯.C++ Primer第3版[M].中國(guó)電力出版社，2006年9月.

[3][美] Scott Meyers，潘愛民，陳銘，鄒開紅譯.Effective STL中文版[M].電子工業(yè)出版社，2013年5月.

[4][臺(tái)]侯杰.STL源碼剖析[M].華中科技大學(xué)出版社，2002年6月.

收稿日期：2015-08-11

作者簡(jiǎn)介：賴祥芳（1979—），男，漢族，福建南平人，本科，產(chǎn)品經(jīng)理，主要從事中國(guó)電信計(jì)費(fèi)域相關(guān)軟件產(chǎn)品研發(fā)。