游戏是怎么做的视频网站,网站开发维护成本,wordpress 视频边栏,手机大全及价格deque原理介绍 deque(双端队列)#xff1a;是一种双开口的连续空间的数据结构#xff0c;双开口的含义是#xff1a;可以在头尾两端进行插入和删除操作#xff0c;且时间复杂度为O(1)。 与vector比较#xff0c;头插效率高#xff0c;不需要搬移元素#xf…deque原理介绍 deque(双端队列)是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1)。 与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高。 deque并不是真正连续的空间而是由一段段连续的小空间拼接而成的实际deque类似于一个动态的二维数组其底层结构如下图所示 双端队列底层是一段假象的连续空间实际是分段连续的。 为了表面看起来上连续的我们就需要迭代器来封装底层。 deque迭代器 成员函数中有两个迭代器start finish中控数组map存储空间的起始地址 而迭代器中有3个一级指针和1个二级指针node(用来找中控数组map中下一段内存空间的地址) 1.start finish迭代器中的first last都是指向这段连续小区间的起始和末尾。 2.start的cur是指向第一个元素而finish的cur是指向最后一个元素后面的位置。 可以看到deque可以支持vector的[]下标的随机访问链表的头删 头插。 1.push_back尾插。 如果最后一段区间没满直接插入就行。反之就需要重新开辟一块空间并在map中记录起始地址再插入。 2.push_front头插 头插的话也要开辟一块空间但数据的存入顺序是在这一段空间的末尾倒着存入。 3.[]随机访问 虽然deque的底层空间并不是完全连续的但每次开辟的空间buff大小是确定的。 对要访问的下标先除buff空间大小找到在第几个buff上再取余找到在buff上的第几个元素。 我们知道头插数据是倒着存入的如果第一段空间没有满又改怎么办呢 我们可以假设第一段空间满了让要访问的下标加上第一段空间空的元素个数cur-first。 4.迭代器遍历 当curlast时说明当前buff数组已经遍历结束set_node(node1)根据map数组找到下一段空间的起始位置。first*new_node new_node是二级指针解引用就是空间的起始地址。 vector list deque优劣势 vector 优势1.尾删/插效率高 2.支持随机访问 3.顺序表CPU高速缓存命中率更高物理地址是连续的 劣势 1.头或中间删/插效率低 2.空间利用效率不高 3.扩容费时间还可能存在空间的浪费。 list 优势1.插入删除效率高 2.按需申请空间避免空间的浪费。 劣势1.不支持随机访问。 2.CPU高速缓存命中率低物理地址是不连续的 deque 优势1.对比vector头插效率更高 2.对比list可以随机访问 劣势1.虽然可以随机访问但效率是不如vector毕竟空间不是完全连续的。 可以少量访问像排序遍历还是用vector好 2.在中间插入删除还是需要移动数据的。
