CODEWITHSUNDEEP
c++structpriority-queue
LKM
LKM

Reputation: 2450

C++ Priority Queue with Struct

I'm using Priority Queue with Struct

my struct is Node below : 

struct Node{
int level;
int bound;
int total;};

And my priority queue is below : 

    std::priority_queue<Node> pq;

What I want to do is to sort my priority queue(pq) as the value of Node.bound so that the Node object whose value of bound is the maximum is at the top of priority queue.

What I found that I have to overload the method 'operator'

So I did it as below

bool operator<(Node const& lhs, Node const& rhs) {
return lhs.bound < rhs.bound;}

After I overload that method, pq sorted node objects but there are some often exceptions that 271,268,267,261,268,249,255,260,246,256 that 271 is the top value of pq.

What should I do to solve this situation? I think if I solve this, I could solve my problem perfectly!

Upvotes: 0

Views: 1946

Answers (1)

Loki Astari
Loki Astari

Reputation: 264401

The priority queue keeps the top element (the one it is about to pop) as the first element. The other elements are in an unspecified order.

I am betting the default implementation is to use a heap structure underneath the covers to make it as efficient as possible. Which is why the elements seem to be in a random order.

Note this is why std::priority_queue interface only allows you to pop() elements and does not provide random access to the elements in the queue.

Additional note: The order of the priority queue is defined by the third template parameter. If you do not define this it defaults to std::less which by default will use operator< to do the comparison.

Upvotes: 1

Related Questions