priority_queue help

[Joe, G.I.]

Can anyone help me w/ a priority_queue. I'm generating MyEvent classes
and I put them on a priority_queue, but I don't know how to get them in
priority. The priority is the event w/ the smallest timestamp.

// just a wrapper around priority_queue
pq = new MyPriorityQueue ();

// I generate 10 events w/ a random timestamp
for (int i = 0; i < 10; i++) {
MyEvent *event = new MyEvent();
event->set_id(idx++ );
event->set_gen_tstamp ();

pq->push_event(eve nt);
}

// Now I need to find the event w/ the smallest timestamp
if (pq->size() 0) {
MyEvent *evnt = pq->top_event();

if (evnt->is_expired() ) {
// do stuff ... then remove this event

pq->pop_event();
}
}

// Not sure what I'm doing here, but I'm trying to do an overload
// operator and have it return the priority of the smallest time. I
// think this is where I need help.
// Not even sure if this is the thing to do.

bool MyEvent::operat or < (const MyEvent *event)
{
if (_timestamp < event->_timestamp() )
return true;
}

return false;
}

[=?ISO-8859-1?Q?Marcel_M=FCller?=]

Re: priority_queue help

Hi,

Joe, G.I. schrieb:

Can anyone help me w/ a priority_queue. I'm generating MyEvent classes
and I put them on a priority_queue, but I don't know how to get them in
priority. The priority is the event w/ the smallest timestamp.

Normally a priority queue with n levels of priority can be modelled by a
silgle linked list with a head and n tail pointers. The priority is in
fact applied by the insert operation at the right place in the queue.
Put and get are O(1) in this case.

However, if you take a time index as priority you have an nearly
infinite number of priority levels. So you need either random access to
the queue elements to do a binary search. std::deque is such a container.
Or if the time stamps of the inserted queue elements are likely to be
close together compared to the queue depth a doubly linked list with
linear search from the back might be sufficient. You can use std::list
for that purpose.

// Not sure what I'm doing here, but I'm trying to do an overload
// operator and have it return the priority of the smallest time. I
// think this is where I need help.
// Not even sure if this is the thing to do.
>
bool MyEvent::operat or < (const MyEvent *event)
{
if (_timestamp < event->_timestamp() )
return true;
}
>
return false;
}

I would not overload the comparsion operators here, since the events are
not characterized by the time only and giving them a 'greater than'
semantic is not meaningful. I would pass a comparer function to the
Queue either as template argument at compile time or as funtion pointer
as constructor argument at run time.


Marcel

[Kai-Uwe Bux]

Re: priority_queue help

Joe, G.I. wrote:

>
Can anyone help me w/ a priority_queue. I'm generating MyEvent classes
and I put them on a priority_queue, but I don't know how to get them in
priority. The priority is the event w/ the smallest timestamp.
>
// just a wrapper around priority_queue
pq = new MyPriorityQueue ();

a) There is no other use for a wrapper of a standard template than
obfuscation.

b) Why the new() ?

// I generate 10 events w/ a random timestamp
for (int i = 0; i < 10; i++) {
MyEvent *event = new MyEvent();
event->set_id(idx++ );
event->set_gen_tstamp ();
>
pq->push_event(eve nt);
}

Ok: your priority queue has value_type = MyEvent*.

// Now I need to find the event w/ the smallest timestamp
if (pq->size() 0) {
MyEvent *evnt = pq->top_event();
>
if (evnt->is_expired() ) {

Shouldn't that if be a while ?

// do stuff ... then remove this event
>
pq->pop_event();
}
}
>
// Not sure what I'm doing here, but I'm trying to do an overload
// operator and have it return the priority of the smallest time. I
// think this is where I need help.
// Not even sure if this is the thing to do.
>
bool MyEvent::operat or < (const MyEvent *event)
{
if (_timestamp < event->_timestamp() )
return true;
}
>
return false;
}

a) This is a type mismatch. Your queue is templated on MyEvent* not MyEvent.

b) You cannot overload operator< for pointer types.

c) Your best bet is to define a functor class:

struct MyEventPointerC ompare {

bool operator() ( MyEvent* lhs, MyEvent* rhs ) const {
return ( lhs->_timestamp < rhs->_timestamp );
}

};

Now you can have

std::priority_q ueue< MyEvent*, MyEventPointerC ompare the_queue;



Best

Kai-Uwe Bux

[Kai-Uwe Bux]

Re: priority_queue help

Kai-Uwe Bux wrote:

Joe, G.I. wrote:
>

