vector是單向開口的連續線性空間，用戶只能在vector尾部進行插入刪除操作，而 deque 是一種雙向開口的連續線性空間，允許我們在頭尾兩端操作。
deque 和 vector 的最大差異在於：
deque 允許常數時間對頭端元素進行插入和移除操作 deque 沒有所謂容量（capacity）概念，因為它是動態地以分段連續的空間組合而成，隨時可以增加一段新的空間並鏈接起來deque提供的迭代器也是 RandomAccess Iterator，但它的迭代器並不是普通指針，其復雜度遠遠大於 vector 的迭代器，從而影響了各個運算層面。因此，除非必要，我們應盡可能選擇使用 vector 而非 deque。對 deque 進行排序操作，為了最高效率，可將 deque 先完整的復制到一個 vector 身上，將 vector 排序後(利用 STL 的 sort 算法)，在復制回 deque。
deque 是連續空間（邏輯上來看如此），連續線性空間總令我們聯想到 array 或 vector。array 空間大小無法增長，vector 雖然可以增長，但只能在尾部擴張，而且這種增長是個假象：
配置更大的空間 復制數據 釋放原空間如果不是 vector 每次配置新空間時都有留下一些備用空間，其增長將帶來高昂的代價。
deque 是由一段一段的定量連續空間構成。一旦有必要在 deque 的前端或尾端增加新空間，便配置一段定量的連續空間，串接在 整個 deque 的頭端或尾端。deque 的最大的任務便是在這些分段連續的空間上維護其整體連續的假象，並提供隨機存取接口，避開了“重新配置、復制、釋放”的輪回，代價則是復雜的迭代器架構。
deque 采用一塊所謂的 map 作為主控，即中控器，這個所謂的 map 是一小塊連續空間，其中每個元素都是一個指向另一段較大的連續空間的指針（也稱節點），這段線性空間稱為緩沖區。緩沖區是 deque 的存儲空間主體。SGI STL 允許我們指定緩沖區大小，默認值 0 表示將使用 512 bytes 緩沖區。
template
class deque {
public: // Basic types
typedef T value_type;
typedef value_type* pointer;
...
protected: // Internal typedefs
typedef pointer* map_pointer;
protected: // Data members
...
map_pointer map; // 指向中控器 map，map 是塊連續空間，其中每一個指針，指向一塊緩沖區
size_type map_size; // map 可容納的指針數
...
};
根據上述定義，可以發現 map 其實是一個 T**，即一個指針，所指之物也是一個指針，該指針指向型別為 T 的一塊空間。
![這裡寫圖片描述](https://www.aspphp.online/bianchen/UploadFiles_4619/201701/2017010315030802.jpg "\")
deque 是分段連續空間。維持其“整體連續”假象的任務，落在了迭代器的 operator++ 和 operator– 兩個運算子身上。
deque 迭代器首先需要能夠指出分段連續空間的位置，其次它必須能夠判斷自己是否處於其所在緩沖區邊緣，如果是，一旦前進或後退時就必須跳躍至下一個或者上一個緩沖區。為了掌控緩沖區，deque 必須隨時掌握中控器。實現如下：
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));
}
template
struct __deque_iterator {
typedef __deque_iterator iterator;
typedef __deque_iterator const_iterator;
static size_t buffer_size() {return __deque_buf_size(BufSiz, sizeof(T)); }
// 迭代器 5 個相應型別
typedef random_access_iterator_tag iterator_category; // 1
typedef T value_type; // 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; // 指向中控器
...
};
![這裡寫圖片描述](https://www.aspphp.online/bianchen/UploadFiles_4619/201701/2017010315030856.jpg "\")
在 deque 數據結構中，含有兩個迭代器：start 和 finish。start 的 cur 指向緩沖區的第一個元素，finish 的 cur 指向緩沖區的最後元素（的下一位置）。
以下是迭代器的幾個關鍵行為。
由於迭代器內對各種指針運算都寫進行了重載操作，所以各種指針運算如加、減、前進、後退都不能直觀視之。其中最關鍵的是：一旦行進時遇到緩沖區邊緣，要視前進、後退而定，可能需要調用 set_node() 跳一個緩沖區：
void set_node(map_pointer new_node) {
node = new_node;
first = *new_node;
last = first + difference_type(buffer_size());
}
以下是重載各個運算符的實現：
reference operator*() const { return *cur; }
pointer operator->() const { return &(operator*()); }
difference_type operator-(const self& x) const {
return difference_type(buffer_size()) * (node - x.node - 1) +
(cur - first) + (x.last - x.cur);
}
self& operator++() {
++cur;
if (cur == last) {
set_node(node + 1);
cur = first;
}
return *this;
}
self operator++(int) {
self tmp = *this;
++*this;
return tmp;
}
self& operator--() {
if (cur == first) {
set_node(node - 1);
cur = last;
}
--cur;
return *this;
}
self operator--(int) {
self tmp = *this;
--*this;
return tmp;
}
// 實現隨機存取，迭代器可以直接跳躍 n 個距離
self& operator+=(difference_type n) {
difference_type offset = n + (cur - first);
// 目標位置在同一緩沖區
if (offset >= 0 && offset < difference_type(buffer_size()))
cur += n;
// 目標位置不在同一緩沖區
else {
difference_type node_offset =
offset > 0 ? offset / difference_type(buffer_size())
: -difference_type((-offset - 1) / buffer_size()) - 1;
// 切換至正確的節點（緩沖區）
set_node(node + node_offset);
// 切換至正確的元素
cur = first + (offset - node_offset * difference_type(buffer_size()));
}
return *this;
}
// 調用 operator+=
self operator+(difference_type n) const {
self tmp = *this;
return tmp += n;
}
// 調用 operator+=
self& operator-=(difference_type n) { return *this += -n; }
// 調用 operator-=
self operator-(difference_type n) const {
self tmp = *this;
return tmp -= n;
}
// 調用 operator*、operator+
reference operator[](difference_type n) const { return *(*this + n); }
bool operator==(const self& x) const { return cur == x.cur; }
bool operator!=(const self& x) const { return !(*this == x); }
bool operator<(const self& x) const {
return (node == x.node) ? (cur < x.cur) : (node < x.node);
}
前面提到 deque 除了維護一個指向 map 的指針外，還維護 start、finish 兩個迭代器，分別指向第一個緩沖區的第一個元素和最後緩沖區的最後一個元素（的下一位置）。此外，它必須記住當前 map 大小，因為一旦 map 所提供的節點不足，就必須重新配置一塊更大的 map。
template
class deque {
public: // Basic types
typedef T value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
public: // Iterators
typedef __deque_iterator iterator;
typedef __deque_iterator const_iterator;
protected: // Internal typedefs
// 元素的指針的指針
typedef pointer* map_pointer;
// 兩個配置器
typedef simple_alloc data_allocator;
typedef simple_alloc map_allocator;
static size_type buffer_size() {
return __deque_buf_size(BufSiz, sizeof(value_type));
}
static size_type initial_map_size() { return 8; }
protected: // Data members
iterator start; // 指向第一個緩沖區
iterator finish; // 指向最後一個緩沖區
map_pointer map; // 指向 map，每個元素都指向一個指針
size_type map_size; // map 內的指針個數
...
};
根據上述定義，可完成下面函數：
public: // Basic accessors
iterator begin() { return start; }
iterator end() { return finish; }
const_iterator begin() const { return start; }
const_iterator end() const { return finish; }
// 調用__deque_iterator<>::operator[]
reference operator[](size_type n) { return start[difference_type(n)]; }
const_reference operator[](size_type n) const {
return start[difference_type(n)];
}
// 調用__deque_iterator<>::operator*
reference front() { return *start; }
reference back() {
iterator tmp = finish;
--tmp; // 調用 __deque_iterator<>::operator--
return *tmp; // 調用__deque_iterator<>::operator*
}
const_reference front() const { return *start; }
const_reference back() const {
const_iterator tmp = finish;
--tmp;
return *tmp;
}
size_type size() const { return finish - start;; }
size_type max_size() const { return size_type(-1); }
bool empty() const { return finish == start; }
deque 定義了兩個專屬的空間配置器：
protected: // Internal typedefs
typedef simple_alloc data_allocator;
typedef simple_alloc map_allocator;
還提供了各種構造函數，其中一個定義如下：
deque(size_type n, const value_type& value)
: start(), finish(), map(0), map_size(0)
{
fill_initialize(n, value);
}
其內調用的 fill_initialize() 負責產生並安排好 deque 的結構，並將元素的初值設定妥當：
template
void deque::fill_initialize(size_type n,
const value_type& value) {
create_map_and_nodes(n); // 把 deque 的結構都產生並安排好
map_pointer cur;
__STL_TRY {
// 為每個節點（緩沖區）設置初值
for (cur = start.node; cur < finish.node; ++cur)
uninitialized_fill(*cur, *cur + buffer_size(), value);
// 最後一個節點的設定稍有不同（尾端可能有備用空間，不必設定初值）
uninitialized_fill(finish.first, finish.cur, value);
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) { // commit or rollback
for (map_pointer n = start.node; n < cur; ++n)
destroy(*n, *n + buffer_size());
destroy_map_and_nodes();
throw;
}
# endif /* __STL_USE_EXCEPTIONS */
}
其中，create_map_and_nodes 負責產生並安排好deque 的結構：
template
void deque::create_map_and_nodes(size_type num_elements) {
// 需要緩沖區數 = （元素個數/每個緩沖區可容納元素個數）+ 1
// 若剛好整除，會多分配一個緩沖區
size_type num_nodes = num_elements / buffer_size() + 1;
// 一個 map 需要管理的節點數，最少 8 個，最多 “所需節點數” + 2
// 前後各預留一個
map_size = max(initial_map_size(), num_nodes + 2);
map = map_allocator::allocate(map_size);
// 以下令 nstart 和 nfinish 指向 map 所擁有之全部節點的最中央區段
// 保持在最中央，可使頭尾兩端的擴充能量一樣大。每個節點可對應一個緩沖區
map_pointer nstart = map + (map_size - num_nodes) / 2;
map_pointer nfinish = nstart + num_nodes - 1;
map_pointer cur;
__STL_TRY {
// 為 map 內的每個現用節點配置緩沖區。
// 所有緩沖區加起來就是 deque 的可用空間（最後一個緩沖區可能留有一些備用空間）
for (cur = nstart; cur <= nfinish; ++cur)
*cur = allocate_node();
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) { // commit or rollback
for (map_pointer n = nstart; n < cur; ++n)
deallocate_node(*n);
map_allocator::deallocate(map, map_size);
throw;
}
# endif /* __STL_USE_EXCEPTIONS */
// 為 deque 內的兩個迭代器 start 和 finish 設定正確的值
start.set_node(nstart);
finish.set_node(nfinish);
start.cur = start.first;
finish.cur = finish.first + num_elements % buffer_size();
}
前面提到當 map 的備用空間不足，需要重新配置一塊更大的 map，有兩個函數來判斷 map 什麼時候需要重新配置：
void reserve_map_at_back (size_type nodes_to_add = 1) {
if (nodes_to_add + 1 > map_size - (finish.node - map))
// 如果 map 尾端的節點備用空間不足
// 符合上述條件則必須重新配置 map
reallocate_map(nodes_to_add, false);
}
void reserve_map_at_front (size_type nodes_to_add = 1) {
if (nodes_to_add > start.node - map)
// 如果 map 頭端的節點備用空間不足
// 符合上述條件則必須重新配置 map
reallocate_map(nodes_to_add, true);
}
template
void deque::reallocate_map(size_type nodes_to_add,
bool add_at_front) {
size_type old_num_nodes = finish.node - start.node + 1;
size_type new_num_nodes = old_num_nodes + nodes_to_add;
map_pointer new_nstart;
if (map_size > 2 * new_num_nodes) {
new_nstart = map + (map_size - new_num_nodes) / 2
+ (add_at_front ? nodes_to_add : 0);
if (new_nstart < start.node)
copy(start.node, finish.node + 1, new_nstart);
else
copy_backward(start.node, finish.node + 1, new_nstart + old_num_nodes);
}
else {
size_type new_map_size = map_size + max(map_size, nodes_to_add) + 2;
// 配置一塊空間，准備給新 map 使用
map_pointer new_map = map_allocator::allocate(new_map_size);
new_nstart = new_map + (new_map_size - new_num_nodes) / 2
+ (add_at_front ? nodes_to_add : 0);
// 把原 map 內容拷貝過來
copy(start.node, finish.node + 1, new_nstart);
// 釋放原 map
map_allocator::deallocate(map, map_size);
// 設定新 map 的起始地址與大小
map = new_map;
map_size = new_map_size;
}
// 重新設定迭代器 start 和 finish
start.set_node(new_nstart);
finish.set_node(new_nstart + old_num_nodes - 1);
}
push_*、pop_*：
void push_back(const value_type& t) {
// 最後緩沖區有兩個（或以上）備用空間
if (finish.cur != finish.last - 1) {
construct(finish.cur, t);
++finish.cur;
}
// 最後一個緩沖區只剩一個備用空間
else
push_back_aux(t);
}
void push_front(const value_type& t) {
// 第一個緩沖區有備用空間
if (start.cur != start.first) {
construct(start.cur - 1, t);
--start.cur;
}
// 第一個緩沖區已無備用空間
else
push_front_aux(t);
}
void pop_back() {
// 最後一個緩沖區有一個（或更多元素）
if (finish.cur != finish.first) {
--finish.cur;
destroy(finish.cur);
}
// 最後一個緩沖區沒有任何元素
else
pop_back_aux();
}
void pop_front() {
// 第一個緩沖區有兩個（或更多）元素
if (start.cur != start.last - 1) {
destroy(start.cur);
++start.cur;
}
// 第一個緩沖區只有一個元素
else
pop_front_aux();
}
在上述操作中，當操作發生在緩沖區邊緣時，可能需要調用相應的函數：
// 當 finish.cur == finish.last - 1 時調用
// 最後緩沖區只有一個備用空間
template
void deque::push_back_aux(const value_type& t) {
value_type t_copy = t;
reserve_map_at_back(); // 符合某種條件則必須重換一個 map
*(finish.node + 1) = allocate_node(); // 配置一個新緩沖區
__STL_TRY {
construct(finish.cur, t_copy); // 在 finish.cur 處構造 t
finish.set_node(finish.node + 1); // 改變 finish，使其指向新緩沖區
finish.cur = finish.first; // 設定 finish 狀態
}
__STL_UNWIND(deallocate_node(*(finish.node + 1)));
}
// 當 start.cur == start.first 時調用
// 第一個緩沖區沒有備用空間
template
void deque::push_front_aux(const value_type& t) {
value_type t_copy = t;
reserve_map_at_front(); // 符合某種條件則必須重換一個 map
*(start.node - 1) = allocate_node(); // 配置一個新緩沖區
__STL_TRY {
start.set_node(start.node - 1); // 改變 start，使其指向新緩沖區
start.cur = start.last - 1; // 設定 start狀態
construct(start.cur, t_copy); // 在 start.cur 處構造 t
}
# ifdef __STL_USE_EXCEPTIONS
catch(...) { // commit or rollback
start.set_node(start.node + 1);
start.cur = start.first;
deallocate_node(*(start.node - 1));
throw;
}
# endif /* __STL_USE_EXCEPTIONS */
}
// 當 finish.cur == finish.first 時調用
// 最後一個緩沖區沒有任何元素
template
void deque:: pop_back_aux() {
deallocate_node(finish.first);
finish.set_node(finish.node - 1);
finish.cur = finish.last - 1;
destroy(finish.cur);
}
// 當 start.cur == start.last - 1 時調用
// 第一緩沖區只有一個元素
template
void deque::pop_front_aux() {
destroy(start.cur);
deallocate_node(start.first);
start.set_node(start.node + 1);
start.cur = start.first;
}
clear，清空整個 deque，由於 deque 的最初狀態（不含任何元素）保有一個緩沖區，因此 clear 完成之後要回到初始狀態，即也保留一個緩沖區：
template
void deque::clear() {
// 針對頭尾以外的每一個緩沖區（他們一定是滿的）
for (map_pointer node = start.node + 1; node < finish.node; ++node) {
// 調用 destroy 第二版本，析構所有元素
destroy(*node, *node + buffer_size());
// 釋放緩沖區
data_allocator::deallocate(*node, buffer_size());
}
// 至少含有頭尾兩個緩沖區
if (start.node != finish.node) {
// 析構頭緩沖區元素
destroy(start.cur, start.last);
// 析構尾緩沖區元素
destroy(finish.first, finish.cur);
// 釋放尾緩沖區空間
data_allocator::deallocate(finish.first, buffer_size());
}
// 只有一個緩沖區，則不需要釋放空間
else
destroy(start.cur, finish.cur);
finish = start; // 調整迭代器 finish
}
erase，用於清除某個元素：
// 清除 pos 所指的元素，pos 為清除點
iterator erase(iterator pos) {
iterator next = pos;
++next;
// 清除點之前的元素個數
difference_type index = pos - start;
// 若清除點之前的元素少，就移動清除點之前的元素
if (index < (size() >> 1)) {
copy_backward(start, pos, next); // 移動元素
pop_front(); // 移動完畢，最前一個元素冗余
}
// 若清除點之後的元素少，就移動清除點之後的元素
else {
copy(next, finish, pos); // 移動元素
pop_back(); // 移動完畢，最後一個元素冗余
}
return start + index;
}
erase 還有一個版本用於清除 [first, last) 區間內的所有元素：
template
deque::iterator
deque::erase(iterator first, iterator last) {
// 若清除的是整個 deque，直接調用 clear
if (first == start && last == finish) {
clear();
return finish;
}
else {
difference_type n = last - first; // 清除區間長度
difference_type elems_before = first - start; // 清除區間之前的元素個數
// 清除區間之前的元素個數較少
if (elems_before < (size() - n) / 2) {
copy_backward(start, first, last); // 移動元素
iterator new_start = start + n; // 新的頭端
destroy(start, new_start); // 析構元素
// 釋放空間
for (map_pointer cur = start.node; cur < new_start.node; ++cur)
data_allocator::deallocate(*cur, buffer_size());
start = new_start; // 設定新的頭端
}
else {
copy(last, finish, first); // 移動元素
iterator new_finish = finish - n; // 新的尾端
destroy(new_finish, finish); // 析構元素
// 釋放空間
for (map_pointer cur = new_finish.node + 1; cur <= finish.node; ++cur)
data_allocator::deallocate(*cur, buffer_size());
finish = new_finish; // 設定新的尾
}
return start + elems_before;
}
}
insert，在指定迭代器 pos 處插入值為 x 的節點：
iterator insert(iterator position, const value_type& x) {
// 在 deque 頭端插入，調用 push_front
if (position.cur == start.cur) {
push_front(x);
return start;
}
// 在 deque 尾端插入，調用 push_back
else if (position.cur == finish.cur) {
push_back(x);
iterator tmp = finish;
--tmp;
return tmp;
}
// 在其他位置插入
else {
return insert_aux(position, x);
}
}
template
typename deque::iterator
deque::insert_aux(iterator pos, const value_type& x) {
// 插入點之前的元素個數
difference_type index = pos - start;
value_type x_copy = x;
// 插入點之前元素個數較少，則在頭端插入
if (index < size() / 2) {
push_front(front());
iterator front1 = start;
++front1;
iterator front2 = front1;
++front2;
pos = start + index;
iterator pos1 = pos;
++pos1;
copy(front2, pos1, front1); // 元素移動
}
// 插入點之後元素個數較少，則在尾端插入
else {
push_back(back());
iterator back1 = finish;
--back1;
iterator back2 = back1;
--back2;
pos = start + index;
copy_backward(pos, back2, back1); // 元素移動
}
*pos = x_copy; // 設定新值
return pos;
}
stack 是一種先進後出的數據結構，只有一個開口，允許進行：新增元素、移除元素、取頂端元素等操作，不能進行迭代器訪問操作。
在 SGI STL 的實現中，stack 內含一個 deque 成員，其完整實現如下：
template >
class stack {
friend bool operator== __STL_NULL_TMPL_ARGS (const stack&, const stack&);
friend bool operator< __STL_NULL_TMPL_ARGS (const stack&, const stack&);
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c;
public:
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference top() { return c.back(); }
const_reference top() const { return c.back(); }
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_back(); }
};
template
bool operator==(const stack& x, const stack& y) {
return x.c == y.c;
}
template
bool operator<(const stack& x, const stack& y) {
return x.c < y.c;
}
queue 是一種先進先出的數據結構，只能在一端插入，另一端移除，允許進行：新增元素、移除元素、取首尾元素等操作，不能進行迭代器訪問操作。
在 SGI STL 的實現中，queue 內含一個 deque 成員，其完整實現如下：
template >
class queue {
friend bool operator== __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
friend bool operator< __STL_NULL_TMPL_ARGS (const queue& x, const queue& y);
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequence c;
public:
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
reference front() { return c.front(); }
const_reference front() const { return c.front(); }
reference back() { return c.back(); }
const_reference back() const { return c.back(); }
void push(const value_type& x) { c.push_back(x); }
void pop() { c.pop_front(); }
};
template
bool operator==(const queue& x, const queue& y) {
return x.c == y.c;
}
template
bool operator<(const queue& x, const queue& y) {
return x.c < y.c;
}
