マルチセットコンテナはソートを停止するようです

StackOverflow https://stackoverflow.com/questions/2851868

  •  27-09-2019
  •  | 
  •  

質問

マルチセットコンテナで奇妙な動作をデバッグするのに感謝します。時折、コンテナがソートを停止するように見えます。これはまれなエラーであり、長い間後にいくつかのシミュレーションでのみ明らかになり、私はアイデアが不足しています。 （私はアマチュアプログラマーです。あらゆる種類の接地は大歓迎です。）

私のコンテナはaです std::multiset それは保持されます Event 構造：

typedef std::multiset< Event, std::less< Event > > EventPQ;

とともに Event それらによってソートされた構造体 double time メンバー：

struct Event {

 public:
explicit Event(double t) : time(t), eventID(), hostID(), s() {}
Event(double t, int eid, int hid, int stype) : time(t), eventID( eid ), hostID( hid ), s(stype) {}

  bool operator < ( const Event & rhs ) const {
    return ( time < rhs.time );
  }

  double time;
  ...
};

プログラムは、順序付けられていない時間のあるイベントを追加する期間を繰り返します EventPQ currentEvents そして、イベントを順番に引き出します。まれに、一部のイベントが追加された後（完全に「合法的な」時間がある）、イベントが順調に実行され始めます。

イベントが適切に注文されないのはなぜですか？ （または、イテレーターを台無しにするものは何ですか？） 追加されたイベント時間はすべて正当であることを確認しました（つまり、すべてのシミュレーション時間を超えています）。また、2つのイベントが同じ時間にスケジュールされるため、エラーが発生しないことも確認しました。

これをどのように活動するかについての提案が大好きです。

イベントを実行して追加するためのコードは、好奇心の強い以下です。

  double t = 0.0;
  double nextTimeStep = t + EPID_DELTA_T;
  EventPQ::iterator eventIter = currentEvents.begin();

while ( t < EPID_SIM_LENGTH ) {

     // Add some events to currentEvents

     while ( ( *eventIter ).time < nextTimeStep ) { 

         Event thisEvent = *eventIter;
     t = thisEvent.time;
     executeEvent( thisEvent );
     eventCtr++;
     currentEvents.erase( eventIter );
     eventIter = currentEvents.begin();

  }

  t = nextTimeStep;
  nextTimeStep += EPID_DELTA_T;
}


void Simulation::addEvent( double et, int eid, int hid, int s ) {
  assert( currentEvents.find( Event(et) ) == currentEvents.end() );

  Event thisEvent( et, eid, hid, s ); 
  currentEvents.insert( thisEvent );
}

たまにイベントが実行されたときに、他のイベントが削除されることを追加する必要があります。 currentEvents. 。これはで行われます 

double oldRecTime = 10.0; // gets defined legitimately in simulation
EventPQ::iterator epqItr = currentEvents.find( Event(oldRecTime) );
assert( currentEvents.count( Event(oldRecTime) ) == 1 );
currentEvents.erase( epqItr );

このコードが大丈夫に見えても、何が起こっているのかを調べることができる他の方法を知りたいです。現在、多くのAsserts（）とCout <<チェックを使用しています。

役に立ちましたか？

解決 3

コメントしたシミュレーションで

// Add some events to currentEvents

イベントがCurrentEventsに追加されました。 （それが明確だったことを願っています。）たまたまキューの上部に属していたイベントが追加された場合、CurrentEvents.begin（）を指すイテレーターを台無しにしたと思います。内側のループの直前にイテレーターをリセットすると、物事は機能しているように見えます。

これが解決策ではないことが判明したかどうか、または私がここに持っているものに他の問題があるかどうかを更新します。

コメントしてくれたすべての人に感謝します。これらの問題にどのように近づくべきかを学ぶのに役立ちます。

他のヒント

イベント処理サイクルでは、キューが空であるかどうかを確認できません。それ以外の場合、すべてがうまく見えます（多かれ少なかれ）。

しかし、あなたがあなたのイベントを使い果たした場合 currentEvents キュー、動作は未定義です。それはおそらく、イベントが順不同で処理されているときに現れるものとしてそれ自体を現れる可能性があります。

実際、私が見た連想容器のいくつかの実装は、制御されたシーケンスの終わりを無視して繰り返し続けると、シーケンスの先頭にイテレーターが出現するという意味で、「事実上円形」データ構造で表しています。あなたの場合、そのようなことが起こっているのでしょうか？

コードに関連してすぐに発生する別の質問：新しいイベントがキューに到着した場合はどうなりますか time 「現在の」時間よりも小さい値？あなたのコードでこの状況をキャプチャするチェックはありません。明らかに、これが発生した場合、つまり、いくつかのイベントが「遅すぎる」場合、それらがどのように実装されていても簡単に処理される可能性があります。

可能であれば、変更をお勧めします double 代わりに、整数タイプの鍵として使用しています。 aの鍵 set また multiset 厳格な弱い順序が必要です - およびa double します いいえ （通常）その要件を満たしています（他のIEEEフローティングポイントタイプもありません）。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top