在《初识STL库中deque容器》我们谈到“deque底层是中控区+缓冲区,可以理解为通过指针链接数组块”不知读者是否对这句话有印象。理解这句话,其实已经了解deque的60%了。接下来,我将为读者一一解释deque的神秘面纱。
deque分两部分,一部分是中控区,就是一个指针数组,存放着每一块内存的首地址;另一部分是缓冲区,存放着零散的小数组,所以说deque内元素可能不一定连续存储。
画一张图读者就理解了:
存储各个数组首地址的这个指针数组我们称之为map数组,当deque元素需要填充时(即头增或尾增),deque会通过创建内存——移动数据——更新存储指针来实现扩容。同理,如果map数组选哟扩容,也是需要类似操作实现“动态扩展”效果。
一般来说,只要知道map首地址就能够遍历deque内所有元素,但是为了提高性能,deque底层实际上维护了5个指针,分别是:存储位置首尾各一个,实际存储有效元素首尾各一个,一个map二级指针。它们的功能简单描述为是:首尾存储位置方便插入元素,首尾实际存储有效元素方便遍历元素,map二级指针方便管理各块数组头指针。
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程