Bestell Problem während von priority_queue knallen, Ist das ein Bug mit std :: priority_queue

Question

#include <functional> 
#include <queue> 
#include <vector> 
#include <iostream> 

struct Temp 
{ 
    int p; 
    std::string str; 
}; 

struct TempCompare 
{ 
    bool operator()(Temp const & a, Temp const & b) 
    { 
     return a.p > b.p; 
    } 
}; 

int main() { 

    std::priority_queue<Temp, std::vector<Temp>, TempCompare> pq; 
    //Enable and Disable the following line to see the different output 
    //{Temp t; t.p=8;t.str="str1";pq.push(t);} 
    {Temp t; t.p=8;t.str="str2";pq.push(t);} 
    {Temp t; t.p=9; t.str="str1";pq.push(t);} 
    {Temp t; t.p=9; t.str="str2";pq.push(t);} 

    while(!pq.empty()) 
    { 
     std::cout << pq.top().p << " " << pq.top().str << std::endl; 
     pq.pop(); 
    } 
} 

Führen Sie das obige Programm mit der Aktivierung und die vierte Zeile in Haupt deaktivieren; Die Ausgabe erhalten Sie, wenn ihre behinderten

8 str2 
9 str1 
9 str2 

ist, während, wenn sein Sie

erhalten aktivierter

8 str1 
8 str2 
9 str2 
9 str1 

Shouldnt das Verhalten im Einklang?

Answer 1

Nein. Es gibt keinen Grund für ein konsistentes Verhalten. Temp{9, "str1"} und Temp{9,"str2"} sind entsprechend Ihrer Vergleichsfunktion gleich, so dass sie in beliebiger Reihenfolge zurückgegeben werden. Das Hinzufügen verschiedener Elemente zur Warteschlange ändert diese Reihenfolge sehr wahrscheinlich.

Wenn Sie möchten, dass sie in einer konsistenten Reihenfolge zurückgegeben werden, müssen Sie die Vergleichsfunktion erweitern. Der einfachste Weg,

 bool operator()(Temp const & a, Temp const & b) 
    { 
     return std::tie(a.p,a.str) > std::tie(b.p,b.str); 
    } 

ist Wenn Sie „in p absteigend, aber aufsteigend in str“ wollen, müssen Sie es selbst tun.