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

您的比较器不正确。 std::priority_queue 的 documentation 声明它应该提供严格的弱排序（也就是说，它应该 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();
  }   
};

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

c++ ordered(stable) priority queue

c++

sorting

algorithm

stl

priority-queue