Re: priority_queue help

From:

"Joe, G.I." <invalid.email@address>

Newsgroups:

comp.lang.c++

Date:

Mon, 13 Oct 2008 16:08:40 +0000

Message-ID:

<gd0dne02vkp@news1.newsguy.com>

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

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

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::operator < (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 MyEventPointerCompare {

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

  };

Now you can have

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

Oops, I forgot about the container:

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

Best

Kai-Uwe Bux