c++ - STL Priority Queue on custom class

Question

I'm having a lot of trouble getting my priority queue to recognize which parameter it should sort by. I've overloaded the less than operator in my custom class but it doesn't seem to use it. Here's the relevant code:

Node.h

class Node
{   
public:
    Node(...);
    ~Node();
    bool operator<(Node &aNode);
...
}

Node.cpp

#include "Node.h"
bool Node::operator<(Node &aNode)
{
    return (this->getTotalCost() < aNode.getTotalCost());
}

getTotalCost() returns an int

main.cpp

priority_queue<Node*, vector<Node*>,less<vector<Node*>::value_type> > nodesToCheck;

What am I missing and/or doing wrong?

Answer 1

less<vector<Node*>::value_type> Means that your comparator compares the pointers to each other, meaning your vector will be sorted by the layout in memory of the nodes.

You want to do something like this:

#include <functional>
struct DereferenceCompareNode : public std::binary_function<Node*, Node*, bool>
{
    bool operator()(const Node* lhs, const Node* rhs) const
    {
        return lhs->getTotalCost() < rhs->getTotalCost();
    }
};

// later...
priority_queue<Node*, vector<Node*>, DereferenceCompareNode> nodesToCheck;

Note that you need to be const-correct in your definition of totalCost.

EDIT: Now that C++11 is here, you don't need to inherit from std::binary_function anymore (which means you don't need to #include functional)