c ++有序（稳定）优先级队列 [英] c++ ordered(stable) priority queue

问题描述

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

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.

文件格式为

到达时间，总CPU时间，CPU突发次数，IO突发次数。

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;

其中Event只是封装过程参数的对象。

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.

假设输入文件具有

60 200 5 20

60 200 5 20

60 20 10 10

60 20 10 10

40 100 10 40

40 100 10 40

0 200 40 90

0 200 40 90

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

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?

推荐答案

1. 您的比较器不正确。 std :: priority_queue 文档 $ c>指出应提供严格的弱排序（即，应 event1-> getTimestamp（）> event2-> getTimestamp（），而不是> = ）。

要使其稳定，您只需将行号存储在 Event ，如果 event1-> getTimestamp（）== event2-> getTimestamp（）进行比较，则将其进行比较。

To make it stable, you can just store the line number inside the Event and compare it if 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 ++有序（稳定）优先级队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！