› 看板 C_and_CPP 關於我們 聯絡資訊
作者singlovesong (~"~)
看板C_and_CPP
標題[問題] deque
時間Sat Sep 24 18:00:34 2011
開發平台(Platform): (Ex: VC++, GCC, Linux, ...) g++ 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) deque 請問一下 C++ STL 裡面 deque 是用doubly-linked list 實作的 既然不是array 不是連續的記憶體空間 為什麼可以支援 O(1) 的random access 呢？ 看起來好像有vector的優點 卻沒有vector的缺點 那我還用vector 幹嘛0.0 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 58.115.165.34
推 joefaq:http://www.pcdog.com/edu/cpp/04/12/t286897.html 簡體 09/24 18:10
推 aecho:好棒的實驗數據啊~~ 09/24 22:32
推 yoco315:deque 的 random access 不是 O(1)，而是很接近 O(1) 09/25 11:04
→ yoco315:相對於 linked list 的 randome access. deque 其實是 09/25 11:05
→ yoco315:用比較大的 constant 換一個比較小的成長速度.. 09/25 11:05
→ singlovesong:linked list 好像不能random access 0.0 09/25 11:21