2

私は単純なイベント駆動型シミュレーターを開発しようとしていて、ここから始めました

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

いくつかの変更を加えて例をいじっていたとき、2 つのイベント (到着、出発) が同時に発生した場合 (時間単位 5 など)、シミュレーターが一番上にあるものをポップするという状況に遭遇しました。以下のコード スニペットからわかるように、イベント キュー。

void simulation::run () {

while (! eventQueue.empty ()) {

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

両方のイベントが同時に発生した場合、出発イベントの前に特定のイベント (最初に到着イベント) を常にポップする条件を強制するにはどうすればよいですか。

どんな助けでも大歓迎です。

4

1 に答える 1

5

ここでeventQueue説明されているタイプを持っていると思います（これは、質問のリンクから参照されているためです）。そこから、あなたはそれを読むことができます...top()

優先度が最も高いキュー内の要素への定数参照を返します

...そしてそれpop()...

優先度が最も高いアイテムをキューから削除します。

したがって、質問からコードを取得すると、最も明白なアプローチは、同じ時間のすべてのイベントをキューから取り出してから処理することです。

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;
于 2016-03-09T19:05:48.830 に答える