STL高效程式設計(-) STL的容器

STL有很多概念，疊代器，高效的算法，函數對象，但是對于大多數的開發者而言，STL最突出的地方還是容器(Container)，容器遠遠比數組強大和靈活。

容器可以動态增長，獨立管理記憶體，提供對容器元素的高效的靈活的通路，等等。STL容器是有效的封裝最常見的資料結構和算法，在我看來，STL容器就是代表着c++的資料結構，從數組，連結清單，棧，隊列，表，哈希表。每一個容器代表着一種資料結構。

概括一下，STL的容器可以分為以下幾個大類:

一：序列容器，　有vector, list, deque, string.

二 : 關聯容器,     有set, multiset, map, mulmap, hash_set, hash_map, hash_multiset, hash_multimap

                                 帶有下劃線的是非标準的，如果是VC8.0的話，在stdext名字空間裡。

三: 其他的雜項： stack, queue, valarray, bitset

由此可見，STL為我們提供了那麼多的容器，如果想要有效的使用它們，你真的需要弄明白每個容器是幹什麼的。最好你能知道他們的一些實作原理，陸續的我還會寫一些STL容器實作的文章。容器的實作往往決定着你如何更好的使用容器。下面簡單講一下STL各個容器的實作:

1. vector: 内部實作是數組，一段連續的記憶體。

2. list， 内部實作是雙連結清單

3. deque 内部實作是記憶體塊的連結清單。

4. string： 連續的記憶體

5. set，map： 紅黑樹(平衡二叉樹的一種)

6. hash_map, hash_set 用哈希表(散清單)來實作。

7. stack: 用vector或者是deque來實作

8. queue,用deque實作

本文僅當時抛磚引玉，大緻講一下選擇容器的一些原則。

1. 你需要“可以在容器的任意位置插入一個新元素”的能力嗎？如果是，你需要序列容器，關聯容器做不到。

2. 你關心元素在容器中的順序嗎？如果不，散列容器就是可行的選擇。否則，你要避免使用散列容器。

3. 必須使用标準C++中的容器嗎？如果是，就可以除去散列容器、slist和rope。

4. 你需要哪一類疊代器？如果必須是随機通路疊代器，在技術上你就隻能限于vector、deque和string，但

你也可能會考慮rope.

5. 當插入或者删除資料時，是否非常在意容器内現有元素的移動？如果是，你就必須放棄連續記憶體容器

6. 容器中的資料的記憶體布局需要相容C嗎？如果是，你就隻能用vector.

7. 查找速度很重要嗎？如果是，你就應該看看散列容器，排序的vector和

标準的關聯容器——僅供參考。

● 你介意如果容器的底層使用了引用計數嗎？如果是，你就得避開string，因為很多string的實作是用引

用計數。于是你得重新稽核你的string，你可以考慮使用vector<char>。

● 你需要插入和删除的事務性語義嗎？也就是說，你需要有可靠地回退插入和删除的能力嗎？如果是，

你就需要使用基于節點的容器。如果你需要多元素插入的事務性語義，你就應該選擇list，因為list是唯一

提供多元素插入事務性語義的标準容器。事務性語義對于有興趣寫異常安全代碼的程式員來說非常重要。

（事務性語義也可以在連續記憶體容器上實作，但會有一個性能開銷，而且代碼不那麼直覺。要了解這方

面的知識，請參考Sutter的《Exceptional C++》。

● 你要把疊代器、指針和引用的失效次數減到最少嗎？如果是，你就應該使用基于節點的容器，因為在

這些容器上進行插入和删除不會使疊代器、指針和引用失效（除非它們指向你删除的元素）。一般來

說，在連續記憶體容器上插入和删除會使所有指向容器的疊代器、指針和引用失效。

● 你需要具有有以下特性的序列容器嗎：1）可以使用随機通路疊代器；2）隻要沒有删除而且插入隻發

生在容器結尾，指針和引用的資料就不會失效？  這個一個非常特殊的情況，但如果你遇到這種情況，

