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、max-heap、つまり最大要素 (弱い順序付けで定義されている) を最初にポップするヒープを実装しているためです。

最小ヒープ (要素を最小から最大にポップするもの) を実装する場合は、比較関数を逆にする必要があります。つまり、順序に従ってtrueいる場合にのみ返されます。a > b

于 2013-08-05T19:56:10.743 に答える