>>
>Can anyone help me w/ a priority_queue. I'm generating MyEvent classes
>and I put them on a priority_queue, but I don't know how to get them in
>priority. The priority is the event w/ the smallest timestamp.
>>
> // just a wrapper around priority_queue
> pq = new MyPriorityQueue ();

>
a) There is no other use for a wrapper of a standard template than
obfuscation.
>
b) Why the new() ?
>
>

> // I generate 10 events w/ a random timestamp
> for (int i = 0; i < 10; i++) {
> MyEvent *event = new MyEvent();
> event->set_id(idx++ );
> event->set_gen_tstamp ();
>>
> pq->push_event(eve nt);
> }

>
Ok: your priority queue has value_type = MyEvent*.
>
>

> // Now I need to find the event w/ the smallest timestamp
> if (pq->size() 0) {
> MyEvent *evnt = pq->top_event();
>>
> if (evnt->is_expired() ) {

>
Shouldn't that if be a while ?
>

> // do stuff ... then remove this event
>>
> pq->pop_event();
> }
> }
>>
> // Not sure what I'm doing here, but I'm trying to do an overload
> // operator and have it return the priority of the smallest time. I
> // think this is where I need help.
> // Not even sure if this is the thing to do.
>>
> bool MyEvent::operat or < (const MyEvent *event)
> {
> if (_timestamp < event->_timestamp() )
> return true;
> }
>>
> return false;
> }

>
a) This is a type mismatch. Your queue is templated on MyEvent* not
MyEvent.
>
b) You cannot overload operator< for pointer types.
>
c) Your best bet is to define a functor class:
>
struct MyEventPointerC ompare {
>
bool operator() ( MyEvent* lhs, MyEvent* rhs ) const {
return ( lhs->_timestamp < rhs->_timestamp );
}
>
};
>
Now you can have
>
std::priority_q ueue< MyEvent*, MyEventPointerC ompare the_queue;

Oops, I forgot about the container:

std::priority_q ueue< MyEvent*,
std::vector< MyEvent*>,
MyEventPointerC ompare the_queue;


Best

Kai-Uwe Bux

[Stephen Horne]

Re: priority_queue help

On Mon, 13 Oct 2008 02:34:04 +0000, "Joe, G.I."
<invalid.email@ addresswrote:

// Not sure what I'm doing here, but I'm trying to do an overload
// operator and have it return the priority of the smallest time. I
// think this is where I need help.
// Not even sure if this is the thing to do.
>
bool MyEvent::operat or < (const MyEvent *event)
{
if (_timestamp < event->_timestamp() )
return true;
}
>
return false;
}

Don't do this - you're trying to overload a pointer comparison.

One option is the functor described by Kai-Uwe Bux. Another option is
to create a wrapper class for your items. Define operator< for that
class. For example...

struct MyEventThingy
{
MyEvent* m_Value;

bool operator< (const MyEventThingy &p) const
{
return (m_Value->timestamp p.m_Value->timestamp);
}
};

IIRC, std::priority_q ueue always gives you the highest value item
next. Since you want the lowest timestamp, the operator< uses reverse
logic.

This done, you can use std::priority_q ueue<MyEventThi ngy>.

The functor approach has significant advantages, of course, especially
if you have different containers containing the same kinds of items,
but with different orderings. This not necessarily a good alternative,
just an alternative.

BTW - are you from a more Java / C# background?

Just asking because of the line...

pq = new MyPriorityQueue ();

In C++, you can just write...

MyPriorityQueue localvarname ();

And this is preferred in general because it avoids allocating memory
from the heap, ensures proper cleanup when the object goes out of
scope, etc. You *may* have good reason for using a pointer, but it
seems a little odd.

[Stephen Horne]

Re: priority_queue help

On Mon, 13 Oct 2008 03:58:32 -0400, Kai-Uwe Bux <jkherciueh@gmx .net>
wrote:

>Joe, G.I. wrote:

> // just a wrapper around priority_queue
> pq = new MyPriorityQueue ();

>
>a) There is no other use for a wrapper of a standard template than
>obfuscation.

Specialisation? That is, after all, the whole point of inheritance.

Adapting to fit the required interface for some existing code?

Adding contract asserts, profiling code, etc?

[James Kanze]

Re: priority_queue help

On Oct 13, 10:52 am, Stephen Horne <sh006d3...@blu eyonder.co.uk>
wrote:

[...]

Just asking because of the line...

pq = new MyPriorityQueue ();

In C++, you can just write...

MyPriorityQueue localvarname ();

You can write it, but it doesn't mean quite what I'm sure you
want.
MyPriorityQueue localvarname ;
works, however. (Just an idiotsyncrasy of the the C++
declaration syntax.)

--
James Kanze (GABI Software) email:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

