Warum kann ich den Komparator nicht innerhalb des Knotens setzen?

Question

Ich verwende priority_queue, um ein Problem zu lösen. Ich beabsichtige, meinen Knoten folgendermaßen zu deklarieren.

struct node{ 
     int x, y, val; 
     node(int _x, int _y, int _val){ 
      x = _x; 
      y = _y; 
      val = _val; 
     } 
     bool operator < (const node& rhs) const{ 
      return val > rhs.val; 
     } 
    }; 

und es auf folgende Weise verwenden:

priority_queue<node, vector<node>, node> queue; 

Aber es funktioniert nicht.

Dann wechsle ich auf einen anderen Weg. Es klappt.

Ich weiß nicht, warum es einen Unterschied gibt. Jeder Rat wäre großartig.

In Anbetracht der folgenden Antwort, ich habe verschiedene Wege versucht, meinen Code auszuführen, sie funktioniert:

Version 1

struct node{ 
     int x, y, val; 
     node(int _x, int _y, int _val){ 
      x = _x; 
      y = _y; 
      val = _val; 
     } 
     node(){} 

     bool operator() (const node& lhs, const node& rhs) const{ 
     return lhs.val > rhs.val; 
    } 
}; 

priority_queue<node, vector<node>, node> queue; 

Version 2:

struct node{ 
     int x, y, val; 
     node(int _x, int _y, int _val){ 
      x = _x; 
      y = _y; 
      val = _val; 
     } 
    bool operator < (const node& rhs) const{ 
     return val > rhs.val; 
    } 

}; 
priority_queue<node, vector<node>, less<node>> queue; 
//or 
//priority_queue<node, vector<node>> queue; 
//or 
//priority_queue<node> queue; 

Answer 1

node ist nicht standardmäßig konstruierbar und es hat keine operator()

Seit y Verwenden Sie operator<, müssen Sie den Vergleicher nicht angeben, da der Standardwert std::less<T> ist, der es verwendet, wenn es verfügbar ist. Und wenn Sie keinen Komparator angeben müssen, gibt es keinen Grund, einen Container anzugeben, da std::vector<T> bereits der Standardwert ist.

priority_queue<node, vector<node>, less<node>> queue; 
// same as 
priority_queue<node, vector<node>> queue; 
// also same as 
priority_queue<node> queue; 

Answer 2

Die priority_queue wörtlich nennt com(arg1, arg2) während seiner Bewertung.

Diese Funktion muss entweder als Funktionsobjekt (wie in Ihrem Beispiel funktioniert), als statische Funktion oder als Lambda verfügbar sein. Ihre erste struct hat keine von diesen.

Answer 3

Im ersten Fall ist node ein nicht Komparator als solche — stattdessen es eine Überlastung für operator< bietet, so dass Sie diese verwenden sollten:

priority_queue<node, vector<node>> queue; 

ohne drittes Argument. Das sollte funktionieren.

Beachten Sie, dass ein Komparator ist eine, die als aufgerufen werden kann:

cmp(x,y) 

Also in diesem Sinne, Ihre Klasse node nicht unterstützt, dass — es jedoch unterstützt dies:

x < y 

ist eine andere Sache, und als solche kann mit dem Standardkomparator std::less<T> verwendet werden, von std::priority_queue verwendet.

Answer 4

Da das dritte Vorlageargument nur das Format compareFunction (objA, objB) akzeptiert.Standardmäßig ist es class Compare = std::less<typename Container::value_type>, die der std :: less den Operator <() aufruft.

Der folgende Code sollte

std::priority_queue<node, std::vector<node>> queue;