c++ ordered(stable) priority queue

Question

I am implementing a toy scheduler which reads a input file of process specifications such as arrival time, total run time and then schedules the process based on random io/cpu bursts.

The file is of the format

Arrival time, total CPU time, CPU burst, IO Burst.

Now, when there are two process with same arrival time, the scheduler have to schedule the process first the process which is mentioned first in the file.

I am keeping the entries in the file in a priority queue.

struct EventComparator{
  bool operator()(const Event* event1, const Event* event2){
    return event1->getTimestamp() >= event2->getTimestamp();
  }   
};  
priority_queue<Event*, vector<Event*>, EventComparator> eventQueue;

where Event is just an object encapsulating the process parameters.

My problem is, the priority queue is not stable. By stable I mean that the order of the process gets reversed.

Suppose the input file has

60 200 5 20

60 20 10 10

40 100 10 40

0 200 40 90

If i pop from the priority queue, I expect Line4, line 3, Line1 and then Line2. But I get Line4, Line3, Line2, Line1.

My question is, what can I do to get a stable priority queue?

maybe you need to encode the file line in the information then in your comparison object check if the objects tie and if they do then use the file line information. Otherwise use the time-stamp for the comparison. — NathanOliver
Most standard containers don't bother enforcing stability. It's easiest to simply add additional information to guarantee ordering as @NathanOliver suggests. — Speed8ump

kraskevich kraskevich · Accepted Answer · 2015-03-03T16:13:42

Your comparator is incorrect. The documentation for the std::priority_queue states that it should provide a strict weak ordering(that is, it should event1->getTimestamp() > event2->getTimestamp(), not >=).
To make it stable, you can just store the line number inside the Event and compare it if event1->getTimestamp() == event2->getTimestamp().

Something like this:

struct EventComparator {
  bool operator()(const Event* event1, const Event* event2) {
    if (event1->getTimestamp() != event2->getTimestamp()) {
      return event1->getTimestamp() > event2->getTimestamp();
    }
    return event1->getLineNumber() > event2->getLineNumber();
  }   
};

c++ ordered(stable) priority queue

1 Answers