admin管理员组文章数量:1623797
priority_queue
模板
priority_queue 模板有 3 个参数,其中两个有默认的参数;
第一个参数是存储对象的类型(一个节点中存储的数据类型)
第二个参数是存储元素的底层容器(整个priority的形状)
第三个参数是函数对象,定义了一个用来决定元素顺序的断言(可理解为排序函数)
因此模板类型是:
template <typename T, typename Container=std::vector<T>, typename Compare=std::less<T>> class priority_queue
模板中第二个参数默认为vector容器,第三个参数默认为less<T>
less<T>是头文件function中的一个断言(类似的还有greater<T>)其中使用:
less<T>表示大的元素排在队列前面,是大堆顶
greater<T>表示小的元素排在队列前面,是小堆顶(如下)
用法举例
举个例子:我们希望用priority_queue存储一个同学的成绩、姓名和学号
那么第一个参数可以是:pair<int, pair<string, string>>
仍然选择vector作为底层容器,第二个参数:vector<pair<int, pair<string, string>>>
第三个参数是我们自己定义的比较函数compare
我们需要的priority_queue就长这样:
priority_queue<pair<int, pair<char, int>>, vector<pair<int, pair<char, int>>>, compare> grades;
我们希望在将学生的数据推入priority_queue的时候自动排好序,且成绩高的同学排在前面,那么需要一个能够构成小堆顶的compare,注意是小堆顶,因为最后排序的时候不断地将堆顶的元素和末尾的元素交换,即最小的一直被放到后面,形成降序排列。
struct compare{
template<typename T, typename U>
bool operator()(T const& left, U const&right){
return left.first < right.first;
}
};
将上面的left.first < right.first
改为left.first > right.first
就变成大堆顶了
常用操作
push(const T& obj):将obj的副本放到容器的适当位置,这通常会包含一个排序操作
push(T&& obj):将obj放到容器的适当位置,这通常会包含一个排序操作
emplace(T constructor a rgs…):通过调用传入参数的构造函数,在序列的适当位置构造一个T对象。为了维持优先顺序,通常需要一个排序操作
top():返回优先级队列中第一个元素的引用
pop():移除第一个元素
size():返回队列中元素的个数
empty():如果队列为空的话,返回true
swap(priority_queue& other):和参数的元素进行交换,所包含对象的类型必须相同
底层实现
priority_queue的底层实现是堆排序,如果不了解什么是堆排序可以看看这个视频–>堆排序(heapsort)
本文标签: priorityqueue
版权声明:本文标题:C++ priority_queue的用法 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dongtai/1728895625a1178370.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论