当前位置: 首页 > news >正文

【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;};
}

3. 仿函数

  • 这里先简单了解下仿函数,其实就是重载小括号运算符
  • 仿函数是一个定义了 operator()的类或结构体实例。通过重载 operator(),你可以为对象定义调用时的行为,使其表现得像一个函数。

在这里插入图片描述


在这里插入图片描述


  • 当然,使用仿函数有时也会达不到预期效果

在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


相关文章:

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

文章目录 1. 双端队列deque1.1 认识deque1.2 deque的迭代器1.3 deque的常用接口1.4 deque的优缺点 2. 优先队列priority_queue2.1 认识priority_queue2.2 模拟实现优先队列priority_queue 3. 仿函数 在学习deque之前&#xff0c;回顾一下vector和list各自的优缺点 数据结构优点…...

通过helm在k8s中安装mysql 8.0.37

使用 Helm 在 Kubernetes 中安装 MySQL 8.0.37 是一个相对简单的过程。以下是详细步骤&#xff1a; 下载helm包 #添加 Helm 仓库 helm repo add bitnami https://charts.bitnami.com/bitnami#搜索mysql helm search repo mysql --versions NAME CHAR…...

人工智能 - browser-use:重新定义浏览器自动化的 AI 新范式

在浏览器自动化领域&#xff0c;Selenium 和 Playwright 等工具已成为开发者的标配。但随着网页复杂度的提升&#xff08;如动态渲染、反爬虫机制、验证码等&#xff09;&#xff0c;传统工具逐渐暴露出效率低、扩展性差的缺陷。browser-use 的出现&#xff0c;通过深度融合人…...

Langchain-简单Demo

支持的模型 官方示例&#xff1a; #OpenAI pip install -qU langchain-openai import getpass import os os.environ["OPENAI_API_KEY"] getpass.getpass() from langchain_openai import ChatOpenAI model ChatOpenAI(model"gpt-4") #Anthropic pip ins…...

怎样才能设计好的自动化测试用例

设计一个好的自动化测试用例&#xff0c;就像写一段“自解释的、高质量的代码”——它应该清晰、可靠、独立、易维护&#xff0c;而且对测试目标有价值。 ✅ 好的自动化测试用例应具备的 8 大特性&#xff1a; 特性解释示例&#x1f3af; 目标明确一个用例只验证一个点&#…...

NFC 碰一碰发视频源码搭建全流程详解,支持OEM

在移动互联网时代&#xff0c;便捷的数据传输方式备受关注。NFC&#xff08;近场通信&#xff09;技术以其操作简单、连接迅速的特点&#xff0c;为数据交互提供了新的可能。通过搭建 NFC 碰一碰发视频功能&#xff0c;用户只需将设备轻轻靠近&#xff0c;就能快速完成视频传输…...

vue入门:路由 router

文章目录 介绍安装配置路由模式嵌套路由路由传参编程式导航路由懒加载 底层原理 介绍 vue2 vue router API vue3 vue router API Vue Router 是 Vue.js 的官方路由管理器&#xff0c;它允许你通过不同的 URL 显示不同的组件&#xff0c;从而实现单页面应用&#xff08;SPA&a…...

运营商二要素认证 API 接口具有哪些的好处?

目录 一、提高认证准确性 1.数据真实性可靠 2.实时验证效率高 3.双重验证更精准 4.多场景适用性强 5.动态更新数据准 二、增强安全性 1.防止身份冒用 2.抵御欺诈行为 3.保障数据安全 4.强化业务安全 5.支持安全审计与追溯 三、提升用户体验 1.操作简便快捷 2.认…...

从GPT到Gemini 大模型进化史

从GPT到Gemini&#xff1a;大模型进化史 在过去的几年里&#xff0c;人工智能领域经历了翻天覆地的变化&#xff0c;其中最引人注目的莫过于大规模语言模型的发展。从最初的GPT系列到最近的Gemini&#xff0c;这些模型不仅在技术上取得了重大突破&#xff0c;还在实际应用中展…...

大模型时代下全场景数据消费平台的智能BI—Quick BI深度解析

