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数据项地址。

STL_deque双端队列

各个类:

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().

上一篇:Java学习笔记12---向上转型-父类的对象引用指向子类对象


下一篇:iOS 10 升级后无法真机测试 Could not find Developer Disk Image