【C++初阶学习】第十三弹——优先级队列及容器适配器

 C语言栈:数据结构——栈(C语言版)-CSDN博客

C语言队列:数据结构——队列(C语言版)-CSDN博客

C++栈与队列:【C++初阶学习】第十二弹——stack和queue的介绍和使用-CSDN博客

前言:

在前面,我们已经学习了用C++如何使用stack和queue,今天,我们来讲解一下它们两个底层实现的一些东西和一些扩展内容

目录

一、优先级队列

基本概念

常用成员函数

创建和使用优先级队列

创建小根堆

二、容器适配器

基本概念

deque容器(了解)

stack和queue的模拟实现


一、优先级队列

前面我们已经学习了队列的知识,队列就是先进先出,那么这里的优先级队列是什么呢?

C++中的优先级队列是一种基于容器适配器的抽象数据类型,它提供了队列接口,并允许按照元素的优先级进行排序

基本概念

优先级队列是一种特殊的队列,其中元素的出队顺序不是按照先进先出的原则,而是根据元素的优先级来确定。优先级高的元素先出队,优先级低的元素后出队(一般是按照升序,类似于堆的结构)

常用成员函数

以下是优先级队列的一些常用成员函数:

  1. empty():检查队列是否为空。
  2. size():返回队列中的元素数量。
  3. top():返回队列顶部(优先级最高)的元素,但不从队列中删除它。
  4. push():将一个元素添加到队列中,并重新调整队列以保持排序。
  5. pop():删除队列顶部(优先级最高)的元素。
  6. swap():与另一个优先级队列交换内容

创建和使用优先级队列

以下是如何创建和使用一个优先级队列的示例:

#include <iostream>
#include <queue>
#include <vector>
using namespace std;int main() {// 创建一个存储int类型元素的优先级队列priority_queue<int> pq;// 向队列中添加元素pq.push(10);pq.push(30);pq.push(20);pq.push(5);pq.push(1);// 输出队列中的元素,并观察优先级while (!pq.empty()) {cout << pq.top() << " ";pq.pop();}cout << endl;return 0;
}

运行结果:

通过这个结果我们就可以看出所谓的优先级队列实际上与我们之前所学的堆很像,而且默认的是升序

创建小根堆

如果你想要创建一个小根堆(优先级最低的元素在顶部),你可以传递std::greater<T>作为比较函数:

std::priority_queue<int, std::dequeue<int>, std::greater<int>> pq;

二、容器适配器

基本概念

在将容器适配器前,我们首先要搞明白一点, 什么是容器?什么是容器适配器?

在前面我们讲vector、list、string时,我们讲过这些我们在以后讲时是将其作为容器使用,就是说我们用它们来存放数据,哪个用着方便就用哪个,至于说容器适配器其实就是指这个类型可以用多种容器来模拟实现,比如说:

stack是一种后进先出的特殊线性数据结构,因此只要具有push_back()pop_back()操作的线性结构,都可 以作为stack的底层容器,比如vectorlist都可以;
queue是先进先出的特殊线性数据结构,只要具有 push_backpop_front操作的线性结构,都可以作为queue的底层容器,比如list
当然,上面这两个类型在底层设计时,使用的并不是vector和list,而是用deque来实现的,那么这个容器又是什么呢,在前面我们就涉及到过,下面就来讲一下

deque容器(了解)

deque本质上是一个双向都可以插入删除的队列,更准确的说我们应该拿它与vector和list做对比,下面我们来看一下deque的接口函数

通过这个图片我们可以看出,其实deque是兼顾vector和list的用法的,有点像是它们两个的集大成者,那么我们为什么不直接学习deque,不去学习vector和list呢?

这是因为deque有一个致命缺陷:不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到 某段小空间的边界,导致效率低下,但是一般用到这种线性结构存储的都会需要遍历,所以deque在平时就用不到

下面我们可以来看一下deque的底层架构:

下面我们来看一下deque的应用场景:stack和queue的模拟实现

stack和queue的模拟实现

这里不做详细的讲解了,有不懂的可以私信问我

stack

#include<deque>
namespace zda
{template<class T, class Con = deque<T>>//template<class T, class Con = vector<T>>//template<class T, class Con = list<T>>class stack{public:stack() {}void push(const T& x) { _c.push_back(x); }void pop() { _c.pop_back(); }T& top() { return _c.back(); }const T& top()const { return _c.back(); }size_t size()const { return _c.size(); }bool empty()const { return _c.empty(); }private:Con _c;};
}