deque就是你夢想的容器。（有趣的是，當插入隻在容器結尾時，deque的疊代器也可能會失效，deque

是唯一一個“在疊代器失效時不會使它的指針和引用失效”的标準STL容器。為什麼呢？這是由實作所決定的，

STL高效程式設計(二)- 注意容器的不同特點，小心容器無關的代碼

STL是建立在泛型之上的。數組泛型為容器，以對象類型為參數。函數泛型成算法，以疊代器類型為參數。指針泛型為疊代器，參數化了所指向的對象的類型。

這隻是個開始。獨立的容器類型泛化為序列或關聯容器，而且類似的容器擁有類似的功能。标準的以連續記憶體為實作的容器都提供随機通路疊代器，标準的基 于節點的容器都提供雙向疊代器。序列容器支援push_front或push_back，但關聯容器不支援。關聯容器提供對數時間複雜度的 lower_bound、upper_bound和equal_range成員函數，但序列容器卻沒有。

明白容器的不同特性，對STL程式設計很重要，是以，寫容器無關的代碼是很危險的。盡管STL提供了很多一緻的接口和疊代器類型。

最熱心的“容器無關代碼”的鼓吹者很快發現，寫既要和序列容器又要和關聯容器一起工作的代碼并沒有什麼意義。很多成員函數隻存在于其中一類容器中， 比如，隻有序列容器支援push_front或push_back，隻有關聯容器支援count和lower_bound，等等。在不同種類中，甚至連一 些如insert和erase這樣簡單的操作在名稱和語義上也是天差地别的。舉個例子，當你把一個對象插入一個序列容器中，它保留在你放置的位置。但如果 你把一個對象插入到一個關聯容器中，容器會按照的排列順序把這個對象移到它應該在的位置。舉另一個例子，在一個序列容器上用一個疊代器作為參數調用 erase，會傳回一個新疊代器，但在關聯容器上什麼都不傳回。

假設, 你希望寫一段可以用在所有常用的序列容器上——vector, deque和list——的代碼。很顯然，你必須使用它們接口的交集來編寫，這意味着不能使用reserve或capacity，因為deque和 list不支援它們。由于list的存在意味着你得放棄operator[]，而且你必須受限于雙向疊代器的性能。這意味着你不能使用需要随機通路疊代器 的算法，包括sort，stable_sort，partial_sort和nth_element

另一方面，你渴望支援vector的規則，不使用push_front和pop_front，而且用vector和deque都會使splice和成員函數方式的sort失敗。在上面限制的聯合下，後者意味着你不能在你的“泛化的序列容器”上調用任何一種sort。

這是顯而易見的。如果你冒犯裡其中任何一條限制，你的代碼會在至少一個你想要使用的容器配合時發生編譯錯誤。可見這種代碼有多陰險。

這裡的罪魁禍首是不同的序列容器所對應的不同的疊代器、指針和引用的失效規則。要寫能正确地和vector, deque和list配合的代碼，你必須假設任何使那些容器的疊代器，指針或引用失效的操作符真的在你用的容器上起作用了。是以，你必須假設每次調用 insert都使所有東西失效了，因為deque::insert會使所有疊代器失效，而且因為缺少capacity，vector::insert也必 須假設使所有指針和引用失效。（條款1 解釋了deque是唯一一個在疊代器失效的情況下指針和引用仍然有效的東西）類似的理由可以推出一個結論，所有對erase的調用必須假設使所有東西失效。

STL高效程式設計(三)-使容器元素的拷貝正确和高效

首先，你必須要明白的是，容器容納着許多對象，但不是你傳給它的那些原始對象，而是對象的拷貝。

此外，當你從容器中擷取一個對象時，得到的不是容器裡的那個對象，而是對象的拷貝。同樣的，當你向容器中添加一個對象時（通過insert或push_back），添加到容器的是你給的對象的拷貝 。 copy進去，copy出來,這就是STL的方式。是以，STL要求對象必須是可拷貝的。對象被存到容器裡之後，對它的拷貝并不少見。如果你從 vector、string或deque中插入或删除了元素，現有元素會移動（拷貝）。如果你使用了任何排序算法，一般的排序算法都要求交換，交換是需要 拷貝的，這種例子很多。

