C++編程語言已經推出就受到了廣大開發人員的青睞。其功能的強大性使其在開發領域中占據著重要的地位。我們在這里介紹的C++標準類庫就是其中一個比較基礎的應用技術。#t#

C++標準類庫是一套實現了常見的結構和算法的模板，例如dynamic arrays（稱為vector），set，map等等。使用C++標準類庫可以節省你很多時間來寫和調試那些容器。和之前談到的一樣，如果希望系統的效率***化，你必須要注意你的C++標準類庫的具體實現的細節。

為了能夠對應于***范圍的應用，C++標準類庫的標準在內存分配這個領域保持了沉默。在C++標準類庫容器中的每一個操作都有一定的效率保證，例如，給一個set進行插入操作只要O(log n)的時間，但是，對一個容器的內存使用沒有任何保證。

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

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

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

Set的刪除操作消耗時間O(log n)，看起來是很快，如果你不考慮可能對free()的調用的話。Vector的刪除操作消耗O(n)，這是因為從被刪除的那個元素開始到結尾處的元素，每一個元素都要被拷貝到前一個位置上。如果元素都只是指針的話，那么這個拷貝將可以依靠一個簡單的memcpy()來完成，而這個函數是相當快的。（這也是為什么通常都把對象的指針儲存在C++標準類庫的容器中的一個原因，而不是儲存對象本身。如果你直接保存了對象本身，將會在很多操作中造成許多額外的構造函數的調用，例如刪除等）。

set和map通常來說麻煩大于有用，如果你還沒有意識到這一點的話，考慮遍歷一個容器的代價，例如：

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

如果Collection是vector，那么++it就是一個指針自增。但是當Collection是一個set或者是一個map的話，++it包括了訪問紅黑樹上的下一個節點。這個操作相當復雜而且很容易造成cache不命中，因為樹的節點幾乎遍布內存的各處。

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

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

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

Set、list以及map都沒有這個問題，這是因為他們為每個元素分別分配和釋放內存。