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

news/2024/11/17 20:08:00/

个人主页: 起名字真南的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.ppmy.cn/news/1547797.html

相关文章

STM32设计防丢防摔智能行李箱

目录 目录 前言 一、本设计主要实现哪些很“开门”功能&#xff1f; 二、电路设计原理图 1.电路图采用Altium Designer进行设计&#xff1a; 2.实物展示图片 三、程序源代码设计 四、获取资料内容 前言 随着科技的不断发展&#xff0c;嵌入式系统、物联网技术、智能设备…

HarmonyOS开发 API 13发布首个Beta版本,解决了哪些问题?

HarmonyOS 5.0.1 Beta3&#xff0c;是HarmonyOS开发套件基于API 13正式发布的首个Beta版本。该版本在OS能力上主要增强了C API的相关能力&#xff0c;多个特性补充了C API供开发者使用。HarmonyOS 5.0.1 Beta3完整配套信息如下&#xff1a; 已解决的问题 DevEco Studio 5.0.…

Html Area 图像映射可点击区域 实现响应式图像映射

Html Area 图像映射可点击区域 实现响应式图像映射 主要实现了图片的分区域点击&#xff0c;可以自定义点击的区域&#xff0c;根据点击的位置不同&#xff0c;执行不同的方法或者跳转不同的网页 介绍 引用w3school的Demohttps://www.w3school.com.cn/tags/tag_area.asp#googl…

安装paddle

网址&#xff1a;飞桨PaddlePaddle-源于产业实践的开源深度学习平台 或者找对应python和cuda版本的paddle下载后安装&#xff1a; https://www.paddlepaddle.org.cn/whl/linux/mkl/avx/stable.html 你想要安装paddlepaddle - gpu2.6.1.post112版本。在你提供的文件列表中&am…

蚂蚁金服-OceanBase-测试开发工程师-面经

一面(15:00~16:20 110min) 面试(15:00~15:56) 一面是两个面试官面试&#xff0c;对数据库底层原理&#xff0c;毕业设计和项目流程进行了狠狠的拷打&#xff0c;最终进行了一道sql和一道算法的笔试&#xff0c;笔者觉得总体面试很偏底层&#xff0c;感觉答的很一般。 自我介…

⾃动化运维利器 Ansible-最佳实战

Ansible-最佳实战 一、ansible调试二、优化 Ansible 执行速度2.1 设置 SSH 为长连接2.1.1 设置 ansible 配置⽂件2.1.2 建⽴⻓连接并测试 2.2 开启 pipelining2.2.1 在 ansible.cfg 配置⽂件中设置 pipelining 为 True2.2.2 配置被控主机的 /etc/sudoers 文件 2.3 设置 facts 缓…

ODC 如何精确呈现SQL耗时 | OceanBase 开发者工具解析

前言 在程序员或DBA的日常工作中&#xff0c;编写并执行SQL语句如同日常饮食中的一餐一饭&#xff0c;再寻常不过。然而&#xff0c;在使用命令行或黑屏客户端处理SQL时&#xff0c;常会遇到编写难、错误排查缓慢以及查询结果可读性不佳等难题&#xff0c;因此&#xff0c;图形…

行业类别-智能制造-子类别工业4.0-细分类别物联网应用-应用场景智能工厂建设

1.大纲分析 针对您提出的题目“4.0 行业类别-智能制造-子类别工业4.0-细分类别物联网应用-应用场景智能工厂建设”&#xff0c;以下是一个详细的大纲分析&#xff0c;旨在深入探讨该应用场景下的各个方面&#xff1a; 一、引言 智能制造与工业4.0概述 智能制造的定义与发展趋…