deque与priority_queue：底层原理、接口分析与模拟实现

本文代码已同步Github一、deque的简单介绍1、deque的特点deque全称是double-ended queue也叫双端队列。它是一种序列式容器最大的特点是可以在头部和尾部高效地插入、删除元素。和vector相比vector适合尾插尾删但头插头删效率较低deque头尾插入、删除效率都较高和list相比list不支持随机访问deque支持随机访问比如dq[i]不过deque并不是真正连续的一整块空间而是由多段连续的小空间组成整体上通过迭代器维护成“看起来连续”的结构。那么如果deque真的既有vector的优点同时还有list的优点那么我们数据结构直接学习deque就好了为什么还要学习vector和list呢难道deque没有缺点下面我们便来介绍一下deque的底层通过底层我们再来分析deque的优缺点2、deque的底层原理我们先来思考一下vector的优点是1、尾插尾删效率不错支持高效下标随机访问2、物理空间连续所以高速缓存利用率高vector的缺点是1、需要扩容扩容有代价2、头部和中间插入删除效率低接着来看listlist的优点是1、按需申请释放空间不需要扩容2、任意位置插入删除list的缺点是1、不支持下标随机访问deque既然想同时拥有两者的优点那就需要在底层设计上下功夫vector只是顺序存储而list是链式存储我们来看deque的结构核心结构就是中控数组缓冲区中控数组里面存放的是指针每个指针指向一段连续的小空间每个指针指向的就是缓冲区缓冲区内部是连续的用来真正存放数据我们通过一张图来理解显然deque是一段假想的连续空间实际是多段连续小空间组成这样的结构用什么来维护呢普通的下标直接访问当然无法满足要求答案就是迭代器来维护通常一个迭代器需要维护四个信息T*_cur;// 当前元素位置T*_first;// 当前缓冲区的起始位置T*_last;// 当前缓冲区的结束位置T**_node;// 当前缓冲区在中控数组中的位置迭代器移动时如果当前缓冲区没有越界直接移动_cur如果_cur到达缓冲区边界就通过_node找到下一个缓冲区然后更新_first、_last和_cur因此迭代器不仅要记录当前元素还要知道当前元素属于哪一段缓冲区以及如何切换到下一段我们通过一张图来理解注意⚠️对于deque实际上第一次插入数据会将指针存放在中控数组的中间位置而不是第一个位置3、核心接口逻辑分析那么deque是怎样借助迭代器来维护呢是通过两个迭代器start和finish start和finish是两个 deque 迭代器分别描述有效数据的起始位置和尾后位置。下面我们来分析一下核心接口的实现逻辑1、对于push_back首先会找到finish的cur此时cur指向的是尾后位置判断curlast如果相等则需要重新开一个buff并更新finish然后进行插入如果不相等则直接在cur位置插入即可之后更新迭代器时间复杂度为O(1)2、对于pop_back首先找到finish的cur如果删除之后当前buff已经没有有效元素就需要释放buff否则就直接--cur即可时间复杂度为O(1)3、对于push_front首先找到start的cur此时cur指向的是第一个有效元素的位置如果curfirst需要新开一个buff并更新start然后再进行插入否则就直接--cur,然后在cur位置插入4、对于pop_front首先找到start的cur此时cur指向的是第一个有效元素的位置如果删除之后当前buff为空需要释放buff同时将start指向下一个buff否则就直接cur时间复杂度为O(1)5、对于operator[]:deque 支持随机访问但由于底层不是一整块连续空间因此不能像 vector 那样直接通过首地址 index 访问;它需要根据 index 计算目标元素位于哪个 buffer以及在该 buffer 中的具体位置:注意⚠️:计算时要以 start.cur 作为起点而不是简单地从某个 buffer 的 first 位置开始。下面来看insert和erase6、对于insert传入的参数是迭代器pos在pos前插入元素插入元素后为了保持元素顺序需要移动一部分元素如果移动过程中超出当前缓冲区边界则可能涉及其他缓冲区时间复杂度为线性级别最差为O(N)7、对于erase无论传入的参数是迭代器还是迭代器区间都需要挪动数据进行覆盖删除时间复杂度为线性级别最差为O(N)4、deque的缺陷与vector相比deque的优势是头插和头删时不需要挪动数据效率很高在扩容时也不需要挪动大量数据与list相比底层是分段连续空间可以用[]来访问空间利用率高但是deque同样不能够大量的调用insert和erase这两个接口效率不高deque 的明显缺点遍历效率通常不如 vectordeque 的遍历效率相较于 vector 会低一些因为 vector 底层是一整块连续空间迭代器移动时基本就是指针后移而 deque 底层是分段连续空间迭代器在移动时需要判断是否到达当前 buff 的边界必要时还要切换到下一个 buff因此当需要线性结构时大多数情况下优先考虑vector和list5、为什么stack和queue默认使用dequestack是一种后进先出的特殊线性数据结构因此只要具有push_back()和pop_back()操作的线性结构都可以作为stack的底层容器比如vector和listqueue是先进先出的特殊线性数据结构只要具有push_back()和pop_front()操作的线性结构都可以作为queue的底层容器比如list但是STL中对stack和queue默认选择deque作为其底层容器主要是因为stack和queue不需要遍历(因此stack和queue没有迭代器)只需要在固定的一端或者两端进行操作。对于stack来说deque比vector的效率高尾插尾删都是O(1)但deque扩容时不需要搬移大量数据对于queue来说deque头删和尾插均为O(1)相较于list不需要为每个节点额外维护指针而且内存使用率高综上deque在作为stack和queue的底层容器时既满足了头尾操作的需求又避开了自身不适合高效遍历的缺点。二、priority_queue的介绍与使用1、priority_queue的特点首先我们先给出priority_queue的文档priority_queue使用文档接着我们来了解一下priority_queuepriority_queue是 C STL 中的容器适配器本质上是堆Heap数据结构;它的核心特点是优先级最高的元素总是位于队首即top()而出队顺序与入队顺序无关只与优先级大小有关。对于堆我们在前面的数据结构中已经学习过当时采用的是动态数组作为底层容器传送门数据结构堆详解原理、实现与应用、和stack,queue一样都是容器适配器那么对于堆而言数组就是很好的容器通过对数组进行包装使其在逻辑结构上是一颗完全二叉树2、priority_queue的核心接口整理出核心接口函数声明接口说明priority_queue()/priority_queue(first, last)构造一个空的优先级队列empty()检测优先级队列是否为空是返回true否则返回falsetop()返回优先级队列中最大或最小元素即堆顶元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大或最小元素即堆顶元素对于这些接口我们都是在熟悉不过了简单来测试一下3、大堆与小堆注意⚠️在默认情况下priority_queue是大根堆怎样换成小根堆呢我们仔细来看其模板参数有三个模板参数第一个是参数类型T第二个是底层容器默认是vector第三个是一个仿函数什么是仿函数呢仿函数Functor是 C 中一种行为类似函数的对象它的本质是一个重载了函数调用运算符 operator() 的类或结构体因此该类的实例可以像普通函数一样被调用。本质上就是一个类里面没有成员变量重载了比较函数怎么调用呢创建对象后使用**对象名参数**的语法和函数调用完全一致我们先来实现一个默认的Less以及Greater仿函数templateclassTclassLess{public:booloperator()(constTx,constTy){returnxy;}};templateclassTclassGreater{public:booloperator()(constTx,constTy){returnxy;}};我们来测试一下三、priority_queue的模拟实现1、底层结构分析我们来看文档中对于优先级队列底层容器的要求要求是随机迭代器高效的上述接口首先想到的就是vector完美符合上述要求还有一个容器同样符合要求就是dequedeque同样也是随机迭代器尾插尾删也是O(1)级别那为什么库里面选择了vector作为底层容器呢priority_queue不需要deque的头部O(1)操作vector就能满足要求堆算法涉及大量的随机下标访问vector效率更高vector的开销极小而deque还需要中控数组map来维护因此选择vector是最划算的选择下面来完成基础的框架搭建//priority_queue.h#includevectortemplateclassTclassLess{public:booloperator()(constTx,constTy){returnxy;}};templateclassTclassGreater{public:booloperator()(constTx,constTy){returnxy;}};namespacestl{templateclassT,classContainerstd::vectorT,classCompareLessTclasspriority_queue{private:Container _con;Compare _cmp;public:};}2、插入元素向上调整其实就是前面数据结构中的堆的向上调整算法我们封装一个函数即可voidAdjustUp(size_t child){size_t parent(child-1)/2;while(child0){//Less:父节点 孩子节点 - 大根堆//Greater:父节点 孩子节点 - 小根堆if(_cmp(_con[parent],_con[child])){std::swap(_con[parent],_con[child]);childparent;parent(child-1)/2;}elsebreak;}}3、删除堆顶向下调整也就是堆的向下调整算法voidAdjustDown(size_t parent){size_t childparent*21;while(child_con.size()){if(child1_con.size()_cmp(_con[child],_con[child1]))child;//Less:父节点 孩子节点 - 大根堆//Greater:父节点 孩子节点 - 小根堆if(_cmp(_con[parent],_con[child])){std::swap(_con[parent],_con[child]);parentchild;childparent*21;}elsebreak;}}4、核心接口实现由于是适配器模式因此是直接在底层容器基础上保留特定场景的接口即可voidpush(constTx){_con.push_back(x);AdjustUp(_con.size()-1);}voidpop(){std::swap(_con[0],_con[_con.size()-1]);_con.pop_back();AdjustDown(0);}Ttop(){return_con.front();}constTtop()const{return_con.front();}constsize_tsize()const{return_con.size();}boolempty()const{return_con.empty();}接着来测试一下五、总结通过这两篇文章我们学习了deque、stack、queue以及priority_queue。对于deque我们不仅学习了它的基本接口更重要的是理解了它的底层设计deque通过中控数组 多段缓冲区的方式在保证随机访问能力的同时实现了高效的头尾插入和删除但是这种分段存储的结构也带来了额外的迭代器维护开销因此deque虽然功能比较全面却并不是一种适合大量遍历的容器。进一步我们理解了为什么stack和queue默认使用deque作为底层容器stack和queue本质上都是容器适配器它们并没有重新设计一套底层数据结构而是在已有容器的基础上保留自己需要的接口deque恰好能够很好地满足它们对于头尾操作的需求同时又不需要使用自身不擅长的遍历功能。对于priority_queue我们进一步接触了 STL 中的另一种容器适配器它本质上是对堆进行封装通过底层容器存储数据并利用堆的向上调整和向下调整来维护优先级关系同时通过仿函数可以灵活地改变元素之间的比较规则从而实现大根堆和小根堆。最后通过模拟实现priority_queue我们也能够更加直观地理解 STL 容器适配器的设计思想底层容器负责数据的存储适配器负责限制和组织接口而具体的数据结构算法则负责实现对应的功能。从stack、queue到priority_queue它们看似是不同的容器实际上都建立在已有数据结构之上理解这一点之后我们在学习 STL 时就不应该只停留在“记住接口怎么用”而应该进一步思考这个容器底层是什么为什么选择它接口又是如何利用底层结构实现的这也是学习 STL 和数据结构过程中非常重要的一种思维方式。如果觉得有帮助可以关注Github项目持续更新