deque源码1(deque概述、deque中的控制器)
deque源码1(deque概述、deque中的控制器)
deque源码3(deque的构造与内存、ctor、push_back、push_front)
deque源码4(deque元素操作:pop_back、pop_front、clear、erase、insert)
deque概述
vector是单向开口的连续性线性空间,deque则是一种双开的连续性空间,即两边都可以进行插入和删除操作(vector也可进行头部的删除、插入操作,但效率很差,不被接受)。
deque和vector最大差异,一是deque允许在常数时间内对头部元素进行插入和移除操作,二在于deque没有所谓的容量的概念,因为它是动态地以分段连续空间组合而成,随时可以增加一段新的空间并链接起来。
虽然deque也提供Random Access Iterator,但它的迭代器并不是普通指针,其复杂度远高于vector,所以除非必要尽可能使用vector。为了deque排序效率最高,deuqe会先将所有的元素复制到vector中,进行排序后,再复制回deque。
deque中的控制器
deque是一段一段连续的空间构成,一旦在deque前端或尾端增加新空间,便配置一段定量连续空间,串联在头端和尾端。deque的最大任务就是将这些定量的空间,维护成连续的假象,并提供随机存储的接口,避开了“重新配置、复制、释放”的轮回,代价即是复杂的迭代器架构。
既然是分段连续的线性空间,就必须要有中央控制,而为了维持连续的假象,数据结构的设计及迭代器前进后退等操作都比较麻烦,所以deque的实现代码分量远比vector或list都多得多。
deque采用一块map(不是STL的map容器)作为主控,这里的map是一块连续空间,其中每个元素都是指针,指向另一段连续线性空间,称为缓冲区。缓冲区才是deque的存储空间主体。
template <class T,class Alloc=alloc,size_t BufSiz=>
class deque{
public:
typedef T value_type;
typedef value_type* pointer;
...
protected:
typedef pointer* map_pointer;
protected:
map_pointer map; //指向map,map是连续空间,其内的每个元素都是一个指针,指向一块缓冲区
size_type map_size; //map可容纳多少指针
...
};从上面可以看出,map其实是一个T**,也就是说它是一个指针,所指向另一个指针,指向型别为T的一块空间。具体如下图:
最新文章
- 就publish/subscribe功能看redis集群模式下的队列技术(一)
- javascript中的自增与自减
- 去除inline-block之间的间隙
- arguments .length .callee caller
- WebApi2 jsonp跨域问题
- 《Maven_孔浩》Maven命令
- centos6.5搭建vpn服务器
- 关于kali安装vmware的坑,linux套路太深。
- 【转】java中byte, int的转换, byte String转换
- iOS10收集IDFA,植入第三方广告[终结]--ADMob
- s3c2440的GPIO驱动
- Android中的java层的线程暂停和恢复实现
- C# TryParse()用法
- (原)怎样解决python dataframe loc,iloc循环处理速度很慢的问题
- poj 2345 Central heating
- 流行的报表生成工具-JXLS
- Jquery常用的一些事件 keyup focus
- css细节:尖角处理
- SQL Server中灾难时备份结尾日志(Tail of log)的两种方法
- Angularjs集成第三方js插件之Uploadify