C++ 頭文件系列(deque)

簡介

deque是double ended queue（即雙端隊列）的簡稱。 就像C++中的大部分容器的一樣，deque具有以下屬性：

• 順序的（sequence）
• 動態增長的（dynamic growing）
• 自定義內存分配的（allocator-aware）

動態內存分配

容器的順序性（或序列性）和內存分配器我們留到以後再說，這裡我們先來探討下容器的動態增長需求所帶來的動態內存分配性質。

動態內存分配在這裡的意思是容器的大小會隨著需要而增長，這經常伴隨著一些內存需求性的操作而發生（例如insert操作，插入一個元素勢必需要為這個元素預留內存空間，不然它會成為一個無處息身的流浪狗-^-）。 每個容器都有其實際上的容量（capacity），當容量耗盡，沒有多余的空間時，就需要為這個容器動態地增長(正方形單元表示內存單元，深色表示已使用，白色表示未使用)：

之所以稱之為動態，是因為這個操作發生在運行時。

擴大因子

這裡就涉及到resize factor， 也就是重新分配內存時應該分配的內存大小問題。 分配因子太小很可能會造成後續頻繁的內存分配需求，因為當前剩下的內存太少；太大又可能造成內存浪費（尤其是當原內存本身就很大時）。

sgi stl的擴大因子好像是2（即新的內存大小是原內存的2倍），但有研究指出值為1.5的factor在實際中似乎擁有更好的效果。

實現

在實現上，容器內存的動態增長本質上由以下幾步完成：

1. 分配一塊更大的內存空間
2. 釋放之前的內存（在完成內容復制之後）
3. 替換為新的內存空間

解決的問題

用過C語言的人都知道，C代碼中充斥著各種各樣的靜態內存分配，大部分都以數組的形式出現：

char buffer[1024] = {0};

然而，使用靜態內存會帶來很多問題：

• 第一，硬編碼，降低了代碼的可讀性， 看的人根本不知道1024意味著什麼。 還好，1024還算是比較典型的數字。但如果換成23、33這些數字，天啊，我完全不知道這些數字是不是有著特殊的含義（你還真別說，有些奇怪的數字還真是特殊考慮過的）！嗯，我們戲稱這些數字為魔數（magic number）。
• 第二，內存利用率。 你分配了很大一塊內存，但實際上只使用了很小的一部分。什麼？為什麼不分配的小一點？哈哈，因為我也不知道到底要分配多大。
• 第三，靜態內存不可增長。 當你知道之前定義的內存大小根本不夠用的時候怎麼辦呢？哦，我可以再定義一個足夠大的內存或者把之前的數組大小改得大一些。 那要是這種情況發生在代碼運行時呢？
• 第四，降低工作效率。 處理以上這些瑣碎而簡單的問題真是讓我操碎了神，更煩人的是到處都是這些問題。

如果有那麼一種機制，讓我在調用各種插入、串接操作時都不用考慮這些問題就好了。 不用想了，那就是動態內存分配！！ 動態內存分配的重要性對於C++來說，就像是Garbage Collector對於Java那樣重要！

雙端隊列

好了，言歸正傳。 實際上，deque想要實現的是一種概念----雙端隊列。 它是一種LIFO (last in first out)隊列，具有以下特性：

• 雙端，即頭端和尾端
• 每個端口都支持入隊和出隊操作

雙端

雙端分別是頭端和尾端，在deque類中對應front和back字樣。 帶有這兩個字樣的操作，也即成員函數，都是與端口相關的。

至於為什麼采用這兩個名稱，而不采用諸如headPort、tailPort這樣的，我猜想是為了保持各個容器接口之間的一致性與簡潔性， 便於記憶。 因為有很多容器都具有 第一個 元素和 最後一個 元素這兩個通用概念，front和back剛好對應了它們。 同時，front和back也在一定程度上反映了容器的方向與位置信息，適合用來投射概念上的東西（例如雙向鏈表和雙端隊列）。

入隊和出隊

入隊、出隊操作分別為帶有push、pop操作，道理與雙端概念大致相似，這裡不再贅述。

但這兩個操作非常重要的一點就是----不管是在頭端還是尾端，時間復雜度都是O(1)，即常數時間。

雙端隊列接口

• push_back
• push_front
• pop_back
• pop_front

其他接口

理論與實踐總是會有不小的距離，容器在實際使用中的易用性有時候更重要。 所以deque類提供的接口遠遠不止理論上的那幾個， 還包括普遍出現在其它容器中的一些接口。 例如Iterator系列、插入、swap、clear等。