C++ 頭文件系列(deque)

C++ 頭文件系列(deque)。本站提示廣大學習愛好者：（C++ 頭文件系列(deque)）文章只能為提供參考，不一定能成為您想要的結果。以下是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等。