Posted on 2010-08-12 13:54
幻海藍夢 閱讀(302)
評論(0) 編輯 收藏 所屬分類:
C++
C++中的容器類包括“順序存儲結構”和“關聯存儲結構”，前者包括vector，list，deque等；后者包括set，map，multiset，multimap等。
若需要存儲的元素數在編譯器間就可以確定，可以使用數組來存儲，否則，就需要用到容器類了。
1、vector
連續存儲結構，每個元素是在內存上是連續的；
支持高效的隨機訪問和在尾端插入/刪除操作，但其他位置的插入/刪除操作效率低下；
2、deque
連續存儲結構，即其每個元素在內存上也是連續的，類似于vector，不同之處在于，deque提供了兩級數組結構，第一級完全類似于vector，代表實際容器；另一級維護容器的首位地址。
這樣，deque除了具有vector的所有功能外，還支持高效的首端插入/刪除操作。
3、list
非連續存儲結構，具有雙鏈表結構，每個元素維護一對前向和后向指針，因此支持前向/后向遍歷。
支持高效的隨機插入/刪除操作，但隨機訪問效率低下，且由于需要額外維護指針，開銷也比較大。
4、vector V.S. list V.S. deque：
a、若需要隨機訪問操作，則選擇vector；
b、若已經知道需要存儲元素的數目， 則選擇vector；
c、若需要隨機插入/刪除（不僅僅在兩端），則選擇list
d、只有需要在首端進行插入/刪除操作的時候，才選擇deque，否則都選擇vector。
e、若既需要隨機插入/刪除，又需要隨機訪問，則需要在vector與list間做個折中。
f、當要存儲的是大型負責類對象時，list要優于vector；當然這時候也可以用vector來存儲指向對象的指針，同樣會取得較高的效率，但是指針的維護非常容易出錯，因此不推薦使用。
5、capacity V.S size
a、capacity是容器需要增長之前，能夠盛的元素總數；只有連續存儲的容器才有capacity的概念（例如vector，deque，string），list不需要capacity。
b、size是容器當前存儲的元素的數目。
c、vector默認的容量初始值，以及增長規則是依賴于編譯器的。
6、用vector存儲自定義類對象時，自定義類對象須滿足：
a、有可供調用的無參構造函數（默認的或自定義的）；
b、有可用的拷貝賦值函數（默認的或自定義的）
7、迭代器iterator
a、vector與deque的迭代器支持算術運算，list的迭代器只能進行++/--操作，不支持普通的算術運算。