STL priority_queue of pairs<int, struct> error

Question

Finding a shortest path in a grid and struggling to set up priority queue properly.

struct position{
    int row;
    int col;
    position* parent;
    position(int a, int b):row(a),col(b), parent(nullptr){}
};

vector<position>vec;


priority_queue<pair<int, position>, vector<pair<int, position>>, greater<pair<int, position>>>pq;

int distance = 0;
position *t = new p(0,0);

pq.push(make_pair(distance, t));

Getting this error:

no matching function for call to ‘std::priority_queue, std::vector >, std::greater > >::push(std::pair)’
     pq.push(make_pair(distance, t));

Answer 1

You need to write a functor ( or use a lambda) to compare the distance - position pair, std::greater won't automatically do it for you. Try this snippet:

struct position {
    int row;
    int col;
    position* parent;
    position(int a, int b) :row(a), col(b), parent(nullptr) {}
};

typedef std::pair<int, position> dist_pos_t;

class compare
{
public:
    bool operator()(const dist_pos_t& lhs, const dist_pos_t& rhs)
    {
        return rhs.first < lhs.first;
    }

};
std::priority_queue<dist_pos_t, std::vector<dist_pos_t>, compare >pq;

int main() {
    int distance = 0;
    position *t = new position(0, 0);
    pq.push(std::make_pair(distance, *t));
}