admin管理员组

文章数量:1623789

文章目录

    • 1、优先队列（priority_queue）的定义
      • （1）priority_queue 在头文件中的定义
      • （2）priority_queue 声明
    • 2、元素自定义类型的优先队列（priority_queue）
    • 3、优先队列（priority_queue）的主要成员函数
      • （1）优先队列主要的三个成员函数
      • （2）注意
      • （3）用法示例
    • 4、优先队列（priority_queue）的应用
      • 丑数（Ugly Numbers，Uva 136）
        • 题目描述
        • 问题分析
        • 代码

1、优先队列（priority_queue）的定义

优先队列是一种抽象数据类型，其元素根据优先级被读取。

（1）priority_queue 在头文件中的定义

运用 priority_queue， 必须声明请头文件：#include <queue>。
在头文件 <queue> 中，class priority_queue 定义如下：

namespace std{
   
	template < class T,
			   class Container = vector<T>,
			   class Compare = less<typename Container :: value_type>
	class priority_queue;
}

第一个 template 参数是元素型别，带有默认值的第二个 template 参数定义了 priority queue 内部用来存放元素的容器。缺省容器是 vector 。带有默认值的第三个 template 参数定义出“用以搜寻下一个最高优先元素”的排序准则。缺省情况下是以 operator< 作为比较标准。

（2）priority_queue 声明

如声明一个元素类型为整型的 priority_queue：priority_queue<int> pq，pq 是一个“越小的整数优先级越低的优先队列”。

2、元素自定义类型的优先队列（priority_queue）

自定义类型也可以组成优先队列，但 必须为每个元素定义一个优先级。这个优先级并不需要一个确定的数字，只需要能比较大小即可。所以，只要元素定义了“小于”运算符，就可以使用优先队列。
在一些特殊情况下，需要自定义方式比较优先级，例如，要实现“个位数大的整数优先级反而小”的优先队列，可以定义一个结构体cmp，重载()运算符；使其“看上去”像一个函数，然后用priority_queue<int, vector<int>, cmp> pq的方式定义。cmd定义如下：

struct cmp{
   
	bool operator() (const int a, const int b) const {
   
		// a 的优先级比 b 小时返回 true
		return a % 10 < b

本文标签： 队列stlpriorityqueue

版权声明：本文标题：STL之优先队列priority_queue（C++） 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dianzi/1728896126a1178431.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。