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?

You must be in Chai's AI class :) stackoverflow.com/questions/1517854/… — DigitalZebra
– DigitalZebra, Commented Oct 9, 2009 at 5:04

user673679 · Accepted Answer · 2015-06-09 16:52:52Z

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)

Out of curiosity: why define a struct with operator() rather than just a function?
You have to. You can't specialize templates with functions, just types (excluding specific circumstances). Function objects are a very important part of STL programming. A great book to read up on is Scott Meyer's Effective STL. It explains all about the STL and the best ways to take advantage of it.
Also, I should point out that std::less<T> is also a function object (i.e., a struct with operator())

GManNickG · Accepted Answer · 2009-10-09 02:58:38Z

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(); }

Actually, I have to disagree with the definition of operator< outside the class in some instances. If it's clear cut what it's supposed to do, I don't think it's really a big deal to define it as a member. Plus it allows use of Boost.Operators.

Collectives™ on Stack Overflow

STL Priority Queue on custom class

2 Answers 2

5 Comments

1 Comment

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

1 Comment

Linked

Related