[TOC] # 簡介 Vector容器是單向開口的連續內存空間，deque則是一種雙向開口的連續線性空間。所謂的雙向開口，意思是可以在頭尾兩端分別做元素的插入和刪除操作，當然，vector容器也可以在頭尾兩端插入元素，但是在其頭部操作效率奇差，無法被接受。  Deque容器和vector容器最大的差異，一在于deque允許使用常數項時間對頭端進行元素的插入和刪除操作。二在于deque沒有容量的概念，因為它是動態的以分段連續空間組合而成，隨時可以增加一段新的空間并鏈接起來，換句話說，像vector那樣，”舊空間不足而重新配置一塊更大空間，然后復制元素，再釋放舊空間”這樣的事情在deque身上是不會發生的。也因此，deque沒有必須要提供所謂的空間保留(reserve)功能. 雖然deque容器也提供了Random Access Iterator,但是它的迭代器并不是普通的指針，其復雜度和vector不是一個量級，這當然影響各個運算的層面。因此，除非有必要，我們應該盡可能的使用vector，而不是deque。對deque進行的排序操作，為了最高效率，可將deque先完整的復制到一個vector中，對vector容器進行排序，再復制回deque. # 實現原理 Deque容器是連續的空間，至少邏輯上看來如此，連續現行空間總是令我們聯想到array和vector,array無法成長，vector雖可成長，卻只能向尾端成長，而且其成長其實是一個假象，事實上(1) 申請更大空間 (2)原數據復制新空間 (3)釋放原空間 三步驟，如果不是vector每次配置新的空間時都留有余裕，其成長假象所帶來的代價是非常昂貴的。 Deque是由一段一段的定量的連續空間構成。一旦有必要在deque前端或者尾端增加新的空間，便配置一段連續定量的空間，串接在deque的頭端或者尾端。Deque最大的工作就是維護這些分段連續的內存空間的整體性的假象，并提供隨機存取的接口，避開了重新配置空間，復制，釋放的輪回，代價就是復雜的迭代器架構。 既然deque是分段連續內存空間，那么就必須有中央控制，維持整體連續的假象，數據結構的設計及迭代器的前進后退操作頗為繁瑣。Deque代碼的實現遠比vector或list都多得多。 Deque采取一塊所謂的map(注意，不是STL的map容器)作為主控，這里所謂的map是一小塊連續的內存空間，其中每一個元素(此處成為一個結點)都是一個指針，指向另一段連續性內存空間，稱作緩沖區。緩沖區才是deque的存儲空間的主體。  # 常用api ## 構造函數 ~~~ deque<T> deqT;//默認構造形式 deque(beg, end);//構造函數將[beg, end)區間中的元素拷貝給本身。 deque(n, elem);//構造函數將n個elem拷貝給本身。 deque(const deque &deq);//拷貝構造函數。 ~~~ ~~~ int arr[] = { 1, 3, 8, 9, 2 }; deque<int> d1(arr, arr + sizeof(arr) / sizeof(int)); ~~~ ## 賦值操作 ~~~ assign(beg, end);//將[beg, end)區間中的數據拷貝賦值給本身。 assign(n, elem);//將n個elem拷貝賦值給本身。 deque&operator=(const deque &deq); //重載等號操作符 swap(deq);// 將deq與本身的元素互換 ~~~ ~~~ int arr[] = { 1, 3, 8, 9, 2 }; deque<int> d1(arr, arr + sizeof(arr) / sizeof(int)); deque<int> d2; d2.assign(d1.begin(), d1.end()); d2.push_back(100); cout << "------------" << endl; d1.swap(d2); ~~~ ## 大小操作 ~~~ deque.size();//返回容器中元素的個數 deque.empty();//判斷容器是否為空 deque.resize(num);//重新指定容器的長度為num,若容器變長，則以默認值填充新位置。如果容器變短，則末尾超出容器長度的元素被刪除。 deque.resize(num, elem); //重新指定容器的長度為num,若容器變長，則以elem值填充新位置,如果容器變短，則末尾超出容器長度的元素被刪除。 ~~~ ~~~ deque<int> d; cout << d.size() << endl; if (d.empty()) { cout << "空" << endl; } d.resize(10, 7); ~~~ ## 雙端插入和刪除操作 ~~~ push_back(elem);//在容器尾部添加一個數據 push_front(elem);//在容器頭部插入一個數據 pop_back();//刪除容器最后一個數據 pop_front();//刪除容器第一個數據 at(idx);//返回索引idx所指的數據，如果idx越界，拋出out_of_range。 operator[];//返回索引idx所指的數據，如果idx越界，不拋出異常，直接出錯。 front();//返回第一個數據。 back();//返回最后一個數據 ~~~ ~~~ deque<int> d; d.push_back(10); d.push_front(20); d[0] = 200; //d.at(8) = 800;err d.at(1) = 100; d.pop_back(); d.pop_front(); ~~~ ## 插入操作 ~~~ insert(pos,elem);//在pos位置插入一個elem元素的拷貝，返回新數據的位置。 insert(pos,n,elem);//在pos位置插入n個elem數據，無返回值。 insert(pos,beg,end);//在pos位置插入[beg,end)區間的數據，無返回值。 ~~~ ~~~ deque<int> d; d.push_back(10); d.push_back(20); d.push_back(30); d.push_back(40); d.push_back(50); d.insert(d.begin() + 1, 100); d.insert(d.begin() + 2, 2, 0); deque<int> d2; d2.push_back(1000); d2.push_back(2000); d2.push_back(3000); d2.insert(d2.begin() + 1, d.begin(), d.end()); ~~~ ## 刪除操作 ~~~ clear();//移除容器的所有數據 erase(beg,end);//刪除[beg,end)區間的數據，返回下一個數據的位置。 erase(pos);//刪除pos位置的數據，返回下一個數據的位置。 ~~~ ~~~ deque<int> d; d.push_back(10); d.push_back(20); d.push_back(30); d.push_back(40); d.push_back(50); deque<int>::iterator it=d.erase(d.begin() + 1, d.end() - 1); cout << *it << endl; d.clear(); ~~~