C++中优先级队列自定义排序异常

Question

我浏览了几篇 Whosebug 和 Codeforces 文章，了解如何在 C++ 中自定义排序优先级队列。默认情况下，C++ 实现是 MaxHeap ，因此它将按降序输出元素。我稍微调整一下，添加 greater<int> 会向上弹出。我使用自己的比较器函数对此进行了尝试，如下所示：

#include<bits/stdc++.h>
using namespace std;
class comp{
    public:
bool operator()(const int &a,const int &b){
        return a>b;
    }
};
int main(){
    priority_queue<int,vector<int>,comp> pq;
    pq.push(5);
    pq.push(1);
    pq.push(8);
    while(!pq.empty()){
        cout<<pq.top()<<" ";
        pq.pop();
    }
    return 0;
}

这给出了预期的输出：1 5 8

但如果我将其更改为：

#include<bits/stdc++.h>
using namespace std;
class comp{
    public:
bool operator()(const int &a,const int &b){
        if(a>b)
            return true;
    }
};
int main(){
    priority_queue<int,vector<int>,comp> pq;
    pq.push(5);
    pq.push(1);
    pq.push(8);
    while(!pq.empty()){
        cout<<pq.top()<<" ";
        pq.pop();
    }
    return 0;
}

输出变为：8 1 5

不知何故我无法得到这个，非常感谢任何帮助。

Answer 1

我建议您阅读编译器警告...您会看到 bool operator()(const int &a,const int &b) 如果 a<=b 没有 return 语句...这就是未定义行为

你应该这样做：

#include<bits/stdc++.h>
using namespace std;
class comp{
    public:
    bool operator()(const int &a,const int &b){
        if(a>b)
            return true;
        /* else */ return false;
    }
};
int main(){
    priority_queue<int,vector<int>,comp> pq;
    pq.push(5);
    pq.push(1);
    pq.push(8);
    while(!pq.empty()){
        cout<<pq.top()<<" ";
        pq.pop();
    }
    return 0;
}

C++中优先级队列自定义排序异常

Anomaly in Priority Queue Custom Sort in C++

c++

queue

priority-queue

minmax-heap