[Stephen Horne]

Re: priority_queue help

On Mon, 13 Oct 2008 02:49:49 -0700 (PDT), James Kanze
<james.kanze@gm ail.comwrote:

> MyPriorityQueue localvarname ();

>
>You can write it, but it doesn't mean quite what I'm sure you
>want.
MyPriorityQueue localvarname ;

It means *precisely* what I want - both of the above forms define a
variable within the current scope, calling the default constructor to
initialise it. Both do exactly the same if there is no default
constructor available, or if an implicit default constructor is
needed. Which form you use makes no difference in any circumstance to
the best of my knowledge, so I simply used the form closest to what GI
Joe used - he had the () in his code using new, so I used it in my
simple variable alternative.

BTW, what exactly is it that you were so sure I wanted? I can't think
of any possibility that's different from what your alternative does.

[Kai-Uwe Bux]

Re: priority_queue help

Stephen Horne wrote:

On Mon, 13 Oct 2008 02:49:49 -0700 (PDT), James Kanze
<james.kanze@gm ail.comwrote:
>

>> MyPriorityQueue localvarname ();

>>
>>You can write it, but it doesn't mean quite what I'm sure you
>>want.
> MyPriorityQueue localvarname ;

>
It means *precisely* what I want - both of the above forms define a
variable within the current scope, calling the default constructor to
initialise it.

No. The second does. The first does not initialize anything and does not
even declare a variable.

Both do exactly the same if there is no default
constructor available, or if an implicit default constructor is
needed. Which form you use makes no difference in any circumstance to
the best of my knowledge, so I simply used the form closest to what GI
Joe used - he had the () in his code using new, so I used it in my
simple variable alternative.
>
BTW, what exactly is it that you were so sure I wanted? I can't think
of any possibility that's different from what your alternative does.

The declaration

MyPriorityQueue localvarname ();

is parsed as a function declaration. It declares a function without
arguments and result type MyPriorityQueue . It is one of the gotchas of C++
syntax.


Best

Kai-Uwe Bux

[Eberhard Schefold]

Re: priority_queue help

Stephen Horne wrote:

On Mon, 13 Oct 2008 02:49:49 -0700 (PDT), James Kanze
<james.kanze@gm ail.comwrote:
>

>> MyPriorityQueue localvarname ();

>You can write it, but it doesn't mean quite what I'm sure you
>want.
> MyPriorityQueue localvarname ;

>
It means *precisely* what I want - both of the above forms define a
variable within the current scope, calling the default constructor to
initialise it.

You've fallen into this trap:

http://www.parashift.com/c++-faq-lite/ctors.html#faq-10.2

[James Kanze]

Re: priority_queue help

On Oct 13, 12:28 pm, Stephen Horne <sh006d3...@blu eyonder.co.uk>
wrote:

On Mon, 13 Oct 2008 02:49:49 -0700 (PDT), James Kanze

<james.ka...@gm ail.comwrote:

MyPriorityQueue localvarname ();

You can write it, but it doesn't mean quite what I'm sure you
want.
MyPriorityQueue localvarname ;

It means *precisely* what I want - both of the above forms
define a variable within the current scope, calling the
default constructor to initialise it.

Not quite. The first declares a function with external linkage
which takes no arguments, and returns a MyPriorityQueue . And
I'm pretty sure that that is not what you want.

Both do exactly the same if there is no default constructor
available, or if an implicit default constructor is needed.
Which form you use makes no difference in any circumstance to
the best of my knowledge, so I simply used the form closest to
what GI Joe used - he had the () in his code using new, so I
used it in my simple variable alternative.

Except that the parse is ambiguous in the case os a declaration,
and for historical reasons, the C++ standard says that it is
interpreted as a function declaration.

BTW, what exactly is it that you were so sure I wanted? I
can't think of any possibility that's different from what your
alternative does.

A function declaration. It may not be what you wanted, but
that's what it is.

--
James Kanze (GABI Software) email:james.kan ze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientier ter Datenverarbeitu ng
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

[Joe, G.I.]

Re: priority_queue help

Ok, yes, I have higher level language backgrounds, but my c++ books also
use 'new' so I'm a bit confused here. Is everywhere I'm using 'new' here
not correct? I've added more detail here to clarify what I can and tried
to make the priority_queue changes.

This all compiles, but crashes so I know I've got something wrong w/ the
new queue.


App::App()
{
pq = new EventQueue();
}

// Here I generate my Event classes w/ timestamps that will expire soon.
App::init()
{
for (int i = 0; i < 10; i++) {
Event *event = new Event();
event->set_tstamp() ;

pq->push_event(eve nt);
}
}

