Deque双端队列容器
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双端队列的元素地址。
二、应用
1、创建
(1)deque()
创建一个没有任何元素的deque对象。此构造函数的更一般形式是“deque(const A& a = A())”,A是一个内存分配器,可缺省。如deque<int> d;
(2)deque(size_type n)
创建一个具有n个元素的deque对象,每个元素采用它的类型下的默认值。deque<int> d(10); //默认值为0
(3)deque(size_type n, const T& value)
创建一个具有n个元素的deque对象,这些元素的初始值为value。
(4)deque(const deque&)
deque的拷贝构造函数,通过拷贝一个deque对象的元素值,创建一个新的deque对象。此时,新旧deque对象具有相同块数的deque块,各自内部的元素也对应相等。
deque<char> d1(5,'k');
deque<char> d2(d1);
(5)deque(const InputIterator first, const InputIterator last, const A& a=A())
将迭代器区间[first,last)所指的元素拷贝到一个新创建的deque对象中,其中内存分配器可缺省。
//利用int数组iArray,创建了一个deque对象d
int iArray [] = {11, 13, 19, 23, 27};
deque<int> d(iArray, iArray + 5);
2、初始化
利用deque提供的push_back()函数,可在尾部压入新元素value,常用作deque容器的初始化赋值。
3、访问
deque的元素同样可采用数组和迭代器方式进行访问,用“d[i]”取得deque对象d的第i个元素(0≤i<d.size()),或用迭代器i的“*”操作“*i”取得i所指向的元素。
(1)iterator begin()
(2)iterator end()
可反向遍历deque双端队列中元素迭代器:
(1)reverse_iterator rbegin()
(2)reverse_iterator rend()
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的最后一个元素。
(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不为空。