priority_queue help

J

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(event);
}

// 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::eek:perator < (const MyEvent *event)
{
if (_timestamp < event->_timestamp())
return true;
}

return false;
}
 
M

Marcel Müller

Hi,

Joe said:
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.
Click to expand...

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::eek:perator < (const MyEvent *event)
{
if (_timestamp < event->_timestamp())
return true;
}

return false;
}
Click to expand...

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
 
K

Kai-Uwe Bux

Joe said:
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();
Click to expand...

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(event);
}
Click to expand...

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()) {
Click to expand...

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::eek:perator < (const MyEvent *event)
{
if (_timestamp < event->_timestamp())
return true;
}

return false;
}
Click to expand...

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 MyEventPointerCompare {

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

};

Now you can have

std::priority_queue< MyEvent*, MyEventPointerCompare > the_queue;



Best

Kai-Uwe Bux
 
K

Kai-Uwe Bux

Kai-Uwe Bux said:
a) There is no other use for a wrapper of a standard template than
obfuscation.

b) Why the new() ?



Ok: your priority queue has value_type = MyEvent*.



Shouldn't that if be a while ?


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 MyEventPointerCompare {

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

};

Now you can have

std::priority_queue< MyEvent*, MyEventPointerCompare > the_queue;
Click to expand...

Oops, I forgot about the container:

std::priority_queue< MyEvent*,
std::vector< MyEvent*>,
MyEventPointerCompare > the_queue;


Best

Kai-Uwe Bux
 
S

Stephen Horne

// 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::eek:perator < (const MyEvent *event)
{
if (_timestamp < event->_timestamp())
return true;
}

return false;
}
Click to expand...

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_queue 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_queue<MyEventThingy>.

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.
 
S

Stephen Horne

Joe, G.I. wrote:

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

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?
 
S

Stephen Horne

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

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.
 
K

Kai-Uwe Bux

Stephen said:
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.
Click to expand...

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.
Click to expand...

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
 
J

Joe, G.I.

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(event);
}
}

// 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(evnt->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 EventPointerCompare {
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(Event *event);
bool pop_event();
Event* top_event();
bool execute_event();
bool check_queue();
bool contains_typeA_events();
};
 
J

James Kanze

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.
Click to expand...

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.
Click to expand...

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.
Click to expand...

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

Joe, G.I.

Bo said:
Java, right? Also.


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.
Click to expand...
Match the new w/ a delete, or declare them as such ...

EventQueue localvarname ;

....and still use delete?
This looks very much like Java. In C++ you don't have to allocate
everything dynamically.
Click to expand...
Ok, I guess I need to go read more about this then.

Here you will lose you object. The pointer is destroyed when popped,
but the pointed-to object is not.
Click to expand...
Yeah, this is an easier point I understand.
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!
Click to expand...
Yeah, using functors is really confusing for me. I'm not sure how this
is done yet.
 
J

Joe, G.I.

red said:
Since it's an automatic variable, not a pointer, it gets cleaned up
when it goes out of scope.
Click to expand...

So, I guess since it's in my constructor of the App class, out of scope
is when this class, my app shuts down?
 
B

Bo Persson

Joe said:
Ok, yes, I have higher level language backgrounds,
Click to expand...

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.
Click to expand...

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();
}
Click to expand...

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(event);
}
}

// 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(evnt->id());

pq->pop_event();
Click to expand...

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 EventPointerCompare {
bool operator() ( Event* lhs, Event* rhs ) const {
return ( lhs->_exec_time < rhs->_exec_time );
}
};
Click to expand...

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!
 
R

red floyd

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

EventQueue localvarname ;

...and still use delete?
Click to expand...

No. You only delete what you've new'ed.

[remainder redacted]
 
S

Stephen Horne

You've fallen into this trap:

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

OK - looks like you both got me. Clearly I got that wrong.

Of course I'd never define a nested function. C++ doesn't support what
I think of as *correct* nested functions, therefore there's really not
much point defining functions within another function. Second, on
those rare cases where having a function with that small a scope (but
no other features associated with nested functions) was beneficial,
I've always found that every compiler chokes on it.

Changing the subject a bit, but just what is going on with language
standardisation these days. Back in the day, the remit of standards
people was to formalise and standardise *existing* *best* *practice*.
Not to invent untested code-breaking "nice" ideas and inflict them on
unsuspecting developers.

That's not about nested function prototypes for the half-baked C++
nested functions - god knows when they were first thought up, probably
for K&R C - just other stuff that's seriously bugging me right now.

I mean, processors have had alignment issues for as long as I can
remember now. Even 16 bit processors such as the 68000 and 8086. Yet
even now, 20+ years after the fact (more if you move off the desktop),
they're still thinking about it. Without taking account of alignment
issues, you simply *cannot* write a reasonable container library, it's
a trivial thing to define a couple of features to do the job, but
they're too busy.

But when it comes to template scoping rules, they're more than happy
to invent standards that contradict what those compilers that could
actually cope with templates properly had been doing since the
mid-to-late 90s.

Clearly, their priorities are screwed up. Thank god they're part time
and underfunded - can you imagine what it would be like if they were
full time?

Wonder what they're dreaming up now. Probably ways to turn C++ into
bizarre Haskell hybrid, or something equally stupid. I wouldn't even
be surprised if they're planning to add garbage collection to jump on
the Java/.NET bandwagon.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

help create events w/ boost 0
std::priority_queue: Abysmally bad performance versus std::set, can'tfigure out why. 5
Q: STL priority_queue with boost shared_ptr 3
Top 10 players minheap sort - need help 1
Python battle game help 2
Initializing priority_queue in constructor 11
multi-threaded priority_queue in C++? 2
Using priority_queue 13

Members online

No members online now.
Total: 51 (members: 1, guests: 50)
Robots: 302

Forum statistics

Threads
473,995
Messages
2,570,236
Members
46,825
Latest member
VernonQuy6

Latest Threads

Top