Re: [問題] deque

看板C_and_CPP (C/C++)作者loveme00835 (高髮箍)時間14年前 (2011/09/24 19:45)推噓3(3推 0噓 5→)

留言8則, 6人參與討論串2/2 (看更多)

※ 引述《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