Deklarieren einer priority_queue in c ++ mit einem benutzerdefinierten Komparator

84

Ich versuche, a zu deklarieren priority_queue of nodesund bool Compare(Node a, Node b)als Komparatorfunktion zu verwenden (die außerhalb der Knotenklasse liegt).

Was ich derzeit habe, ist:

priority_queue<Node, vector<Node>, Compare> openSet;

Aus irgendeinem Grund bekomme ich Error: "Compare" is not a type name

Ändern der Deklaration in priority_queue <Node, vector<Node>, bool Compare>

gibt mir Error: expected a '>'

Ich habe auch versucht:

priority_queue<Node, vector<Node>, Compare()> openSet;
priority_queue<Node, vector<Node>, bool Compare()> openSet;
priority_queue<Node, vector<Node>, Compare<Node, Node>> openSet; 

Wie soll ich meine richtig deklarieren priority_queue?

Steven Morad
quelle

Antworten:

110

Sie sollten eine Klasse deklarieren Compareund operator()dafür wie folgt überladen :

class Foo
{

};

class Compare
{
public:
    bool operator() (Foo, Foo)
    {
        return true;
    }
};

int main()
{
    std::priority_queue<Foo, std::vector<Foo>, Compare> pq;
    return 0;
}

Oder wenn Sie es aus bestimmten Gründen nicht als Klasse schaffen, können Sie std::functiones verwenden:

class Foo
{

};

bool Compare(Foo, Foo)
{
    return true;
}

int main()
{
    std::priority_queue<Foo, std::vector<Foo>, std::function<bool(Foo, Foo)>> pq(Compare);
    return 0;
}
Awesoon
quelle
1
Perfekt, genau das, wonach ich gesucht habe. Ich hätte nie gedacht, eine eigene Klasse zu bilden. Wäre das erste Beispiel ein besserer Stil?
Steven Morad
2
@StevenMorad, ich bevorzuge die Verwendung von Klassen mit überladenen operator(), es sieht einfacher aus.
Awesoon
1
@soon Warum überladen wir den Operator ()? Ist dies damit verbunden, wie priority_queues intern implementiert werden? Überladen> oder <macht intuitiv Sinn, aber () Operator nicht so sehr
Piyush
2
@Piyush, die Frage ist über die Übergabe eines benutzerdefinierten Komparators an die pritority_queue. Es ist jedoch möglich, den operator<eingebauten std::lessKomparator zu überladen und zu verwenden , der bool Compare(Node a, Node b)außerhalb der Klasse deklariert ist Node.
Awesoon
1
Ich komme immer wieder auf diese Antwort zurück, wahrscheinlich wie jetzt 50 Mal. Ich kann mich nie an die Syntax erinnern
Rockstar5645
48

Die akzeptierte Antwort lässt Sie glauben, dass Sie eine Klasse oder eine verwenden müssen std::function als Vergleich verwenden müssen. Das ist nicht wahr! Wie die Antwort von cute_ptr zeigt, können Sie dem Konstruktor einen Funktionszeiger übergeben. Die Syntax dafür ist jedoch viel einfacher als dort gezeigt:

class Node;
bool Compare(Node a, Node b);

std::priority_queue<Node, std::vector<Node>, decltype(&Compare)> openSet(Compare);

Das heißt, es ist nicht erforderlich, den Funktionstyp explizit zu codieren. Sie können dies vom Compiler für Sie tun lassen decltype .

Dies ist sehr nützlich, wenn der Komparator ein Lambda ist. Sie können den Typ eines Lambda nur auf andere Weise als mit angeben decltype. Zum Beispiel:

auto compare = [](Node a, Node b) { return a.foo < b.foo; }
std::priority_queue<Node, std::vector<Node>, decltype(compare)> openSet(compare);
Cris Luengo
quelle
1
Das ist fantastisch, ich frage mich, ob es hier mögliche Fallen (Probleme) gibt. Würde gerne sehen, dass diese Antwort mehr Sichtbarkeit und Diskussion bekommt.
Apollys unterstützt Monica
1
@Apollys: Ich benutze diese Methode regelmäßig (normalerweise Compareist es ein Lambda, für das es unmöglich ist, eine Erklärung zu schreiben), ich kenne keine Fallen.
Cris Luengo
Wenn Sie dies für eine Lambda-Funktion tun würden, wo würden Sie den Körper der Lambda-Funktion platzieren? Würden Sie speichern sie in einer Variable fvorher und ersetzen Sie dann Comparemit f?
Eric Auld
@EricAuld: Ja, Comparekann dort eine Lambda-Funktion sein, wie in auto Compare = [](){};. Aber Sie müssen verwenden decltype(Compare), anstatt decltype(&Compare).
Cris Luengo
Hallo Chris, das ist großartig. Ich habe nach einem Format gesucht, das mit decltype für priority_queue verwendet werden kann. Ohne eine Klasse zu deklarieren, hast du die perfekte Antwort gegeben! Vielen Dank!
Amanda Wang
16

Der dritte Vorlagenparameter muss eine operator()(Node,Node)überladene Klasse sein . Sie müssen also eine Klasse wie folgt erstellen:

class ComparisonClass {
    bool operator() (Node, Node) {
        //comparison code here
    }
};

Und dann verwenden Sie diese Klasse als dritten Vorlagenparameter wie folgt:

priority_queue<Node, vector<Node>, ComparisonClass> q;
Mic
quelle
13
Die Operatormethode muss öffentlich sein.
Knezi
Die dritte Vorlage muss keine Klasse sein. Dies kann der Typ einer Funktion sein.
Cris Luengo
Laut cpluplus : Dies kann ein Funktionszeiger oder ein Funktionsobjekt sein
Benav
9

Beantworten Sie Ihre Frage direkt:

Ich versuche, einen priority_queueder Knoten mit zu deklarierenbool Compare(Node a, Node b) as the comparator function

Was ich derzeit habe, ist:

priority_queue<Node, vector<Node>, Compare> openSet;

Aus irgendeinem Grund erhalte ich den Fehler:

"Compare" is not a type name

Der Compiler sagt Ihnen genau, was falsch ist: Es Comparehandelt sich nicht um einen Typnamen, sondern um eine Instanz einer Funktion, die zwei verwendet Nodesund a zurückgibt bool.
Sie müssen lediglich den Funktionszeigertyp angeben:
std::priority_queue<Node, std::vector<Node>, bool (*)(Node, Node)> openSet(Compare)

cute_ptr
quelle
Dies ist genau das, wonach ich suche, um eine Funktion in der Priority_queue-Deklaration zu geben, danke!
Amanda Wang
4

Man kann auch eine Lambda-Funktion verwenden.

auto Compare = [](Node &a, Node &b) { //compare };
std::priority_queue<Node, std::vector<Node>, decltype(Compare)> openset(Compare);
frei geboren
quelle
2

Falls dies jemandem hilft:

static bool myFunction(Node& p1, Node& p2) {}
priority_queue <Node, vector<Node>, function<bool(Node&, Node&)>> pq1(myFunction);
Mazhar MIK
quelle
2

Sie müssen zuerst den Vergleich definieren. Dafür gibt es drei Möglichkeiten:

  1. benutze Klasse
  2. benutze struct (das ist dasselbe wie class)
  3. Verwenden Sie die Lambda-Funktion.

Es ist einfach, class / struct zu verwenden, da es einfach zu deklarieren ist, schreiben Sie einfach diese Codezeile über Ihren ausführenden Code

struct compare{
  public:
  bool operator()(Node& a,Node& b) // overloading both operators 
  {
      return a.w < b.w: // if you want increasing order;(i.e increasing for minPQ)
      return a.w > b.w // if you want reverse of default order;(i.e decreasing for minPQ)
   }
};

Aufrufcode:

priority_queue<Node,vector<Node>,compare> pq;
Shivam Kumar Mishra
quelle
0

bevorzuge struct und es ist das, was std :: Greater macht

struct Compare {
  bool operator()(Node const&, Node &) {}
}
Canhua Li
quelle