【C++初阶】第14课—缝合怪deque和优先队列、仿函数

文章目录

1. 双端队列deque
- 1.1 认识deque
- 1.2 deque的迭代器
- 1.3 deque的常用接口
- 1.4 deque的优缺点
2. 优先队列priority_queue
- 2.1 认识priority_queue
- 2.2 模拟实现优先队列priority_queue
3. 仿函数

在学习deque之前，回顾一下vector和list各自的优缺点

数据结构	优点	缺点
vector	支持下标随机访问	中间或头部插入删除效率低/扩容有一定的消耗，可能存在空间的浪费
list	支持任意位置的插入删除/按需扩容或释放，不存在空间浪费	不支持随机访问

1. 双端队列deque

1.1 认识deque

前面学过了vector和list，不过两个容器各有各的优点，后来就衍生出集合两者优点的deque
由于deque只是简单的将两者的优点结合，因此它也被称为缝合怪

在这里插入图片描述

deque是一种双开口的“连续”空间的数据结构，但从物理结构上将，其实它只是一段一段连续的物理空间片段拼接而成的，并非整段都是连续的

在这里插入图片描述

1.2 deque的迭代器

想要理解deque的结构，重中之重就要了解它的迭代器是如何作用的

在这里插入图片描述

deque整个的工作原理

在这里插入图片描述

有了以上理解后，如果deque尾插元素时，判断first等不等于end(),等于说明该buffer数组满了，需要扩容，然后finish迭代器的cur和first指向下个buffer数组的首元素位置，last指向下个buffer数组的尾元素下个位置，此时node也得更新，它得指向map有效元素的下个位置，map满了的话也得扩容，这样就避免了插入元素时需要频繁扩容的困扰

需要注意的是deque的头插

在这里插入图片描述

deque的下标随机访问

在这里插入图片描述

1.3 deque的常用接口

在这里插入图片描述

1.4 deque的优缺点

	优点	缺点
deque	头部插入删除数据时，与vector相比，不需要额外移动数据；扩容时，不需要开辟大量的空间；与list相比，deque底层空间是"连续"的，空间的利用率比较高	不适用与遍历，因为它遍历时需要通过迭代器频繁检查每个buffer数组的边界，效率低下

因此deque通常不会去使用它，除非在某些特定的场景下

在这里插入图片描述

这里stack和queue的模版默认给的是deque，这是因为stack是"先进后出"的数据结构，它的常用接口也就是push_back()和pop_back()，这对于deque来说，刚好对应上其优点，deque在头部插入删除效率明显要高于vector
而对于queue来讲，它是"先进先出"的数据结构，而deque是双端队列，在头部尾部插入/删除数据消耗也少，内存使用率也高

对于双端队列deque来说，其应用场景目前就是作为stack和queue的底层默认容器

2. 优先队列priority_queue

2.1 认识priority_queue

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。

在这里插入图片描述

priority_queue的常用接口

在这里插入图片描述

如果要实现队列中所有元素按照升序排列呢？

在这里插入图片描述

2.2 模拟实现优先队列priority_queue

首先优先级队列默认是一个大堆，入队列出队列主要依靠向上向下调整算法

入队列

在这里插入图片描述

出队列

在这里插入图片描述

代码

#include <deque>
#include <vector>
using namespace std;namespace PQ
{template<class T,class Container = vector<T>>class Priority_Queue{public://向上调整算法void adjust_up(size_t child){size_t parent = (child - 1) / 2;while (child > 0){if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}elsebreak;}}//向下调整算法void adjust_down(size_t parent){size_t child = parent * 2 + 1;while (child < _con.size()){//优先找最小的孩子if (child + 1 < _con.size() && _con[child + 1] > _con[child]){++child;}//对比最小孩子和父节点if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}//有序elsebreak;}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}const T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size() const{return _con.size();}private:Container _con;};
}