Multiset of shared_ptrs as a dynamic priority queue: Concept and practice
- by Sarah
I was using a vector-based priority queue
typedef std::priority_queue< Event, vector< Event >, std::greater< Event > > EventPQ;
to manage my Event objects. Now my simulation has to be able to find and delete certain Event objects not at the top of the queue. I'd like to know if my planned work-around can do what I need it to, and if I have the syntax right. I'd also like to know if dramatically better solutions exist.
My plan is to make EventPQ a multiset of smart pointers to Event objects:
typedef std::multi_set< boost::shared_ptr< Event > > EventPQ;
I'm borrowing functions of the Event class from a related post on a multimap priority queue.
// Event.h
#include <cstdlib>
using namespace std;
#include <set>
#include <boost/shared_ptr.hpp>
class Event;
typedef std::multi_set< boost::shared_ptr< Event > > EventPQ;
class Event {
public:
Event( double t, int eid, int hid );
~Event();
void add( EventPQ& q );
void remove();
bool operator < ( const Event & rhs ) const {
return ( time < rhs.time );
}
bool operator > ( const Event & rhs ) const {
return ( time > rhs.time );
}
double time;
int eventID;
int hostID;
EventPQ* mq;
EventPQ::iterator mIt;
};
// Event.cpp
Event::Event( double t, int eid, int hid ) {
time = t;
eventID = eid;
hostID = hid;
}
Event::~Event() {}
void Event::add( EventPQ& q ) {
mq = &q;
mIt = q.insert( boost::shared_ptr<Event>(this) );
}
void Event::remove() {
mq.erase( mIt );
mq = 0;
mIt = EventPQ::iterator();
}
I was hoping that by making EventPQ a container of pointers, I could avoid wasting time copying Events into the container and avoid accidentally editing the wrong copy. Would it be dramatically easier to store the Events themselves in EventPQ instead?
Does it make more sense to remove the time keys from Event objects and use them instead as keys in a multimap?
Assuming the current implementation seems okay, my questions are:
Do I need to specify how to sort on the pointers, rather than the objects, or does the multiset automatically know to sort on the objects pointed to?
If I have a shared_ptr ptr1 to an Event that also has a pointer in the EventPQ container, how do I find and delete the corresponding pointer in EventPQ? Is it enough to .find( ptr1 ), or do I instead have to find by the key (time)? Is the Event::remove() sufficient for removing the pointer in the EventPQ container?
There's a small chance multiple events could be created with the same time (obviously implied in the use of multiset). If the find() works on event times, to avoid accidentally deleting the wrong event, I was planning to throw in a further check on eventID and hostID. Does this seem reasonable?
(Dumb syntax question) In Event.h, is the declaration of dummy class Event;, then the EventPQ typedef, and then the real class Event declaration appropriate?
I'm obviously an inexperienced programmer with very spotty background--this isn't for homework. Would love suggestions and explanations. Please let me know if any part of this is confusing. Thanks.
