c++---deque的使用

1. deque的介紹
2. deque的使用
3. deque的應用

一， deque的介紹及使用

• deque的介紹

1. deque(發音類似“deck”)，是雙端隊列不規則的首字母縮寫，雙端隊列是動态大小的序列式容器，其可 以像兩端進行伸縮。
2. 特定的庫可以以不同的方式實作deque，但通常都是一種動态數組。不論在何種情況下，它都允許通過 随機通路疊代器直接通路單個元素，可以根據需要動态的伸縮。
3. 是以，deque提供了一些與vector相似的功能，但deque在頭部和尾部進行資料插入和删除操作更加高 效。與vector不同的是，deque不能保證所有的元素存儲在連續的空間中，在deque中通過指針加偏移 量方式通路元素可能會導緻非法的操作。
4. vector與list提供了相似的接口，是以其具有類似的用途，但是内部的實作原理不同：vector使用使用了 動态數組，該數組通常需要動态增長；deque中的元素可能分散在不同的存儲塊中，在deque中儲存了 一些必要的資訊，通常用來在常數範圍内直接通路deque中的任何一個元素，是以deque的内部實作比 vector複雜，但是這些額外資訊使得dque在某些情況下增長更加的高效，特别是在序列比較大，重新分 配成本比較高的情況下。
5. 除了在頻繁在頭部或尾部進行插入和删除操作外，deque比list和forward_list的性能更差。

二，deque的使用

• deque的構造

deque()//構造空的雙端隊列
deque(n,val=value type());//用n個值為val的元素構造雙端隊列
deque(InputIterator first, InputIterator last)；//用[first, last)的區間構造雙端隊列
deque(const deque& x);//雙端隊列的拷貝構造函數
           

• deque的疊代器、

  

  deque的疊代器雙端隊列底層是一段假象的連續空間，實際是分段連續的，為了維護其“整體連續”的假象，落在了deque的 疊代器身上。下圖為deque的原理圖：

  

[begin(), end()()) ；//begin:容器起始位置   end最後一個元素下一個位置
[rbegin(), rend()) ；//反向疊代器rbegin在end位置，rend在begin
[cbegin(), cend()) ；//const疊代器，與begin和end位置相同，但不能修改其空間内容
[crbegin(), crend()) ；//const反向疊代器，與crbegin在cend位置，crend在cbegin位置
           

• deque的容量操作

size();//傳回deque有效元素的個數
empty();//檢測deque是否為空，是傳回true，否則傳回false
resize();//将deque中的元素改變到sz，多處的空間用value填充
           

• deque的元素通路操作

operator[];//傳回deque中n位置上元素的引用
front();//傳回deque中首元素的引用
back();//傳回deque中最後一個元素的引用
           

• deque中修改操作

push_back() ；
pop_back() ；//deque的尾插和尾删 
push_front() ；
 pop_front() ；//deque任意位置插入和删除
insert(pos, value) ；
 erase(pos)； 删除deque頭部元素
swap() ；交換兩個deque中的内容
clear() ；将deque中的元素清
           

例子：

#include <iostream>
#include <deque>
using namespace std;
int main(){
	deque<int>q;//構造一個空的deque
	q.push_back(1);//尾插1 2 3
	q.push_back(2);
	q.push_back(3);
	deque<int>::iterator be = q.begin();
	while (be != q.end()){
		cout << *be << endl;
		be++;
	}
	cout << q.front() << endl;
	cout << q.back() << endl;
	q.push_front(0);
	deque<int>::reverse_iterator be1 = q.rbegin();
	while (be1 != q.rend()){
		cout << *be1 << endl;
		be1++;
	}

	system("pause");
	return EXIT_SUCCESS;
}
           

三，deque的應用場景

deque再序列式容器中比較雞肋，因為如果隻是簡單的存儲元素，使用vector即可，如果對元素任意位置進行插入或者删除操作比較多，使用list即可，是以一般對deque很少去使用。deque最大的應用就是作為标準庫中stack和queue的底層結構。