一、前言 在数字化转型浪潮中&#xff0c;BI工具已成为企业数据驱动决策的核心引擎。Quick BI作为阿里云旗下的全场景数据消费平台&#xff0c;以其"让业务决策触手可及"的理念在市场中占据一席之地。通过Quick BI可以让企业的数据资产快速的流动起来&#xff0c;通…...

高防ip的原理

高防IP&#xff08;高防御IP地址&#xff09;是一种专门用于抵御大规模网络攻击的防护服务&#xff0c;其核心原理是通过​​流量清洗、协议分析与智能调度​​等技术&#xff0c;将恶意流量与正常业务流量分离&#xff0c;保障目标服务器或应用的可用性。以下是其核心技术原理…...

微服务4--服务网关

网关 在微服务架构中&#xff0c;一个系统会被拆分为很多个微服务&#xff0c;那么作为客户端要如何去调用 这么多的微服务呢&#xff1f;如果没有网关的存在&#xff0c;我们只能在客户端记录每个微服务的地址&#xff0c;然后分别去调用。 这样的架构&#xff0c;会存在着诸…...

容器docker入门学习

这里写目录标题 容器容器的软件厂商 dockerdocker引擎 虚拟化虚拟化技术 docker安装详解1、安装检查2、安装yum相关的工具3、安装docker-ce软件4、查看docker版本5、启动docker服务6、设置docker开机启动7、查看有哪些docker容器运行进程8、查看容器里有哪些镜像9、下载nginx软…...

Flink调优面试题及参考答案20道

1. 如何优化Flink的Checkpoint机制? 答案: 增大Checkpoint间隔:减少对作业吞吐量的影响(如从1分钟调整为5分钟)。 使用增量Checkpoint(RocksDB状态后端):仅上传变化的文件,降低IO压力。 调整超时时间:checkpointTimeout避免因短暂反压导致失败。 对齐优化:使用非对…...

【音视频】MP4解封装

一、概述 实现了读取mp4文件&#xff0c;提取出h264和aac文件&#xff0c;可以直接播放 二、实现过程 准备文件 在build路径下添加mp4文件 同时&#xff0c;添加main函数参数&#xff0c;表示输入文件和输出文件 打开文件 打开输入文件&#xff0c;初始化格式上下文 char…...

全球6G大会 | 紫光展锐用“芯”推动空天地一体创新纪元

近日&#xff0c;全球6G技术与产业生态大会&#xff08;简称“全球6G技术大会”&#xff09;在南京召开。紫光展锐应邀出席“空天地一体化与数字低空”平行论坛&#xff0c;并从6G通信、感知、定位等多方面分享了紫光展锐在6G前沿科技领域的创新理念及在空天地一体化技术方面的…...

C++学习:六个月从基础到就业——面向对象编程:虚函数与抽象类

C学习&#xff1a;六个月从基础到就业——面向对象编程&#xff1a;虚函数与抽象类 本文是我C学习之旅系列的第十四篇技术文章&#xff0c;主要探讨C中的虚函数与抽象类&#xff0c;这是实现多态性的核心机制。查看完整系列目录了解更多内容。 引言 多态性是面向对象编程的三大…...

git分支操作

一、git branch&#xff1a;分支管理 1. 查看分支 git branch # 查看本地分支&#xff08;* 表示当前分支&#xff09; git branch -a # 查看所有分支&#xff08;本地远程&#xff09; git branch -vv # 查看分支跟踪关系 2. 创建/删除分支…...

IDEA 中 Scala 项目远程连接虚拟机 Spark 环境

IDEA 中 Scala 项目远程连接虚拟机 Spark 环境 1. 环境准备 确保虚拟机 Spark 环境正常运行 虚拟机中已安装并启动 Spark记录虚拟机的 IP 地址和 Spark 端口&#xff08;默认 7077&#xff09;确保虚拟机防火墙允许相关端口访问 本地 IDEA 环境配置 安装 Scala 插件安装 Spar…...

2. 判断列表元素的单一性

