deque概述
vector是單向開口的連續線性空間，deque則是一種雙向開口的連續線性空間。所謂雙向開口，意思是可以在頭尾兩端分别做元素的插入和删除操作。vector當然也可以在頭尾兩端分别做元素的插入删除操作（從技術上說），但是其頭部操作效率極差而無法被接受。
deque和vector的最大差異，一是在于deque允許于常數時間内對起頭端進元素的插入或移除操作，二在于deque沒有所謂容量（capacity）觀念，因為它是動态地以分段連續空間組合而成，随時可以增加一段新的空間并連接配接起來。換言之，如vector那樣“因舊空間不足而重新配置一塊更大空間，然後複制元素，再釋放舊空間”這樣的事情在deque是不會發生的。也是以，deque沒有必要提供所謂的空間保留（reserve）功能。
雖然deque也提供Ramdon Access Iterator,但它的疊代器并不是普通指針，其複雜度和vector不可以道理計，是以也影響了各個運算層面。是以，除非必要，我們盡可能選擇使用vector而非deque。對deque進行的排序操作，為了最高效率，可将deque先完整複制到一個vector身上，将vector排序後，在複制回deque。
deque的中控器
deque是連續的空間（至少邏輯上看），連續的線性空間總令我們聯想到array或vector。array無法成長，vector雖可成長，卻隻能向尾部成長，而且所謂成長原是個假象，事實上a.另尋更大的空間，b.将原資料複制過去，c.釋放原空間三部曲。如果不是vector每次配置空間時都有留下一些餘裕，其成長假象帶來的代價是非常高昂的。
deque是由一段一段的定量連續空間構成。一旦有必要在deque的前端或尾端增加新空間，便配置一端定量連續空間，串接在整個deque的頭端或尾端，deque的最大任務，便是在這些分段的定量連續空間上，維護其整體連續的假象。并提供随機存取的接口。避開了“重新配置、複制、釋放”的輪回，代價是複雜的疊代器架構。
受到分段連續線性空間的字面影響，我們可能以為deque的實作複雜度和vector相比雖不中也不遠，其實不然。因為分段連續線性空間必須要有中央控制，而為了維持整體連續的假象，資料結構的設計及疊代器前進後退等操作都較為複雜和繁瑣。deque的實作代碼分量遠比vector或list都多得多。
deque采用一塊所謂的map（這裡并不是map容器）作為主要，是一小塊連續空間，其中每個元素（此處稱為一個節點，node）都是指針，指向另一段較大的連續線性空間，稱為緩沖區。緩沖區才是deque的儲存空間主體。SGI STL允許指定緩沖區的大小，預設值為0，表示将使用512 bytes 緩沖區。
deque部分源代碼
template<class T,class Alloc=alloc, size_t BufSiz=0>
class dedue
{
public:
typedef T value_type;
typedef value_type* pointer;
.......
protected:
//元素的指針的指針
typedef pointer* map_pointer;//二級指針
map_pointer map;//指向map,map是塊連續空間，每一個元素都是一個指針（節點），指向一塊緩沖區
size_type map_size;//map内可容納的指針
........
}
map和node-buffer（節點和緩沖區）的關系
deque的疊代器
deque是分段連續空間，維持其：“整體連續”假象的任務，落在疊代器傳遞operator++和operator–兩個運算子身上。
deque疊代器必須能夠指出分段連續空間（緩沖區）在哪裡，其次它必須判斷自己是否已經處于其所在緩沖區的邊緣，如果是，一旦前進或者後退時就必須跳躍至下一個或上一個緩沖區，為了能夠正确跳躍，deque必須随時掌握管控中心（map）。
template<class T, class Ref, class Ptr, size_t BufSiz>
struct _deque_iterator
{
typedef _deque_itertaor<T ,T&,T*,BufSiz> iterator;
typedef _deque_itertaor<T ,const T&,const T*,BufSiz> const_iterator;
static size_t buffer_size() {return _deque_buf_size(BufSiz,sizeof(T));}
//未繼承 std::iterator, 是以必須自行撰寫五個必要的疊代器相應型别
typedef random_access_iterator_tag iterator_category;//(1)
typedef T value_typel;//(2)
typedef Ptr pointer;//(3)
typedef Ref reference;//(4)
typedef size_t size_type;
typedef ptrdiff_t difference_type;//(5)
typedef T** map_pointer;
typedef _deque_iterator self;
//保持與容器的聯接
T* cur;//此疊代器所指之緩沖區的現行元素
T* first;//此疊代器所指之緩沖區的頭
T* last;//此疊代器所指之緩沖區的尾（包含備用空間）
map_pointer node;//指向管控中心
......
}
其中用來決定緩沖區的大小的函數buff_size()，調用_deque_buf_size(),後者是一個全局函數，定義如下：
//如果n不為0，傳回n，表示buffer size有使用者自定義
//如果n為0，表示buffer size使用預設值，那麼如果sz(元素大小，sizeof(value_type))小于512，傳回512/sz；如果sz不小于512，傳回1
inline size_t _deque_buf_size(size_t n,size_t sz)
{
return n!=0?n:(sz<512? size_t(512/sz):size_t(1));
}
deque的中控器、緩沖區、疊代器的互相關系
deque的構造圖
deque的元素操作