Hey guys, I was hoping you could help me with a little problem I'm having. I'd like to create a priority queue from the STL of Node objects. Node is a class I've written myself. From what I understand, the STL uses the < (less than) operator (well, it uses less<>) to compare objects when it sorts them in the queue, so I had to overload the < (less than) operator in my Node class. However, when I try to do this, I get the following error in Visual C++:


error C2678: binary '<' : no operator found which takes a left-hand operand of type 'const Node' (or there is no acceptable conversion)

could be 'bool Node::operator <(Node)'
while trying to match the argument list '(const Node, const Node)'

while compiling class template member function 'bool std::less<_Ty>::operator ()(const _Ty &,const _Ty &) const'
with
[
_Ty=Node
]
c:\program files\microsoft visual studio 8\vc\include\queue(219) : see reference to class template instantiation 'std::less<_Ty>' being compiled
with
[
_Ty=Node
]
see reference to class template instantiation 'std::priority_queue<_Ty>' being compiled
with
[
_Ty=Node
]

OK, so it looked like it was expecting two Nodes in the arguement list. However, if I try to include two Node arguements, Visual C++ tells me that operator < has too many arguements.

Here is my overloaded operator < code:

and here is how I'm declaring the priority queue:

Can anyone point out my obvious flaw? I'm baffled!

Thanks so much!

make your operator< const correct.

vijayan's solution should be correct. There's a few things different between his and yours, though, which are important. First, his parameter takes a const object. This allows you to have a const Node on the right side of the expression. Second, he uses the pass-by-reference mechanism (the &) to avoid copying the node unnecessarily. Third, and the solution to your question, is the const at the end of the line which dictates that the function may be called for constant objects (which would be on the left-hand side).

Thanks so much guys! Works perfectly...

Actually, I have one more quick question. I'd actually like this to be a priority_queue of Node* (pointers to Node), but if I do that, then it sorts the queue using pointer arithmetic. So the Node*s with the lower addresses are put at the front and the higher ones are at the back. Is there any way for me to define a custom way to sort them in the Node class? Like, can I overload the "<" operator for just Node pointers somehow? Know what I mean?

How are you currently sorting them?

Right now, I'm just using the default priority_queue sort which uses less<Typ> to sort the Node objects by their heuristic value which is a member variable of the Node class. However, I'd really like the priority_queue to use Node* instead. Is this possible? It's not that I absolutely can't use Node objects, it would just be easier to integrate with the rest of my code if they were Node*s.

pointers are a standard type and you can not define how pointers are to be
compared anywhere. however, you can tell the priority_queue of Node*
how you want priorities to be compared.
a. write a binary predicate to compare nodes
b. specify the predicate to the priority_queue
remember that the predicate must be a relation that is asymetric,
irreflexive and transitive; ie. one that imposes a strict oredering
on the sequence.

Thanks for the reply! I actually had figured this out already but forgot to post here about it. The only trouble I'm having is that sometimes the heuristic value for two of the Nodes is the same, but I can't check for that in the predicate. If I try to compare using >= or ==, an assertion gets thrown by visual c++. I'd like to tell the priority queue that if two heuristic values are equal, it should consider the new value that is being inserted in the queue to be lesser one so that newer generated Nodes are inspected last for Nodes with an equal heuristic.

Right now, it seems to work while I'm debugging in Visual Studio, i.e. the Nodes appear in the correct order, but when I pop them off to inspect them, Nodes having the same priority seem to rendomly jump around in the queue. This seems odd...

I assume this is because my predicate does not meet the criteria above. Perhaps I should also number the nodes in increasing order as they are generated and then compare not just the heuristic value but when the node was generated - this should strictly order them, no?

OK, this is just strange:

If I use this predicate (which is wrong):
then the Nodes are ordered correctly by order, just backwards. So the most recently added Node becomes the next to pop off if the heuristics are equal. Here is the output showing this (Node value - heuristic value - order generated):

346 - 0 - 6
344 - 2 - 5
355 - 2 - 4
335 - 2 - 3
445 - 2 - 2
245 - 2 - 1

See, I would like all the ones with heuristic value of 2 to be ordered in increasing order.

However, if I use the correct predicate:

then the order turns out all jumbled, like this:
346 - 0 - 6
245 - 2 - 1
335 - 2 - 3
344 - 2 - 5
445 - 2 - 2
355 - 2 - 4

Which is not right. Any ideas why?