// Now I need to find the event w/ the smallest timestamp.
// And this actually is in a while loop of sorts.
void EventListener:: check_queue()
{
if (pq->count() 0) {
Event *evnt = pq->top_event();

if (evnt->is_expired() ) {
app.do_this(evn t->id());

pq->pop_event();
}
}
}

// Here's what's now in my Event.h
class Event
{
private:
...
long _id;

public:
Event();
~Event();

double _exec_time;

long id();
bool set_id(long idx);
bool is_expired();
bool set_tstamp();
};

struct EventPointerCom pare {
bool operator() ( Event* lhs, Event* rhs ) const {
return ( lhs->_exec_time < rhs->_exec_time );
}
};

// EventQueue.h
// my priority_queue has to be checked for expired events and
// there are cases where I want to know what type of event it is ...
// so that is why it's in a wrapper. not ok?
class EventQueue
{
private:
priority_queue< Event *pq;

public:
EventQueue();
EventQueue(int queue_size);
~EventQueue();

int count();
bool push_event(Even t *event);
bool pop_event();
Event* top_event();
bool execute_event() ;
bool check_queue();
bool contains_typeA_ events();
};


Kai-Uwe Bux wrote:

Kai-Uwe Bux wrote:
>

>Joe, G.I. wrote:
>>

>>Can anyone help me w/ a priority_queue. I'm generating MyEvent classes
>>and I put them on a priority_queue, but I don't know how to get them in
>>priority. The priority is the event w/ the smallest timestamp.
>>>
>> // just a wrapper around priority_queue
>> pq = new MyPriorityQueue ();

>a) There is no other use for a wrapper of a standard template than
>obfuscation.
>>
>b) Why the new() ?
>>
>>

>> // I generate 10 events w/ a random timestamp
>> for (int i = 0; i < 10; i++) {
>> MyEvent *event = new MyEvent();
>> event->set_id(idx++ );
>> event->set_gen_tstamp ();
>>>
>> pq->push_event(eve nt);
>> }

>Ok: your priority queue has value_type = MyEvent*.
>>
>>

>> // Now I need to find the event w/ the smallest timestamp
>> if (pq->size() 0) {
>> MyEvent *evnt = pq->top_event();
>>>
>> if (evnt->is_expired() ) {

>Shouldn't that if be a while ?
>>

>> // do stuff ... then remove this event
>>>
>> pq->pop_event();
>> }
>> }
>>>
>> // Not sure what I'm doing here, but I'm trying to do an overload
>> // operator and have it return the priority of the smallest time. I
>> // think this is where I need help.
>> // Not even sure if this is the thing to do.
>>>
>> bool MyEvent::operat or < (const MyEvent *event)
>> {
>> if (_timestamp < event->_timestamp() )
>> return true;
>> }
>>>
>> return false;
>> }

>a) This is a type mismatch. Your queue is templated on MyEvent* not
>MyEvent.
>>
>b) You cannot overload operator< for pointer types.
>>
>c) Your best bet is to define a functor class:
>>
> struct MyEventPointerC ompare {
>>
> bool operator() ( MyEvent* lhs, MyEvent* rhs ) const {
> return ( lhs->_timestamp < rhs->_timestamp );
> }
>>
> };
>>
>Now you can have
>>
> std::priority_q ueue< MyEvent*, MyEventPointerC ompare the_queue;

>
Oops, I forgot about the container:
>
std::priority_q ueue< MyEvent*,
std::vector< MyEvent*>,
MyEventPointerC ompare the_queue;
>
>
Best
>
Kai-Uwe Bux

[Bo Persson]

Re: priority_queue help

Joe, G.I. wrote:

Ok, yes, I have higher level language backgrounds,

Java, right?

but my c++ books
also use 'new' so I'm a bit confused here. Is everywhere I'm using
'new' here not correct? I've added more detail here to clarify what
I can and tried to make the priority_queue changes.

C++ also has a new, but it is more unusual. There is no garbage
collection in the language, so you should also match each new with a
delete.

>
This all compiles, but crashes so I know I've got something wrong
w/ the new queue.
>
>
App::App()
{
pq = new EventQueue();
}

This looks very much like Java. In C++ you don't have to allocate
everything dynamically.

