deque底层原理
- 一、目的
- 二、底层实现
- 三、原理图
- 四、类结构
- 五、push_back
- 六、pop_back
一、目的
实现双端数组
二、底层实现
双向开口的连续线性空间
三、原理图
四、类结构
-
class deque : protected Deque base
-
_Deque_base._Deque_impl
M_map 指针数组
_M_map_size _M_map的容量
_M_start 记录 map 数组中首个连续空间的信息
_M_finish 记录 map 数组中最后一个连续空间的信息
- _Deque_iterator
_M_cur 指向当前正在遍历的元素
_M_first 指向当前连续空间的首地址
_M_last 指向当前连续空间的末尾地址
_M_node 用于指向 map 数组中存储的指向连续空间的指针
- _deque buf size 连续空间中能容纳元素的个数
- _M_initialize _map
创建 map，并配置缓冲区
_M_start 和_M_finish 指向中间的位置，方便公平地往上或者向下扩展空间
五、push_back
- 当前连续空间够不够
- map 空间够不够
六、pop_back
- 删除最后一个节点，如果当前连续空间没有数据了，则释放该连续空间
推荐一个零声学院项目课，个人觉得老师讲得不错，分享给大家：
零声白金学习卡（含基础架构/高性能存储/golang云原生/音视频/Linux内核）
https://xxetb.xet.tech/s/VsFMs
