“deque”是简写形式，其原意为“double-ended queue”。
deque模板类提供了对序列随机访问的功能，可以实现在序列两端快速插入和删除操作的功能，在需要时修改自身大小。deque型容器是典型的双端队列，可以完成标准C＋＋数据结构中队列的所有功能。
deque型容器采用动态数组来管理序列中的元素，提供随机存取，和vector具有几乎类似的接口。模板类deque最重要的特征是在deque两端高效地放置元素和删除元素，其原因在于deque型序列开放了序列的两端，即头尾均开放，可以快速地在序列两端进行快速插入和删除操作。当需要向序列两端频繁地插入或删除数据元素时，最佳的容器就是deque。
采用动态数组，deque型容器具有其优势的同时，必然存在其局限性：当在deque型序列中间插入元素时，是非常费时费力的，必须移动其他元素。
deque型容器的数据结构逻辑图如图3-23所示。
图3-23 deque型容器的数据结构逻辑图
1.deque型容器和vector型容器的对比
deque型容器和vector型容器相比，具有如下优越之处。
1）deque可以在两端迅速插入和删除元素，而vector只提供了成员函数push_back（）和pop_back（）。
2）存取元素时，deque型容器会稍慢一些。
3）deque型容器的迭代器是智能型指针。
4）在内存区块受限制的系统中，deque型容器可以包含更多元素，因为它使用了多块内存。
5）deque型容器不支持对容器和内存重分配时机的控制。
6）deque的内存区块不使用时，会被释放。
7）在序列中间插入和删除元素时，deque的速度很慢，需要移动相关的所有元素。
8）deque型容器的迭代器属于随机存取迭代器。
2.deque型容器的定义和容量
（1）deque定义
deque是动态数组，可以向两端发展。在STL库的头文件＜deque＞中定义了4种构造函数：
第一种形式构造器定义了一种空的可控序列；第二种形式构造器定义了n个相同的元素x；第三种形式构造器通过另一个deque型容器定义，实现从另一个deque型容器复制到新建容器；第四种型式构造器通过另一个容器的某范围内元素，创建新容器。
根据以上4种构造函数，可以有以下型式用于定义deque对象：
上述5种型式，第1种方法创建容纳类型T的空deque容器对象；第2种方法创建初始大小为size的deque对象；第3种方法创建初始大小为size，每个元素初始值为value的de- que容器对象；第4种方法用复制构造函数从现有的deque型容器elsedeque中创建新的de- que容器对象；第5种方法使用迭代器创建deque容器对象。
（2）容量
deque为度量数据成员数量和容器的大小，提供了以下几种方法。
resize（size_typen，Tx＝T（））：把deque容器对象的大小重新调整为n，并把对象中的新元素初始化为x。
max_size（）：返回deque容器对象中的最大允许值。
size（）：返回deque容器对象的大小，即容器中元素的个数。
例3-23
例3-23的执行效果如图3-24所示。
图3-24 例3-23的执行效果
总结
通过例3-23，读者应掌握5种deque容器对象的定义形式。
3.deque型容器的基本成员函数
（1）赋值
deque型容器提供了两个数据成员函数push_front（）和push_back（），以实现把新元素插入到deque对象中的功能。push_front（）函数用于在容器的头部插入新元素；push_back（）函数用于在容器的尾部插入新元素。同理，pop_front（）函数和pop_back（）函数分别用于获取容器的头、尾两个元素。
注：在vector型容器中，在序列最前端插入新元素的效率非常低，所以vector型容器中不包括在序列头部插入新元素的成员函数。
deque容器还提供了operator［］。其原型为：
通过赋值运算符“＝”，也可以实现对容器中元素的赋值。
例3-24
例3-24的执行效果如图3-25所示。
图3-25 例3-24的执行效果
（2）迭代器相关函数
deque型容器提供了返回deque对象的迭代器或引用的成员函数，具体分类如下：(www.xing528.com)
1）begin（）、rbegin（）、end（）和rend（）。
2）back（）和front（）。
1）类中的4个函数返回值均为迭代器/逆迭代器型；2）类中的两个函数的返回值为引用类型。
上述函数的原型为：
（3）判断迭代器是否为空
deque型容器提供了成员函数empty（）。如果容器为空，empty（）函数返回值为真。其原型为：
（4）元素的访问
deque型容器提供了用于随机访问容器中元素的成员函数at（），at（）函数的原型为：
（5）deque序列的元素值重置技术
deque型容器提供了assign（）函数。该函数可以便捷地重置deque序列中某个元素的数值。其原型为：
下面利用例3-25，对上述（2），（3），（4），（5）的内容进行说明，以帮助读者加深印象。
例3-25
例3-25的执行效果如图3-26所示。
图3-26 例3-25的执行效果
4.deque型容器的高级编程
（1）容器元素交换
deque型容器提供了成员函数swap（），用以进行两个deque变量的交换操作。通过swap（）函数可以完成两个deque变量的内容交换。其原型为：
swap（）函数即可以作为deque的成员函数来使用，还可以作为通用算法使用，两者功能是一致的。
（2）插入和删除
deque型容器提供了可实现丰富而又灵活的插入和删除元素操作功能的函数。除了deque型容器提供的push_front（）、push_back（）、pop_front（）和pop_back（）之外，insert（）函数既可以把某个元素插入到指定的位置，也可以把指定范围的多个元素插入到deque型容器中迭代器所指的位置，还可以把某个具体数值的多个副本重复插入到deque型容器中迭代器所指的位置。erase（）函数主要用来删除deque型容器中的元素。该函数既可以删除具体位置的某个元素，也可以删除指定范围内的多个元素。clear（）函数用于删除deque型容器中的所有元素。
1）insert（）函数。其原型为：
第一种原型的作用在于把某个元素插入到指定位置，返回值为被插入元素的位置；第二种原型的作用是把某个值的多个备份插入到deque容器中迭代器所指位置。
2）erase（）和clear（）。在进行deque操作时，经常需要进行元素的删除操作，包括在deque的头部、尾部和中间任何位置进行该操作。由于deque是双端队列，因此在队列的头部和尾部删除操作最简单、最高效。deque型容器提供了pop_front（）和pop_back（）两个函数，用以实现从队列的头部和尾部删除元素。成员函数erase（）比这两个函数更为灵活实用，它可以删除迭代器指向的任意单个元素或相联的多个元素。
clear（）函数可以无条件地删除容器中的所有元素，可以被erase（begin，end）所代替。
3）查找。deque型容器没有提供“查找”和“搜索”相关的函数。但使用头文件＜algorithm＞中声明的算法find（）函数，同样可以实现对deque型容器的查找。详见例3-26的中文注释。
例3-26
例3-26的执行效果如图3-27所示。
图3-27 例3-26的执行效果
5.deque的函数模板
deque模板类提供了大量函数模板，这使得deque型容器功能异常强大，同时也使编程变得异常便捷。deque容器既包括运算符函数，也包括swap（）函数（前面已介绍），此处主要介绍运算符函数。以函数模板形式实现的运算符主要包括［］、＝＝、＜、！＝、＞、＞＝和＜＝。
其中，“［］”用于访问容器中任意元素。
“＝＝”用于判断两个容器是否相等。
“＜”判断两个容器是否相同，如果前者小于后者，返回true；否则，返回false。
“！＝”判断两个容器是否不相等，如果不相等，返回true；否则，返回false。
“＜＝”用于判断两个容器是否相等，如果前者不大于后者，返回true；否则返回false。
“＞”用于判断两个容器是否相同，如果前者大于后者，返回true；否则，返回false。
“＞＝”用于判断两个容器是否相等，如果前者不小于后者，返回true；否则，返回false。
上述函数模板不受数据类型限制，顺序型容器全部提供了这些成员函数，且其使用方法也相同。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
