C++編程語言已經(jīng)推出就受到了廣大開發(fā)人員的青睞。其功能的強(qiáng)大性使其在開發(fā)領(lǐng)域中占據(jù)著重要的地位。我們?cè)谶@里介紹的C++標(biāo)準(zhǔn)類庫就是其中一個(gè)比較基礎(chǔ)的應(yīng)用技術(shù)。#t#

C++標(biāo)準(zhǔn)類庫是一套實(shí)現(xiàn)了常見的結(jié)構(gòu)和算法的模板，例如dynamic arrays（稱為vector），set，map等等。使用C++標(biāo)準(zhǔn)類庫可以節(jié)省你很多時(shí)間來寫和調(diào)試那些容器。和之前談到的一樣，如果希望系統(tǒng)的效率***化，你必須要注意你的C++標(biāo)準(zhǔn)類庫的具體實(shí)現(xiàn)的細(xì)節(jié)。

為了能夠?qū)?yīng)于***范圍的應(yīng)用，C++標(biāo)準(zhǔn)類庫的標(biāo)準(zhǔn)在內(nèi)存分配這個(gè)領(lǐng)域保持了沉默。在C++標(biāo)準(zhǔn)類庫容器中的每一個(gè)操作都有一定的效率保證，例如，給一個(gè)set進(jìn)行插入操作只要O(log n)的時(shí)間，但是，對(duì)一個(gè)容器的內(nèi)存使用沒有任何保證。

讓我們來仔細(xì)了解游戲開發(fā)中的一個(gè)非常普遍的問題：你希望保存一組對(duì)象，（我們會(huì)稱其為對(duì)象列表，雖然不一定要保存在C++標(biāo)準(zhǔn)類庫的列表中）通常你會(huì)要求每個(gè)對(duì)象在這個(gè)表有且僅有一個(gè)，這樣你就不用擔(dān)心一個(gè)偶然產(chǎn)生的在容器中插入一個(gè)已存在單元的操作了。C++標(biāo)準(zhǔn)類庫的set忽略副本，所有的插入、刪除和查詢的速度都是O(log n)，這是不是就是很好的選擇呢？

雖然在set上的大多數(shù)操作的速度都是O(log n)，但是這里面依然存在著潛在的危機(jī)。雖然容器的內(nèi)存使用依賴于實(shí)現(xiàn)，但很多實(shí)現(xiàn)還是在紅黑樹的基礎(chǔ)上實(shí)現(xiàn)的。在紅黑樹上，樹的每一個(gè)節(jié)點(diǎn)都是容器的一個(gè)元素。常見的實(shí)現(xiàn)方法是在每一個(gè)元素被加入到樹時(shí)，分配一個(gè)節(jié)點(diǎn)，而當(dāng)每個(gè)元素被移出樹時(shí)，釋放一個(gè)節(jié)點(diǎn)。根據(jù)你插入和刪除的頻繁程度，在內(nèi)存管理器上所花費(fèi)的時(shí)間將或多或少的影響你通過使用set而獲得的好處。

另外一個(gè)解決方案是使用vector來存儲(chǔ)元素，vector保證在容器的末端添加元素有很高的效率。這表示實(shí)際上vector只在很偶然的情況下才重新分配內(nèi)存，也就是說，當(dāng)滿的時(shí)候擴(kuò)容一倍。當(dāng)使用vector來保存一個(gè)不同元素列表的時(shí)候，你首先要檢查元素是否已經(jīng)存在，如果沒有，那么加入。而對(duì)整個(gè)vector檢查一遍需要花費(fèi)O(n)的時(shí)間，但是但實(shí)際牽涉到的部分應(yīng)該比較少，這是因?yàn)関ector的每個(gè)元素都在內(nèi)存中連續(xù)存放，所以檢查整個(gè)vector實(shí)際上是一個(gè)易于cache的操作。檢查整個(gè)set將造成cache不命中，這是因?yàn)樵诩t黑樹上分別存放的元素可能散布在內(nèi)存的各個(gè)角落。同時(shí)，我們也注意到set必須額外維護(hù)一組標(biāo)記以設(shè)置整個(gè)樹。如果你要保存的是對(duì)象的指針，set可能要花費(fèi)vector所要花費(fèi)的內(nèi)存的3到4倍。

Set的刪除操作消耗時(shí)間O(log n)，看起來是很快，如果你不考慮可能對(duì)free()的調(diào)用的話。Vector的刪除操作消耗O(n)，這是因?yàn)閺谋粍h除的那個(gè)元素開始到結(jié)尾處的元素，每一個(gè)元素都要被拷貝到前一個(gè)位置上。如果元素都只是指針的話，那么這個(gè)拷貝將可以依靠一個(gè)簡(jiǎn)單的memcpy()來完成，而這個(gè)函數(shù)是相當(dāng)快的。（這也是為什么通常都把對(duì)象的指針儲(chǔ)存在C++標(biāo)準(zhǔn)類庫的容器中的一個(gè)原因，而不是儲(chǔ)存對(duì)象本身。如果你直接保存了對(duì)象本身，將會(huì)在很多操作中造成許多額外的構(gòu)造函數(shù)的調(diào)用，例如刪除等）。

set和map通常來說麻煩大于有用，如果你還沒有意識(shí)到這一點(diǎn)的話，考慮遍歷一個(gè)容器的代價(jià)，例如：

for(Collection::iterator it = Collection.begin(); 
it != Collection.end(); ++it) 

如果Collection是vector，那么++it就是一個(gè)指針自增。但是當(dāng)Collection是一個(gè)set或者是一個(gè)map的話，++it包括了訪問紅黑樹上的下一個(gè)節(jié)點(diǎn)。這個(gè)操作相當(dāng)復(fù)雜而且很容易造成cache不命中，因?yàn)闃涞墓?jié)點(diǎn)幾乎遍布內(nèi)存的各處。

當(dāng)然，如果你要在容器中保存大量的元素，并且進(jìn)行許多的成員請(qǐng)求，那么set的O(log n)的效率完全可以抵消那些內(nèi)存方面的消耗。近似的，如果你偶爾才使用容器，那么這里的效率差別就非常的小。你應(yīng)該做一些效率評(píng)估以了解多大的n會(huì)使set變得更快。也許你會(huì)驚奇的發(fā)現(xiàn)在游戲的大多數(shù)典型應(yīng)用下vector的所有效率都比set要高。

這還不是C++標(biāo)準(zhǔn)類庫內(nèi)存使用的全部。一定要了解當(dāng)你使用clear方法時(shí)，容器是否真的釋放掉了它的內(nèi)存。如果沒有，就可能產(chǎn)生內(nèi)存碎片。比如，如果你開始游戲的時(shí)候建立了一個(gè)空的vector，在游戲過程中增加元素，然后在游戲restart時(shí)調(diào)用clear，這時(shí)vector未必釋放它的全部?jī)?nèi)存。這個(gè)空的vector，可能依然占據(jù)了堆中的內(nèi)存，并使其變成碎片。如果你真的需要這樣來實(shí)現(xiàn)游戲的話，對(duì)這個(gè)問題有兩種解法。一是你可以在創(chuàng)建vector時(shí)調(diào)用reserve()，為你可能需要的***數(shù)量的元素保留足夠的空間。如果這不可行的話，你可以強(qiáng)迫vector完全釋放內(nèi)存：

Vector V;  
// … elements are inserted into V here  
Vector().swap(v);　　  
// causes v to free its memory 

Set、list以及map都沒有這個(gè)問題，這是因?yàn)樗麄優(yōu)槊總€(gè)元素分別分配和釋放內(nèi)存。