你可能會對所有這些拷貝是怎麼完成的感興趣。這很簡單，一個對象通過使用它的拷貝成員函數來拷貝，特别是它的拷貝構造函數和它的拷貝指派構造函數。這就是傳說中的BIG 3. 對于使用者自定義類，比如Widget，這些函數傳統上是這麼聲明的：

class Widget { 

public: 

	...      

 Widget();       

Widget(const Widget&);		// 拷貝構造函數      

Widget& operator=(const Widget&);	// 拷貝指派操作符

 	... 

};

      

如果你自己沒有聲明這些函數，你的編譯器會在需要的時候為你生成它們。拷貝内建類型（比如int、指針等）也始終是通過簡單地拷貝他們的二進制 bit值來完成的。（有關拷貝構造函數和指派操作符的詳細情況，請參考任何C++的介紹性書籍。我想你推薦c++ programming和inside c++ project model.這兩本書講的很透徹）。

如果你用一個拷貝操作很昂貴的對象填充一個容器，那麼一個簡單的操作——把對象放進容器也會被證明為是一個性能瓶頸。容器中移動越多的東西，你就會在拷貝上浪費越多的記憶體和CPU時鐘周期。此外，如果你定義了的有問題拷貝構造函數，這也會直接影響到容器。

當然由于繼承的存在，拷貝會導緻切割片（slicing）。那就是說，如果你以基類對象建立一個容器，而你試圖插入派生類對象，那麼當對象（通過基類的拷貝構造函數）拷入容器的時候對象的派生部分會被删除。

vector<Widget> vw; 

class SpecialWidget:	// SpecialWidget從上面的Widget派生

public Widget {...};

SpecialWidget sw; 

vw.push_back(sw);		// sw被當作基類對象拷入vw， 當拷貝時它的子類部分丢失了      

切片問題暗示了把一個派生類對象插入基類對象的容器幾乎總是錯的。如果你希望結果對象表現為派生類對象，比如，調用派生類的虛函數等，總是錯的。（關于slicing問題更多的背景知識，請參考《Effective C++》條款22。）

一個使拷貝更高效、正确而且避免分割問題的簡單的方式是建立指針的容器而不是對象的容器。也就是說，不是建立一個Widget的容器，建立一個 Widget*的容器。拷貝指針很快，而且不會有額外的開銷（僅僅是簡單的的二進制值的拷貝），而且當指針拷貝時不會産生slicing的問題。美中不足 的是，指針的容器有帶來了另外一個令人頭疼的問題，你需要自己手動來删除這些指針。如果你不想手動來删除指針，在權衡效率、正确性和slicing這些因 素時，智能指針會是一個不錯的解決方案。

如果所有這些使STL的拷貝機制聽起來很瘋狂，就請重新想想。是，STL進行了大量拷貝，但它一般設計時，會盡量避免不必要的對象拷貝，實際上，它的實作也盡量避免不必要的對象拷貝。和C和C++内建容器的行為做個對比，下面的數組：

即使我們一般隻使用其中的一些或者我們立刻使用從某個地方擷取（比如，一個檔案）的值覆寫每個預設構造的值，這也得構造maxNumWidgets個Widget對象。使用STL來代替數組，你可以使用一個可以在需要的時候增長的vector：

我們也可以建立一個可以足夠包含maxNumWidgets個Widget的空vector，但沒有構造Widget：

vector<Widget> vw;

vw.reserve(maxNumWidgets);

和數組對比，STL容器更靈活。它們隻建立（通過拷貝）你需要的個數的對象，而且它們隻在你指定的時候做。是的，我們需要知道STL容器使用了拷貝，但是别忘了一個事實：相比數組來說它們仍然是一個進步。