STL priority queue and overloading with pointers

Question

This is my first time using a priority queue. I'm trying to implement Dijkstra's algorithm for school and I figured I need a min heap to do this. Right now my nodes are pointers and I want to compare their weight, but I don't think I can overload > and < with pointers? Is there a way I could accomplish this?

Code this far:

priority_queue<Node*, vector<Node*>, node_comparison> minHeap;

And then I have a struct to compare the node's weights

struct node_comparison 
{
   bool operator<( const Node* a, const Node* b ) const 
   {
    return a->totalWeight < b->totalWeight;
   }
};

However it says there are too many parameters for this operator function. I've been trying to figure out how I could manage a min heap priority queue with my nodes for a while now and keep getting stuck. Any ideas?

In the documentation, see the example which uses std::less<int>. You need to implement something similar for Node*. — Peter Wood

Andy Prowl Andy Prowl · Accepted Answer · 2013-03-26T20:13:34

If I understand your question correctly, I believe what you actually want is to make node_comparison a functor (more specifically, a binary predicate):

struct node_comparison 
{
    bool operator () ( const Node* a, const Node* b ) const 
    {
        return a->totalWeight < b->totalWeight;
    }
};

A functor is a class whose objects provide an overload of the call operator (operator ()) and, therefore, can be invoked with the same syntax you would use for invoking a function:

Node* p1 = ...;
Node* p2 = ...;
node_comparison comp;
bool res = comp(p1, p2) // <== Invokes your overload of operator ()

Internally, std::priority_queue will instantiate your predicate more or less like I did in the code snippet above, and invoke it that way to perform comparisons between its elements.

The advantage of functors over regular functions is that they could hold state information (something you probably won't need for the moment, but which often turns out to be desirable):

#include <cmath>

struct my_comparator
{
    my_comparator(int x) : _x(x) { }

    bool operator () (int n, int m) const
    {
        return abs(n - _x) < abs(m - _x);
    }

    int _x;
};

The above predicate, for instance, compares integers based on how distant they are from another integer provided at construction time. This is how it could be used:

#include <queue>
#include <iostream>

void foo(int pivot)
{
    my_comparator mc(pivot);
    std::priority_queue<int, std::deque<int>, my_comparator> pq(mc);

    pq.push(9);
    pq.push(2);
    pq.push(17);

    while (!pq.empty())
    {
        std::cout << pq.top();
        pq.pop();
    }
}

int main()
{
    foo(7);

    std::cout << std::endl;

    foo(10);
}

STL priority queue and overloading with pointers

2 Answers