Using a Struct in a Priority Queue

[bwquestion]

Hey All,

I need some help with the use of a Priority Queue.

I have a Struct

struct node
{
string typeItem;
int sizes[9];
int d;
int h;
int c;
};

Up until now this info has been pushed into a FIFO queue and all was working good using

queue.push(box);

Now I need to do the same thing except push the struct into a priority_queue using the value stored in

int c;

with the lowest value being the one on top and the one with higher values pushed down the line.

Example. Push in 18, 7, 23, 4, 12 and get out 4, 7, 12, 18, 23.

I have looked at the examples from a search on the internet but cant seem to make this happen.

Anyone know the syntax for what I am trying to do?

[tejashs]

you could do multi-set or multi map with priority stored as the key of the map

take a look at this and the example given in the link...
http://www.cplusplus.com/reference/set/multiset/insert/

[mik2718]

You just need to an an operator< to your class/struct

then you can use the container

http://www.cplusplus.com/reference/queue/priority_queue/

unfortunately the container is coded to give max heap at the top

One option is to cheat and code you operator< in reverse i.e.

int node::operator<(const node& other)
{
  return c > other.c;
}

or you could write a comparison object

[bwquestion]

mik2718,

I looked at the link you provided last night.

That is what I need to do but the page reads like a foreign language to me.

I tried to set up

priority_queue <node, vector<int>, greater<int> > pQueue (node.c);

The word

node.c

gets underlined in red and gives me the message

Error: a non-static member reference must be relative to a specific object.

I have no idea how to fix.

[bwquestion]

I really need something for this. Anybody got a clue?

[mik2718]

use this to declare your queue

priority_queue<node> pQueue;

add the operator< code to your class

struct node
{
string typeItem;
int sizes[9];
int d;
int h;
int c;
int operator<(const node& other)
  { return c > other.c)
};

should work

[bwquestion]

I added the above as you suggested.

At the end of what is line 9 above, there is a red curly line under the

)

and it says

Error: Expected a ';'

Also there is an open curly brace on line 9 that has no closed curly brace. Did it get cut off?

[mik2718]

sorry , my typo

struct node
{
string typeItem;
int sizes[9];
int d;
int h;
int c;
int operator<(const node& other)
  { return c > other.c; }
}; 

[bwquestion]

I think we are on the right track.

now I get

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

could be 'int node::operator <(const node &)'
while trying to match the argument list '(const node, const node)'

I looked up the error but it is way out of my league.

[JLBorges]

//int operator<(const node& other)
bool operator< ( const node& other ) const
  { return c > other.c; }

[bwquestion]

It is compiling correctly now. I will follow up.

[bwquestion]

This worked you guys are great.

[JLBorges]

I suppose you have also reasoned out why the comparison predicate must be const-correct.

[bwquestion]

Not sure there was ever an issue with the const part. It was the syntax that was throwing me. When I look at the documentation, in my mind I cannot connect what they show with what it actually ended up being. When I look at what you and mik2718 showed me it made perfect sense. In my work I very seldom have to write code. When I do and run across something new, I have to rely on the documentation. If it is bad such as this I have to find an example or rely on good people like yourself to break it down for me.

[JLBorges]

> Not sure there was ever an issue with the const part.

What would happen if the non-const predicate was allowed to modify the nodes in a way that their priorities changed as comparisons were being made?

int node::operator<(const node& other)
//bool operator< ( const node& other ) const
{ bool result = c > other.c ; c = other.c - 1 ; return result ; }