Deque双端队列容器

一、基本原理

    deque的元素数据采用分块的线性结构进行存储，如图所示。deque分成若干线性存储块，称为deque块。块的大小一般为512个字节，元素的数据类型所占用的字节数，决定了每个deque块可容纳的元素个数。

所有的deque块使用一个Map块进行管理，每个Map数据项记录各个deque块的首地址。Map是deque的中心部件，将先于deque块，依照deque元素的个数计算出deque块数，作为Map块的数据项数，创建出Map块。以后，每创建一个deque块，都将deque块的首地址存入Map的相应数据项中。

  在Map和deque块的结构之下，deque使用了两个迭代器M_start和M_finish，对首个deque块和末deque块进行控制访问。迭代器iterator共有4个变量域，包括M_first、M_last、M_cur和M_node。M_node存放当前deque块的Map数据项地址，M_first和M_last分别存放该deque块的首尾元素的地址（M_last实际存放的是deque块的末尾字节的地址），M_cur则存放当前访问的deque双端队列的元素地址。

二、应用

4、插入

1）deque 具有高效的头部插入元素的函数push_front()。

void push_front(const T&)

2）将在pos位置之前，插入新元素x。

iterator insert(iterator pos, const T& x)

5、删除

（1）void pop_front()    

删除deque的第一个元素。

（2）void pop_back()

删除deque的最后一个元素。         //声明一点是vector 没有pop_back();

（3）iterator erase(iterator pos)

删除pos所指向的元素。

（4）iterator erase(iterator first, iterator last)

删除迭代器区间[first,last)所指向的所有元素。

（5）void clear()

删除所有元素。

6、交换

void swap(deque&)

如d1.swap(d2);

7、其它

（1）bool empty()

判断deque容器是否已有元素，是则返回true，否则返回false。

（2）size_type size()

当前deque容器的元素个数。

（3）size_type max_size()

系统所支持的deque容器的最大元素个数。

（4）reference front()

deque容器的首元素（引用返回），要求deque不为空。

（5）reference back()

deque容器的末元素（引用返回），要求deque不为空。