>
// Here I generate my Event classes w/ timestamps that will expire
soon. App::init()
{
for (int i = 0; i < 10; i++) {
Event *event = new Event();
event->set_tstamp() ;
>
pq->push_event(eve nt);
}
}
>
// Now I need to find the event w/ the smallest timestamp.
// And this actually is in a while loop of sorts.
void EventListener:: check_queue()
{
if (pq->count() 0) {
Event *evnt = pq->top_event();
>
if (evnt->is_expired() ) {
app.do_this(evn t->id());
>
pq->pop_event();

Here you will lose you object. The pointer is destroyed when popped,
but the pointed-to object is not.

}
}
}
>
// Here's what's now in my Event.h
class Event
{
private:
...
long _id;
>
public:
Event();
~Event();
>
double _exec_time;
>
long id();
bool set_id(long idx);
bool is_expired();
bool set_tstamp();
};
>
struct EventPointerCom pare {
bool operator() ( Event* lhs, Event* rhs ) const {
return ( lhs->_exec_time < rhs->_exec_time );
}
};

I can't see that you are using this anywhere. The default for the
priority_queue is to sort elements stored - the pointers. the priority
will then be the address of the Events - random!

>
// EventQueue.h
// my priority_queue has to be checked for expired events and
// there are cases where I want to know what type of event it is ...
// so that is why it's in a wrapper. not ok?
class EventQueue
{
private:
priority_queue< Event *pq;
>
public:
EventQueue();
EventQueue(int queue_size);
~EventQueue();
>
int count();
bool push_event(Even t *event);
bool pop_event();
Event* top_event();
bool execute_event() ;
bool check_queue();
bool contains_typeA_ events();
};
>
>

[Default User]

Re: priority_queue help

Kai-Uwe Bux wrote:

Joe, G.I. wrote:

a) There is no other use for a wrapper of a standard template than
obfuscation.
>
b) Why the new() ?

Probably a Java guy.




Brian

--
If televison's a babysitter, the Internet is a drunk librarian who
won't shut up.
-- Dorothy Gambrell (http://catandgirl.com)

[Joe, G.I.]

Re: priority_queue help

Bo Persson wrote:

Joe, G.I. wrote:

>Ok, yes, I have higher level language backgrounds,

>
Java, right?

Also.

>

>but my c++ books
>also use 'new' so I'm a bit confused here. Is everywhere I'm using
>'new' here not correct? I've added more detail here to clarify what
>I can and tried to make the priority_queue changes.

>
C++ also has a new, but it is more unusual. There is no garbage
collection in the language, so you should also match each new with a
delete.
>

Match the new w/ a delete, or declare them as such ...

EventQueue localvarname ;

....and still use delete?

>This all compiles, but crashes so I know I've got something wrong
>w/ the new queue.
>>
>>
>App::App()
>{
> pq = new EventQueue();
>}

>
This looks very much like Java. In C++ you don't have to allocate
everything dynamically.
>

Ok, I guess I need to go read more about this then.

>// Here I generate my Event classes w/ timestamps that will expire
>soon. App::init()
>{
> for (int i = 0; i < 10; i++) {
> Event *event = new Event();
> event->set_tstamp() ;
>>
> pq->push_event(eve nt);
> }
>}
>>
>// Now I need to find the event w/ the smallest timestamp.
>// And this actually is in a while loop of sorts.
>void EventListener:: check_queue()
>{
> if (pq->count() 0) {
> Event *evnt = pq->top_event();
>>
> if (evnt->is_expired() ) {
> app.do_this(evn t->id());
>>
> pq->pop_event();

>
Here you will lose you object. The pointer is destroyed when popped,
but the pointed-to object is not.

Yeah, this is an easier point I understand.

>
>

> }
> }
>}
>>
>// Here's what's now in my Event.h
>class Event
>{
> private:
> ...
> long _id;
>>
> public:
> Event();
> ~Event();
>>
> double _exec_time;
>>
> long id();
> bool set_id(long idx);
> bool is_expired();
> bool set_tstamp();
>};
>>
>struct EventPointerCom pare {
> bool operator() ( Event* lhs, Event* rhs ) const {
> return ( lhs->_exec_time < rhs->_exec_time );
> }
>};

>
I can't see that you are using this anywhere. The default for the
priority_queue is to sort elements stored - the pointers. the priority
will then be the address of the Events - random!
>

Yeah, using functors is really confusing for me. I'm not sure how this
is done yet.

>

>// EventQueue.h
>// my priority_queue has to be checked for expired events and
>// there are cases where I want to know what type of event it is ...
>// so that is why it's in a wrapper. not ok?
>class EventQueue
>{
> private:
> priority_queue< Event *pq;
>>
> public:
> EventQueue();
> EventQueue(int queue_size);
> ~EventQueue();
>>
> int count();
> bool push_event(Even t *event);
> bool pop_event();
> Event* top_event();
> bool execute_event() ;
> bool check_queue();
> bool contains_typeA_ events();
>};
>>
>>

>
>