STL容器deque使用
deque簡介
deque與vector非常相似。它也采用動态數組來管理元素，提供随機存取，并有着和vector幾乎一模一樣的接口。不同的是deque的動态數組頭尾都開放，是以能在頭尾兩端進行快速安插和删除。
與vector相比，deque功能上的不同在于：
兩端都能快速安插元素和移除元素（vector隻在尾端插入）。這些操作可以在分期攤還的常數時間内完成。
存取元素時，deque的内部結構會多一個間接過程，是以元素的存取和疊代器的動作會稍稍慢一些。
疊代器需要在不同區塊間跳轉，是以必須是特殊的智能型指針，非一般指針。
在對記憶體區塊有所限制的系統中，deque可以内含更多的元素，因為它使用不止一塊記憶體。故deque的max_size()可能更大。
deque不支援對容量和記憶體重配置設定時機的控制。特别注意的是，除了頭尾兩端，在任何地方安插或删除元素，都将導緻指向deque元素的任何pointers、references、iterators失效。不過，deque的記憶體重配置設定優于vectors，因為其内部結構顯示，deuqe不必在記憶體重配置設定時複制所有元素。
deque的記憶體區塊不再被使用時，會被釋放。deque的記憶體大小是可能縮減的。
deque與vector相似特性如下：
在中段部分安插、移除元素的速度相對較慢，因為所有元素都需移動以騰出或填補空間。
疊代器屬于随機存取疊代器。
在以下情形，最好采用deque：
需要在兩端安插和移除元素。
無需引用（refer to）容器内的元素。
要求容器釋放不再使用的元素。
deque基本操作
- 構造、析構操作
deque c：産生一個空的deque
deque c1(c2)：針對某個deque産生同型副本（所有元素都被拷貝）
deque c(n)：産生一個deque，含有n個元素，這些元素均勻default構造函數産生出來
deque c(n, elem)：産生一個deque，含有n個元素，這些元素均是elem的副本
deque c(beg, end)：産生一個deque，以區間[beg; end]内的元素為初值
c.~deque()：銷毀所有元素，釋放記憶體
- 非變動性操作
c.size()：傳回容器的實際元素個數
c.empty()：判斷容器大小是否為零。等同于size()==0，但可能更快
c.max_size()：傳回可容納的最大元素數量
c1 == c2：判斷是否c1等于c2
c1 != c2：判斷是否c1不等于c2。等同于!(c1 == c2)
c1 < c2：判斷是否c1小于c2
c1 > c2：判斷是否c1大于c2。等同于c2 < c1
c1 <= c2：判斷是否c1小于等于c2。等同于!(c2 < c1)
c1 >= c2：判斷是否c1大于等于c2。等同于!(c1 < c2)
c.at(idx)：判斷索引idx所标示的元素。如果idx越界，抛出out_of_range
c[idx]：傳回索引idx所标示的元素。不進行範圍檢查
c.front()：傳回第一個元素。不檢查元素是否存在
c.back()：傳回最後一個元素。不檢查元素是否存在
c.begin()：傳回第一個元素。不檢查元素是否存在
c.end()：傳回一個随機疊代器，指向第一個元素
c.rbegin()：傳回一個逆向疊代器，指向逆向疊代時的第一個元素
c.rend()：傳回一個逆向疊代器，指向逆向疊代時的最後元素的下一位置
c1 == c2：将c2的所有元素指派給c1
c.assign(n, elem)：将n個elem副本指派給c
c.assign(beg, end)：将區間[beg; end]中的元素指派給c
c1.swap(c2)：将c1和c2的元素互換
swap(c1, c2)：将c1和c2的元素互換
c.insert(pos, elem)：在pos位置插入一個elem副本，并傳回新元素的位置
c.insert(pos, n, elem)：在pos位置插入elem的n個副本，并無傳回值
c.insert(pos, beg, end)：在pos位置插入在區間[beg; end]所有元素的副本，無傳回值
c.push_back(elem)：在尾部添加elem的一個副本
c.pop_back()：移除最後一個元素（但不回傳）
c.push_front(elem)：在頭部插入elem的一個副本
c.pop_front()：移除頭部元素（但不回傳）
c.erase(pos)：移除pos位置上的元素，傳回下一個元素位置
c.erase(beg, end)：移除[beg, end)區間内的所有元素，傳回下一個元素位置
c.resize(num)：将大小（元素個數）改為num。如果size()增長了，新增元素都以default構造函數産生出來
c.resize(num, elem)：将大小（元素個數）給位num。如果size()增長了，新增元素都是elem的副本
c.clear()：移除所有元素，将容器清空
deque的各項操作隻有以下數點和vectors不同：
deque不提供容量操作capacity()和reserve()
deque直接提供函數，用以完成頭部元素的安插和删除（push_front()和pop_front()。
需要考慮如下：
除了at()，沒有任何成員函數會檢查索引或疊代器是否有效
元素的插入或删除可能導緻記憶體重新配置設定，是以任何插入或删除動作都會使所有指向deque元素的pointers、references和iterators失效。唯一例外的是在頭部或尾部插入元素，動作之後，pointers和references仍然有效（但iterators沒這麼幸運）。
- 異常處理
如果已push_back()或push_front()安插元素時發生異常，則該操作不帶來任何效應
pop_back()和pop_front()不會抛出任何異常。
參考文獻：C++标準庫、STL源碼分析