priority_queue（c++ STL求讲解priority_queue<int, vector<int>, less<int> >）

本文目录

• c++ STL求讲解priority_queue, less >
• priority_queue的问题
• 能不能用哈希表（hash table)实现优先队列（priority queue)
• 什么是优先队列
• c++ priority_queue 的使用问题
• 怎么判断一个值在priority_queue中是否存在
• 《STL源码分析》中如何priority_queue使用greater函数对象
• C++ priority_queue问题

c++ STL求讲解priority_queue, less >

priority_queue是一个顺序容器适配器，其原型：
template 《class T, class Container = vector《T》,
class Compare = less《typename Container::value_type》 》 class priority_queue;
可见第二个vector《int》是其Container，即优先队列的基础容器是vector《int》，优先队列在vector《int》这一容器类型基础上实现。

priority_queue的问题

C++ Priority Queues(优先队列)
C++优先队列类似队列，但是在这个数据结构中的元素按照一定的断言排列有序。
empty() 如果优先队列为空，则返回真
pop() 删除第一个元素
push() 加入一个元素
size() 返回优先队列中拥有的元素的个数
top() 返回优先队列中有最高优先级的元素
...对不起，我看了下priority_queue的方法...还真的没有什么能简化的，他没begin也没end，只能pop出，然后一个一个的push_back，所以..认了吧

能不能用哈希表（hash table)实现优先队列（priority queue)

不行，hash table里面的元素是无序的。

Hash表本来就是按照内容存储，可以在确定散列函数的时候考虑优先级，一个思路是先将元素按优先级排序，根据散列函数自变量是优先级，按数值大小对应过去。

哈希表是不可以排序的，你可以查查哈希表的作用，概念等，哈希表是为了查找方便而设计的一种数据结构，它的排列是按照哈希函数计算得出的。具体内部的运行机制我也不知道。

扩展资料：

若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数，按这个思想建立的表为散列表。

对不同的关键字可能得到同一散列地址，即k1≠k2，而f(k1)=f(k2)，这种现象称为冲突（英语：Collision）。具有相同函数值的关键字对该散列函数来说称做同义词。

综上所述，根据散列函数f(k)和处理冲突的方法将一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称散列地址。

参考资料来源：百度百科-哈希表

什么是优先队列

优先队列(priority queue)普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高进先出 （largest-in，first-out）的行为特征。

c++ priority_queue 的使用问题

struct cmp {
bool operator()(node* a, node* b){
    // 你自己定义的比较方法
}
};

然后把 priority_queue《node*》 换成 priority_queue《node*,std::vector《node*》,cmp》 大概就行了（std::vector《node*》 是 priority_queue《node*》 底层使用的容器）

怎么判断一个值在priority_queue中是否存在

contains
public boolean contains(Object o)如果此队列包含指定的元素，则返回 true。更确切地讲，当且仅当此队列至少包含一个满足 o.equals(e) 的元素 e 时，才返回 true。
指定者：
接口 Collection《E》 中的 contains
覆盖：
类 AbstractCollection《E》 中的 contains
参数：
o - 要检查是否包含于此队列的对象
返回：
如果此队列包含指定元素，则返回 true

《STL源码分析》中如何priority_queue使用greater函数对象

首先查看手册，priority_queue的定义如下：

template《class T, class Container = std::vector《T》, class Compare = std::less《typename Container::value_type》》 class priority_queue;

然后继续看模板的三个参数的说明

—————————以下直接摘抄的—————

Template parameters

T    -    The type of the stored elements. The behavior is undefined if T is not the same type asContainer::value_type. (since C++17)    

Container    -    The type of the underlying container to use to store the elements. The container must satisfy the requirements of SequenceContainer, and its iterators must satisfy the requirements of LegacyRandomAccessIterator. Additionally, it must provide the following functions with the usual semantics:

• front()

• push_back()

• pop_back()

The standard containers std::vector and std::deque satisfy these requirements.

Compare    -    A Compare type providing a strict weak ordering.    

—————————以上直接摘抄的—————

故可知，使用priority_queue需要给三个类来实现模板，其中第三个类就是那个比较函数，你问的，为什么要priority_queue《int, vector《int》, greater《int》 》 q1;已经回答完毕。

另外，可以参考std::less的定义，更深入学习第三个类的含义。已附在引用部分，自行查阅。

std::priority_queue std::less

PS：第一个那家伙回答的什么东西！我本来是不想回答的。。。看见那家伙胡诌一气，气不过。

C++ priority_queue问题

#include《iostream》
#include《queue》
#include《vector》
using namespace std;
int main()
{
priority_queue《pair《int,int》,vector《pair《int,int》 》,greater《pair《int,int》 》 》 coll;
pair《int,int》 a(3,4);
pair《int,int》 b(3,5);
pair《int,int》 c(4,3);
coll.push(a);
coll.push(b);
coll.push(c);
while(!coll.empty())
{
cout《《coll.top().first《《“\t“《《coll.top().second《《endl;
coll.pop();
}
}