本文主要是介绍【STL源码剖析】第四章 序列式容器 之 deque底层实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
deque概述
vector是单向开口的连续线性空间,deque则是一种双向开口的连续线性空间。所谓双向开口,意思是可以在头尾两端分别做元素的插入和删除操所。vector当然也可以在头尾端进行操作(从技术观点),但是其从头部操作效率奇差,无法被接受。
deque和vector的最大差异,一在于deque允许常数时间内对起头端进行元素的插入或移除操作,二在于deque没有所谓的容量概念,因为它是动态地以分段连续空间组合而成,随时可以增加一段新的空间并链接起来。
虽然deque也提供了Ramdon Access Iterator,但它的迭代器并不是普通指针,其复杂度和vector不可以道里计,这影响了各个运算层面。因此,除非必要,应尽可能选用vector而非deque。对deque进行的排序操作,为了最高效率,可讲deque先完整复制到一个vector上,然后vector排序后,再复制到deque。
deque的中控器
deque系由一段一段的定量连续空间构成。一旦有必要在deque的前端或尾端增加新空间,便配置一段定量连续空间,串接在整个deque的头端或尾端。deque的最大任务,便是在这些分段的定量连续空间上,维护其整体连续的假象,并提供随机存取的接口。避开了“重新配置、复制、释放”的轮回,代价则是复杂的迭代器结构。
deque采用一块所谓的map(不是STL的map容器)作为主控。这里所谓map是一小块连续空间,其中每个元素(此处称为一个节点,node)都是指针,指向另一段(较大的)连续线性空间,称为缓冲区。缓冲区才是deque的储存空间主体。
template<class T, class Alloc = alloc, size_t BufSiz = 0> class deque{ public : typedef T value_type ; typedef value_type* pointer ; ... protected : //元素的指针的指针(pointer of pointer of T) typedef pointer* map_pointer ; //其实就是T** protected : map_pointer map ; //指向map,map是块连续空间,其内的每个元素 //都是一个指针(称为节点),指向一块缓冲区 size_type map_size ;//map内可容纳多少指针 ... };
deque的迭代器
deque是分段连续空间。维持”整体连续“假象的任务,落在迭代器的operator++和operator—两个运算子上。deque的迭代器首先必须能指出分段连续空间在哪里,其次它必须能够判断自己是否以及处于其所在缓冲区的边缘,如果是,一旦前进或后退时就必须跳跃至下一个或上一个缓冲区。为了能够正确跳跃,deque必须随时掌控管控中心(map)。下面这个实现符合需求:
这篇关于【STL源码剖析】第四章 序列式容器 之 deque底层实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!