queue

#include<deque>
#include <list>
namespace bite
{template<class T, class Con = deque<T>>//template<class T, class Con = list<T>>class queue{public:queue() {}void push(const T& x) { _c.push_back(x); }void pop() { _c.pop_front(); }T& back() { return _c.back(); }const T& back()const { return _c.back(); }T& front() { return _c.front(); }const T& front()const { return _c.front(); }size_t size()const { return _c.size(); }bool empty()const { return _c.empty(); }private:Con _c;};
}

三、总结

学完我们再回头体会一下,其实优先级队列就是我们之前所学的堆,而容器适配器其实就是一种能够调用容器的特殊数据类型,并没有什么新的知识,今天的内容暂且到此,有不理解的地方可以与我私信交流

感谢各位大佬观看,创作不易,还请各位大佬一键三连!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/346108.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

CodeMeter助力Hilscher,推动实现全球智能制造连接解决方案

Hilscher的旗舰店为开放工业4.0联盟&#xff08;OI4&#xff09;社区提供了应用商店的便捷和开放性&#xff0c;将这一概念引入工业领域。该商店依托CodeMeter的许可证管理和加密保护&#xff0c;为工业用户提供了丰富的应用和解决方案库&#xff0c;满足他们在车间自动化和连接…

深入理解 C++ 智能指针

文章目录 一、引言二、 原始指针的问题1、原始指针的问题2、智能指针如何解决这些问题 三、智能指针的类型四、std::shared_ptr1、shared_ptr使用2、shared_ptr的使用注意事项3、定制删除器4、shared_ptr的优缺点5、shared_ptr的模拟实现 五、std::unique_ptr1、unique_ptr的使…

讯飞星火大模型个人API账号免费使用申请教程

文章目录 1.登录讯飞星火大模型官网 https://www.xfyun.cn/ 2.下滑找到Spark Lite&#xff0c;点击立即调用 3.星火大模型需要和具体的应用绑定&#xff0c;我们需要先创建一个新应用 https://console.xfyun.cn/app/myapp&#xff0c;应用名称可以按照自己的意愿起。 4.填写应用…

1688商品库存查询

目录 下载安装与运行 功能简介 快速入门&#xff08;视频&#xff09; 当前支持的导出项 常用功能 历史商品是什么意思 粘贴商品有什么要求 导入商品需要什么样的模板 单个商品的查看 查看单个商品详情 下载安装与运行 下载、安装与运行 语雀 功能简介 最近一次测…

kafka-集群-生产消费测试

文章目录 1、集群生产消费测试1.1、消费者消费消息1.2、生产者生产消息 1、集群生产消费测试 1.1、消费者消费消息 [rootlocalhost ~]# kafka-console-consumer.sh --bootstrap-server 192.168.74.148:9095,192.168.74.148:9096,192.168.74.148:9097 --topic my_topic11.2、生…

深度解析地铁票务系统的技术架构与创新应用

在城市交通体系中&#xff0c;地铁作为一种快速、便捷的公共交通方式&#xff0c;已经成为现代都市生活的重要组成部分。而地铁票务系统的技术架构&#xff0c;则是支撑地铁运营的核心之一。本文将深度解析地铁票务系统的技术架构与创新应用&#xff0c;从系统设计、数据管理、…

vuInhub靶场实战系列--Kioptrix Level #3

免责声明 本文档仅供学习和研究使用,请勿使用文中的技术源码用于非法用途,任何人造成的任何负面影响,与本人无关。 目录 免责声明前言一、环境配置1.1 靶场信息1.2 靶场配置 二、信息收集2.1 主机发现2.1.1 netdiscover2.1.2 arp-scan主机扫描 2.2 端口扫描2.3 指纹识别2.4 目…

每日复盘-20240607

今日关注&#xff1a; 这几天市场环境不好&#xff0c;一直空仓。 六日涨幅最大: ------1--------605258--------- 协和电子 五日涨幅最大: ------1--------605258--------- 协和电子 四日涨幅最大: ------1--------605258--------- 协和电子 三日涨幅最大: ------1--------0…

