事件驱动模拟器中同时发生的事件

Question

我一直在尝试开发一个简单的事件驱动模拟器并从这里开始

http://stdcxx.apache.org/doc/stdlibug/11-3.html

当我对这个例子进行一些修改时，我遇到了一个情况，当两个事件（到达、离开）同时发生时（比如在时间单元 5），然后模拟器会弹出任何内容从下面的代码片段可以看出，它位于事件队列的顶部。

void simulation::run () {

while (! eventQueue.empty ()) {

event * nextEvent = eventQueue.top ();
eventQueue.pop ();
time = nextEvent->time;
nextEvent->processEvent ();
delete nextEvent;
  }
}

如果两个事件同时发生，我如何强制在出发事件之前总是弹出某个事件（首先到达事件）的条件。

非常感谢任何帮助。

Answer 1

我假设 eventQueue 具有 here 描述的类型（因为这是您问题中 link 所引用的类型）。从那里，你可以读到 top() ...

Returns a constant reference to the element in the queue with the highest priority

... pop() ...

Removes the item with the highest priority from the queue.

因此，从您的问题中提取代码，最明显的方法是将所有具有相同时间的事件从队列中取出，然后才处理它们：

while (! eventQueue.empty ()) {
  event * ev = eventQueue.top (); // WHY do you have pointers here ?!?!?
  time = ev->time;
  some_container<event *> arrivals, departures;
  // Take out all events that happen "now" from the queue
  while (time == ev->time) {
    eventQueue->pop();
    if (ev->type == ARRIVAL) {
      arrivals.push_back(ev);
    } else {
      departures.push_back(ev);
    }
    ev = eventQueue->top();
  }
  // Process arrivals
  for (event * e : arrivals) {
    e->processEvent();
    delete e; // Again: WTF pointers? raw? NOT a good idea!
  }
  // Process departures
  for (event * e : departures) {
    e->processEvent();
    delete e;
  }
}

但是...

...这不是在 C++ 中处理此问题的惯用方式。 C++ 中的容器（至少是有序容器）通常有一个模板参数来指定元素的排序方式。 std::priority_queue:

namespace std {
  template <class T,
            class Container = vector<T>,
            class Compare = less<Container::value_type> >
  class priority_queue;
}

因此，这里更好的方法是使用自定义比较函数对象在所有事件中建立总顺序：

// sigh ... pointers ... raw pointers ... just WHY???!?
template<typename Event>
struct less_event_ptr {
  std::less<time_type> time_compare; // time_type hopefully is self-describing ...
  bool operator()(Event * lhs, Event * rhs) const {
    if (time_compare(lhs->time, rhs>-time)) {
      return true;
    }
    if (time_compare(rhs->time, lhs->time)) {
      return false;
    }
    if (lhs->type == ARRIVAL && rhs->type == DEPARTURE) {
      return true;
    }
    return false;
  }
};

请注意，对于总计订单，您需要确保不会有多个同时到达（或离开）。如果（可能）存在这种情况，那么您应该（如果您想要确定性模拟）找到事件的其他属性（名称？来源？）以使它们井然有序。

您的 eventQueue 将被声明为

std::priority_queue<event *, std::vector<event *>, less_event_ptr<event>> eventQueue;

事件驱动模拟器中同时发生的事件

events happening at the same time in event-driven simulator

c++

event-driven

event-driven-design

但是...