Question on std::priority_queue
Assume this structure:
struct Node
{
int Value;
int ID;
};
and lets say I make the following priority queue based on the above structure:
std::priority_queue<Node> pq;
My question is, how can I tell the priority_queue class how to compare the 'Value' member of the Node class with other 'Value' members from other Node objects?
Do I do this via an overloaded operator? Or some other external, global function? MSDN doesn't really support any examples of this, at least that I saw.
All help appreciated. Thank you!
# 1 Re: Question on std::priority_queue
I believe you can do it via either an overloaded less than operator, or a functor, in which case you would have to pass the name of your functor class in as the third template argument to the priority queue constructor. Of course that would require you to also pass in a second parameter, which IIRC is just the container class to be used, and defaults to vector<T>.
ejmw at 2007-11-9 0:41:14 >
# 2 Re: Question on std::priority_queue
Never heard of functors before... so I guess I'll stick with the less than operator :)
Could I get a small example?
# 3 Re: Question on std::priority_queue
Less than operator:
bool operator < (const Node& arg1, const Node& arg2)
{
return(arg1.Value < arg2.Value);
}
priority_queue<Node> queue1; //how to instantiate with a less than operator
Functor: class Node_Less_Than
{
public:
bool operator() (const Node& arg1, const Node& arg2);
};
bool Node_Less_Than::operator () (const Node& arg1, const Node& arg2)
{
return(arg1.Value < arg2.Value);
}
priority_queue<Node, vector<Node>, Node_Less_Than> queue2; //how to instantiate with a functor
Functor is just a fancy name for a class with the function operator defined.
ejmw at 2007-11-9 0:43:21 >
# 4 Re: Question on std::priority_queue
I don't understand why the operator < must accept 2 parameters? It is assumed that one of the operands are of type 'Node' because the operator is overloaded in the class Node, so the other operand is what is accepted in the parameter... How do 2 parameters differ from 1?
# 5 Re: Question on std::priority_queue
struct Node
{
int x;
int y;
int ID;
int Depth;
int Priority;
bool Goal;
bool operator< (const Node &Obj1, const Node &Obj2)
{
return Obj1.Priority < Obj2.Priority;
}
};
This returns the follow compiler error:
error C2804: binary 'operator <' has too many parameters
# 6 Re: Question on std::priority_queue
If you include the operator declaration inside your class or struct, the first parameter is implied and unnecessary. I should have been more specific as to where I was putting my function. Either of these is valid: struct Node
{
int Value;
int ID;
};
bool operator < (const Node& arg1, const Node& arg2)
{
return(arg1.Value < arg2.Value);
}
or: struct Node
{
int Value;
int ID;
bool operator < (const Node& arg);
};
bool Node::operator < (const Node& arg)
{
return(Value < arg.Value);
}
ejmw at 2007-11-9 0:46:16 >
# 7 Re: Question on std::priority_queue
Well with my pasted structure code above, the compiler says that it can't find any overloaded < operator that accepts "const Node" as my left operand... but it works fine with the overloaded operator being OUTSIDE of the structure's scope... why is this?
# 8 Re: Question on std::priority_queue
Try: struct Node
{
int x;
int y;
int ID;
int Depth;
int Priority;
bool Goal;
bool operator< (const Node &Obj2) const
{
return Priority < Obj2.Priority;
}
};
ejmw at 2007-11-9 0:48:18 >
# 9 Re: Question on std::priority_queue
Awesome! it works! Now only to remember this stuff for future occurances :)
Thank you so much! I would give you some rep, but I already did before lol. It won't let me.
