寫在前面：本文是閱讀《C++標準庫(第二版)》的讀書筆記。

文章目錄

• • 7.4 Deque
  • • 7.4.1 Deque的能力
    • 7.4.2 Deque的操作函數
    • 7.4.3 Exception Handling
    • 7.4.4 Deque運用實例

7.4 Deque

容器deque（發音為“deck”）和vector非常相似。它也采用dynamic array來管理元素，提供隨機訪問，并有著和vector幾乎一模一樣的接口。不同的是deque的dynamic array頭和尾都開放，因此能在頭尾兩端進行快速安插和刪除。

為了提供這種能力，deque通常實現為一組獨立區塊(a bunch of individual blocks) ,第一區塊朝向某方向擴展，最后的區塊朝另一方向擴展。

使用deque之間，必須先包含頭文件< deque> :#include< deque>
其中，deque類型定義于命名空間std內的一個 class template：

namespace std{tamplate< typename T,typename Allocator = allocator<T>>class deque; }

和vector相同，這里的第一個template參數用來指明元素類型，第二個template實參可有可無，用來指定內存模型（memory model），默認為allocator.

7.4.1 Deque的能力

Deque和vector相比，功能上的差異如下：

兩端都能快速安插元素和移除元素（vector只能在尾部可以）。這些操作可以在攤提的常量時間內完成。

訪問元素時deque內部結構會多一個間接過程，所以元素的訪問和迭代器的動作會稍微慢一些。

迭代器需要在不同的區塊間跳轉，所以必須是個smart pointer,不能是個普通的pointer。

在內存區塊大小有限制的系統中，deque可以內含更多元素，因為它使用不止一塊內存。因此deque的max_size()可能更大。

Deque不支持對容量和內存重新分配時機的控制。特別要注意的是，除了頭尾兩端，在任何地點安插和刪除元素都將導致指向deque元素的任何pointer、reference和iterator失效。不過，deque 的內存重分配由于vector，因為其內部結構顯示，deque不必在內存重新分配時復制所有元素。

Deque會釋放不再使用的內存區塊。deque的內存大小使可所建的，但要不要這么做，以及如何做，由實現決定。

Deque的的以下特性和vector差不多：

在中段安插、移除元素的速度相對較慢，因為所有元素都需要移動以騰出或者填補空間。

迭代器屬于random-access iterator（隨機訪問迭代器）。

總之，以下情形最好使用deque：

• 你需要在兩端安插和刪除元素（這是deque的拿手好戲）。
• 無需指向容器內的元素。
• 要求”不再使用的元素必須釋放“（不過，C++ standard 對此無任何保證）。

7.4.2 Deque的操作函數

下面列出了deque的操作函數。

deque的各項操作只有以下兩點和vector不同：

deque不提供容量操作 (capacity()和reserve()).

deque直接提供函數完成頭部元素的安插和刪除（push_front()和pop_front()）。

其他操作都相同。

請注意，C++11 添加了 shrink_to_fit() ，那是個不具有強制力(nonbinding)的函數，負責縮小內部內存以匹配元素個數。你可能會認為shrink_to_fit()對deque沒意義，因為deque本來就會釋放不再使用的區塊內存。然而，deque內部用來存放”指向獨立區塊“的所有pointer的空間，通常不會被縮小，如果用了這個函數就有可能真的被縮小。

還有一些值得考慮的事情：

除了at(),沒有任何成員函數會檢查”索引或迭代器是否有效“。

除了頭尾兩端，在任何地點安插和刪除元素都將導致指向deque元素的任何pointer、reference和iterator失效。

7.4.3 Exception Handling

原則上deque提供的異常處理和vector提供的一樣。新增的操作函數push_front()和pop_front()分別對應于push_back()和pop_back()。因此C++標準庫保證下列行為：
如果以push_back() 、 push_front()安插元素時發生異常，則該操作不帶來任何效應。
pop_back()和 pop_front() 不會拋出任何異常。

7.4.4 Deque運用實例

#include<iostream> #include<deque> #include<iterator> #include<algorithm> #include<string> using namespace std;int main(){//create empty deque of stringsdeque<string> coll;//insert several elementscoll.assign(3,string("string"));//復制3個 ”string“ ，賦值給coll coll.push_back("last string") ; //尾部添加一個字符串 coll.push_front("first string"); //頭部添加一個字符串 //print elements separated by newlinescopy( coll.cbegin(),coll.cend(),ostream_iterator<string>(cout,"\n"));cout<<endl;//remove first and last elementcoll.pop_back();coll.pop_front();//insert "another" into every element but the firstfor(int i=1; i<coll.size();i++)coll[i]="another"+coll[i];// change size to four elementscoll.resize(4,"resized string"); //將元素數量改為4，如果size()變大，多出來的新元素都是”resized string“的拷貝 //print elements separated by newlinescopy( coll.cbegin(),coll.cend(),ostream_iterator<string>(cout,"\n"));cout<<endl;}

輸出結果

總結

以上是生活随笔為你收集整理的STL容器之Deque-《C++标准库(第二版)》读书笔记的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。