STL使用：deque雙端隊列

雙端隊列deque支援兩端的插入和删除操作。由于它是動态地以分段連續空間組合而成的，是以沒有容量（capacity）的概念，可以随時增加一段新的空間并連結起來。deque不會像vector那樣因為舊空間不足而重新配置一塊更大的空間，然後再複制元素，再釋放舊空間。是以，deque也就沒有必要提供所謂的空間保留（reserve）功能。

1)支援随即存取。

2)支援兩端操作，push(pop)-back(front)，在 兩端操作上與list效率差不多。  在“中間”插入和删除元素具有與vector一樣的低效率。 vector，list，deque為三種獨立的容器

在實際使用時，如何選擇這三個容器中哪一個，應根據需要而定，一般應遵循下面的原則：

1、如果你需要 高效的随機存取，而不在乎插入和删除的效率，使用vector

2、如果你需要大量的插入和删除，而不關心随機存取，則應使用list

3、如果你需要随即存取，而且關心兩端資料的插入和删除，則應使用deque。

函數：

(1)    構造函數

deque():建立一個空deque

deque(int nSize):建立一個deque,元素個數為nSize

deque(int nSize,const T& t):建立一個deque,元素個數為nSize,且值均為t

deque(const deque &):複制構造函數

(2)    增加函數

void push_front(const T& x):雙端隊列頭部增加一個元素X

void push_back(const T& x):雙端隊列尾部增加一個元素x

iterator insert(iterator it,const T& x):雙端隊列中某一進制素前增加一個元素x

void insert(iterator it,int n,const T& x):雙端隊列中某一進制素前增加n個相同的元素x

void insert(iterator it,const_iterator first,const_iteratorlast):雙端隊列中某一進制素前插入另一個相同類型向量的[forst,last)間的資料

(3)    删除函數

Iterator erase(iterator it):删除雙端隊列中的某一個元素

Iterator erase(iterator first,iterator last):删除雙端隊列中[first,last）中的元素

void pop_front():删除雙端隊列中最前一個元素

void pop_back():删除雙端隊列中最後一個元素

void clear():清空雙端隊列中最後一個元素

(4)    周遊函數

reference at(int pos):傳回pos位置元素的引用

reference front():傳回手元素的引用

reference back():傳回尾元素的引用

iterator begin():傳回向量頭指針，指向第一個元素

iterator end():傳回指向向量中最後一個元素下一個元素的指針（不包含在向量中）

reverse_iterator rbegin():反向疊代器，指向最後一個元素

reverse_iterator rend():反向疊代器，指向第一個元素的前一個元素

(5)    判斷函數

bool empty() const:向量是否為空，若true,則向量中無元素

(6)    大小函數

Int size() const:傳回向量中元素的個數

int max_size() const:傳回最大可允許的雙端對了元素數量值

(7)    其他函數

void swap(deque&):交換兩個同類型向量的資料

void assign(int n,const T& x):向量中第n個元素的值設定為x

執行個體：

// deque.cpp : 定義控制台應用程式的入口點。

#include<iostream>
#include<deque>

using namespace std;
void printDeque(deque<int> d)
{
    //使用下标
    for (unsigned int i = 0; i < d.size(); i++)
    {
        cout<<d.at(i)<<"\t";//貌似使用a[i]也是可行的
    }
    cout<<endl;

    //使用疊代器
    //deque<int>::iterator iter = d.begin();
    //for (;iter != d.end(); iter ++)
    //{
    // cout<<"d["<<iter-d.begin()<<"] = "<<(*iter)<<", ";
    //}
}
int main()
{
    deque<int> d;
    d.push_back( 10 );
    d.push_back(20);
    d.push_back(30);
    cout<<"原始雙端隊列："<<endl;
    for(int i = 0; i < d.size(); i++)
    {
        cout<<d.at(i)<<"\t";//at()傳回在特定位置元素的引用
    }
    cout<<endl;
    d.push_front(5);
    d.push_front(3);
    d.push_front(1);

    cout<<"after push_front(5.3.1):"<<endl;
    for(int i = 0;i < d.size();i++)
    {
        cout<<d.at(i)<<"\t";
    }
    cout<<endl;
    d.pop_front();
    d.pop_front();
    cout<<"after pop_front() two times:"<<endl;
    for(int i = 0;i < d.size();i++)
    {
        cout<<d.at(i)<<"\t";
    }
    cout<<endl;
    //若是采用疊代器進行輸出呢？
    //使用疊代器指針
    cout<<"采用疊代器進行輸出："<<endl;
    deque<int>::iterator *pIter = new deque<int>::iterator;
    if ( NULL == pIter )
    {
        return 0;
    }
    for (*pIter = d.begin(); *pIter != d.end(); (*pIter)++)
    {
        //cout<<"d["<<*pIter - d.begin() <<"]="<<**pIter<<", ";
        cout<<**pIter<<"\t";
    }
    if (NULL != pIter)
    {
        delete pIter;
        pIter = NULL;
    }
    cout<<endl;
    //進行pop_back
    d.pop_back();
    d.pop_back();
    cout<<"after pop_back two times:"<<endl;
    for(int i = 0;i < d.size();i++)
    {
        cout<<d.at(i)<<"\t";
    }
    cout<<endl;
    //測試erase操作
    //任意疊代位置或疊代區間上的元素删除用erase(&pos)/erase(&first, &last)；删除所有元素用clear();
    d.push_back(20);
    d.push_back(30);
    cout<<"先恢複，再d.erase(d.begin()+1): "<<endl;
    d.erase(d.begin()+1); //删除第2個元素d[1]，即删除10
    printDeque(d);//此時隻剩下5，20，30

    //測試區間删除
    deque<int> d1; 
    cout<<"New deque d1:"<<endl;
    for (int i = 1; i < 6 ; i++)
        d1.push_back(i*10);
    printDeque(d1);
    cout<<"d1.erase(d1.begin()+1, d1.begin() + 3) = "<<endl;
    d1.erase(d1.begin()+1, d1.begin() + 3);//删除雙端隊列中[first,last）中的元素
    printDeque(d1);

    return 0;
}


           

結果圖如下：