我作了雙向擴(kuò)充實(shí)現(xiàn)。昨天的方案是：

先判斷插入的元素靠前還是靠后，靠哪邊就準(zhǔn)備往哪邊挪舊元素，然后檢查那頭有沒(méi)有空，沒(méi)空換另一頭，要是都沒(méi)空但兩頭加起來(lái)卻有空，那就重新調(diào)整位置，最后才重新分配空間。

我原以為考慮得好周到，可是實(shí)現(xiàn)起來(lái)卻傻了眼。往末尾插入10萬(wàn)數(shù)據(jù)，有9萬(wàn)多次發(fā)生移動(dòng)元素，不慢才怪。

調(diào)整了下，變成：

先判斷考前還是靠后，靠哪邊就往哪邊挪舊元素，如果那頭沒(méi)空，直接重新分配空間，空間按每次*3增長(zhǎng)直至足夠。

這樣，push_back 的性能與 std::vector 以及 std::deque 的粗略比較如下（圖中的單位寫(xiě)錯(cuò)了，全是秒）：

insert(begin(), i) 比較：

（vector 參與這項(xiàng)比較果然是不公平的，呵呵）

insert 到 begin + size() / 2 處：

resize 至固定大小，然后用 iterator 遍歷賦值：

（今天回家了。以上測(cè)試都在家里的機(jī)器上做的，配置： AMD SP2500+ 1.4GHz，512MB RAM。）

這樣的結(jié)果還算滿(mǎn)意的。不知道 vector 為什么能保持 push_back 如此高效~

還有個(gè)挺奇怪的現(xiàn)象，使用 deque 的時(shí)候，如果數(shù)據(jù)量到百萬(wàn)，臨退出前有好長(zhǎng)一段時(shí)間要等待，難道是 deque 在做某些析構(gòu)動(dòng)作？

再呢。。貌似 deque 的 push_front 并沒(méi)有 vector 的 push_back 神么、、

嗯……我的本意不是為了著重性能，而是嘗試些有著那么一套接口的東西出來(lái)，同時(shí)也給自己用。現(xiàn)在來(lái)比性能只是為了論證一下實(shí)用程度如何，如此而已。

具體實(shí)現(xiàn)代碼就不貼了，基本接口和上上篇里沒(méi)多少變化。等以后這方面的東西做完了再一起拿出來(lái)。