【C++】深入理解 C++ 优先级队列、容器适配器与 deque:实现与应用解析

个人主页: 起名字真南的CSDN博客

个人专栏:

  • 【数据结构初阶】 📘 基础数据结构
  • 【C语言】 💻 C语言编程技巧
  • 【C++】 🚀 进阶C++
  • 【OJ题解】 📝 题解精讲

目录

  • 前言
  • 📌 1. 优先级队列、容器适配器和 `deque` 概述
    • ✨1.1 什么是优先级队列?
    • ✨ 1.2 容器适配器与 `deque`
  • 📌 2. `deque` 的特点与基本操作
    • ✨2.1 特点
    • ✨2.2 基本操作
  • 📌 3. 容器适配器的类型与实现原理
  • 📌 4. `priority_queue` 的基本使用
  • 📌 5. 实际应用场景:任务调度与路径搜索
    • ✨5.1 优先级队列在任务调度中的应用
    • ✨ 5.2 `deque` 在滑动窗口问题中的应用
  • 📌 6. 总结与常见问题解答
    • ✨ 6.1 常见问题
  • 总结

前言

在 C++ 标准库中,优先级队列(priority_queue)是一种容器适配器,特别适合处理需要频繁访问最大值或最小值的数据集。同时,双端队列 deque 也是一种灵活的标准容器,支持高效的头尾插入、删除操作,被广泛用于实现队列、栈等数据结构。本文将深入讲解优先级队列、deque 及其在容器适配器中的应用。


📌 1. 优先级队列、容器适配器和 deque 概述

✨1.1 什么是优先级队列?

优先级队列是一种基于优先级的特殊队列。默认情况下,C++ 的 priority_queue 是最大堆,出队时总是返回最大元素。实现优先级队列的底层容器通常是 vectordeque,其中 deque 是标准库提供的双端队列容器,支持高效的头尾插入和删除。

✨ 1.2 容器适配器与 deque

C++ 容器适配器包括 stackqueuepriority_queue,它们对底层容器进行封装,提供栈、队列等结构的特定接口。dequequeuestack 默认使用的底层容器,提供两端的灵活操作。


📌 2. deque 的特点与基本操作

在这里插入图片描述

deque(双端队列)是 C++ 中的一种序列容器,支持在两端快速插入和删除。deque 的实现类似一个分段的动态数组,因此具备更灵活的内存管理方式,可以在前后两端动态扩展。

✨2.1 特点

  • 双端插入与删除:支持在头尾两端快速插入和删除,效率接近 O(1)
  • 动态扩展:不像 vector 只能从尾部扩展,deque 可以在头部或尾部自由扩展。
  • 支持随机访问:与 vector 类似,可以通过索引访问任意位置的元素,但相比 vector 速度稍慢。

✨2.2 基本操作

#include <iostream>
#include <deque>void deque_example() {std::deque<int> dq;// 在尾部插入dq.push_back(10);dq.push_back(20);// 在头部插入dq.push_front(5);// 访问元素std::cout << "Front: " << dq.front() << std::endl;  // 5std::cout << "Back: " << dq.back() << std::endl;    // 20// 删除头尾元素dq.pop_front();dq.pop_back();// 遍历std::cout << "Elements: ";for (int elem : dq) {std::cout << elem << " ";}std::cout << std::endl;
}int main() {deque_example();return 0;
}

输出

Front: 5
Back: 20
Elements: 10 

代码解析

  • push_backpush_front:分别在尾部和头部插入元素。
  • pop_backpop_front:分别从尾部和头部删除元素。
  • frontback:访问头部和尾部的元素。

📌 3. 容器适配器的类型与实现原理

C++ 容器适配器使用底层容器来构建特定的数据结构,例如栈、队列和优先级队列。以下是容器适配器的类型及默认底层容器:

  • stack:默认使用 deque 实现的后进先出(LIFO)数据结构,也支持 vector
  • queue:使用 deque 实现的先进先出(FIFO)数据结构,提供 pushpopfrontback 操作。
  • priority_queue:通常使用 vectordeque 实现,提供最高优先级元素的访问和出队操作。

使用 deque 作为底层容器时,可以灵活利用其双端插入和删除的特性。


📌 4. priority_queue 的基本使用

在这里插入图片描述

priority_queue 默认是最大堆,每次 pop 操作返回当前的最大值。其底层容器通常使用 vector,但 deque 也可以用作其底层容器。
如果我们想让他最小堆可以在传入参数的时候传入 greater

#include <iostream>
#include <queue>
#include <vector>
#include <functional>  // std::greaterint main()
{std::priority_queue<int> pq_max;pq_max.push(10);pq_max.push(20);pq_max.push(30);pq_max.push(40);while (!pq_max.empty()){cout << pq_max.top() << " ";pq_max.pop();}cout << endl;std::priority_queue<int,vector<int>,greater<int>> pq_min;pq_min.push(10);pq_min.push(20);pq_min.push(30);pq_min.push(40);while (!pq_min.empty()){cout << pq_min.top() << " ";pq_min.pop();}cout << endl;return 0;
}

