STL中的队列（一）

双端队列（double-ended queue)

deque是一种双向开口的连续线性空间，允许在队列的两端进行操作（插入和删除）。

deque和vector的区别：

deque与vector非常相似。它也采用动态数组管理元素，提供随机存取，有着和vector几乎一样的接口。不同的是deque的动态数组头尾都开放，因此能在头尾两端进行快速安插和删除。

1）deque是动态地以分段连续空间组合而成，随时可以增加一端新的空间并链接起来。迭代器需要在不同区块间跳转，(迭代器属于random access iterator（随机存取迭代器）)，所以它非一般指针，这会影响运算层面。而vector必须使用一块连续内存，所以不像vector那样“因旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”。deque的max_size()可能更大。

2）元素的存取和迭代器的动作比vector稍慢。因此，尽可能选择使用vector而非deque。这里，对deque进行排序操作，如果为了提高效率，可将deque先完整复制到一个vector，然后对vector排序，再复制回vector。

3）不支持对容量和内存重新分配时机的控制。不过deque的内存重分配优于vector，因为其内部结构显示，deque不必在内存重分配时复制所有元素。

deque的中控器

在底层，deque按“页”（page）或“块”（chunk）来分配存储器，每页包含固定数目的元素，（定量连续空间）一旦有必要在deque的前端或尾端增加新空间，便配置一段定量连续空间，串接在整个deque的头端或尾端。deque的最大任务就是在这些分段的定量连续空间上，维护其整体连续的假像，并提供随机存取的接口。

例如，一个10M字节的vector使用的是一整块10M字节的内存，而deque可以使用一串更小的内存块，比如10块1M的内存。所以不能将deque的地址（如&deque[0]）传递给传统的C API，因为deque内部所使用的内存不一定会连续。

中央控制

deque采用一块所谓的map(区别于STL的map容器）作为主控。这里的map是一小段连续空间，其中每个元素都是指针（node），指向另一端（较大的）连续线性空间，即缓冲区。默认值为0表示将使用512bytes的缓冲区。