【问题描述】编写程序&#xff0c;判断一个列表中的各个元素如果相同(例如[2,2,2,2,2]),则输出True&#xff0c;不相同(例如[1,2,3,2,3])则输出False。 【输入形式】ainput() 【输出形式】用print()函数 【样例输入】 [2,2,2,2,2] 【样例输出】 True 【样例输入】 [1,2,…...

King3399(ubuntu文件系统)GDB/GDBServer调试配置

0 引言 最近在用king3399进行驱动开发&#xff0c;即使是一些简单的外设也不免反复修改与烧录&#xff0c;若仅仅通过printk这种方法对程序进行打印调试&#xff0c;其过程也是相当复杂&#xff0c;因此想通过GDB/GDBServer的方式进行调试&#xff0c;本文主要是记录配置过程的…...

机器学习简介

目录 机器学习简介机器学习的大致分类监督学习 (Supervised learning)RegressionClassification / Predict categories 无监督学习 (Unsupervised learning)Clustering algorithmAnomaly DetectionDimensionality Reduction对比总结 强化学习 (Reinforcement learning)强化学习…...

k8s调度器:如何控制Pod的分布

引言&#xff1a;从“随机分配”到“智能调度” 想象你的Kubernetes集群是一个繁忙的物流中心&#xff0c;节点&#xff08;Node&#xff09;是仓库&#xff0c;Pod是货物。 默认调度器 就像一名普通分拣员&#xff0c;简单地将货物塞进最近的仓库&#xff0c;可能导致某些仓…...

机器学习在催化剂设计中的应用理论加实操

背景介绍​​ 数据智能驱动&#xff0c;催化理性设计新纪元​​ 催化材料设计是能源转化、化工合成及环境治理等领域的核心挑战。传统催化研究主要依赖密度泛函理论(DFT)计算与实验试错法&#xff0c;通过量子力学模拟揭示活性位点电子结构&#xff0c;结合高通量实验筛选候选…...

Spring Cloud Alibaba微服务-微服务介绍和搭建

1. 课程介绍 单体服务中有订单&#xff0c;用户&#xff0c;库存&#xff0c; 两个缺陷&#xff1a; a. 是以应用的维度进行负载均衡&#xff0c;资源占用大 b. 当其中一个模块宕机&#xff0c;整个应用就不能用了&#xff1b; nacos&#xff1b;ribbon&#xff0c;loadBa…...

量子通信应用:量子安全物联网(三)协议融合

第一部分:引言与概述 1.1 量子安全物联网的背景与必要性 随着物联网(IoT)设备的爆炸式增长(预计2030年全球连接设备超750亿台),传统安全机制(如RSA、ECC加密)正面临量子计算的颠覆性威胁。量子计算机的Shor算法可在多项式时间内破解非对称加密体系,而Grover算法则对…...

JUC学习(1) 线程和进程

2.线程和进程 线程&#xff0c;进程进程&#xff1a;一个程序。 一个进程往往可以包含多个线程&#xff0c;至少包含一个&#xff01; Java默认有2个线程 mainGC 对于Java而言&#xff0c;三种开启线程的方式 ThreadRunnableCallable Java真的可以开启线程吗 不可以&am…...

Java基础系列-LinkedList源码解析

文章目录 简介LinkedList 插入和删除元素的时间复杂度&#xff1f;LinkedList 为什么不能实现 RandomAccess 接口&#xff1f; LinkedList 源码分析Node 定义初始化获取元素插入元素删除元素遍历链表 简介 LinkedList 是一个基于双向链表实现的集合类&#xff0c;经常被拿来和…...

pycharm无法识别到本地python的conda环境解决方法

问题一 现象描述&#xff1a; 本地已经安装了conda&#xff0c;但在pycharm中选择conda环境却识别不到&#xff0c; 解决方法&#xff1a;手动输入conda path&#xff0c;点击R eload environments基本就能修复&#xff0c;比如我的路径如下 /Users/test/conda/miniconda3/b…...

【机器人创新创业应需明确产品定位与方向指南】

