【C++】详细介绍:priority_queue的使用、适配器、deque介绍、仿函数

news/2024/11/7 17:37:09/

目录

一、介绍

二、使用

三、函数模版和类模板的区别

四、适配器

1、适配器适配栈

扩展:

2、deque(双端队列)

缺省模版

五、仿函数


一、介绍

(1)、priority_queue称为优先级队列,是一种容器适配器,不是队列也不是容器。

(2)、该结构的底层是堆结构,默认是大堆,用模版参数来区分是大堆还是小堆。

(3)、具体信息可查看官网手册:https://legacy.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue

二、使用

注意: 如果在priority_queue中放自定义类型的数据,用户需要在自定义类型中提供> 或者< 的重载。
(1)、大堆使用:
//默认是大堆
priority_queue<int, vector<int>> big_heap;
big_heap.push(1);
big_heap.push(10);
big_heap.push(2);
big_heap.push(4);
big_heap.push(2);
big_heap.push(4);
while (!big_heap.empty())
{cout << big_heap.top() << " ";big_heap.pop();
}
cout << endl;

(2)、小堆使用,第三个参数模版传大于

//小堆,第三个模版参数用大于
priority_queue<int, vector<int>, greater<int>> small_heap;
small_heap.push(1);
small_heap.push(10);
small_heap.push(2);
small_heap.push(4);
small_heap.push(2);
small_heap.push(4);
while (!small_heap.empty())
{cout << small_heap.top() << " ";small_heap.pop();
}

三、函数模版和类模板的区别

如下:

sort(s1.begin(), s1.end(), greater<int>());
priority_queue<int, vector<int>, greater<int>>;

看这两段代码的,第一个是sort函数的传参,第二个是类的传参,看第三个参数,看似好像没区别,但实则有个括号的差异,一个传递的是对象,一个传递的是类型

四、适配器

priority_queue的实现是通过适配器实现的,那么什么是适配器呐?

适配器是一种设计模式,该种模式是将一个类的接口转换成客户希望的另外一个接口。
也就是说,是通过复用对应容器的接口来构成自己想要的结构。适配器的核心是大量复用。

1、适配器适配栈

先看源代码:

namespace HF
{template<class T ,class Container>class stack{private:Container _con;public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}};
}
HF::stack<int,vector<int>> pq;
pq.push(1);
pq.push(2);
pq.push(3);
pq.push(4);
while (!pq.empty())
{cout << pq.top() << " ";pq.pop();
}

看代码我们更容易理解适配器的概念,首先用一个类模版,第一个参数T是数据类型,第二个参数Container是具体的容器,为了实现我们需要的结构,必须确保我们所传入的容器有对应的接口:

如上我们实现栈,而栈的核心接口就是插入(push_back),删除(pop_back),取栈顶元素(top),判空(empty),而我们传入的模版是vector类型:

很显然vector都具备这些接口,所以可以用vector适配出一个栈,其步骤就是在栈的相应接口下调用vector对应的接口:

我们知道,因为我们模版传入的是vector,所以成员变量_con就是vector对象,所以就复用相应接口。

扩展:

根据上面内容我们可以思考一个问题:

​​​​​​vector底层是连续的空间,所以适配出的栈就是数组栈,那么当我们传的模版是list,自然而然适配出的就是链式栈。

2、deque(双端队列)

(1)、手册官网: https://legacy.cplusplus.com/reference/deque/deque/?kw=deque
(2)、deque是一种双开口的"连续"空间的数据结构,双开口的含义是:可以在头尾两端进行插入和 删除操作,且时间复杂度为O(1),与vector比较,头插效率高,不需要搬移元素;与list比较,空间利用率比 较高。
(3)、注意:deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维 数组。
(4)、也就是说deque是包含头插头删尾插尾删等一系列接口的东西,相当于把vector和list的优点结合在一起。(但要注意,并不能取代vector和list)
由此我们引出以下内容:

缺省模版

扩展:模版在编译阶段就进行传参。
理解缺省模版,我们可以结合函数参数的缺省值辅助理解。当实参没有传参的时候,形参就会用缺省值,同理,当实参模版没有传参时,就会使用缺省模版,如下:
template<class T ,class Container = deque<T>>