输出

40 30 20 10
10 20 30 40

📌 5. 实际应用场景:任务调度与路径搜索

✨5.1 优先级队列在任务调度中的应用

在任务调度中,priority_queue 可以用来根据任务优先级调度任务。例如,操作系统内核中的进程管理通常需要根据优先级选择任务执行。可以使用 priority_queue 来存储任务,每次从队列中取出最高优先级的任务执行。

✨ 5.2 deque 在滑动窗口问题中的应用

deque 因其双端特性,被广泛用于解决滑动窗口问题。例如,在一个数组中找到滑动窗口的最大值,可以通过 deque 快速实现。每当窗口向前滑动时,使用 dequepush_backpop_front 可以高效地更新窗口中的最大值。


📌 6. 总结与常见问题解答

通过本文的介绍,我们全面了解了 priority_queuedeque 的实现与应用场景。以下是一些常见问题解答:

✨ 6.1 常见问题

  1. dequevector 的区别是什么?

    • deque 支持在两端高效插入和删除,而 vector 仅支持尾部的快速插入与删除。
  2. 为什么 priority_queue 默认使用 vector

    • priority_queue 主要关注堆操作的效率,而 vector 是一个连续内存容器,适合在堆排序中实现高效的随机访问。
  3. deque 可以用在 priority_queue 中吗?

    • 可以,priority_queue 支持以 deque 为底层容器,但因为 priority_queue 中通常不需要双端操作,因此更常使用 vector

总结

本文介绍了 C++ 中的 priority_queuedeque 容器,分别适合实现优先级调度和双端队列操作。priority_queuedeque 在实际应用中扮演着重要角色,为各种算法和数据处理提供了高效、简洁的解决方案。希望本篇内容能帮助您更好地理解 C++ 容器的灵活性,并在项目中合理使用这些数据结构。
参考链接:C/C++ Reference

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

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

相关文章

SpringMVC学习笔记(一)

一、SpringMVC的基本概念 &#xff08;一&#xff09;三层架构和MVC 1、三层架构概述 我们的开发架构一般都是基于两种形式&#xff0c;一种是 C/S 架构&#xff0c;也就是客户端/服务器&#xff0c;另一种是 B/S 架构&#xff0c;也就是浏览器服务器。在 JavaEE 开发中&…

Jav项目实战II基于微信小程序的助农扶贫的设计与实现(开发文档+数据库+源码)

目录 一、前言 二、技术介绍 三、系统实现 四、文档参考 五、核心代码 六、源码获取 全栈码农以及毕业设计实战开发&#xff0c;CSDN平台Java领域新星创作者&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。获取源码联系方式请查看文末 一、前言 在当前社会…

Ubuntu安装ollama,并运行ollama和通义千问,使用gradio做界面

Ubuntu安装ollama&#xff0c;并运行ollama和通义千问 安装ollama方式一&#xff1a;方式二 下载安装模型运行大模型运行ollama服务前端的实现python环境安装修改pip国内源前端页面搭建测试前后端联通设计完整的ui 安装ollama 方式一&#xff1a; 访问网站连接&#xff0c;选…

对接阿里云实人认证

对接阿里云实人认证-身份二要素核验接口整理 目录 应用场景 接口文档 接口信息 请求参数 响应参数 调试 阿里云openApi平台调试 查看调用结果 查看SDK示例 下载SDK 遇到问题 本地调试 总结 应用场景 项目有一个提现的场景&#xff0c;需要用户真实的身份信息。 …

C++ 的发展

目录 C 的发展总结&#xff1a;​编辑 1. C 的早期发展&#xff08;1979-1985&#xff09; 2. C 标准化过程&#xff08;1985-1998&#xff09; 3. C 标准演化&#xff08;2003-2011&#xff09; 4. C11&#xff08;2011年&#xff09; 5. C14&#xff08;2014年&#xf…

蓝桥杯——数组

