What is this C++ code doing?

Q_Ball

hey all,

sifting through some code and i've found this. Its the function for a priority_queue in c++ STL. I understand the node element but its the bold code i'm stuck on.

struct Node
{
	D3DXVECTOR3 pos;
	float f;
	float g;
	float h;
	Node * parent;	
};

class NodeLessFunctor 
{
    Node * p;
	public:
		NodeLessFunctor() { p = NULL;}
		[b]NodeLessFunctor(Node * p) : p(p) {}[/b]
		[b]bool operator()(Node * f1, Node * f2)
		{
			return (f1->f > f2->f);
		}[/b]
};

I understand that the first bold line is a constructor with a pointer to a node p passed in, but what is the

: p(p)

part do?

My second question is what is an operator method? when is it used?

This code comes from a header file, i cant find any reference to it in the cpp code (altho there is an operator method there with different parameters)

also, the priority queue is declared as

priority_queue<Node*, vector<Node*>, NodeLessFunctor> _open;

so NodeLessFunctor is used for comparisons, node* is the first element and the vector being the last (i presume doesnt have a last element because its a vector) element. When would NodeLessFunctor be called? When an element is pushed onto the queue?

My head hurts thinking about it

Blowfish

: p(p) is essentially:

this->p = p;

All its doing is passing in the variable really.

The operator() is a function object

Tobias Greeshman

Are you sure you typed that operator function out correctly?

Overloading () operator to check if one node is greater than the other doesn't make sense.

Are you sure it's not meant to be something like this??

bool operator > ( Node *p1, Node *p2 )
{
  return ( p1->f > p2->f ) ;
}

Sometimes some library code has entire implementation of classes written in header files.

The syntax after a constructor in the form
: x ( y )

x = class object
y = new objects value

literally is a quick mechanism to initialize class objects, and it's quicker than initializing the object inside the constructor braces.

Q_Ball

code was cut and paste from the header file.

cheers!

PhantomBeaker

Might be helpful if you're still confused.

First off, I have to admit, I'm winging a lot of this. I've only done about 3 months of C++, so my grasp of the intricate mechanics of this won't be spot on... but I think this is a workable understanding of what's going on, if it's of any help. But either way, read the article Blowfish referenced.

You may also want to read this API, which explains the priority_queue very technically.

silas wrote:

Are you sure you typed that operator function out correctly?

Overloading () operator to check if one node is greater than the other doesn't make sense.

Are you sure it's not meant to be something like this??

bool operator > ( Node *p1, Node *p2 )
{
  return ( p1->f > p2->f ) ;
}

I just realised the reason for this. We're dealing with a functor here. It's an object that's trying to act like a function (a lot of places describe it as a "function with a state"). It's a bit like pointer to a function, but conceptually a lot easier.

So when you overload the () operator, you can then say something like:

// Create Node* p1 and p2 somehow

NodelessFunctor f;
if ( f(p1, p2) ) {
  //do something funky
}

Now I get it... (I love this stuff, I start off explaining a functor, and then question why it's needed in the first place, then realise why)

Ok, to the OP, I'm assuming you know what a priority queue is. If you don't: In short, it's like a normal queue, but some nodes can skip the queue on the basis of priority.

Now, how to you decide priority, or sort things? A lot of the time people use really simple functions that will just swap your node up (or down) the list until it reaches the right spot. So the priority queue has a nice little way to let you decide the priority - you define the function yourself, implement it as a functor (i.e. an object that acts like a function), and it'll let you decide what's prioritised and how you prioritise it.

So if you wanted to prioritise your nodes on the basis of the value g, instead of f, you'd make a new functor:

class NodeOtherFunctor 
{
    Node * p;
	public:
		NodeOtherFunctor() { p = NULL;}
		NodeOtherFunctor(Node * p) : p(p) {}
		bool operator()(Node * f1, Node * f2)
		{
			return (f1->g > f2->g);
		}
};

And create your priotity queue like so:

priority_queue<Node*, vector<Node*>, NodeOtherFunctor> _open;

So if you want a lot of different priority_queue objects all prioritising in different ways, you can just pass in different Functors for how you want it to sort.

Hope this helps somewhat.
Aoife