deque类

基础介绍

deque是双端队列，它提供了和vector类似的接口但是底层的实现与vector完全不同，vector底层用三个指针指向数组的起点，尾部和总容量的尾部，并且所有元素都是连续的，但是在deque中所有元素并不一定都是在连续的内存空间上的。deque在底层实现上是将一个连续的空间分段进行管理，并将它们的首地址用一个指针数组进行管理，这样特殊的存储结构使得它在头部和尾部增加元素比vector更加高效，但是底层实现更为复杂，存储了很多额外信息。如果抛去在头部和尾部增加元素，在中间任意位置添加元素，它的效率比vector更高，但是比list要低。

常用接口

构造函数

deque();                                                  //构造空的双端队列
deque(size_type n, const value_type &val = value_type()); //用n个值为val的元素构造双端队列
deque(InputIterator first, InputIterator last);           //用[first, last)的区间构造双端队列
deque(const deque &x);                                    //双端队列的拷贝构造函数

迭代器相关

由于deque在内存上并不完全是连续的因此想要保持deque的连续性，这个任务就落到了迭代器身上。在底层实现上，deque将一段一段连续的内存称为一个缓冲区(buffer)，并将这些缓冲区的首尾地址存储在一个map中用以映射，map中一个存储缓冲区的地址对应一个结点(node)信息用于标记这个键值对，这样就构建好了基础架构。在迭代器中存储了4个信息，分别是当前结点(cur)，当前缓冲区的头(first)，当前缓冲区的尾(last)以及在map中用以标记当前缓冲区的地址的结点(node)信息。并且在deque内部已经存储好了两个迭代器start和finish用于标记deque的头和尾元素。这样即可完成将一段一段连续的空间在逻辑结构上构成一段连续空间的目的。
当从头遍历deque时，start迭代器中first和last已经从map中找到了第一个结点的缓冲区首尾信息并进行了保存，于是cur就从first开始遍历这个缓冲区，当遍历到last时就重新到map中寻找写一个结点的缓冲区收尾地址并且替换掉原来first和last值，继续遍历，这样即可完成遍历直到最后一个结点也遍历完。

iterator begin();                       //返回deque起始位置迭代器
iterator end();                         //返回deque最后一个元素下一个位置的迭代器
reverse_iterator rbegin();              //返回deque起始位置的反向迭代器(即end())
reverse_iterator rend();                //返回deque最后一个元素下一个位置的反向迭代器(begin())
const_iterator cbegin() const;          //返回deque起始位置的const迭代器
const_iterator cend() const;            //返回deque最后一个元素下一个位置的const迭代器
const_reverse_iterator crbegin() const; //返回deque起始位置的const反向迭代器(即crend())
const_reverse_iterator crend() const;   //返回deque最后一个元素下一个位置的const反向迭代器(crbegin())

容量相关

1
2
3

size_type size() const;               //返回deque中有效元素个数
bool empty() const;                   //检测deque是否为空，是返回true，否则返回false
void resize(size_type sz, T c = T()); //将deque中的元素改变到sz，多出的空间用c填充

增删改查

reference operator[](size_type n);                         //返回deque中n位置上元素的引用
const_reference operator[](size_type n) const;             //返回deque中n位置上元素的const 引用
reference front();                                         //返回deque中首元素的引用
const_reference front() const;                             //返回deque中首元素的const引用
reference back();                                          //返回deque中最后一个元素的引用
const_reference back() const;                              //返回deque中最后一个元素的const引用
void push_back(const value_type &val);                     //deque尾部插入元素val
void pop_back();                                           //删除deque尾部元素
void push_front(const value_type &val);                    //deque头部插入元素val
void pop_front();                                          //删除deque头部元素
iterator insert(iterator position, const value_type &val); //在deque的position位置插入值为val的元素
void insert(iterator position, size_type n,
            const value_type &val);                                      //在deque的position位置插入n个值为val的元素
void insert(iterator position, InputIterator first, InputIterator last); //在deque的position位置插入[first, last)区间中的元素
iterator erase(iterator position);                                       //删除deque中position位置的元素，并返回该位置的下一个位置
iterator erase(iterator first, iterator last);                           //删除deque中[first, last)区间中的元素，并返回last位置
void swap(deque & x);                                                    //交换两个deque中的内容
void clear();                                                            //将deque中的元素清空
iterator emplace(const_iterator position, Args && ... args);             //在deque的position位置构造元素，将元素所需内容通过参数类表传入
void emplace_front(Args && ... args);                                    //在deque的头部构造元素，元素的参数通过参数列表传入
void emplace_back(Args && ... args);                                     //在deque的尾部构造元素，元素的参数通过参数列表传入

综合运用

#include <iostream>
#include <deque>
using namespace std;
int main()
{
    deque<int> deq;
    deq.push_front(1);
    deq.push_back(2);
    deque<int>::iterator it = deq.begin();
    it = deq.insert(it, 0);
    while(it != deq.end())
    {
        cout << *it << endl;
        it++;
    }
    it = deq.erase(--it);
    it = deq.begin();
    while(it != deq.end())
    {
        cout << *it << endl;
        it++;
    }
}

总结

双端队列deque是一个设计并不算成功的容器，如果要随机访问单纯的查询多一点可以用vector而且更加方便，如果需要频繁插入那么list效率又会跟高，因此deque并不常用，其最常用的地方就是在作为适配器stack和queue的底层存储容器。