Java面向对象-方法的重写、super

Java面向对象-方法的重写、super 一、方法的重写二、super关键字1、super可以省略2、super不可以省略3、super修饰构造器4、继承条件下构造方法的执行过程 一、方法的重写 1、发生在子类和父类中&#xff0c;当子类对父类提供的方法不满意的时候&#xff0c;要对父类的方法进行…

原生小程序一键获取手机号

1.效果图 2.代码index.wxml <!-- 获取手机号 利用手机号快速填写的功能&#xff0c;将button组件 open-type 的值设置为 getPhoneNumber--><button open-type"getPhoneNumber" bindgetphonenumber"getPhoneNumber">获取手机号</button> …

PPT设置为本框的默认格式以及固定文本框

调整文本框固定位置 双击文本框之后勾选如下三个位置 设置文本框为默认 在调整好文本框的基本性质后&#xff0c;设置为默认即可

MySQL数据库的基础:逻辑集合数据库与表的基础操作

本篇会加入个人的所谓鱼式疯言 ❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言 而是理解过并总结出来通俗易懂的大白话, 小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的. &#x1f92d;&#x1f92d;&#x1f92d;可能说的不是那么严谨.但小编初心是能让更多人能接…

你还不知道无线PLC?

随着技术的不断发展&#xff0c;工业控制系统也在经历着革新。无线PLC&#xff08;Programmable Logic Controller&#xff0c;可编程逻辑控制器&#xff09;是一种结合了无线通讯技术和传统PLC系统的创新型技术。它为工业自动化提供了一种更灵活、更便捷的解决方案&#xff0c…

大模型基础——从零实现一个Transformer(2)

大模型基础——从零实现一个Transformer(1) 一、引言 上一章主要实现了一下Transformer里面的BPE算法和 Embedding模块定义 本章主要讲一下 Transformer里面的位置编码以及多头注意力 二、位置编码 2.1正弦位置编码(Sinusoidal Position Encoding) 其中&#xff1a; pos&…

jmeter性能优化之mysql配置

一、连接数据库和grafana 准备&#xff1a;连接好数据库和启动grafana并导入mysql模板 大批量注册、登录、下单等&#xff0c;还有过节像618&#xff0c;双11和数据库交互非常庞大&#xff0c;都会存在数据库的某一张表里面&#xff0c;当用户在登录或者查询某一个界面时&…

第十二届蓝桥杯单片机国赛练习代码

文章目录 前言一、问题重述二、主函数总结 前言 第十五蓝桥杯国赛落幕已有十天&#xff0c;是时候总结一下&#xff0c;这个专栏也将结束。虽然并没有取得预期的结果&#xff0c;但故事结尾并不总是美满的。下面是赛前练习的第十二届国赛的代码。 一、问题重述 二、主函数 完整…

渗透测试模拟实战-tomexam网络考试系统

渗透测试&#xff0c;也称为“pentest”或“道德黑客”&#xff0c;是一种模拟攻击的网络安全评估方法&#xff0c;旨在识别和利用系统中的安全漏洞。这种测试通常由专业的安全专家执行&#xff0c;他们使用各种技术和工具来尝试突破系统的防御&#xff0c;如网络、应用程序、主…

高德地图简单实现点标,和区域绘制

高德地图开发文档:https://lbs.amap.com/api/javascript-api/guide/abc/quickstart 百度搜索高德地图开发平台 注册高德地图开发账号 在应用管理中 我的应用中 添加一个Key 点击提交 进入高德地图开发文档:https://lbs.amap.com/api/javascript-api/guide/abc/quickstart …

定个小目标之刷LeetCode热题(15)

这道题直接就采用两数相加的规则&#xff0c;维护一个进阶值&#xff08;n&#xff09;即可&#xff0c;代码如下 class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {// 新建一个值为0的头结点ListNode newHead new ListNode(0);// 创建几个指针用于…

从零开始,手把手教你文旅产业策划全攻略

如果你想深入了解文旅策划的世界&#xff0c;那么有很多途径可以获取知识和灵感。 首先&#xff0c;阅读一些专业书籍也是一个不错的选择。书店或图书馆里有许多关于文旅策划的书籍&#xff0c;它们通常涵盖了策划的基本理论、方法和实践案例。通过阅读这些书籍&#xff0c;你…