標題 [筆記] 在STL中vector與deque提供了相似的功能, 請簡單說明兩者的差異及使用
時間 2012/05/13 Sun 21:38:19
───────────────────────────────────────
Q. 在STL中vector與deque提供了相似的功能, 請簡單說明兩者的差異及使用的時機
在STL中提供了vector, list,deque幾種可當作清單使用的資料結構，
他們都是動態增長的
在這三者之中選擇的準則主要是關注插入特性以及對元素的後續訪問要求。
差異
從後面刪除vector跟deque差不多一樣快
vector
表示一段連續的記憶體區域每個元素被順序存儲在這段記憶體中
對vector 的隨機訪問效率很高(vector::at())。
(JiangMiao:不是因為它快，而是因為他不慢且安全).
刪除非末尾元素效率比較低。
在任意位置而不是在vector 末尾(插入/刪除)元素則效率很低，
因為它需要把待(插入/刪除)元素右邊的每個元素都拷貝一遍
(從前面刪除， "後面的都要copy到前面" )。
一旦太多東西時,vector容器得另覓連續記憶體區塊,而將整個資料搬移
vector 的動態自我增長越頻繁元素插入的開銷就越大。
實際上對於小的物件，vector 在實踐中比list效率更高
deque
從前後刪除都很快，也表示一段連續的記憶體區域，
但是與vector 不同的是它支持高效地在其首部插入和刪除元素
它通過兩級陣列結構來實現一級表示實際的容器第二級指向容器的首和尾
如果有大量釋放操作，deque將花費更多的時間(和 vector相比)
list
表示非連續的記憶體區域，並通過一對指向首尾元素的指標雙向連結起來，
從而允許向前和向後兩個方向進行遍歷
在list 的任意位置插入和刪除元素的效率都很高，指標必須被重新賦值，
但是不需要用拷貝元素來實現移動
對隨機訪問的支援並不好，訪問一個元素需要遍歷中間的元素，
每個元素還有兩個指標的額外空間開銷
使用時機
對這幾種容器類型選擇的一些準則
如果我們需要隨機訪問一個容器則：vector 要比list 好得多
如果我們已知要存儲元素的個數則：vector 又是一個比list 好的選擇
如果我們需要的不只是在容器兩端插入和刪除元素則：list 顯然要比vector 好
除非我們需要在容器首部插入和刪除元素：否則vector 要比deque 好
vector
優先默認選擇的容器
已經知道vector要很大的szie 你可以一開始就擴充至你要的size，
這樣就可以減少配置和copy了
停止擴充後 對iterator的存取率很高的時候
因為deque的記憶體是分開的 所以他的 iterator的運算會多幾個檢查會比較慢
所以此時用vector會比較好
當有大量數據要push_back，記得要vector::reserve().
deque
當有大量的首或尾刪除操作.
或記憶體須不斷配置
或copy成本很高
如果你打算用insert或者有pop_front()的需要，使用deque.
使用記憶體圖解
vector
□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□
deque
□□□□□□
□□□□□□
□□□□□□
□□□□□□
□□□□□□
list
[ ]□[ ]
[ ]□[ ]
[ ]□[ ]
[ ]□[ ]
[ ]□[ ]
[ ]□[ ]
書上雖說除非有其他不利於 vector 的因素，不然主要還是以使用 vector 為主，
但主管說在他實際使用的經驗上，除非對於「連續記憶體」這點很要求，
不然還是會比較常用 deque，
不過我還是認為看程式需求吧，畢竟這兩個各佔擅場。
--
▅◣ Origin: 謠 言 報 bbs.csie.fju.edu.tw
▋◤ Author: ie945167 從 219-85-42-130-adsl-TPE.dynamic.so-net.net.tw 發表
沒有留言:
張貼留言