c++ упорядоченная (стабильная) приоритетная очередь

Я внедряю игрушечный планировщик, который считывает входной файл спецификаций процесса, таких как время прибытия, общее время выполнения, а затем планирует процесс на основе случайных пакетов ввода-вывода/процессора.

Файл имеет формат

Время прибытия, общее время процессора, пакет процессора, пакет ввода-вывода.

Теперь, когда есть два процесса с одинаковым временем прибытия, планировщик должен сначала запланировать процесс, который упоминается первым в файле.

Я сохраняю записи в файле в приоритетной очереди.

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

Где событие-это просто объект, инкапсулирующий параметры процесса.

Моя проблема в том, что приоритетная очередь не стабильна. Под стабильностью я подразумеваю, что порядок процесса меняется на противоположный.

Предположим, что входной файл имеет

60 200 5 20

60 20 10 10

40 100 10 40

0 200 40 90

Если я выскакиваю из очереди приоритетов, я ожидаю Line4, line 3, Line1 а потом Линия 2. Но я получаю Line4, Line3, Line2, Line1.

Мой вопрос в том, что я могу сделать, чтобы получить стабильную очередь приоритетов?

1 2
c++ sorting algorithm priority-queue

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