priority queue size is 0 but priority_queue top returns an element-CodePudding

I came across this weird behaviour of priority_queue in c while solving a leetcode puzzle . The priority_queue has a size of zero but on doing pq.top() it returns an element which is quite weird to me .

class Solution {
public:
    int lastStoneWeight(vector<int>& stones) {
        
        priority_queue <int> pq ;
        
        for(auto &it: stones){
            pq.push(it);
        }
           
        while(pq.size() >1){
            int x = pq.top(); pq.pop();
            int y = pq.top(); pq.pop();
         
            if(x>y){
                pq.push(x-y);
            }
            if(y> x){
                pq.push(y-x);
            }
        }
        
        cout <<"pq.size() is "<< pq.size() << endl;
        cout <<"pq.top() is "<< pq.top() << endl;
        if(pq.size() == 0){
            return 0;
        }
        return pq.top();
        
    }
};

When this code is run for input [2,2] this is what I get on doing cout . Note that i had two elements in priority_queue and i have popped out both elements .

pq.size() is 0
pq.top() is 2

CodePudding user response：

Doing pop operation on an empty priority queue is an undefined behaviour and it can give anything as output.

CodePudding user response：

As others have pointed out your code, specifically the second cout line, exhibits undefined behaviour. Why is that?

Have a look at what std::priority_queue's top does:

Reference to the top element as if obtained by a call to c.front()

(c here refers to the instance of the underlying container, which is std::vector by default).

std::vector::front() has this to say:

Returns a reference to the first element in the container.

Calling front on an empty container is undefined.

The rationale here is that top returns by const_reference and an empty container has no valid values it could refer to.

If you remove the second cout, your code will be fine.

A note on what value you get: This depends on the implementation of your compiler and the library that goes with it. As stated this is highly undefined behaviour. However, the typical implementation of a std::vector (remember, the underlying container) is to never release the allocated memory it uses. Even if you empty it.

So, since you are dealing with ints here, the last value that was at position 0 of the vector (i.e. front()) will be retuned despite having been destroyed. The destuction of an int is a noop, and the value remains unchanged in memory. It's still not a legal C program.