C++中的标准容器类 deque 双端队列使用实例剖析

C++中的标准容器 deque（发音像 deck）是双端队列（double-ended queue）的缩写，本质上是队列容器，修饰词“双端”说明它可以在两端进行扩展或者收缩。

deque 容器类的特点

就单单 deque 来说，它的实现方式有很多种，其用途也会因实现方式的差异略有不同。不过，C++通常是将其作为某种形式的动态数组，对于 C++中的 deque，我们可以通过迭代器直接访问 deque 容器中存储的各个元素，并且根据需要在其两端进行任意的扩展和收缩。

C++中 deque 容器提供的功能有些类似于向量（vector，后面会说），但是 deque 既支持将元素插入容器的头部，也支持将元素插入容器的尾部，而向量容器则只能将新元素插入尾部，请看下面这几行C++代码：

#include <vector>
#include <deque>

using namespace std;

int main()
{
    vector<int>       v;
    deque<int>        d;

    d.push_back(1);
    d.push_front(2);

    v.push_back(1);
    v.push_front(2);    // 非法

    return 0;
}

另外需要说明的是，deque 容器不能保证内部元素存储在相邻的位置，也就是说 deque 容器内的元素在内存中的地址可能不是连续的，这一点和普通的链表相似——链表中的各个节点常常并不在内存中连续分布。因此，deque 容器不能提供高效的随机访问。

C++ 中的 deque 容器类与向量 vector 容器类的接口非常相似，但是二者在内部的工作方式截然不同。vector 内部使用类似于数组的一整块连续内存，因此它可以高效的随机访问各个元素。但是，一旦添加的元素超出预先分配的内存长度，那么 vector 将不得不重新分配一块更大的连续内存，并将现有数据拷贝到该新连续内存段，再执行接下来的添加操作。

deque 就不同了，它内部的元素并不需要在地址上相邻，因此各个元素可以分散在不同的存储块中，容器内部保留必要的信息，以便能够在恒定时间内按照统一的顺序访问任何元素。deque 内部管理元素的方式比 vector 复杂一些，但是着允许它在某些情况下更有效的增长，特别适合处理非常长的序列。

deque 容器类的成员函数及其实例

我不打算详细介绍和讨论枯燥的函数原型及其说明，相关资料科自行查阅文档，这里仅通过实例直观的介绍各个成员函数的使用。

deque 的迭代器

deque 是一个容器类，其中可以存放若干个元素，若要逐个访问其中的元素，则可以通过迭代器函数，其中最常用的有以下几个函数：

begin，返回迭代器的起点
end，返回迭代器的终点
rbegin，返回反迭代器的反起点
rend，返回反迭代器的反终点

下面是使用 begin() 和 end() 函数遍历 deque 容器类元素的 C++ 代码示例，请看：

其实从这里可以看出，所谓的迭代器“it”，其实更像是一个指向 deque 内元素的指针，我们可以通过对其执行自加操作，让它指向下一个元素，以此遍历所有元素。编译并执行上述C++代码，得到如下输出：

mydeque contains: 1 2 3 4 5

可见，mydeque 内部的元素按照插入顺序遍历出来了。当然，我们也可以使用 rbegin() 和 rend() 函数倒序操作 deque 容器，下面是一段C++代码示例，请看：

上述C++代码先使用 rbegin() 和 rend() 函数倒序访问 mydeque 容器元素并赋值，然后顺序遍历打印，最终得到的输出为：

mydeque contains: 5 4 3 2 1

deque 的容量

容器究竟存放多少元素，也是一个非常重要的问题，因此 deque 类提供了下面几个常用的函数用于检查和设置容器的容量：

size，返回容量
max_size，返回最大容量
resize，修改容量
empty，检查容器是否为空

size() 函数返回容器内部存放的元素数目，empty() 函数返回容器内是否有元素，这没什么说的。那 max_size() 函数是什么意思呢？它有什么用呢？请看下面这段C++代码示例：

这段C++程序允许用户输入一个整数，并将其中的 mydeque 容器容量设置（resize）为该整数大小。当然了，在设置大小之前，需要检查用户输入的整数是否超出了容器的最大容量。

仔细想想，deque 容器内的各个元素在内存中可以分散分布，因此在内存被使用完毕之前，deque 永远都不会满。也就是说，deque 的 max_size() 是非常大的，这与C++程序运行的机器内存和单个元素大小有关。

