CODEWITHSUNDEEP
c++c++11stlstdpriority-queue
rkb
rkb

Reputation: 11231

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

#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();
    }
}

Run the above program with enabling and disabling the fourth line in main; The output you get when its disabled is

8 str2
9 str1
9 str2

whereas when its enabled you get

8 str1
8 str2
9 str2
9 str1

Shouldnt the behavior be consistent?

Upvotes: 4

Views: 380

Answers (1)

Martin Bonner supports Monica
Martin Bonner supports Monica

Reputation: 29017

No. There is no reason for the behaviour to be consistent. Temp{9, "str1"} and Temp{9,"str2"} are equal according to your comparison function, so they get returned in an arbitrary order. Adding different elements to the queue is quite likely to change that order.

If you want them returned in a consistent order, you need to extend the comparison function. The simplest way is

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

If you want "descending in p, but ascending in str", you'll have to do it yourself.

Upvotes: 8

Related Questions