机器人领域的创新创业, 需要对公司和产品的定位和生态进行深入思考, 明确其定位与发展目标, 明确产品在是为G、为B还是为C进行服务。 本文引用地址&#xff1a;https://www.eepw.com.cn/article/202504/469401.htm 超前的、探索性的创新技术一般是面向G端, 而不是面向B端或者C…...

《似锦》:画饼之—你画给我我画给你

甄珩&#xff0c;看似刚正不阿&#xff0c;正得发邪&#xff0c;一板一眼的严肃角色 可是每次余七和甄珩在一起&#xff0c;就是一部行走的喜剧&#xff0c;众网友称他们为“甄儿八锦” 《似锦》剧集精彩片段&#xff1a;甄珩余七爆笑修罗场&#xff08;四&#xff09; 谁懂这…...

鸿蒙系统开发中路由使用详解

鸿蒙系统提供了两种主要的路由机制&#xff1a;传统的Router模块和组件化的Navigation容器。下面我将详细介绍这两种路由方式的使用方法、区别以及实际应用示例。 一、Router模块基础使用 Router是鸿蒙早期提供的页面路由模块&#xff0c;通过URL实现页面跳转和数据传递。 1…...

拖拉拽效果加点击事件

<!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><title>自由拖拽点击元素</title><style>body {margin: 0;height: 100vh;display: flex;justify-content: center;align-items: center;backgr…...

Ubuntu利用docker搭建Java相关环境记录(二)

Ubuntu利用docker搭建Java相关环境记录&#xff08;二&#xff09; 接上篇&#xff1a;Ubuntu利用docker搭建Java相关环境记录&#xff08;一&#xff09; 启动Docker 1. 查看Docker容器 已启动的容器 docker ps所有容器 docker ps -a本人很懒并不想一直敲命令操作&#…...

2025华中杯B题——AI实现

以下内容全文由以下网站AI实现&#xff0c;内容和代码仅供参考 如需实现自己的需求和目标&#xff0c;请使用网站自行调试。 参考写作 1. 共享单车数量与分布估算 问题分析 本题要求根据校园共享单车在各停车点的不同时段统计数据&#xff0c;估算校园内共享单车总量&#…...

【软考-系统架构设计师】OSI体系解析

一、OSI体系的核心定义 OSI&#xff08;Open System Interconnection&#xff09;模型是国际标准化组织&#xff08;ISO&#xff09;于1984年提出的网络通信分层框架&#xff0c;旨在解决异构网络系统间的兼容性问题。它将复杂的网络通信过程划分为七层&#xff0c;每层独立完…...

用手机也能打《无畏契约》?登录ToDesk即可开玩

《无畏契约》火到出圈&#xff01;但手机玩家只能干瞪眼&#xff1f; 作为拳头游戏继《英雄联盟》后的又一爆款&#xff0c;《无畏契约》凭借快节奏的战术对抗和全球化的地图设计&#xff08;比如东京“霓虹町”、百慕大“微风岛屿”&#xff09;&#xff0c;迅速成为电竞圈的顶…...

jmeter提取返回值到文件

前言 如何将请求的返回值&#xff0c;保存到本地文件&#xff0c;有具体以下3种方式。 保存到响应文件BeanShell 取样器BeanShell 后置处理程序 一、监听器–保存响应到文件 1、提取全部返回值&#xff0c;&#xff08;.json&#xff09;格式 2、保存到响应文件 添加----…...

iPaaS集成平台在电商行业的五大核心应用场景

在电商行业“多平台运营、多系统并行”的竞争格局下&#xff0c;订单激增、数据割裂、跨系统协作低效等问题成为企业增长的隐形阻碍。谷云科技作为国内领先的iPaaS&#xff08;集成平台即服务&#xff09;技术厂商&#xff0c;通过低代码、高扩展的集成能力&#xff0c;帮助电商…...

猪行为视频数据集

猪行为数据集包含 23 天(超过 6 周)的日间猪行为视频,这些视频由近乎架空的摄像机拍摄。视频已配准颜色和深度信息。数据以每秒 6 帧的速度捕获,并以 1800 帧(5 分钟)为一批次进行存储。大多数帧显示 8 头猪。 这里可以看到颜色和深度图像的示例: 喂食器位于图片底部中…...

在conda环境下使用pip安装库无法import

安装seleniumwire包&#xff0c;conda环境没有&#xff0c;pip之后安装不到当前conda环境 网上的方法都试过了&#xff0c;包括强制安装等 python -m pip install --upgrade --force-reinstall selenium-wire 最后定位应该是没有安装到当前conda的环境下&#xff0c;使用list…...

[net 6] udp_chat_server基于udp的简单聊天室(多线程的服务器与业务相分离)

目录 1. 网络聊天室的意义 2. 网络聊天室了解 2.1. 网络聊天室模块分析 2.2. 目标 3. 基本框架 3.1. 文件基本框架 3.2. 设计回调函数解耦 4. Route.hpp 模块(消息转发) 4.1. 头文件包含 4.2. 基本类框架 4.3. Route::Forward() 转发 4.3.1. 函数头设计 4.3.2. 维护…...

驱动-自旋锁

前面原子操作进行了讲解&#xff0c; 并使用原子整形操作对并发与竞争实验进行了改进&#xff0c;但是原子操作只能对整形变量或者位进行保护&#xff0c; 而对于结构体或者其他类型的共享资源&#xff0c; 原子操作就力不从心了&#xff0c; 这时候就轮到自旋锁的出场了。 两个…...

TDengine 存储引擎剖析:数据文件与索引设计(二)

TDengine 索引设计 索引设计关键特性 TDengine 的索引设计采用了多种技术和策略&#xff0c;以满足时序数据高效存储和快速查询的需求&#xff0c;具有以下关键特性&#xff1a; 多级时间戳压缩索引&#xff1a;TDengine 使用了时间戳压缩索引技术&#xff0c;能够有效减少索…...

基于Python的医疗质量管理指标智能提取系统【2025代码版】

系统概述 本系统旨在帮助医疗质量管理部从医院信息系统(HIS)中智能提取《2025年国家医疗质量安全改进目标》中的关键指标数据。系统采用Python编程语言,结合现代数据处理库,实现高效、准确的数据提取与分析功能。 import json import logging import logging.handlers impo…...

中介者模式(Mediator Pattern)

中介者模式(Mediator Pattern)是一种行为型设计模式。它通过引入一个中介者对象,来封装一系列对象之间的交互,使这些对象之间不再直接相互引用和通信,而是通过中介者进行间接通信,从而降低对象之间的耦合度,提高系统的可维护性和可扩展性。 一、基础 1. 意图 核心目的…...

Hbuilder 上的水印相机实现方案 (vue3 + vite + hbuilder)

效果 思路 通过 live-pusher 这个视频推流的组件来获取摄像头拿到视频的一帧图片之后&#xff0c;跳转到正常的 vue 页面&#xff0c;通过 canvas 来处理图片水印 源码 live-pusher 这个组件必须是 nvue 的 至于什么是 nvue&#xff0c;看这个官方文档吧 https://uniapp.dcl…...

聊聊Spring AI Alibaba的PdfTablesParser

序 本文主要研究一下Spring AI Alibaba的PdfTablesParser PdfTablesParser community/document-parsers/spring-ai-alibaba-starter-document-parser-pdf-tables/src/main/java/com/alibaba/cloud/ai/parser/pdf/tables/PdfTablesParser.java public class PdfTablesParser…...

二分查找-LeetCode

题目 给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target&#xff0c;写一个函数搜索 nums 中的 target&#xff0c;如果目标值存在返回下标&#xff0c;否则返回 -1。 示例 1: 输入: nums [-1,0,3,5,9,12], target 9 输出: 4 解释: …...

StarRocks Community Monthly Newsletter (Mar)

版本动态 3.4.1 版本更新 核心功能升级 数据安全与权限管控 支持「安全视图」功能&#xff0c;严格管控视图查询权限 MySQL协议连接支持SSL认证&#xff0c;保障数据传输安全 存算分离架构增强 支持自动创建Snapshot&#xff08;集群恢复更便捷&#xff09; Storage Volu…...