選擇合適的STL容器

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

關鍵詞：STL 容器 vector deque list set map 效率

中圖分類號：TP393 文獻標識碼：A 文章編號：1007-9416（2015）09-0000-00

1概念

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

2 STL容器的分類

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

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

3不同容器的內存管理方式

STL的每種容器內存管理方式在實現(xiàn)上各不相同，可根據不同應用場景要求，結合容器內存管理方式優(yōu)缺點，選取適合使用的容器。

3.1 vector

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

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

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

3.2 deque

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

（1）申請新增一塊內存；（2）將步驟1申請的內存塊納入內部管理器；（3）保存新增元素。

對deque中的元素執(zhí)行刪除后，deque不會主動釋放已經申請的內存空間，deque可在隊列的頭和尾新增元素。

3.3 list

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

3.4 set/map

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

4 不同容器對性能的影響

實際編程過程中對stl容器有各種不同的應用場景，下表根據STL容器的內存管理方式，針對若干典型應用場景進行分析，在具體項目的應用過程中，可以結合項目特點，選擇自己適用的容器見圖1。

圖1

5 結語

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

參考文獻

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

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

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

[4][臺]侯杰.STL源碼剖析[M].華中科技大學出版社，2002年6月.

收稿日期：2015-08-11

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