deque
Vector容器是單向開口的連續(xù)內(nèi)存空間，deque則是一種雙向開口的連續(xù)線性空間。所謂的雙向開口，意思是可以在頭尾兩端分別做元素的插入和刪除操作，當然，vector容器也可以在頭尾兩端插入元素，但是在其頭部操作效率奇差，無法被接受。
Deque容器和vector容器最大的差異，一在于deque允許使用常數(shù)項時間對頭端進行元素的插入和刪除操作。二在于deque沒有容量的概念，因為它是動態(tài)的以分段連續(xù)空間組合而成，隨時可以增加一段新的空間并鏈接起來，換句話說，像vector那樣，”舊空間不足而重新配置一塊更大空間，然后復制元素，再釋放舊空間”這樣的事情在deque身上是不會發(fā)生的。也因此，deque沒有必須要提供所謂的空間保留(reserve)功能.
雖然deque容器也提供了Random Access Iterator,但是它的迭代器并不是普通的指針，其復雜度和vector不是一個量級，這當然影響各個運算的層面。因此，除非有必要，我們應該盡可能的使用vector，而不是deque。對deque進行的排序操作，為了最高效率，可將deque先完整的復制到一個vector中，對vector容器進行排序，再復制回deque.
實現(xiàn)原理
Deque容器是連續(xù)的空間，至少邏輯上看來如此，連續(xù)現(xiàn)行空間總是令我們聯(lián)想到array和vector,array無法成長，vector雖可成長，卻只能向尾端成長，而且其成長其實是一個假象，事實上(1) 申請更大空間 (2)原數(shù)據(jù)復制新空間 (3)釋放原空間 三步驟，如果不是vector每次配置新的空間時都留有余裕，其成長假象所帶來的代價是非常昂貴的。
Deque是由一段一段的定量的連續(xù)空間構成。一旦有必要在deque前端或者尾端增加新的空間，便配置一段連續(xù)定量的空間，串接在deque的頭端或者尾端。Deque最大的工作就是維護這些分段連續(xù)的內(nèi)存空間的整體性的假象，并提供隨機存取的接口，避開了重新配置空間，復制，釋放的輪回，代價就是復雜的迭代器架構。
既然deque是分段連續(xù)內(nèi)存空間，那么就必須有中央控制，維持整體連續(xù)的假象，數(shù)據(jù)結構的設計及迭代器的前進后退操作頗為繁瑣。Deque代碼的實現(xiàn)遠比vector或list都多得多。
Deque采取一塊所謂的map(注意，不是STL的map容器)作為主控，這里所謂的map是一小塊連續(xù)的內(nèi)存空間，其中每一個元素(此處成為一個結點)都是一個指針，指向另一段連續(xù)性內(nèi)存空間，稱作緩沖區(qū)。緩沖區(qū)才是deque的存儲空間的主體。
聲明方法
- 默認構造形式：使用默認構造函數(shù)創(chuàng)建一個空的deque容器。
deque<T> deqT;
deque<int> r1;//默認構造形式：創(chuàng)建一個空的deque容器
- 范圍構造函數(shù)：使用指定范圍內(nèi)的元素創(chuàng)建deque容器，將[beg, end)區(qū)間中的元素拷貝給本身。
deque<T> deqT(beg, end);
int arr[] = { 1,2,3,4,5 };
deque<int> r2(arr, arr + 5);// 范圍構造函數(shù)：將指定范圍內(nèi)的元素拷貝給本身
其中，beg是指向范圍起始位置的迭代器，end是指向范圍結束位置的迭代器。
- 值構造函數(shù)：使用指定值創(chuàng)建deque容器，將n個elem拷貝給本身。
deque<T> deqT(n, elem);
deque<int> r3(3, 100);// 創(chuàng)建包含3個值為10的元素的deque
其中，n是要創(chuàng)建的元素數(shù)量，elem是要拷貝的元素值。
- 拷貝構造函數(shù)：使用另一個deque容器進行拷貝構造，創(chuàng)建一個新的deque容器。
deque<T> deqT(deq);
deque<int> deq4(deq2);
其中，deq是要進行拷貝的deque容器。
賦值操作
-
assign(beg, end);//將[beg, end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身。
-
assign(n, elem);//將n個elem拷貝賦值給本身。
-
deque&operator=(const deque &deq); //重載等號操作符
-
swap(deq);// 將deq與本身的元素互換
template <typename T>
void print(const T& r1, const T& r2){
std::cout << "r1: ";
for (const auto& elem : r1) {
std::cout << elem << " ";
}
std::cout << std::endl;
std::cout << "r2: ";
for (const auto& elem : r2) {
std::cout << elem << " ";
}
std::cout << std::endl;
cout << "-------------" << endl;
}
deque<int> r1, r2;
deque<int> data = { 1,2,3,4,5 };
r1.assign(data.begin(), data.end());
print(r1, r2);
r2.assign(3, 100);
print(r1, r2);
r2 = r1;
print(r1, r2);
r1.swap(r2);
print(r1, r2);
容量大小
deque.size();//返回容器中元素的個數(shù)
deque.empty();//判斷容器是否為空
deque.resize(num);//重新指定容器的長度為num,若容器變長，則以默認值填充新位置。如果容器變短，則末尾超出容器長度的元素被刪除。
deque.resize(num, elem); //重新指定容器的長度為num,若容器變長，則以elem值填充新位置,如果容器變短，則末尾超出容器長度的元素被刪除。
deque<int> r1, r2;
deque<int> data = { 1,2,3,4,5 };
r1.assign(data.begin(), data.end());
cout << "r2.empty:" << r2.empty() << endl;
print(r1, r2);
r2.assign(3, 100);
print(r1, r2);
cout << "r1 size: " << r1.size() << endl;
r1.resize(8);
r2.resize(8, 100);
print(r1, r2);
文章來源：http://www.zghlxwxcb.cn/news/detail-840740.html
插入和刪除
push_back(elem);//在容器尾部添加一個數(shù)據(jù)
push_front(elem);//在容器頭部插入一個數(shù)據(jù)
pop_back();//刪除容器最后一個數(shù)據(jù)
pop_front();//刪除容器第一個數(shù)據(jù)
at(idx);//返回索引idx所指的數(shù)據(jù)，如果idx越界，拋出out_of_range。
operator[];//返回索引idx所指的數(shù)據(jù)，如果idx越界，不拋出異常，直接出錯。
front();//返回第一個數(shù)據(jù)。
back();//返回最后一個數(shù)據(jù)
insert(pos,elem);//在pos位置插入一個elem元素的拷貝，返回新數(shù)據(jù)的位置。
insert(pos,n,elem);//在pos位置插入n個elem數(shù)據(jù)，無返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)區(qū)間的數(shù)據(jù)，無返回值。
clear();//移除容器的所有數(shù)據(jù)
erase(beg,end);//刪除[beg,end)區(qū)間的數(shù)據(jù)，返回下一個數(shù)據(jù)的位置。
erase(pos);//刪除pos位置的數(shù)據(jù)，返回下一個數(shù)據(jù)的位置。insert 函數(shù)的參數(shù) pos 實際上是一個迭代器(iterator)類型，而不是簡單的整數(shù)類型
deque<int> r1;
r1.push_back(27);
print(r1);
r1.push_front(12);
print(r1);
// 返回索引idx所指的數(shù)據(jù)，如果idx越界，拋出out_of_range。
try {
int v = r1.at(12);
cout << "Value at index 12: " << v << std::endl;
v = r1.at(127);
}
catch (const out_of_range& e) {
cerr << "Out of range error: " << e.what() << std::endl;
}
// 返回索引idx所指的數(shù)據(jù)，如果idx越界，不拋出異常，直接出錯。
int value = r1[1]; // 可能會直接出錯，因為不會拋出異常
cout << "First value: " << r1.front() << std::endl;// 返回第一個數(shù)據(jù)
cout << "Last value: " << r1.back() << std::endl;// 返回最后一個數(shù)據(jù)
//在pos位置插入一個elem元素的拷貝，返回新數(shù)據(jù)的位置。
auto it = r1.insert(r1.begin() + 2, 99);
/*在代碼中使用 auto 關鍵字的作用是讓編譯器根據(jù)等號右邊表達式的類型推導出左邊變量的類型，從而簡化代碼書寫。
r1.insert(r1.begin() + 2, 99) 這個表達式的返回類型是一個迭代器(iterator)，它指向插入的元素位置。
由于迭代器的類型可能很復雜且并非顯式指定，因此可以使用 auto 讓編譯器自動推導出正確的類型。*/
// 在pos位置插入n個elem數(shù)據(jù)
r1.insert(r1.begin() + 2, 3, 88);
print(r1);
// 在pos位置插入[beg,end)區(qū)間的數(shù)據(jù)
deque<int> r2 = { 1,2,3 };
r1.insert(r1.begin() + 2, r2.begin(), r2.end());
r2 = r1;
print(r1);
r1.clear();
r1 = r2;
r1.erase(r1.begin() + 2, r1.begin() + 5);
print(r1);
r1.erase(r1.begin()+2);
文章來源地址http://www.zghlxwxcb.cn/news/detail-840740.html
到了這里，關于C++ STL第三篇（搞清楚deque原理和有多少用法）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
