Priority queues, comparisions and pointers

[zecbmo]

So I have a struct Vertex, and I wish to store a collection of Vertex's within a priority queue (as pointers to each vertex).

struct Vertex
{
	std::string name;
	bool blocked;
	int distance; // -1 if not filled yet
	std::list<Vertex *> neighbours;
	Coords position;
	bool isEndPos;
	Vertex(std::string name_)
		: name(name_), blocked(false), distance(-1), isEndPos(false) {};
	Vertex() : blocked(false), distance(-1), isEndPos(false) {};
};

And I also have a comparison struct created,

struct Compare 
{	
	bool operator()(const Vertex &lhs, const Vertex &rhs) const
	{
		return lhs.distance < rhs.distance;
	}
};

This is how I am declaring the queue:

std::priority_queue<Vertex*, Compare> nodesToCheck;

But when trying to compile I get a list of errors all similar to "value_type': is not a member of 'Compare'.

Any help on this would be appreciated

[Peter87]

You are storing pointers in the priority queue so your comparison function should take pointers as argument.

[zecbmo]

I tried this but still receives the same error message

struct Compare
{
	bool operator()(const Vertex* lhs, const Vertex* rhs) const
	{
		return lhs->distance < rhs->distance;
	}
};

[Peter87]

The comparator should be the third template argument so you will have to pass in the second argument as well. The second template argument is the underlying container that the priority queue uses to store the elements. The default is std::vector so you probably want to keep using that.

std::priority_queue<Vertex*, std::vector<Vertex*>, Compare> nodesToCheck;