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