详解C++ STL priority_queue 容器
详解C++ STL priority_queue 容器
本篇随笔简单介绍一下\(C++STL\)中\(priority_queue\)容器的使用方法和常见的使用技巧。
priority_queue容器的概念
\(priority_queue\)在英文中是优先队列的意思。
队列是一种基本的数据结构。其实现的基本示意图如下所示:
而\(C++STL\)中的优先队列就是在这个队列的基础上,把其中的元素加以排序。其内部实现是一个二叉堆。所以优先队列其实就是把堆模板化,将所有入队的元素排成具有单调性的一队,方便我们调用。
priority_queue容器的声明
\(priority_queue\)容器存放在模板库:#include<queue>
里,使用前需要先开这个库。
这里需要注意的是,优先队列的声明与一般\(STL\)模板的声明方式并不一样。事实上,我认为其是\(C++STL\)中最难声明的一个容器。
大根堆声明方式:
大根堆就是把大的元素放在堆顶的堆。优先队列默认实现的就是大根堆,所以大根堆的声明不需要任何花花肠子,直接按\(C++STL\)的声明规则声明即可。
#include<queue>
priority_queue<int> q;
priority_queue<string> q;
priority_queue<pair<int,int> > q;
\(C++\)中的\(int,string\)等类型可以直接比较大小,所以不用我们多操心,优先队列自然会帮我们实现。但是如果是我们自己定义的结构体,就需要进行重载运算符了。关于重载运算符的讲解,请参考这篇博客:
小根堆声明方式
大根堆是把大的元素放堆顶,小根堆就是把小的元素放到堆顶。
实现小根堆有两种方式:
第一种是比较巧妙的,因为优先队列默认实现的是大根堆,所以我们可以把元素取反放进去,因为负数的绝对值越小越大,那么绝对值较小的元素就会被放在前面,我们在取出的时候再取个反,就瞒天过海地用大根堆实现了小根堆。
第二种:
小根堆有自己的声明方式,我们记住即可(我也说不明白道理):
priority_queue<int,vector<int>,greater<int> >q;
注意,当我们声明的时候碰到两个"<"或者">"放在一起的时候,一定要记得在中间加一个空格。这样编译器才不会把两个连在一起的符号判断成位运算的左移/右移。
priority_queue容器的使用方法
\(priority_queue\)容器的使用方法大致如下表所示:
用法 | 作用 |
---|---|
q.top() |
返回priority_queue的首元素 |
q.push() |
向priority_queue中加入一个元素 |
q.size() |
返回priority_queue当前的长度(大小) |
q.pop() |
从priority_queue末尾删除一个元素 |
q.empty() |
返回priority_queue是否为空,1为空、0不为空 |
注意:priority_queue取出队首元素是使用\(top\),而不是\(front\),这点一定要注意!!
相关文章
- [系统安全21]源码免杀、C++壳的编写
- C++ 关联容器
- 【C/C++学院】0829-位容器multimapmutisetString/算法函数兰不达表达式以及类重载/GPU编程
- C++容器使用经验总结(一)
- C++ vector容器的多种遍历方式
- Open3D (C++) 点云变换
- [C++ 面试基础知识总结] 关联容器
- [C++ 面试基础知识总结] 顺序容器
- Android C++基础--vector容器、queue队列、stack栈
- C++Qt 垂直布局 (QVBoxLayout)
- C++实现软件FIFO功能
- AI模型C++部署:ubuntu安装Cython并使用C/C++调用python动态库【附加c++与python互相调用算法demo程序接口的源码】
- C++容器适配器
- Visual Studio现已支持 C++ 开发容器
- PAT 1124 C++版
- PAT 1121 C++ 版
- 第十三届蓝桥杯国赛 C++ B 组 J 题——搬砖(AC)
- 区间合并(c++,java)
- C++Primer笔记——6.函数
- C++下GDAL的详细使用案例(含项目配置、tif读取为cv::Mat、Mat保存为tif)
- OpenCV5(C++)版本docker容器服务器配置分享