c ++有序（稳定）优先级队列

一尘不染

c ++有序（稳定）优先级队列

algorithm

我正在实现一个玩具调度程序，该程序读取过程规范（例如到达时间，总运行时间）的输入文件，然后根据随机的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

如果我从优先级队列中弹出，我希望第4行，第3行，第1行，然后是第2行。但是我得到了Line4，Line3，Line2，Line1。

我的问题是，如何获得稳定的优先级队列？

阅读 297

2020-07-28

共1个答案

一尘不染

您的比较器不正确。该文件的std::priority_queue规定，它应该提供一个严格的弱序（即，它应该event1->getTimestamp() > event2->getTimestamp()不是>=）。
为了使其稳定，您只需将行号存储在中，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();
  }   
};

2020-07-28