1

我的 priority_queue 是倒序排列的，我不明白为什么。这是来自cplusplus.com

表达式 comp(a,b)，其中 comp 是这种类型的对象，a 和 b 是容器中的元素，如果在函数定义的严格弱排序中认为 a 在 b 之前，则应返回true 。

现在在我的 Comparator 的类 operator() 函数中，如果 a 小于 b，a 应该在 b 之前。因此，如果 a 小于 b，我返回 true。但是最后我得到了序列“321”，但我期望的是“123”！

#include <iostream>
#include <queue>
using namespace std;

class Number{
    int x;
public:
    Number(int _x):x(_x){}
    int getX()const{return x;}
};

class Comparator{
public:
    bool operator()(const Number& a,const Number& b){
        if (a.getX()<b.getX()){
            return true;
        } else {
            return false;
        }
    }
};

int main(){
    priority_queue<Number,vector<Number>,Comparator> pq;
    pq.push(2);
    pq.push(1);
    pq.push(3);

    while (!pq.empty()){
        cout<<pq.top().getX();
        pq.pop();
    }

    return 0;
}
4

2 回答 2

9

该网站还说：

根据这种严格的弱排序，弹出的元素是最后一个

所以元素以弱排序的相反顺序弹出。这是因为priority_queue实现了一个最大堆，即首先弹出最大元素（由弱排序定义）的堆。

如果你想实现一个最小堆（一个将元素从最小值弹出到最大值的堆），你需要让你的比较函数做相反的事情，即true当且仅当a > b根据你的排序返回。

于 2013-08-05T19:56:10.743 回答
1

尝试改变你的Comparator：

class Comparator{
public:
    bool operator()(const Number& a,const Number& b){
        if (a.getX()<b.getX()){
            return true;
        } else {
            return false;
        }
    }
};

对于这样的事情：

struct Comparator { 
    bool operator()(Number const &a, Number const &b) { 
        return b.getX() < a.getX();
    }
};

至少对我来说，你Number看起来也很可疑。我想我可能会完全消除它，直接使用int。如果由于某种原因您坚持使用一个类，我会考虑支持转换为int：

class Number {
    int x;
public:
    Number(int x) : x(x) {}
    operator int() const { return x; }
};

...这将类简化Comparator为：

class Comparator { 
    bool operator()(Number const &a, Number const &b) { 
        return b < a;
    }
};

...但这等效于std::greater，因此您不妨直接使用它，以便您的集合定义如下所示：

priority_queue<Number,vector<Number>, greater<Number> > pq;
于 2013-08-05T20:19:01.867 回答