文山网站建设,交互界面设计,小程序游戏制作,正规的建网站公司C 浅谈之 STL Deque
HELLO#xff0c;各位博友好#xff0c;我是阿呆 #x1f648;#x1f648;#x1f648;
这里是 C 浅谈系列#xff0c;收录在专栏 C 语言中 #x1f61c;#x1f61c;#x1f61c;
本系列阿呆将记录一些 C 语言重要的语法特性 #x1f3c3; 浅谈之 STL Deque
HELLO各位博友好我是阿呆
这里是 C 浅谈系列收录在专栏 C 语言中
本系列阿呆将记录一些 C 语言重要的语法特性
OK兄弟们废话不多直接开冲 一 概述
简单介绍
Deque 双端队列在头尾对元素进行删除和插入快中间插入或删除效率低支持元素随机访问。它是动态分段连续空间组合而成无 capacity 概念可即时增加新空间不会像 vector 因旧空间不足而重新申请 和 Vector 维护连续线性空间不同Deque 维护多段连续空间各段间不一定连续Deque 用数组名为 map存储着各连续空间首地址 迭代器
分段存储提高了两端添加删除的效率也使容器迭代器实现更复杂有如下 2 个问题
① 迭代器遍历时须确认各连续空间在 map 数组中的位置
② 迭代器在某个连续空间时须知道是否处于空间边缘一旦前进需要跳到下一个连续空间
//迭代器内部实现如上包含 4 个指针
templateclass T,...
struct __deque_iterator{...T* cur; //指向当前正在遍历的元素T* first; //指向当前连续空间的首地址T* last; //指向当前连续空间的末尾地址map_pointer node; //T** 二级指针, 指向 map 数组中存储的指向当前连续空间的指针
}借助这四个指针和运算符重载使迭代器可以在分段连续空间遍历
//当迭代器处于当前连续空间边缘的位置时如果继续遍历就需要跳跃到其它的连续空间中该函数可用来实现此功能
void set_node(map_pointer new_node){node new_node;//记录新的连续空间在 map 数组中的位置first *new_node; //更新 first 指针//更新 last 指针difference_type(buffer_size())表示每段连续空间的长度last first difference_type(buffer_size());
}//重载 * 运算符
reference operator*() const{return *cur;}
pointer operator-() const{return (operator *());}//重载前置 运算符
self operator(){cur;//处理 cur 处于连续空间边缘的特殊情况if(cur last){//调用该函数将迭代器跳跃到下一个连续空间中set_node(node1);//对 cur 重新赋值cur first;}return *this;
}//重置前置 -- 运算符
self operator--(){//如果 cur 位于连续空间边缘则先将迭代器跳跃到前一个连续空间中if(cur first){set_node(node-1);cur last;}--cur;return *this;
}二 核心
底层实现
STL Deque 有如下的定义代码
//_Alloc为内存分配器
templateclass _Ty,class _Alloc allocator_Ty
class deque{...
protected:iterator start; // map 数组中首个连续空间的信息iterator finish; //map 数组中最后一个连续空间的信息map_pointer map;
...
}内部空间布局如下图所示 三 结语
身处于这个浮躁的社会却有耐心看到这里你一定是个很厉害的人吧
各位博友觉得文章有帮助的话别忘了点赞 关注哦你们的鼓励就是我最大的动力
博主还会不断更新更优质的内容加油吧技术人
