博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
STL~Deque简介
阅读量:7215 次
发布时间:2019-06-29

本文共 1139 字,大约阅读时间需要 3 分钟。

deque简介

    deque是双向开口的连续性存储空间。虽说是连续性存储空间,但这种连续性只是表面上的,实际上它的内存是动态分配的,它在堆上分配了一块一块的动态储存区,每一块动态存储去本身是连续的,deque自身的机制把这一块一块的存储区虚拟地连在一起。

    它首次插入一个元素,默认会动态分配512字节空间,当这512字节空间用完后,它会再动态分配自己另外的512字节空间,然后虚拟地连在一起。deque的这种设计使得它具有比vector复杂得多的架构、算法和迭代器设计。它的性能损失比之vector,是几个数量级的差别。所以说,deque要慎用。

 

deque数据结构

    deque是连续线性空间。但这种连续不同于数组和vector的连续,deque只是逻辑上的连续空间,它把一块一块独立的空间逻辑地连在一起,仿佛整个deque空间是一块完整的连续空间,让我们来看一下deque的数据结构,了解deque是怎么做到这一点的。

    我们发现这里有一个_Map成员变量。大家注意,这可不是STL中的map。这个_Map是一个指针,指向一块特殊的内存地址,这里保存着指向deque动态申请的所有512字节内存空间的首地址。deque先用一段小的连续空间顺序存放了一个一个指针,然后这些顺序存放的指针再各自指向用来真正存放数据的512字节连续性空间。当_Map指向的这块空间不够存放内存指针的时候,就会另觅一块更大的连续性空间,然后把指针一个一个复制过去,并销毁旧的空间。利用这种数据结构,deque就能方便地模拟自身的存储区是连续性空间的假象,并且可以实现双向插入删除的功能。deque没有vector所谓的容量的概念。我们看一下deque的数据结构图,如图1所示。

    deque通过一套复杂的机制实现了双向开口的连续性空间,增加了编程灵活性,但是也降低了效率。所以一定要慎用deque。

 

stack和queue

    用于STL中的stack和queue都是建立在deque数据结构基础上的,所以我们再来看看stack和queue。

 栈stack

    它是一种先进后出(First In Last Out)的数据结构。因为stack不允许对容器的遍历操作,所以stack没有迭代器。只能通过压栈和出栈的办法存取stack中的元素。

队列

    它是一种先进先出(First In First Out)的数据结构。因为queue不允许容器的遍历操作,所以queue没有迭代器,只能通过queue的最顶端和最低端操作数据。

posted on
2017-05-17 14:09 阅读(
...) 评论(
...)

转载于:https://www.cnblogs.com/sanghai/p/6867292.html

你可能感兴趣的文章
Java/Android基础-02
查看>>
nginx代理响应报文体不全解决思路
查看>>
前端性能优化 —— 项目瘦身
查看>>
全球人形机器人接连突破 拟人度越来越高
查看>>
vue按需加载
查看>>
创成汇2019年参加创新创业大赛都能获得什么?
查看>>
vue双向数据绑定原理
查看>>
美研究最新生物活性玻璃 可消灭致命的细菌
查看>>
内部类
查看>>
Vue中数组赋值问题
查看>>
APK path is not specified for module
查看>>
Linux运维宝典:最常用的150个命令汇总
查看>>
使用RecycleView实现无限滚动的日历
查看>>
Golang Failpoint 的设计与实现
查看>>
小微贷是美团的上坡之路?
查看>>
js 将线性数据转为树形
查看>>
java B2B2C 源码 多级分销Springcloud多租户电子商城系统- 整合企业架构的技术点(二)...
查看>>
微信小程序
查看>>
区块链+金融
查看>>
阿里开发者招聘节 | 面试题14:如何实现两金额数据相加(最多小数点两位)...
查看>>