STL通用容器之 deque 容器

1.5deque容器

deque容器为一个给定类型的元素进行线性处理，就如向量，它能够快速地随机进入任一个元素，并且能够高效地

入和删除容器的尾部元素。但它与vector不同，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_iterator last);

; 双端队列中某一元素前插入另一个相同类型向量的[first,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();反向迭代器，功能等同iterator end()

 reverse_iterator rend();反向迭代器，功能等同iterator begin()

(5)判断函数

 bool empty() const;向量是否为空？若true,则向量中无元素。

大小函数

 int size() const;返回向量中元素的个数

 int max_size() const;返回最大可允许的双端队列元素数量值

(6)其它函数

 void swap(vector&);交换两个同类型向量的数据

 void assign(int n, const T& x);向量中第n个元素设置成元素x

 void assign(const_iterator first, const_iterator last);向量中[first,last]元素设置成当前向量元素。

deque中push_front、pop_front函数示例

#include<iostream>
#include<deque>
using namespace std;
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";
     }
     cout<<endl;
     d.push_front(5);
     d.push_front(3);
     d.push_front(1);
     for(int i=0;i<d.size();i++)
     {
          cout<<d.at(i)<<"\t";
     }
     cout<<endl;
     d.pop_front();
     d.pop_front();
     for(int i=0;i<d.size();i++)
     {
          cout<<d[i]<<"\t";
     }
     cout<<endl;
     return 0;
}
           

deque可以通过push_front直接在容器头增加元素，通过pop_front直接删除容器头元素，这一点是vector元素不具备的。

deque与vector内存分配比较示例

<span style="font-size:18px;">#include <iostream>
#include <vector>
#include <deque>
using namespace std;
void main()
{
    vector<int> v(2);
    v[0] = 10;
    int *p = &v[0];
    cout << "vector第1个元素迭代指针*p=" <<*p << endl;	  //10
    v.push_back(20);
    cout << "vector容量变化后原vector第1个元素迭代指针*p=" << *p << endl; //数不确定
    deque<int> d(2);
    d[0] = 10;
    int *q = &d[0];
    cout << "deque第1个元素迭代指针*q=" <<*q << endl;	//10
    d.push_back(20);
    cout << "deque容量变化后第1个元素迭代指针*q=" <<*q << endl;  //10
}
</span>
           

该段程序功能是：deque、vector初始化大小为2，第1个元素都为10，当通过push_back函数分别给两容器

加一个元素后，从结果发现原先保持的指针元素值对vector容器前后发生了变化，而对deque容器前后没有

生变化.

以deque为基础，编一个先进先出的队列类。

<span style="font-size:18px;">#include<iostream>
#include<deque>
using namespace std;
template<class T>
class MyQueue
{
     deque<T>d;
public:
     void push(const T &t);
     void pop();
     int Size();
     bool Empty();
     T &Front();
     T &Back();
     void display();
};
template<class T>
void MyQueue<T>::push(const T &t)
{
     d.push_back(t);
}
template<class T>
void MyQueue<T>::pop()
{
     d.pop_front();
}
template<class T>
int MyQueue<T>::Size()
{
     return d.size();
}
template<class T>
bool MyQueue<T>::Empty()
{
     return d.empty();
}
template<class T>
T &MyQueue<T>::Front()
{
     return *d.begin();
}
template<class T>
T &MyQueue<T>::Back()
{
     return *(--d.end());
}
template<class T>
void MyQueue<T>::display()
{
     for(int i=0;i<d.size();i++)
     {
          cout<<d.at(i)<<"\t";
     }
     cout<<endl;
}
int main()
{
     MyQueue<int>myqueue;
     for(int i=0;i<=5;i++)
     {
          myqueue.push(i);
     }
     myqueue.display();
     myqueue.pop();
     myqueue.display();
     myqueue.push(6);
     myqueue.display();
     cout<<myqueue.Front()<<endl;
     cout<<myqueue.Back()<<endl;
     return 0;
}</span>