C++ Deque(雙向隊列)
是一種優化了的、對序列兩端元素進行添加和删除操作的基本序列容器。它允許較為快速地随機通路，但它不像vector 把所有的對象儲存在一塊連續的記憶體塊，而是采用多個連續的存儲塊，并且在一個映射結構中儲存對這些塊及其順序的跟蹤。向deque 兩端添加或删除元素的開銷很小。它不需要重新配置設定空間，是以向末端增加元素比vector 更有效。
實際上，deque 是對vector 和list 優缺點的結合，它是處于兩者之間的一種容器。
Deque 的特點：
(1) 随機通路友善，即支援[ ] 操作符和vector.at() ，但性能沒有vector 好；
(2) 可以在内部進行插入和删除操作，但性能不及list ；
(3) 可以在兩端進行push 、pop ；
(4) 相對于verctor 占用更多的記憶體。
雙向隊列和向量很相似，但是它允許在容器頭部快速插入和删除（就像在尾部一樣）。
1.Constructors 建立一個新雙向隊列
文法:
deque();//建立一個空雙向隊列
deque( size_type size );// 建立一個大小為size的雙向隊列
deque( size_type num, const TYPE &val ); //放置num個val的拷貝到隊列中
deque( const deque &from );// 從from建立一個内容一樣的雙向隊列
deque( input_iterator start, input_iterator end );
// start 和 end - 建立一個隊列，儲存從start到end的元素。
<span style="font-family:Microsoft YaHei;font-size:18px;">// constructing deques
#include <iostream>
#include <deque>
int main()
{
unsigned int i;
std::deque<int> first; //構造一個空的雙向隊列 // empty deque of ints
std::deque<int> second(4, 100); //設定4個值為100的雙向隊列
std::deque<int> third(second.begin(), second.end()); //以第二個為基本拷貝
std::deque<int> fourth(third);//以第三個為準進行構造
int myints[] = { 16, 2, 77, 29 };
std::deque<int> fifth(myints, myints + sizeof(myints) / sizeof(int));
std::cout << "The contents of fifth are:";
for (std::deque<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
system("pause");
return 0;
}</span> 2.Operators 比較和指派雙向隊列
//可以使用[]操作符通路雙向隊列中單個的元素
3.assign() 設定雙向隊列的值
文法:
void assign( input_iterator start, input_iterator end);
//start和end訓示的範圍為雙向隊列指派
void assign( Size num, const TYPE &val );//設定成num個val。
<span style="font-family:Microsoft YaHei;font-size:18px;">// deque::assign
#include <iostream>
#include <deque>
int main()
{
std::deque<int> first;
std::deque<int> second;
std::deque<int> third;
first.assign(7, 100); //設定7個值為100的雙端隊列
std::deque<int>::iterator it;
it = first.begin() + 1;
//it指向第二個，end()-1---->共5個
second.assign(it, first.end() - 1);
int myints[] = { 1776, 7, 4 };
third.assign(myints, myints + 3); // assigning from array.
std::cout << "Size of first: " << int(first.size()) << '\n';
std::cout << "Size of second: " << int(second.size()) << '\n';
std::cout << "Size of third: " << int(third.size()) << '\n';
system("pause");
return 0;
}</span> 4.at() 傳回指定的元素
文法:
reference at( size_type pos ); 傳回一個引用，指向雙向隊列中位置pos上的元素
<span style="font-family:Microsoft YaHei;font-size:18px;">std::deque<unsigned> mydeque(10); // 10 zero-initialized unsigneds
for (unsigned i = 0; i<mydeque.size(); i++)
mydeque.at(i) = i; //0 1 2 3 4 5 6 7 8 9
std::cout << "mydeque contains:";
for (unsigned i = 0; i<mydeque.size(); i++)
std::cout << ' ' << mydeque.at(i);
</span> 5.back() 傳回最後一個元素
文法:
reference back();//傳回一個引用，指向雙向隊列中最後一個元素
<span style="font-family:Microsoft YaHei;font-size:18px;">// deque::back
#include <iostream>
#include <deque>
int main()
{
std::deque<int> mydeque;
mydeque.push_back(10);//壓入一個10
while (mydeque.back() != 0)
mydeque.push_back(mydeque.back() - 1);
//back每次得到最後一個元素，然後在減一，是以壓入9-0
std::cout << "mydeque contains:";
for (std::deque<int>::iterator it = mydeque.begin(); it != mydeque.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
system("pause");
return 0;
}</span> 6.begin() 傳回指向第一個元素的疊代器
文法:
iterator begin();//傳回一個疊代器，指向雙向隊列的第一個元素
7.clear() 删除所有元素
8.empty() 傳回真如果雙向隊列為空
9.end() 傳回指向尾部的疊代器
10.erase() 删除一個元素
文法:
iterator erase( iterator pos ); //删除pos位置上的元素
iterator erase( iterator start, iterator end ); //删除start和end之間的所有元素
//傳回指向被删除元素的後一個元素
11.front() 傳回第一個元素的引用
12.get_allocator() 傳回雙向隊列的配置器
13.insert() 插入一個元素到雙向隊列中
文法:
iterator insert( iterator pos, size_type num, const TYPE &val ); //pos前插入num個val值
void insert( iterator pos, input_iterator start, input_iterator end );
//插入從start到end範圍内的元素到pos前面
<span style="font-family:Microsoft YaHei;font-size:18px;">// inserting into a deque
#include <iostream>
#include <deque>
#include <vector>
int main()
{
std::deque<int> mydeque;
for (int i = 1; i<6; i++) mydeque.push_back(i); // 1 2 3 4 5
std::deque<int>::iterator it = mydeque.begin();
++it;
it = mydeque.insert(it, 10); //it指向2，在2的前面插入10// 1 10 2 3 4 5
mydeque.insert(it, 2, 20);//it此時指向10，在10前面插入2個20 // 1 20 20 10 2 3 4 5
it = mydeque.begin() + 2;//it指向第二個20。
std::vector<int> myvector(2, 30);//2個30構造
mydeque.insert(it, myvector.begin(), myvector.end());
//在第二個20前插入兩個30 // 1 20 30 30 20 10 2 3 4 5
std::cout << "mydeque contains:";
for (it = mydeque.begin(); it != mydeque.end(); ++it)
std::cout << ' ' << *it;
std::cout << '\n';
system("pause");
return 0;
}</span> 14.max_size() 傳回雙向隊列能容納的最大元素個數
15.pop_back() 删除尾部的元素
16.pop_front() 删除頭部的元素
17.push_back() 在尾部加入一個元素
18.push_front() 在頭部加入一個元素
19.rbegin() 傳回指向尾部的逆向疊代器
20.rend() 傳回指向頭部的逆向疊代器
21.resize() 改變雙向隊列的大小
22.size() 傳回雙向隊列中元素的個數