C++ deque底层原理

一、目的

实现双端数组

二、底层实现

双向开口的连续线性空间

三、原理图

四、类结构

• 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