从 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);
     }

如果你想"descending in p, but ascending in str"，你必须自己做。

从 priority_queue 弹出时出现排序问题，这是 std::priority_queue 的错误吗

Ordering issue while popping from priority_queue, Is this a bug with std::priority_queue

c++

stl

std

priority-queue

c++11