So verstehen Sie den Operator "größer als/kleiner als" im Komparator des C++ - Queue-Containers intuitiv

Question

Ich bin immer verwirrt, wenn ich den Komparator für einen Container für die Prioritätswarteschlange definiere und weiß nicht, wie ich ihn verstehen soll. Zum Beispiel habe ich eine vector von pair<int,int>, wo ich die Paare absteigend durch seinen zweiten Feldwert sortieren möchte.

So sieht die Codes wie folgt aus:

struct Compare 
    { 
     bool operator()(pair<int,int> const &p1, pair<int,int> const &p2) const 
     { 
      return p1.second < p2.second; 
     } 
    }; 



priority_queue<pair<int,int>,vector<pair<int,int> >, Compare> pqueue; 

Wie die Betreiber verstehen "<" hier, weil ich dachte, es ">" das erste Mal sein sollte, und es musste auf Basis ändern auf das Ergebnis. Warum ist es "<" für absteigende Reihenfolge anstelle von ">"? Ich will es beim nächsten Mal einfach bei der ersten Aufnahme richtig machen, wenn ich priority_queue benutze. Vielen Dank.

Answer 1

Prioritätswarteschlange gibt die oben Element basierend auf dem Vergleichsoperator, was bedeutet, dass, wenn Sie die Elemente nacheinander abrufen, können Sie sie in absteigend Bestellung erhalten.

Die Bedeutung des Vergleichsoperators bleibt immer „kleiner als“, was bedeutet, dass, wenn compare(A, B) wahr ist, B höhere Priorität als A hat, und würde früher aus der Prioritätswarteschlange zurückgegeben werden.

Das Invertieren der Vergleichsfunktion kehrt die Reihenfolge um, in der Sie die Elemente aus Ihrer Prioritätswarteschlange erhalten. Bei Verwendung von > anstelle von < wird die Reihenfolge umgekehrt in aufsteigend geändert.

Answer 2

In gewisser Weise ist es richtig, dass Sie sich ein wenig verunsichert fühlen, weil wir höhere Werte mit höchster Priorität assoziieren könnten, was kontraintuitiv sein könnte.

In einer Prioritätswarteschlange wird jedoch normalerweise angenommen, dass die Prioritätsreihenfolge vom niedrigsten Wert zum höchsten Wert geht. Das heißt, das minimale Element des Sets hat die höchste Priorität und so weiter.

Ich denke, der intuitive Grund für diese "Inversion" hängt mit der Tatsache zusammen, dass viele gierige Algorithmen niedrigeren Kosten höhere Priorität einräumen, und um dies zu bewältigen, können diese Algorithmen eine Prioritätswarteschlange verwenden.