在上述的适配器适配栈中,我们就可以使用deque作为缺省模版,因为deque的接口比较多,所以能实现的结构就更多,模版实参没有传容器时,deque能更加确保提供对应所需的接口。

五、仿函数

C++仿函数的功能类似于C语言中的回调函数,只是C语言用的是函数指针。

通俗讲就是在一个类中重载 () ,然后,哪里需要就在哪里调用。

然后在不同类中实现不同的功能,但都重载(),这时,我们需要哪个功能,就可以传哪个类模版,从而获取该类的功能(如判断大于小于):

举例:

class less
{
public:bool operator()(int x,int y){return x < y;}
};class greater
{
public:bool operator()(int x, int y){return x > y;}
};template<class Comapre>
class A
{
public:void func(int xx,int yy){Comapre _per;cout << _per(xx, yy) << endl;}
};int main()
{//传入比较小于功能的模版A<less> a1;a1.func(10, 20);//传入比较大于功能的模版A<greater> a2;a2.func(10, 20);return 0;
}

因为类A里面使用了模版,所以我们想使用哪个功能就传入类类型。


http://www.ppmy.cn/news/1545126.html

相关文章

【软服之家-注册安全分析报告-无验证方式导致安全隐患】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 1. 暴力破解密码&#xff0c;造成用户信息泄露 2. 短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉 3. 带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造…

【PDF提取神器】针对LLM推出的PymuPDF4llm库 可提取pdf中的文字/表格/图像/单词

目录 前言 安装Pymupdf4llm 多模态具体应用 API 文档 前言 PymuPDF4llm 是最新推出的pdf提取工具&#xff0c;针对LLM进行了专门优化&#xff0c;它支持markdown提取和LlamaIndex文档输出&#xff0c;可以准确提取pdf中的结构化数据&#xff0c;包括文字/表格/图像/单词&a…

RFID标签实现企业资产智能化管理

一、RFID技术概述 1.1 RFID技术原理 RFID&#xff08;无线射频识别&#xff09;技术是一种利用无线电波进行自动识别目标对象并获取相关数据的技术。其核心原理基于电磁感应定律和电磁波的空间传播规律&#xff0c;通过无线电频率信号实现非接触式的数据通信和识别。 在RFID…

深入解析Vue3:从入门到实战(详细版)

文章目录 前言一、Vue3简介官网地址主要特点 二、安装与创建Vue3项目使用Vue CLI创建项目使用Vite创建项目 三、Composition API详解Setup函数ref与Reactive生命周期钩子计算属性和监听器 四、新特性与优化响应式系统更好的TypeScript支持类型定义类型推断新组件全局API重构更好…

如何在算家云搭建Aatrox-Bert-VITS2(音频生成)

一、模型介绍 ‌ Aatrox - Bert -VITS2 模型是一种基于深度学习的语音合成系统&#xff0c;结合了 BERT 的预训练能力和 VITS2 的微调技术&#xff0c;旨在实现高质量的个性化语音合成。 二、模型搭建流程 1. 创建容器实例 进入算家云的“应用社区”&#xff0c;点击搜索找到…

【物联网技术】ESP8266 WIFI模块STA、AP、STA+AP、TCP/UDP透传工作模式介绍与AT指令介绍

前言:本文对ESP8266 WIFI模块STA、AP、STA+AP、TCP/UDP透传工作模式进行介绍;以及AT指令介绍,包括基础AT指令,WIFI功能AT指令、TCP/IP相关AT指令、常用AT指令实例进行介绍。 ESP8266 WIFI模块的接线及固件烧写可参考我的这篇博客:正点原子ATK-ESP8266 WIFI模块接线及固件…

【go从零单排】go中的三种数据类型array、slices、maps

Don’t worry , just coding! 内耗与overthinking只会削弱你的精力&#xff0c;虚度你的光阴&#xff0c;每天迈出一小步&#xff0c;回头时发现已经走了很远。 array数组 package mainimport "fmt"func main() {var a [5]int //var关键字定义数组&#xff0c;[5]表…

51单片机教程(二)- 创建项目

1 创建项目 创建项目存储文件夹&#xff1a;C51Project 打开Keil5软件&#xff0c;选择 Project -> New uVision Project&#xff1a; 选择项目路径&#xff0c;即刚才创建的文件夹 选择芯片&#xff0c;选择 Microchip&#xff08;微型集成电路&#xff09;&#xff0…