字節流動 - std c++ deque 的實現原理－鑽石舞台

Deque 簡介

deque是「double—ended queue」的縮寫，和vector一樣都是STL的容器，deque 是雙端數組，而 vector 是單端的。

deque 在接口上和 vector 非常相似，在許多操作的地方可以直接替換。deque 可以隨機存取元素（支持索引值直接存取，用[]操作符或at()方法，這個等下會詳講）。

deque 頭部和尾部添加或移除元素都非常快速。但是在中部安插元素或移除元素比較費時。

使用時需要包含頭文件 #include<deque> 。

Deque 實現原理

deque 的中控器

deque是連續空間（至少邏輯上看來如此），連續線性空間總令我們聯想到array或vector。

array無法成長，vector雖可成長，卻只能向尾端成長，而且其所謂的成長原是個假象，事實上是（1）另覓更大空間；（2）將原數據複製過去；（3）釋放原空間三部曲。如果不是vector每次配置新空間時都有留下一些餘裕，其成長假象所帶來的代價將是相當高昂。

deque系由一段一段的定量連續空間構成。一旦有必要在deque的前端或尾端增加新空間，便配置一段定量連續空間，串接在整個deque的頭端或尾端。

deque的最大任務，便是在這些分段的定量連續空間上，維護其整體連續的假象，並提供隨機存取的接口。避開了「重新配置、複製、釋放」的輪迴，代價則是複雜的迭代器架構。

受到分段連續線性空間的字面影響，我們可能以為deque的實現複雜度和vector相比雖不中亦不遠矣，其實不然。

主要因為，既是分段連續線性空間，就必須有中央控制，而為了維持整體連續的假象，數據結構的設計及迭代器前進後退等操作都頗為繁瑣。deque的實現代碼分量遠比vector或list都多得多。

deque採用一塊所謂的map（注意，不是STL的map容器）作為主控。

這裡所謂map是一小塊連續空間，其中每個元素（此處稱為一個節點，node）都是指針，指向另一段（較大的）連續線性空間，稱為緩衝區。

緩衝區才是 deque 的儲存空間主體。SGI STL 允許我們指定緩衝區大小，默認值0表示將使用512 bytes 緩衝區。

deque 的整體架構如下圖所示：

deque 的迭代器

讓我們思考一下，deque的迭代器應該具備什麼結構，首先，它必須能夠指出分段連續空間（亦即緩衝區）在哪裡，其次它必須能夠判斷自己是否已經處於其所在緩衝區的邊緣。

如果是，一旦前進或後退就必須跳躍至下一個或上一個緩衝區。為了能夠正確跳躍，deque必須隨時掌握管控中心（map）。

所以在迭代器中需要定義：當前元素的指針，當前元素所在緩衝區的起始指針，當前元素所在緩衝區的尾指針，指向map中指向所在緩區地址的指針，分別為cur, first, last, node。

指針結構如下圖所示：

————————————————

原文鏈接：https://blog.csdn.net/baidu_28312631/article/details/48000123

-- END --

進技術交流群，掃碼添加我的微信：Byte-Flow

獲取視頻教程和源碼

鑽石舞台