deque用法 和与vector的区别（转）

使用deque之前，必须先包含头文件<deque>：#include <deque>

deque是双向开口的连续性存储空间。

虽说是连续性存储空间，但这种连续性只是表面上的，实际上它的内存是动态分配的，它在堆上分配了一块一块的动态储存区，每一块动态存储去本身是连续的，deque自身的机制把这一块一块的存储区虚拟地连在一起。

 它首次插入一个元素，默认会动态分配512字节空间，当这512字节空间用完后，它会再动态分配自己另外的512字节空间，然后虚拟地连在一起。deque的这种设计使得它具有比vector复杂得多的架构、算法和迭代器设计。它的性能损失比之vector，是几个数量级的差别。所以说，deque要慎用

与vector相比，deque功能上的不同之处在于：

1）两端都能快速插入元素和删除元素（vector只在尾端快速进行此类操作）。

2）存取元素时，deque的内部结构会多一个间接过程，所以元素的存取和迭代器的动作会稍稍慢一些。

3）迭代器需要在不同区块间跳转，所以必须是特殊的智能型指针，非一般指针。

4）在对内存区块有所限制的系统中（例如PC系统），deque可以内含更多元素，因为它使用不止一块内存。因此deque的max_size()可能更大。

5）deque不支持对容量和内存重分配时机的控制。特别要注意的是，除了头尾两端，在任何地方插入或删除元素，都将导致指向deque元素的任何指针、引用、迭代器失效。不过，deque的内存重分配优于vector，因为其内部结构显示，deque不必在内存重分配时复制所有元素。

6）deque的内存区块不再被使用时，会被释放。deque的内存大小是可缩减的。

deque的保存形式如下:
[堆1]
...
[堆2]
...
[堆3]

每个堆保存好几个元素,然后堆和堆之间有指针指向,看起来像是list和vector的结合品,不过确实也是如此
deque可以让你在前面快速地添加删除元素,或是在后面快速地添加删除元素,然后还可以有比较高的随机访问速度
vector是可以快速地在最后添加删除元素,并可以快速地访问任意元素
list是可以快速地在所有地方添加删除元素,但是只能快速地访问最开始与最后的元素

deque在开始和最后添加元素都一样快,并提供了随机访问方法,像vector一样使用[]访问任意元素,但是随机访问速度比不上vector快,因为它要内部处理堆跳转。deque也有保留空间.另外,由于deque不要求连续空间,所以可以保存的元素比vector更大,这点也要注意一下.还有就是在前面和后面添加元素时都不需要移动其它块的元素,所以性能也很高。

以下情形，最好采用deque：

1）需要在两端插入和删除元素。

2）无需引用容器内的元素。

3）要求容器释放不再使用的元素。

 

deque的各项操作只在以下几点和vector不同：

1）deque不提供容量操作（capacity()和reserve()）。

2）deque直接提供函数，用以完成头部元素的插入和删除（push_front()和pop_front()）。

 

除了at()，没有任何成员函数会检查索引或迭代器是否有效。元素的插入或删除可能导致内存重新分配，所以任何插入或删除动作都会使所有指向deque元素的指针、引用和迭代器失效。惟一例外的是在头部或尾部插入元素，操作之后，指针和引用仍然有效，但迭代器将失效。

 

deque头部元素的插入和删除

deque<int> d;

for (int index = 0; index < 10; index++)

{

d.push_front(index);

}

d.pop_front();

 

异常处理

C++标准程序库保证下列行为：

1）如果以push_back()或push_front()插入元素时发生异常，则该操作不带来任何效应。

2）pop_back()和pop_front()不会抛出任何异常。