从priority_queue弹出时排序问题,这是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();
    }
}

运行上面的程序,启用和禁用main中的第四行; 禁用时获得的输出

8 str2
9 str1
9 str2

而当它启用时你会得到

8 str1
8 str2
9 str2
9 str1

这种行为不一致吗？

Answer 1

没有.行为没有理由保持一致. Temp{9, "str1"}并且Temp{9,"str2"}根据您的比较函数是相等的,因此它们以任意顺序返回.向队列添加不同的元素很可能会改变该顺序.

如果希望以一致的顺序返回它们,则需要扩展比较功能.最简单的方法是

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

如果你想"下降p,但要上升str",你必须自己做.