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

Question

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

文件格式

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

现在，当有两个进程到达时间相同时，调度程序必须首先调度文件中最先提到的进程。

我将文件中的条目保存在优先队列中。

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。

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

Answer 1

1. 您的比较器不正确。 documentation对于 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();
  }   
};