c ++有序(稳定)优先级队列

Question

我正在实现一个玩具调度程序,它读取进程规范的输入文件,如到达时间,总运行时间,然后根据随机io/cpu突发调度进程.

该文件的格式

到达时间,总CPU时间,CPU突发,IO突发.

现在,当有两个具有相同到达时间的进程时,调度程序必须首先调度该进程,该进程首先在文件中提到.

我将文件中的条目保留在优先级队列中.

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

其中Event只是一个封装过程参数的对象.

我的问题是,优先级队列不稳定.稳定我的意思是过程的顺序颠倒过来.

假设输入文件有

60 200 5 20

60 20 10 10

40 100 10 40

0 200 40 90

如果我从优先级队列弹出,我期待Line4,第3行,第1行,然后是Line2.但我得到了Line4,Line3,Line2,Line1.

我的问题是,我该怎么做才能获得稳定的优先级队列？

Answer 1

1. 您的比较器不正确.该文档的std::priority_queue,它应该提供一个严格的弱序状态(即,它应该event1->getTimestamp() > event2->getTimestamp()不是>=).

2. 为了使其稳定,您只需将行号存储在其中Event并进行比较即可event1->getTimestamp() == event2->getTimestamp().

像这样的东西:

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