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?

Solution 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)

Solution 2

You need to make your parameter const, because as of now you're giving it a non-cost reference, which means you might modify the object you're comparing with. (Which you aren't, and probably shouldn't).

You're not being const-correct. Your operator< doesn't make modifications to the Node, so the function should be const:

bool operator<(const Node &aNode) const;

After that, if you have trouble calling the getTotalCost() function, it's likely that it is not const as well. Mark it as const if it's not already:

int getTotalCost(void) const;

Your code is now (more) const-correct.

On a side note, binary operators are usually implemented outside the class:

class Node
{
public:
    // ...

    int getTotalCost(void) const;

    // ...
};

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