1、移动数组元素 package day3;import java.util.Arrays;public class Demo1 {public static void main(String[] args) {int[] arr {1,2,3,4,5,6};int k 2;int[] arr_new f(arr,k);for (int i : arr_new) {System.out.print(i",");}//或System.out.println();St…

六自由度双足机器人运动控制

最近迷上了研究机器人&#xff0c;花了很多时间研究机器人的控制和交互。先后开发出来了四足四自自由度&#xff0c;四足八自由度&#xff0c;两足四自由度&#xff0c;两足六自由度机器人&#xff0c;并为他们开发了相应的大模型语音交互。通过努力&#xff0c;既锻炼了动手组…

超好用shell脚本NuShell mac安装

利用管道控制任意系统 Nu 可以在 Linux、macOS 和 Windows 上运行。一次学习&#xff0c;处处可用。 一切皆数据 Nu 管道使用结构化数据&#xff0c;你可以用同样的方式安全地选择&#xff0c;过滤和排序。停止解析字符串&#xff0c;开始解决问题。 强大的插件系统 具备强…

第9章 DIV+CSS布局作业

html代码 <!DOCTYPE html> <html><head><meta charset"utf-8"><title>服务中心</title><link type"text/css" href"../css/322-1.css" rel"stylesheet"/></head><body><di…

nginx源码安装配置ssl域名

nginx源码安装 下载 wget http://nginx.org/download/nginx-1.24.0.tar.gz 解压 tar -zxvf nginx-1.24.0.tar.gz 下载openssl apt install openssl 安装nginx cd nginx-1.24.0 sudo apt-get install libpcre3 libpcre3-dev ./configure --prefix=/home/nginx24 --with-http_ss…

【Linux:IO多路复用(select、poll函数)

目录 什么是IO多路复用&#xff1f; select: 参数介绍&#xff1a; select函数返回值&#xff1a; fd_set类型&#xff1a; 内核如何更新集合中的标志位 处理并发问题 处理流程的步骤&#xff1a; poll: poll的函数原型&#xff1a; 参数介绍&#xff1a; select与p…

容器内的Jenkins使用docker部署服务,服务数据文件挂载问题

问题 docker 容器运行服务更推荐是那种无状态的服务&#xff0c;这样可以做到 “ 开箱即用 ”&#xff0c;需要持久化存储的话使用存储卷挂载数据库文件即可&#xff0c;这都是基于在宿主机上执行的&#xff1b; 现在Jenkins是在docker容器中运行&#xff0c;并需要使用docker部…

六、volatile

volatile 能保证内存可⻅性 运行下面的例子&#xff1a; package Demo03;import java.util.Scanner;public class demo01 {private static int flag 0;public static void main(String[] args) {Thread t1 new Thread(() -> {while (flag 0) {}System.out.println(&quo…

LSTM(长短期记忆网络)详解

1️⃣ LSTM介绍 标准的RNN存在梯度消失和梯度爆炸问题&#xff0c;无法捕捉长期依赖关系。那么如何理解这个长期依赖关系呢&#xff1f; 例如&#xff0c;有一个语言模型基于先前的词来预测下一个词&#xff0c;我们有一句话 “the clouds are in the sky”&#xff0c;基于&…

Servlet⽣生命周期超级细(笔记)

简介: 讲解Servlet的⽣生命周期 Servlet 接⼝口⾥里里⾯面有5个⽅方法&#xff0c;其中三个⽣生命周期⽅方法和两个普通⽅方法 1. 加载和初始化阶段 过程&#xff1a; 当一个 Servlet 第一次被客户端请求时或者服务器启动时&#xff0c;Servlet 容器会加载该 Servlet 类&…

HBuilder(uniapp) 配置android模拟器

HBuilder&#xff08;uniapp&#xff09; 配置android模拟器 选择完成之后&#xff0c;点击ok&#xff0c;再次点击Configure—》AVD Manager

基于麒麟服务器操作系统V10版本,部署Nginx服务、MySql服务搭建PHP环境,实现静态网站平台的搭建。

一、环境准备 关闭防火墙。 查看当前防火墙的状态 systemctl status firewalld Copy 如果防火墙的状态参数是inactive,则防火墙为关闭状态。 如果防火墙的状态参数是active,则防火墙为开启状态。 关闭防火墙。 如果您想临时关闭防火墙,需要运行以下命令: systemctl…

用OMS进行 OceanBase 租户间数据迁移的测评

基本概念 OceanBase迁移服务&#xff08;&#xff0c;简称OMS&#xff09;&#xff0c;可以让用户在同构或异构 RDBMS 与OceanBase 数据库之间进行数据交互&#xff0c;支持数据的在线迁移&#xff0c;以及实时增量同步的复制功能。 OMS 提供了可视化的集中管控平台&#xff…

Hadoop生态圈框架部署(六)- HBase完全分布式部署

文章目录 前言一、Hbase完全分布式部署&#xff08;手动部署&#xff09;1. 下载Hbase2. 上传安装包3. 解压HBase安装包4. 配置HBase配置文件4.1 修改hbase-env.sh配置文件4.2 修改hbase-site.xml配置文件4.3 修改regionservers配置文件4.4 删除hbase中slf4j-reload4j-1.7.33.j…

108. UE5 GAS RPG 实现地图名称更新和加载关卡

在这一篇里&#xff0c;我们将实现对存档的删除功能&#xff0c;在删除时会有弹框确认。接着实现获取玩家的等级和地图名称和存档位置&#xff0c;我们可以通过存档进入游戏&#xff0c;玩家在游戏中可以在存档点存储存档。 实现删除存档 删除存档需要一个弹框确认&#xff0…