STL_deque双端队列

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

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

deque使用了两个迭代器M_start，M_finish，对首个deque块和末deque块进行控制访问。迭代器包含4个变量域，M_first,M_last,M_cur,M_node。M_first和M_last分别指向该deque块的首尾元素地址（M_last实际指向deque块末尾字节地址，即尾后），M_cur存放当前访问的deque双端队列的元素地址，M_node存放当前deque块的Map数据项地址。

各个类：

Deque_iterator类：迭代器类，包含迭代器中四个数据项，以及迭代器的*，->操作，++，--操作等。

Deque_alloc_base类：deque块和Map块内存的创建和释放函数类，包含存放Map块的首地址，deque块数，deque块内存分配器，Map块内存分配器，以及deque，Map的分配和释放函数等。

Deque_base，继承自Deque_alloc_base类：定义了迭代器M_start，M_finish，提供了创建Map块和相关deque块的M_initialize_map函数（其中调用自己的deque块创建函数），和释放deque块函数。

M_initialize_map函数中（参数提供所有元素个数）：计算需要deque块数（至少一块）->计算Map块项数（至少8项，超过则至少头尾都预留一空项）->分配map内存->设置Map首尾项地址->调用deque块创建函数，按照Map首尾项迭代依次指向->设置迭代器的所在块和指向当前元素。

deque类，继承自Deque_base类：实现获取队首队尾元素，deque块数，是否为空，队首队尾入队出队等等。

deque应用：

创建deque对象：deque（）； deque（n）；dque（n，const T& value）;deque(const deque&);deque(first,last)

初始化赋值：push_back()

元素遍历：iterator begin();iterator end();reverse_iterator rbegin()；reverse_iterator rend（）；

元素插入：push_front(const T&), insert(iterator pos, const T&);

元素删除：pop_front(),pop_back(),erase(iterator pos);erase(first,last);clear();

deque交换：d1.swap（d2）；

其他：empty（）；size();max_size();front();back().

巴特西

STL_deque双端队列

最新文章

热门文章