感兴趣的读者可以将本例中的 max_size() 的值打印出来，应该能够发现它是一个非常非常大的值。

resize() 函数可以设置 deque 容器的容量，这意味着它既可以压缩 deque 容器，也可以拉伸 deque 容器。若是使用 resize() 函数拉伸了 deque 容器，那么就会多出一部分空间， resize() 函数还可以为这部分多出的空间设置默认值，请看下面这段C++代码示例：

程序首先往 mydeque 容器中添加了 9 个连续的数字，然后使用 resize() 函数将容器容量压缩到 5，接着又将容量拉伸值 8，并且将多出的 3 个位置赋值为 100，最后将 mydeque 容器容量拉伸值 12，因此上述C++程序的最终输出结果为：

mydeque contains: 1 2 3 4 5 100 100 100 0 0 0 0

最后多出的 4 个空闲位置元素为 0，是因为 resize(12) 没有显式的指定初值，因此这几个位置被赋为默认的 0 了。

访问 deque 容器的元素

以下几个函数是 deque 类提供的常用的访问容器内元素的函数，请看：

operator[]，访问元素
at，访问元素
front，访问第一个元素
back，访问最后一个元素

这几个函数非常简单，相关的C++代码示例如下，请看：

编译并执行这段C++代码示例，得到如下输出：

mydeque[3] = 4
mydeque.at(4) = 5
mydeque.front() = 1
mydeque.back() = 9

deque 的其他函数

为了便于使用，deque 容器类还提供了其他的函数，比较常用的有下面这几个：

assign，赋值
push_back，将元素添加到容器尾部
push_front，将元素添加到容器头部
pop_back，删除最后一个元素
pop_front，删除第一个元素
insert，插入元素
erase，擦除元素
swap，交换
clear，清除

assign() 函数可以实现类似于“拷贝”的操作，也可以实现类似于“resize”的操作，下面是C++代码示例，请看：

若 assign() 函数的第一个参数为整数（n），则表示将该 deque 容器的容量设置为 n，我们也可以在第二个参数为其制定默认值。assign() 也可以通过迭代器将一个 deque 中的元素拷贝给另外一个 deque，例如上面的C++代码，second 容器类拷贝了由 it 索引的 first 容器类中的第二个元素到倒数第二个元素（第一个和最后一个元素没有拷贝，因此 second 容器容量比 first 容器容量小 2）。编译并执行这段C++代码，得到如下输出，请看：

Size of first: 7
Size of second: 5
Size of third: 3

前面的例子中几乎都用到了 push_back() 函数，它可以将元素插入到 deque 的尾部，与之对应的，pop_back() 函数则可以将 deque 尾部的元素删除。下面是C++代码示例，请看：

之所以可以使用 mydeque.empty() 决定 while() 循环条件，是因为C++程序在使用完容器尾部元素之后，调用了 pop_back() 将之删除了。编译并执行这段代码，得到如下输出：

The elements of mydeque add up to 60

push_front() 和 pop_front() 也可使用类似于上面这样的C++代码示例，唯一不同的是它们操作的是容器的头部元素——即 push_front() 将元素插入容器头部，pop_front() 将容器的头部元素删除。

erase() 函数则可以从 deque 容器中擦除指定的元素，究竟擦除哪一个元素则由 erase() 的参数决定，通常 erase() 接收一个迭代器指针。请看下面这段C++代码示例：

从代码中可见，erase() 函数可以接收一个迭代器指针删除单个元素，也可以接收两个迭代器指针表示的区间，删除区间内的元素。编译并执行这段C++代码，得到如下输出：

mydeque contains: 4 5 7 8 9 10

swap() 函数则提供了交换功能，使用它可以交换两个 deque 容器内的内容，下面这段C++代码示例很好的说明了这一点，请看：

编译并执行这段C++代码，得到如下输出，可见 foo 和 bar 容器的内容被交换了：

foo contains: 200 200 200 200 200 
bar contains: 100 100 100

小结

本文主要通过一系列C++代码示例讨论了标准容器类 deque 的使用，文中的例子都是以 deque<int> 作为示范的，应该明白 deque 本身是一个模版容器类，因此它可以存储任意类型的数据，例如 deque<float>，deque<struct s>，deque<myclass c>，deque<deque<int>> 等等。