deque實施選項

我需要建立自己的deque，因爲我編程的環境中沒有這種東西。我發現自己在如何實現它的兩種選擇之間自我撕裂：deque實施選項

我可以管理一個可擴展的數組指針指針，用於存放數據。問題是，我如何確定每個陣列次級的大小？
我可以有一個大的緩衝區，我定期增長，基本上在它上面建立一個循環隊列。這在大規模分配變得難以有效實現之後在一定規模之後看起來很糟糕。

任何想法？

來源

2011-05-05 McCormick

只是實現一個雙向鏈表... – YXD 2011-05-05 15:22:58

在C++中，當一個引用一個雙端隊列時，除了更一般的需求之外，還需要隨機訪問是合理的，這要歸功於原始設計者選擇的命名方案。 – 2011-05-05 15:32:12

啊，你是對的。 – YXD 2011-05-05 15:33:37

對於第一個選項，您可以簡單地將每個數組的大小加上前一個數組的大小，因爲您分配它們，可能達到由您瞭解應用程序或內存約束條件的某些上限。

第二個你似乎已經想通了。

爲什麼不只是一個簡單的雙向鏈表？你需要快速的隨機訪問？

來源

2011-05-05 15:24:48 Collin

+1的指數增長。 IIRC大多數標準容器也是這樣做的。 – 2011-05-05 15:25:46

雙向鏈表會浪費指針上的大量內存。對於我的結構，使用循環緩衝區可以讓我存儲兩倍的元素。 – McCormick 2011-05-05 15:31:36

然後你的第一個選擇可能是理想的。在嘗試展開列表時，不會產生任何副本開銷（在內存和時間上），並且如果需要，還可以輕鬆縮小列表。 – Collin 2011-05-05 15:39:33

我會做你的兩個選項的組合 - 多個較小的緩衝區，並使每個「結束」指向另一個，本質上成爲一個更大的圓形陣列。這樣你就不需要像往常一樣分配緩衝區。至於第二緩衝區的大小，我認爲科林的建議是一個很好的建議 - 隨着您的增長而增加規模。

來源

2011-05-05 15:26:36

另一種方法可能是向量列表（固定大小）。列表作爲第一個DS的好處是您可以在頭部和尾部以及之間添加元素。具有固定大小的向量的好處是你可以模擬二維陣列，添加/刪除行是恆定的時間。現在假設你想添加頭像。您應該在頭部（常量時間）在列表中添加一個節點，然後將該條目添加到固定大小矢量的最後一個。因此，當出列已經有數據時，想想任何入口，您將插入第一行的最後一列。如果行中存在可用空間，則頭部的任何進一步插入都會發生在第一行的第二個未填充列上。其他明智的重複同樣的步驟。末尾的正常插入通常會發生在列表向量的結尾，插入行爲是從向量開始的。

來源

2012-05-08 07:12:53 siddhusingh

回答

相關問題