Re: [問題] deque

[loveme00835 (高髮箍)]

※ 引述《singlovesong (~"~)》之銘言：
: 開發平台(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
: 謝謝
標準規定了各操作的特性, 對實作方法還是給予很大的自由度, 但是
因為某些條件太嚴苛了, 所以內部可能還是大同小異, 以下提出一個
可能的實作: 動態二維陣列

假如我現在定義了一個 deque<int> q(1, 0), 內部結構可能長這樣:

  ┌─┐
  │  │
  ├─┤  ┌─┬─┬─┐
  │  ├→│０│  │  │
  ├─┤  └─┴─┴─┘
  │  │
  ├─┤
  │  │
  └─┘

設每一列都固定配置可容納3個value_type的空間, 那再執行以下操作:

   q.push_back( 1 ), q.push_back( 2 );

二維陣列便成為下面的樣子:

  ┌─┐
  │  │
  ├─┤  ┌─┬─┬─┐
  │  ├→│０│１│２│
  ├─┤  └─┴─┴─┘
  │  │
  ├─┤
  │  │
  └─┘

實際上它配置來的記憶體已經不夠用了, 下一次push_back時增加新的
列:

  ┌─┐
  │  │
  ├─┤  ┌─┬─┬─┐
  │  ├→│０│１│２│
  ├─┤  └─┴─┴─┘
  │  ├┐  ┌─┬─┬─┐
  ├─┤└→│３│  │  │
  │  │    └─┴─┴─┘
  └─┘

從前面增加元素當然也可以:

            ┌─┬─┬─┐
  ┌─┐┌→│  │  │-1│
  │  ├┘  └─┴─┴─┘
  ├─┤  ┌─┬─┬─┐
  │  ├→│０│１│２│
  ├─┤  └─┴─┴─┘
  │  ├┐  ┌─┬─┬─┐
  ├─┤└→│３│  │  │
  │  │    └─┴─┴─┘
  └─┘

只要記錄第[0]個元素的位置, 從欄的個數自然可以逆推算出其他元
素的所在.

你可以看得到: (1)計算位置跟(2)配置記憶體應會比 vector花費較
多時間.

最後補充一點: queue is not equal to linked list.

--
   ★    ★                                                          ★    ★
 ★   ★   ★  ███  ███  █  █▌█  ██◣  ███  ▋▋█  ★   ★   ★
               █▂█  █▃█  █  ███  █▆█  █▄█  ███
   ★    ★    █  ◣  █  █  █  ▋██  █▆◤  ███  ███    ★    ★
 Kim Jae Kyung  Koh Woo Ri  Cho Hyun Young Kim Ji Sook
φwindyhorse                                  No Eul  Oh Seung A  Jung Yoon Hye

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.121.197.115
推 tomap41017:推最後一點!!
推 LPH66:linked list 通常會出現在 list<> 裡面就是了
→ firejox:dequeue不是像圈圈嗎@@
→ adxis:樓上說的是 circular queue 喔
→ james732:deque 應該是兩端都可以做 push 跟 pop 的東西
→ james732:其實有的時候我會不確定要用 dequq 或 list
→ firejox:喔喔 謝謝a大更正小弟我錯誤的想法<(_ _)>
推 xatier:推最後一點!